Residue number systems with six modules and efficient circuits based on power-of-two diagonal modulus.

The paper suggests an algorithm for finding Residue Number Systems (RNS) with six modules (6-tuples) with the Sum of Quotients S Q = 2 k for some positive integer k. It is shown that there are exactly thirteen such 6-tuples (m 1 , ... , m 6) with m 1 + m 2 ≤ 10000 and m 3 + m 4 ≤ m 5 + m 6 ≤ 10000 and investigated the three smallest among them, namely (5 , 2399 , 7 , 11 , 23 , 1691) , (47 , 293 , 25 , 193 , 41 , 257) , and (23 , 1433 , 13 , 29 , 681 , 821) , having k = 34 , 36, and 40, respectively. The hypothesis is that such RNS allow efficient hardware implementations of non-modular operations — division, sign detection, comparison of numbers, and reverse conversion from the point of hardware resource usage and balancedness. The special case S Q = 2 k allows a significant simplification of these operations and increased efficiency of hardware implementations. Hardware modeling of circuits based on the above 6-tuples that implement magnitude comparison and reverse RNS to binary conversion (reverse conversion) is presented. The suggested magnitude comparison and reverse conversion devices, which operate with the six modules, are built using the methodology and values of the diagonal function, carry-save, and Kogge-Stone adders. The results of FPGA-based hardware modeling and the theoretical parameters of devices calculated using the unit-gate model are compared with state-of-the-art approaches. The unit-gate model showed that the use of the proposed circuits allows us to reduce the area by 17.82%–50.81% and the delay by 1.56%–97.76% for the implementation of the magnitude comparison, and to reduce the delay by 2.80%–95.03% for the implementation of reverse conversion. The FPGA synthesis also showed that the new design has reduced the area and delay by 46.96%–86.80% and 7.15%–47.65%, respectively, for the implementation of magnitude comparison and reduced the delay by 13.63%–81.53% for the implementation of reverse conversion. It is shown that a proposed technique to measure the RNS balance can adequately reflect differences in the RNS performance. [Display omitted] • An algorithm for finding Residue Number Systems (RNS) with six modules and Sum of Quotients 2 k was developed. • Presented RNS preserve the usual advantages of RNS but also allow efficient hardware implementations of non-modular operations — division, sign detection, comparison of numbers, and reverse conversion. It was proved that exactly thirteen 6-tuples with S Q = 2 k exist under certain restrictions. • A measure of RNS balance was applied to the three smallest among the discovered 6-tuples and recommendations for their applications in practice were given. • Hardware modeling of circuits based on the three smallest 6-tuples that implement magnitude comparison and reverse RNS to binary conversion was presented. • Theoretic and practice (hardware implementation in FPGA) comparisons of our findings with the most effective state-of-the-art techniques (Chinese Remainder Theorem (CRT), CRT with fraction values, Mixed Radix Conversion) were provided and the efficiency of the proposed solution was confirmed. [ABSTRACT FROM AUTHOR]