Hierarchical residue number systems with small moduli and simple converters

Tadeusz Tomczak

International Journal of Applied Mathematics and Computer Science (2011)

  • Volume: 21, Issue: 1, page 173-192
  • ISSN: 1641-876X

Abstract

top
In this paper, a new class of Hierarchical Residue Number Systems (HRNSs) is proposed, where the numbers are represented as a set of residues modulo factors of 2k ± 1 and modulo 2k . The converters between the proposed HRNS and the positional binary number system can be built as 2-level structures using efficient circuits designed for the RNS (2k-1, 2k, 2k+1). This approach allows using many small moduli in arithmetic channels without large conversion overhead. The advantages resulting from the use of the proposed HRNS depend on the possibility of factorisation of moduli 2k ± 1.

How to cite

top

Tadeusz Tomczak. "Hierarchical residue number systems with small moduli and simple converters." International Journal of Applied Mathematics and Computer Science 21.1 (2011): 173-192. <http://eudml.org/doc/208032>.

@article{TadeuszTomczak2011,
abstract = {In this paper, a new class of Hierarchical Residue Number Systems (HRNSs) is proposed, where the numbers are represented as a set of residues modulo factors of 2k ± 1 and modulo 2k . The converters between the proposed HRNS and the positional binary number system can be built as 2-level structures using efficient circuits designed for the RNS (2k-1, 2k, 2k+1). This approach allows using many small moduli in arithmetic channels without large conversion overhead. The advantages resulting from the use of the proposed HRNS depend on the possibility of factorisation of moduli 2k ± 1.},
author = {Tadeusz Tomczak},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {digital arithmetic; digital circuits; residue number system; VLSI},
language = {eng},
number = {1},
pages = {173-192},
title = {Hierarchical residue number systems with small moduli and simple converters},
url = {http://eudml.org/doc/208032},
volume = {21},
year = {2011},
}

TY - JOUR
AU - Tadeusz Tomczak
TI - Hierarchical residue number systems with small moduli and simple converters
JO - International Journal of Applied Mathematics and Computer Science
PY - 2011
VL - 21
IS - 1
SP - 173
EP - 192
AB - In this paper, a new class of Hierarchical Residue Number Systems (HRNSs) is proposed, where the numbers are represented as a set of residues modulo factors of 2k ± 1 and modulo 2k . The converters between the proposed HRNS and the positional binary number system can be built as 2-level structures using efficient circuits designed for the RNS (2k-1, 2k, 2k+1). This approach allows using many small moduli in arithmetic channels without large conversion overhead. The advantages resulting from the use of the proposed HRNS depend on the possibility of factorisation of moduli 2k ± 1.
LA - eng
KW - digital arithmetic; digital circuits; residue number system; VLSI
UR - http://eudml.org/doc/208032
ER -

References

top
  1. Akušskij, I.J. and Judickij, D.I. (1968). Machine Arithmetic in Residual Classes, Sovetskoje Radio, Moscow, (in Russian). 
  2. Bi, S., Wang, W. and Al-Khalili, A. (2004). Modulo deflation in (2n + 1, 2n, 2n - 1) converters, Proceedings of the 2004 International Symposium on Circuits and Systems, ISCAS '04, Vancouver, BC, Canada, Vol. 2, pp. 429-432. 
  3. Biernat, J. (2007). Architecture of Residue Arithmetic Circuits, Exit, Warsaw, (in Polish). 
  4. Cao, B., Chang, C.-H. and Srikanthan, T. (2003). An efficient reverse converter for the 4-moduli set 2n-1, 2ⁿ, 2ⁿ+1, 2^{2n}+1 based on the new Chinese remainder theorem, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 50(10): 1296-1303. 
  5. Cao, B., Chang, C.-H. and Srikanthan, T. (2007). A residueto-binary converter for a new five-moduli set, IEEE Transactions on Circuits and Systems I: Regular Papers, 54(5): 1041-1049. 
  6. Chokshi, R., Berezowski, K.S., Shrivastava, A. and Piestrak, S.J. (2009). Exploiting residue number system for powerefficient digital signal processing in embedded processors, Proceedings of the 2009 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES '09, Grenoble, France, pp. 19-28. 
  7. Conway, R. and Nelson, J. (2004). Improved RNS FIR filter architectures, IEEE Transactions on Circuits and Systems II: Express Briefs 51(1): 26-28. 
  8. Hiasat, A.A. (2000). New efficient structure for a modular multiplier for RNS, IEEE Transactions on Computers 49(2): 170-174. 
  9. Mohan, P.V.A. (2001). Comments on 'Breaking the 2n-bit carry propagation barrier in residue to binary conversion for the [2ⁿ-1, 2ⁿ, 2ⁿ+1] moduli set', IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 48(8): 1031. 
  10. Mohan, P.V. (2002). Residue Number Systems: Algorithms and Architectures, Kluwer Academic Publishers, Norwell, MA. 
  11. Molahosseini, A., Navi, K., Dadkhah, C., Kavehei, O. and Timarchi, S. (2010). Efficient reverse converter designs for the new 4-moduli sets 2ⁿ - 1, 2ⁿ, 2ⁿ + 1, 2^{2n}+1 - 1 and 2ⁿ - 1, 2ⁿ + 1, 2^{2n}, 2^{2n} + 1 based on new CRTs, IEEE Transactions on Circuits and Systems I: Regular Papers 57(4): 823-835. 
  12. Piestrak, S.J. (1994). Design of residue generators and multioperand modular adders using carry-save adders, IEEE Transactions on Computers 43(1): 68-77. Zbl0818.94026
  13. Piestrak, S.J. (1995). A high-speed realization of a residue to binary number system converter, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 42(10): 661-663. 
  14. Piestrak, S. and Berezowski, K. (2008a). Design of residue multipliers-accumulators using periodicity, Proceedings of the IET Irish Signals and Systems Conference, ISSC 2008, Galway, Republic of Ireland, pp. 380-385. 
  15. Piestrak, S.J. and Berezowski, K.S. (2008). Architecture of efficient RNS-based digital signal processor with very lowlevel pipelining, Proceedings of the IET Irish Signals and Systems Conference, ISSC 2008, Galway, Republic of Ireland, pp. 127-132. 
  16. Skavantzos, A. and Abdallah, M. (1999). Implementation issues of the two-level residue number system with pairs of conjugate moduli, IEEE Transactions on Signal Processing 47(3): 826-838. 
  17. Soderstrand, M.A., Jenkins, W.K., Jullien, G.A. and Taylor, F.J. (Eds.) (1986). Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, IEEE Press, Piscataway, NJ. Zbl0649.94001
  18. Stine, J. E., Grad, J., Castellanos, I., Blank, J., Dave, V., Prakash, M., Iliev, N. and Jachimiec, N. (2005). A framework for high-level synthesis of system-on-chip designs, Proceedings of the International Conference on Microelectronic Systems Education, Anaheim, CA, USA, pp. 11-12. 
  19. Tomczak, T. (2008). Fast sign detection for RNS (2ⁿ - 1, 2ⁿ, 2ⁿ + 1), IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 55(6): 1502-1511. 
  20. Wang, W., Swamy, M.N.S., Ahmad, M.O. and Wang, Y. (2000). A high-speed residue-to-binary converter for threemoduli 2^k, 2^k - 1, 2^{k-1} - 1 RNS and a scheme for its VLSI implementation, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 47(12): 1576-1581. Zbl0980.68006
  21. Wang, W., Swamy, M.N.S., Ahmad, M.O. and Wang, Y. (2003). A study of the residue-to-binary converters for the threemoduli sets, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 50(2): 235-243. 
  22. Wang, W., Swamy, M.N.S. and Ahmad, M.O. (2004). RNS application for digital image processing, Proceedings of the 4th IEEE International Workshop on System-on-Chip for Real-Time Applications, IWSOC'04, Banff, Alberta, Canada, pp. 77-80. 
  23. Wang, Y. (2000). Residue-to-binary converters based on new chinese remainder theorems, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 47(3): 197-205. Zbl0979.68002
  24. Wang, Y., Song, X., Aboulhamid, M. and Shen, H. (2002). Adder based residue to binary number converters for (2ⁿ - 1, 2ⁿ, 2ⁿ + 1), IEEE Transactions on Signal Processing 5(7): 1772-1779. 
  25. Wang, Z., Jullien, G.A. and Miller, W.C. (2000). An improved residue-to-binary converter, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 47(9), pp. 1437-1440. Zbl1010.94018
  26. Wnuk, M. (2008). Remarks on hardware implementation of image processing algorithms, International Journal of Applied Mathematics and Computer Science 18(1): 105-110, DOI: 10.2478/v10006-008-0010-2. 
  27. Yassine, H.M. (1992). Hierarchical residue numbering system suitable for VLSI arithmetic architectures, Proceedings of the IEEE International Symposium on Circuits and Systems, ISCAS '92, San Diego, CA, USA, pp. 811-814. 
  28. Zimmermann, R. (1998). VHDL library of arithmetic units, Proceedings of the 1st International Forum on Design Languages, FDL'98, Lausanne, Switzerland, http://www.iis.ee.ethz.ch/~zimmi/publications/arith_lib_fdl.ps.gz. 
  29. Zimmermann, R. (1999). Efficient VLSI implementation of modulo (2n ± 1) addition and multiplication, Proceedings of the 14th IEEE Symposium on Computer Arithmetic, Adelaide, Australia, pp. 158-167. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.