A partial table-lookup rns-decimal number conversion algorithm and its implementations
Zhi Li, Robert J. Marks · 1993
Efficient implementation of digital signal processing architecture has made possible robust high speed parallel signal processing structure based on residue arithmetic operations. In order to utilize the Residue Number System (RNS) based architecture, the binary or analog signals must be mapped into RNS representation and then converted back to binary representation. Numerous techniques have been discussed for the decoding operation using Chinese Reminder Theory (CRT) and Mixed Radix Conversion (MRC). The problem associated with the CRT approach is the requirement of molulo N (which is the dynamic range of the chosen RNS) adders. The drawback of MRC is its high computational complexity. In this dissertation, we investigate a new method and its implementations to transform the RNS to decimal number system. For a 2-tuple RNS to decimal conversion, by using a property discovered in this research project, we propose a partial table-lookup conversion algorithm. By memorizing only partial decimal numbers, ($m\sb2$, or $m\sb1$, out of $m\sb1m\sb2$), in the dynamic range of any RNS, this method can generate a correct decimal number with only additions. This conversion algorithm can be implemented in hardware level by shifting operation with one addition. This method can be extended to converting any Q-tuple RNS by a simple modulized decoding structure. We discuss implementation methods for the partial table-lookup algorithm and the modulized implementation structure, then, compare our implementations for the new modular decoding structure with five conventional decoding structures reported in the literatures so far in terms of arithimetic operation complexity, dynamic range requirements, hardware implementation complexity and decoding time as well as accuracy. The modulized structure proposed in this dissertation is very suitable for VLSI implementation and the dynamic range requirements for the processors are always constrained to the chosen RNS system.