Design and Analysis of RNS-based Sign Detector for Moduli Set {2^n, 2^n - 1, 2^n + 1}

Raj Kumar, Ram Awadh Mishra

Abstract


Magnitude comparison, overflow detection and sign detection are essential operations of residue number system (RNS) based digital signal processing (DSP) applications.  Moreover, sign detection attracts significant attention in RNS as it can also be used in division and magnitude comparison operations. However, these operations are not easy to perform in RNS. So, there is a need arise to propose a computationally advanced RNS based sign detector. This paper presents an area and power efficient sign detection for RNS {2n - 1, 2n, 2n + 1} using mixed radix conversion technique. The proposed sign detector circuit is built using a carry save adder (CSA), a modified parallel prefix adder and a carry-generation circuit. Based on synthesized results using Synopsys design compiler tool, the proposed design offers better results in terms of area required and power dissipation. Although, the speed will remains same when compared to the recent sign detectors for the same moduli set.

Keywords


Digital Signal Processing; Mixed radix conversion (MRC); Residue Number System; Sign detection; VLSI design

References


L. Kalampoukas, D. Nikolos, C. Efstathiou, H. T. Vergos, and J. Kalamatianos, “High-speed parallel-prefix module 2^n-1 adders,” IEEE Trans. Comput., vol. 49, no. 7, pp. 673–680, 2000.

H. T. Vergos and D. Bakalis, “Area-time efficient multi-modulus adders and their applications,” Microprocess. Microsyst., vol. 36, no. 5, pp. 409–419, 2012.

S. K. Singhal, B. K. Mohanty, S. K. Patel, and G. Saxena, “Efficient Diminished-1 Modulo (2 ^n+ 1) Adder Using Parallel Prefix Adder,” J. Circuits, Syst. Comput., p. 2050186, 2020.

R. Zimmermann, “Efficient VLSI implementation of modulo (2^n±1) addition and multiplication,” Proc. 14th IEEE Symp. Comput. Arith. (Cat. No.99CB36336), no. 4, pp. 158–167, 1999.

R. Muralidharan and C.-H. H. Chang, “Radix-4 and Radix-8 booth encoded multi-modulus multipliers,” IEEE Trans. Circuits Syst. I Regul. Pap., vol. 60, no. 11, pp. 2940–2952, 2013.

R. Kumar, R. K. Jaiswal, and R. A. Mishra, “Perspective and Opportunities of Modulo 2^n-1 Multipliers in Residue Number System: A Review,” J. Circuits, Syst. Comput., vol. 29, no. 11, p. 2030008, 2020.

A. S. Madhukumar and F. Chin, “Enhanced architecture for residue number system-based CDMA for high-rate data transmission,” IEEE Trans. Wirel. Commun., vol. 3, no. 5, pp. 1363–1368, 2004.

P. V. A. Mohan, Residue number systems: algorithms and architectures, vol. 677. Springer Science & Business Media, 2012.

R. Conway and J. Nelson, “Improved RNS FIR filter architectures,” IEEE Trans. Circuits Syst. II Express Briefs, vol. 51, no. 1, pp. 26–28, 2004.

J. Ramirez, U. Meyer-Base, A. Garcia, and A. Lloris, “Design and implementation of RNS-based adaptive filters,” Proc. 13th Int. Conf. F. Program. Log. Appl. Lisbon, Spain, pp. 1135–1138, 2003.

C. B. Dutta, P. Garai, and A. Sinha, “Design of a reconfigurable DSP processor with bit efficient residue number system,” Int. J. VLSI Des. Commun. Syst., vol. 3, no. 5, pp. 175–189, 2012.

G. carlo Cardarilli, L. Di Nunzio, R. Fazzolari, A. Nannarelli, M. Petricca, and M. Re, “Design Space Exploration based Methodology for Residue Number System Digital Filters Implementation,” IEEE Trans. Emerg. Top. Comput., 2020.

J.-C. C. Bajard and L. Imbert, “A Full RNS Implementation of RSA,” IEEE Trans. Comput., vol. 53, no. 6, pp. 769–774, 2004.

J. Schwemmlein, K. C. Posch, and R. Posch, “RNS-modulo reduction upon a restricted base value set and its applicability to RSA cryptography,” Comput. Secur., vol. 17, no. 7, pp. 637–650, 1998.

S. Andraos and H. Ahmad, “A New efficient memoryless residue to binary converter,” IEEE Trans. circuits Syst., vol. 35, no. 11, pp. 1441–1444, 1988.

P. Patronik and S. J. Piestrak, “Design of reverse converters for general RNS moduli Sets {2^k, 2^n-1, 2^n+1, 2^(n+1)-1} and {2^k, 2^n-1, 2^n+1, 2^(n-1)-1} (n even),” IEEE Trans. Circuits Syst. I Regul. Pap., vol. 61, no. 6, pp. 1687–1700, 2014.

R. K. Jaiswal, R. Kumar, and R. A. Mishra, “Area Efficient Memoryless Reverse Converter for New Four Moduli Set {2^(n−1), 2^n − 1, 2^n + 1, 2^(2n+1 )− 1},” J. Circuits, Syst. Comput., no. 26, p. 1850075, 2017.

