Hierarchical residue number systems with small moduli and simple converters

Tadeusz Tomczak

doi:10.2478/v10006-011-0013-2

.blurhash-client-img { display: none !important; }

Hierarchical residue number systems with small moduli and simple converters

International Journal of Applied Mathematics and Computer Science

Volume 21 (2011): Issue 1 (March 2011)

By: Tadeusz Tomczak

Open Access

|Mar 2011

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 2^k ± 1 and modulo 2^k. 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 (2^k - 1, 2^k, 2^k + 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 2^k ± 1.

References

Akušskij, I. J. and Judickij, D. I. (1968). Machine Arithmetic in Residual Classes, Sovetskoje Radio, Moscow, (in Russian).
Search in Google Scholar
Bi, S., Wang, W. and Al-Khalili, A. (2004). Modulo deflation in (2ⁿ + 1, 2ⁿ, 2ⁿ - 1) converters, Proceedings of the 2004 International Symposium on Circuits and Systems, ISCAS '04, Vancouver, BC, Canada, Vol. 2, pp. 429-432.
Search in Google Scholar
Biernat, J. (2007). Architecture of Residue Arithmetic Circuits, Exit, Warsaw, (in Polish).
Search in Google Scholar
Cao, B., Chang, C.-H. and Srikanthan, T. (2003). An efficient reverse converter for the 4-moduli set (2ⁿ - 1, 2ⁿ, 2ⁿ + 1, 2²ⁿ + 1) based on the new Chinese remainder theorem, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 50(10): 1296-1303.10.1109/TCSI.2003.817789
Search in Google Scholar
Cao, B., Chang, C.-H. and Srikanthan, T. (2007). A residue-to-binary converter for a new five-moduli set, IEEE Transactions on Circuits and Systems I: Regular Papers, 54(5): 1041-1049.10.1109/TCSI.2007.890623
Search in Google Scholar
Chokshi, R., Berezowski, K. S., Shrivastava, A. and Piestrak, S. J. (2009). Exploiting residue number system for power-efficient 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.
Search in Google Scholar
Conway, R. and Nelson, J. (2004). Improved RNS FIR filter architectures, IEEE Transactions on Circuits and Systems II: Express Briefs 51(1): 26-28.10.1109/TCSII.2003.821524
Search in Google Scholar
Hiasat, A. A. (2000). New efficient structure for a modular multiplier for RNS, IEEE Transactions on Computers 49(2): 170-174.10.1109/12.833113
Search in Google Scholar
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.1109/81.940195
Search in Google Scholar
Mohan, P. V. (2002). Residue Number Systems: Algorithms and Architectures, Kluwer Academic Publishers, Norwell, MA.
Search in Google Scholar
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²ⁿ⁺¹ - 1 and 2ⁿ - 1, 2ⁿ + 1, 2²ⁿ, 2²ⁿ + 1 based on new CRTs, IEEE Transactions on Circuits and Systems I: Regular Papers 57(4): 823-835.10.1109/TCSI.2009.2026681
Search in Google Scholar
Piestrak, S. J. (1994). Design of residue generators and multi-operand modular adders using carry-save adders, IEEE Transactions on Computers 43(1): 68-77.10.1109/12.250610
Search in Google Scholar
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.10.1109/82.471401
Search in Google Scholar
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.10.1049/cp:20080692
Search in Google Scholar
Piestrak, S. J. and Berezowski, K. S. (2008). Architecture of efficient RNS-based digital signal processor with very low-level pipelining, Proceedings of the IET Irish Signals and Systems Conference, ISSC 2008, Galway, Republic of Ireland, pp. 127-132.
Search in Google Scholar
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.10.1109/78.747787
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/TCSI.2008.917994
Search in Google Scholar
Wang, W., Swamy, M. N. S., Ahmad, M. O. and Wang, Y. (2000). A high-speed residue-to-binary converter for three-moduli (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.10.1109/82.899659
Search in Google Scholar
Wang, W., Swamy, M. N. S., Ahmad, M. O. and Wang, Y. (2003). A study of the residue-to-binary converters for the three-moduli sets, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 50(2): 235-243.10.1109/TCSI.2002.808191
Search in Google Scholar
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.
Search in Google Scholar
Wang, Y. (2000). Residue-to-binary converters based on new chinese remainder the orems, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 47(3): 197-205.10.1109/82.826745
Search in Google Scholar
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.10.1109/TSP.2002.1011216
Search in Google Scholar
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.
Search in Google Scholar
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.10.2478/v10006-008-0010-2
Search in Google Scholar
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.
Search in Google Scholar
Zimmermann, R. (1998). VHDL library of arithmetic units, Proceedings of the 1st International Forum on Design Languages, FDL'98, Lausanne, Switzerlandhttp://www.iis.ee.ethz.ch/~zimmi/publications/arith_lib_fdl.ps.gz
Search in Google Scholar
Zimmermann, R. (1999). Efficient VLSI implementation of modulo (2ⁿ ± 1) addition and multiplication, Proceedings of the 14th IEEE Symposium on Computer Arithmetic, Adelaide, Australia, pp. 158-167.
Search in Google Scholar