IEEE Access (Jan 2020)

Classification of Moduli Sets for Residue Number System With Special Diagonal Functions

  • Peter Boyvalenkov,
  • Nikolay I. Chervyakov,
  • Pavel Lyakhov,
  • Nataliya Semyonova,
  • Anton Nazarov,
  • Maria Valueva,
  • Georgi Boyvalenkov,
  • Danil Bogaevskiy,
  • Dmitrii Kaplun

DOI
https://doi.org/10.1109/ACCESS.2020.3019452
Journal volume & issue
Vol. 8
pp. 156104 – 156116

Abstract

Read online

The paper presents algorithms for the generation of Residue Number System (RNS) triples with $SQ=2^{k}-1$ and quadruples with $SQ=2^{k}$ for some k. Triples and quadruples allow us to design efficient hardware implementations of non-modular operations in RNS such as division, sign detection, comparison of numbers, reverse conversion with using of a diagonal function from requiring division with the remainder by the diagonal module SQ. Division with a remainder in the general case is the most complex arithmetic operation in computer technology. However, the consideration of special cases can significantly simplify this operation and increase the efficiency of hardware implementation. We show that there are 5573 good RNS triples (2301 even and 2372 odd) with elements less than 10 000, as the values of SQ vary from $2^{5}-1$ to $2^{27}-1$ . In contrast, RNS quadruples with $SQ=2^{k}$ seem to be quite rare. Restricting our search to sums of the elements in a quadruple less than 4000 we find that exactly 31 such quadruples exist. Their values of SQ vary between 220 and 230 with always even exponent. We suggest the measure of RNS balance and find perfectly balanced RNS among triples according to this measure. We demonstrate the advantages of more balanced quadruples by means of hardware implementation.

Keywords