M. A. Hitz and E. Kaltofen, “Integer division in residue number systems,” IEEE Trans. Comput., vol. 44, no. 8, pp. 983–989, 1995.

Z. Torabi, G. Jaberipur, and A. Belghadr, “Fast division in the residue number system {2^n+ 1, 2^n, 2^n-1} based on shortcut mixed radix conversion,” Comput. Electr. Eng., vol. 83, p. 106571, 2020.

G. Dimauro, S. Impedovo, and G. Pirlo, “A new technique for fast number comparison in the residue number system,” IEEE Trans. Comput., vol. 42, no. 5, pp. 608–612, 1993.

L. Sousa, “Efficient method for magnitude comparison in RNS based on two pairs of conjugate moduli,” Proc. - Symp. Comput. Arith., pp. 240–247, 2007.

A. Hiasat, “A New Scaler for the Expanded 4-Moduli Set {2^k- 1, 2^k+ 1, 2^(2k)+ 1, 2^(2k)},” in 2020 11th International Conference on Information and Communication Systems (ICICS), 2020, pp. 429–433.

M. Askarzadeh, M. Hosseinzadeh, and K. Navi, “A New approach to overflow detection in moduli set {2^n-3, 2^n-1, 2^n+ 1, 2^n+ 3},” in 2009 Second International Conference on Computer and Electrical Engineering, 2009, vol. 1, pp. 439–442.

M. Rouhifar, M. Hosseinzadeh, S. Bahanfar, and M. Teshnehlab, “Fast Overflow Detection in Moduli Set {2^n – 1, 2^n, 2^n + 1},” Int. J. Comput. Sci., vol. 8, no. 3, pp. 407–414, 2011.

H. Siewobr and K. A. Gbolagade, “RNS Overflow Detection by Operands Examination,” Int. J. Comput. Appl., vol. 85, no. 18, pp. 1–5, 2014.

T. Van Vu, “Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding,” IEEE Trans. Comput., vol. c-34, no. 7, pp. 646–651, 1985.

G. Alia and E. Martinelli, “Sign detection in residue arithmetic units,” J. Syst. Archit., vol. 45, no. 3, pp. 251–258, 1998.

E. Al-Radadi and P. Siy, “RNS sign detector based on Chinese remainder theorem II (CRT II),” Comput. Math. with Appl., vol. 46, no. 10–11, pp. 1559–1570, 2003.

M. Akkal and P. Siy, “Optimum RNS sign detection algorithm using MRC-II with special moduli set,” J. Syst. Archit., vol. 54, no. 10, pp. 911–918, 2008.

T. Tomczak, “Fast Sign Detection for RNS (2^n-1, 2^n, 2^n+ 1),” IEEE Trans. Circuits Syst. I Regul. Pap., vol. 55, no. 6, pp. 1502–1511, 2008.

M. Xu, R. Yao, and F. Luo, “Low-Complexity Sign Detection Algorithm for RNS { 2^n − 1, 2^n, 2^n+1},” IEICE Trans. Electron., vol. E95.C, no. 9, pp. 1552–1556, 2012.

S. Kumar and C.-H. Chang, “A high-speed and area-efficient sign detector for three moduli set RNS {2^n, 2^n-1, 2^n+ 1},” in 2015 IEEE 11th International Conference on ASIC (ASICON), 2015, pp. 1–4.

S. Kumar and C.-H. Chang, “A New Fast and Area-Efficient Adder-Based Sign Detector for RNS {2^n-1, 2^n, 2^n+ 1},” IEEE Trans. Very Large Scale Integr. Syst., vol. 24, no. 7, pp. 2608–2612, 2016.

M. Xu, Z. Bian, and R. Yao, “Fast Sign Detection Algorithm for the RNS Moduli Set {2^(n+1) −1, 2^n −1, 2^n},” IEEE Trans. Very Large Scale Integr. Syst., vol. 23, no. 2, pp. 379–383, 2015.

C.-H. Chang and S. Kumar, “Area-efficient and fast sign detection for four-moduli set RNS {2^n- 1, 2^n, 2^n+ 1, 2^(2n)+ 1},” in 2014 IEEE International Symposium on Circuits and Systems (ISCAS), 2014, pp. 1540–1543.

C.-H. C. Sachin Kumar, “New Algorithm for Signed Integer Comparison in {2^(n+k), 2^n −1, 2^n +1, 2^(n±1) −1} and Its Efficient Hardware Implementation,” IEEE Trans. CIRCUITS Syst., vol. 64, no. 6, pp. 1481–1493, 2017.

A. Hiasat, “Sign detector for the extended four-moduli set { 2^n − 1 , 2^n + 1 , 2^(2 n) + 1 , 2^(n + k) },” IET Comput. Digit. Tech., vol. 12, no. 2, pp. 39–43, 2018.




DOI: http://doi.org/10.11591/ijeecs.v22.i1.pp%25p
Total views : 4 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

shopify stats IJEECS visitor statistics