A signed-digit architecture for residue to binary transformation
F. Pourbigharaz · IEEE Transactions on Computers · 1997
A residue to binary converter architecture based on the Chinese Remainder Theorem (CRT) is presented. This is achieved by introducing a general moduli set S/sup k/ S/sup k/={2/sup m/-1, 2/sup 2om/+1, 2/sup 21m/+1, 2/sup 22m/+1,....,2/sup 22km/+1} for Residue Number System (RNS) applications. Residue to binary converter architectures based on moduli sets S/sup o/={2/sup m/-1, 2/sup m/+1} and S/sup 1/=(2/sup m/-1, 2/sup m/+1, 2/sup 2m/+1) are developed. The conversion procedure is performed in the following three levels: residue to signed-digit, signed-digit to binary, end-around carry addition/subtraction. In the first level of operation, the signed-digit representation of the CRT equation is realized by using redundant adder/subtracter blocks. Here, the necessary embedded multiplications are replaced by simple shift-left operations and the carry propagation is totally eliminated. In the second level, the redundant representation of CRT is directly converted to binary format. Finally, an end-around carry (EAC) addition/subtraction is performed to obtain the result at the third level of operation. The proposed architectures are simple, fast, free of memory blocks and module adders.