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.
@article{bwmeta1.element.bwnjournal-article-amcv21i1p173bwm,
author = {Tadeusz Tomczak},
title = {Hierarchical residue number systems with small moduli and simple converters},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {21},
year = {2011},
pages = {173-192},
zbl = {1221.94108},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv21i1p173bwm}
}
Tadeusz Tomczak. Hierarchical residue number systems with small moduli and simple converters. International Journal of Applied Mathematics and Computer Science, Tome 21 (2011) pp. 173-192. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv21i1p173bwm/
[000] Akušskij, I.J. and Judickij, D.I. (1968). Machine Arithmetic in Residual Classes, Sovetskoje Radio, Moscow, (in Russian).
[001] 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.
[002] Biernat, J. (2007). Architecture of Residue Arithmetic Circuits, Exit, Warsaw, (in Polish).
[003] 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.
[004] 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.
[005] 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.
[006] Conway, R. and Nelson, J. (2004). Improved RNS FIR filter architectures, IEEE Transactions on Circuits and Systems II: Express Briefs 51(1): 26-28.
[007] Hiasat, A.A. (2000). New efficient structure for a modular multiplier for RNS, IEEE Transactions on Computers 49(2): 170-174.
[008] 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.
[009] Mohan, P.V. (2002). Residue Number Systems: Algorithms and Architectures, Kluwer Academic Publishers, Norwell, MA.
[010] 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.
[011] Piestrak, S.J. (1994). Design of residue generators and multioperand modular adders using carry-save adders, IEEE Transactions on Computers 43(1): 68-77. | Zbl 0818.94026
[012] 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.
[013] 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.
[014] 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.
[015] 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.
[016] 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. | Zbl 0649.94001
[017] 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.
[018] 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.
[019] 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. | Zbl 0980.68006
[020] 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.
[021] 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.
[022] 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. | Zbl 0979.68002
[023] 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.
[024] 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. | Zbl 1010.94018
[025] 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.
[026] 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.
[027] 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.
[028] 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.