A residue to binary converter for the {2n + 2, 2n + 1, 2n} moduli set

摘要

In this paper, we investigate residue number system (RNS) to decimal conversion for a three moduli set with a common factor. We propose a new RNS to binary converter for the moduli set {2n + 2, 2n + 1, 2n} for any even integer n > 0. First, we demonstrate that for such a moduli set, the computation of the multiplicative inverses can be eliminated. Secondly, we simplify the Chinese Remainder Theorem (CRT) to obtain a reverse conveter that uses mod-n instead of mod-(2n+2)(2n) or mod-2n required by other state of the art equivalent converters. Next, we present a low complexity implementation that does not require explicit use of the modulo operation in the conversion process as it is normally the case in the traditional CRT and other state of the art equivalent converters. In terms of area, our proposal requires four 2:1 adders and 2 multipliers while the best state of the art equivalent converter requires one 3:1 adder, two 2:1 adders, and four multipliers. In terms of critical path delay, our scheme requires 3 additions and 1 multiplication with mod-n operations whereas the best state of the art equivalent converter requires 2 additions and 2 multiplications with mod-2n operations. Consequently, our scheme outperforms state of the art converters in terms of area and delay. Moreover, due to the fact that our scheme operates on smaller magnitude operands, it requires less complex adders and multipliers, which potentially results in even faster and smaller implementations.