Title page for ETD etd-11052010-141445

Type of Document Master's Thesis
Author Narayanaswamy, Narendran
Author's Email Address nnaray1@tigers.lsu.edu
URN etd-11052010-141445
Title Optimization of New Chinese Remainder Theorems Using Special Moduli Sets
Degree Master of Science (M.S.)
Department Electrical & Computer Engineering
Advisory Committee
Advisor Name Title
Skavantzos, Alex Committee Chair
Moreno, Juana Committee Member
Srivastava, Ashok Committee Member
  • Optimization of New CRT
Date of Defense 2010-10-29
Availability unrestricted
The residue number system (RNS) is an integer number representation system, which is capable of supporting parallel, high-speed arithmetic. This system also offers some useful properties for error detection, error correction and fault tolerance. It has numerous applications in computation-intensive digital signal processing (DSP) operations, like digital filtering, convolution, correlation, Discrete Fourier Transform, Fast Fourier Transform, direct digital frequency synthesis, etc.

The residue to binary conversion is based on Chinese Remainder Theorem (CRT) and Mixed Radix Conversion (MRC). However, the CRT requires a slow large modulo operation while the MRC requires finding the mixed radix digits which is a slow process. The new Chinese Remainder Theorems (CRT I, CRT II and CRT III) make the computations faster and efficient without any extra overheads. But, New CRTs are hardware intensive as they require many inverse modulus operators, modulus operators, multipliers and dividers. Dividers and inverse modulus operators in turn needs many half and full adders and subtractors. So, some kind of optimization is necessary to implement these theorems practically.

In this research, for the optimization, new both co-prime and non co-prime multi modulus sets are proposed that simplify the new Chinese Remainder theorems by eliminating the huge summations, inverse modulo operators, and dividers. Furthermore, the proposed hardware optimization removes the multiplication terms in the theorems, which further simplifies the implementation.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Report_Nov2.pdf 1.05 Mb 00:04:51 00:02:30 00:02:11 00:01:05 00:00:05

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.