×

Design of reverse converters for a new flexible RNS five-moduli set \(\{ 2^k, 2^n-1, 2^n+1, 2^{n+1}-1, 2^{n-1}-1 \}\) (\(n\) even). (English) Zbl 1373.94680

Summary: This paper presents the design methods of residue-to-binary (reverse) converters for the new flexible balanced five-moduli set \(\{ 2^k, 2^n-1, 2^n+1,2^{n+1}-1, 2^{n-1}-1 \}\) for the pairs of positive integers \({n \geq 4}\) (even) and any \(k>0\), which can provide the exact required dynamic range of the residue number system. This modulus set is the generalisation of the five-moduli set \(\{ 2^n, 2^n-1, 2^n+1, 2^{n+1}-1, 2^{n-1}-1 \}\) (\(n\) even) with only a single parameter \(n\). The reverse converter for the new modulus set is the first ever proposed. Synthesis results obtained for the \(65\,\)nm technology for all dynamic ranges from 19 to \(88\,\)bits have shown that the state-of-the-art converters available for the five-modulus sets with a single parameter \(n\{ 2^n, 2^n-1, 2^n+1, 2^{n+1}-1, 2^{n-1}-1 \}\) (\(n\) even) and \({\{ 2^n-1, 2^n, 2^n+1, 2^{n+1}+1, 2^{n-1}+1 \} }\) (\(n\) odd) not only introduce from 28 to 40% larger delay but also still consume more area and power than the converters proposed here.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
11Z05 Miscellaneous applications of number theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.V. Ananda Mohan, Residue Number Systems: Algorithms and Architectures (Birkhäuser, Basel, 2016) · Zbl 1429.11001 · doi:10.1007/978-3-319-41385-3
[2] P.V. Ananda Mohan, A.B. Premkumar, RNS-to-binary converters for two four-moduli sets \[\{2^n - 1\]{2n-\[1, 2^n2\] n, \[2^n + 12\] n+\[1, 2^{n+1} - 1 \}2\] n+1-1} and \[\{2^n -1\]{2n-\[1, 2^n2\] n, \[2^n + 12\] n+\[1, 2^{n+1}+1\}2\] n+1+1}. IEEE Trans. Circuits Syst. I 54(6), 1245-1254 (2007) · Zbl 1130.68017 · doi:10.1109/TCSI.2007.895515
[3] M. Bhardwaj, T. Srikanthan, C.T. Clarke, in Reverse Converter for the 4-Moduli Superset \[\{ 2^n - 1, 2^n, 2^n + 1, 2^{n+1}-1 \}\]{2n-1,2n,2n+1,2n+1-1}. Proceedings of the 14th IEEE Symposium on Comput. Arithm., pp. 168-175, Adelaide, Australia, 14-16 April 1999
[4] B. Cao, C.-H. Chang, T. Srikanthan, A residue-to-binary converter for a new five-moduli set. IEEE Trans. Circuits Syst. I 54(5), 1041-1049 (2007) · Zbl 1374.68013 · doi:10.1109/TCSI.2007.890623
[5] B. Cao, T. Srikanthan, C.H. Chang, Efficient reverse converters for the four-moduli sets \[\{ 2^n, 2^n-1, 2^n+1, 2^{n+1}-1 \}\]{2n,2n-1,2n+1,2n+1-1} and \[\{ 2^n, 2^n-1, 2^n+1, 2^{n-1}-1 \}\]{2n,2n-1,2n+1,2n-1-1}. IEE Proc. Comput. Digit. Tech. 152(5), 687-696 (2005) · Zbl 1368.68019 · doi:10.1049/ip-cdt:20045155
[6] G. Chalivendra, V. Hanumaiah, S. Vrudhula, in A New Balanced 4-Moduli Set \[\{ 2^k, 2^n - 1, 2^n + 1, 2^{n+1}-1 \}\]{2k,2n-1,2n+1,2n+1-1}and Its Reverse Converter Design for Efficient FIR Filter Implementation. Proceedings of the ACM Great Lakes Symposium on VLSI (GLSVLSI), pp. 139-144, Lausanne, Switzerland, 2-4 May 2011 · Zbl 0979.68002
[7] R. Chaves, L. Sousa, Improving residue number system multiplication with more balanced moduli sets and enhanced modular arithmetic structures. IET Proc. Comput. Digit. Tech. 1(5), 472-480 (2007) · doi:10.1049/iet-cdt:20060059
[8] J. Chen, J.E. Stine, in Parallel Prefix Ling Structures for Modulo \[2^n-12\] n-1Addition. Proceedings of the IEEE International Conference on Application Specific Systems, Architectures and Processors, pp. 16-23, Boston, MA, USA, 7-9, 2009
[9] R. Conway, J. Nelson, Improved RNS FIR filter architectures. IEEE Trans. Circuits Syst. II 51(1), 26-28 (2004) · doi:10.1109/TCSII.2003.821524
[10] A. Dhurkadas, Comments on “A high speed realization of a residue to binary number system converter”. IEEE Trans. Circuits Syst. II 45(3), 446-447 (1998) · doi:10.1109/82.664260
[11] C. Efstathiou, H.T. Vergos, D. Nikolos, Fast parallel-prefix modulo \[2^n+12\] n+1 adders. IEEE Trans. Comput. 53(9), 1211-1216 (2004) · doi:10.1109/TC.2004.60
[12] G. Jaberipur, B. Parhami, in Unified Approach to the Design of Modulo-\[(2^n \pm 12\] n±1) Adders Based on Signed-LSB Representation of Residues. Proceedings of the IEEE Symposium on Comput. Arithm., pp. 57-64, Portland, OR, USA, 8-10 June 2009
[13] T.-B. Juang, C.-C. Chiu, M.-Y. Tsai, Improved area-efficient weighted modulo \[2^n + 12\] n+1 adder design with simple correction schemes. IEEE Trans. Circuits Syst. II 57(3), 198-202 (2010) · doi:10.1109/TCSII.2010.2040302
[14] Y. Liu, E.M.-K. Lai, Moduli set selection and cost estimation for RNS-based FIR filter and filter bank design. Des. Autom. Embed. Syst. 9(2), 123-139 (2004) · doi:10.1007/s10617-005-1186-4
[15] U. Meyer-Baese, Digital Signal Processing with Field Programmable Gate Arrays, 4th edn. (Springer, Berlin, 2014) · Zbl 1050.94005 · doi:10.1007/978-3-642-45309-0
[16] R. Muralidharan, C.H. Chang, Area-power efficient modulo \[2^n -12\] n-1 and modulo \[2^n +12\] n+1 multipliers for \[\{2^n-1, 2^n, 2^n+1\}\]{2n-1,2n,2n+1} based RNS. IEEE Trans. Circuits Syst. I Regul. Pap. 59(10), 2263-2274 (2012) · Zbl 1468.65238 · doi:10.1109/TCSI.2012.2185334
[17] R.A. Patel, S. Boussakta, Fast parallel-prefix architectures for modulo \[2^n-12\] n-1 addition with a single representation of zero. IEEE Trans. Comput. 56(11), 1484-1492 (2007) · Zbl 1390.65191 · doi:10.1109/TC.2007.70750
[18] P. Patronik, K. Berezowski, J. Biernat, S.J. Piestrak, A. Shrivastava, in Design of an RNS Reverse Converter for a New Five-Moduli Special Set. Proceedings of the ACM Great Lakes Symp. VLSI (GLSVLSI), pp. 67-70, Salt Lake City, UT, USA, 3-4 May 2012
[19] P. Patronik, S.J. Piestrak, Design of reverse converters for general RNS moduli sets \[\{ 2^k, 2^n-1, 2^n+1, 2^{n-1}-1 \}\]{2k,2n-1,2n+1,2n-1-1} and \[\{ 2^k, 2^n-1, 2^n+1, 2^{n+1}-1 \}\]{2k,2n-1,2n+1,2n+1-1} \[(n\] n even). IEEE Trans. Circuits Syst. I Reg. Pap. 61(6), 1687-1700 (2014) · doi:10.1109/TCSI.2013.2290843
[20] P. Patronik, S.J. Piestrak, Design of reverse converters for the new RNS moduli set \[\{ 2^n+1, 2^n-1, 2^n, 2^{n-1}+1 \}\]{2n+1,2n-1,2n,2n-1+1} \[(n\] n odd). IEEE Trans. Circuits Syst. I Reg. Pap. 61(12), 3436-3449 (2014) · doi:10.1109/TCSI.2014.2337237
[21] S.J. Piestrak, Design of residue generators and multioperand modular adders using carry-save adders. IEEE Trans. Comput. 43(1), 68-77 (1994) · Zbl 0818.94026 · doi:10.1109/12.250610
[22] S.J. Piestrak, A high-speed realization of a residue to binary number system converter. IEEE Trans. Circuits Syst. II 42(10), 661-663 (1995) · doi:10.1109/82.471401
[23] S.J. Piestrak, in Design of Multi-residue Generators Using Shared Logic. Proceedings of the IEEE International Symposium on Circuits & Systems (ISCAS), pp. 1435-1438, Rio de Janeiro, Brazil, 15-18 May 2011
[24] S.J. Piestrak, K.S. Berezowski, in Architecture of Efficient RNS-Based Digital Signal Processor with Very Low-Level Pipelining. Proceedings of the IET Irish Sign. & Syst. Conference, pp. 127-132, Galway, Ireland, 18-19 June 2008
[25] S.J. Piestrak, K.S. Berezowski, in Design of Residue Multipliers-Accumulators Using Periodicity. Proceedings of the IET Irish Sign. & Syst. Conference, pp. 380-385, Galway, Ireland, 18-19 June 2008 · Zbl 1374.68013
[26] A. Skavantzos, M. Abdallah, Implementation issues of the two-level residue number system with pairs of conjugate moduli. IEEE Trans. Signal Process. 47(3), 826-838 (1999) · doi:10.1109/78.747787
[27] A. Skavantzos, in Efficient Residue to Weighted Converter for a New Residue Number System. Proceedings of the IEEE Great Lakes Symposium on VLSI (GLSVLSI), pp. 185-191, Lafayette, LA, USA, 19-21 February 1998
[28] A. Skavantzos, in Grouped-Moduli Residue Number Systems for Fast Signal Processing. Proceedings of the IEEE International Symposium on Circuits & Systems (ISCAS), vol. 3, pp. III-478-III-483, Orlando, FL, USA, 30 May-2 June 1999
[29] L. Sousa, S. Antão, R. Chaves, On the design of RNS reverse converters for the four-moduli set \[\{ 2^n+ 1, 2^n-1, 2^n, 2^{n+1} + 1 \}\]{2n+1,2n-1,2n,2n+1+1}. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21(10), 1945-1949 (2013) · doi:10.1109/TVLSI.2012.2219564
[30] A.P. Vinod, A.B. Premkumar, A memoryless reverse converter for the 4-moduli superset \[\{ 2^n - 1, 2^n, 2^n + 1, 2^{n+1}-1 \}\]{2n-1,2n,2n+1,2n+1-1}. J. Circuits Syst. Comput. 10(1-2), 85-99 (2000)
[31] Y. Wang, Residue-to-binary converters based on new Chinese remainder theorem. IEEE Trans. Circuits Syst. II 47(3), 197-205 (2000) · Zbl 0979.68002 · doi:10.1109/82.826745
[32] Z. Wang, G.A. Jullien, W.C. Miller, An improved residue-to-binary converter. IEEE Trans. Circuits Syst. I 47(9), 1437-1440 (2000) · Zbl 1010.94018 · doi:10.1109/81.883337
[33] M. Wesołowski, P. Patronik, K. Berezowski, J. Biernat, in Design of a Novel Flexible 4-Moduli RNS and Reverse Converter. Proceedings of the 23nd IET Irish Sign. & Syst. Conference (ISSC), pp. 1-6, Maynooth, Ireland, 28-29 June 2012 · Zbl 1374.68013
[34] A. Wrzyszcz, D. Milford, in A New Modulo \[2^a+12\] a+1Multiplier. Proceedings of the International Conference on Comput. Des., pp. 614-617, Boston, MA, USA, 3-6 October 1993 · Zbl 1010.94018
[35] R. Zimmerman, in Efficient VLSI Implementation of Modulo \[2^n \pm 12\] n±1Addition and Multiplication. Proceedings of the IEEE Symp. Comput. Arithm., pp. 158-167, Adelaide, Australia, 14-16 April 1999
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.