Sign Detection and Signed Integer Comparison  for the 3-Moduli Set {2^n±1,2^(n+k)}

Zeinab Torabi; Somayeh Timarchi

doi:10.7494/csci.2021.22.3.3955

Authors

Zeinab Torabi Department of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran https://orcid.org/0000-0002-2526-688X
Somayeh Timarchi

DOI:

https://doi.org/10.7494/csci.2021.22.3.3955

Keywords:

computer arithmetic, residue number system, signed integer comparison, dynamic range partitioning

Abstract

Comparison, division and sign detection are considered complicated operations in residue number system (RNS). A straightforward solution is to convert RNS numbers into binary formats and then perform complicated operations using conventional binary operators. If efficient circuits are provided for comparison, division and sign detection, the application of RNS can be extended to the cases including these operations.

For RNS comparison in the 3-moduli set , we have only found one hardware realization. In this paper, an efficient RNS comparator is proposed for the moduli set which employs sign detection method and operates more efficient than its counterparts. The proposed sign detector and comparator utilize dynamic range partitioning (DRP), which has been recently presented for unsigned RNS comparison. Delay and cost of the proposed comparator are lower than the previous works and makes it appropriate for RNS applications with limited delay and cost.

Downloads

Download data is not yet available.

References

Bernocchi G. L., Cardarilli G. C., Del Re A., Nannarelli A., Re M.: Low-power adaptive filter based on RNS components. In: IEEE International Symposium on Circuits and Systems, pp. 3211-3214, 2007.

Madhukumar A. S., Chin F.: Enhanced architecture for residue number system-based CDMA for high-rate data transmission, In: IEEE Transactions on Wireless Communications, vol. 3(5), pp. 1363-1368, 2004.

Schinianakis D. M., Fournaris A. P., Michail H. E., Kakarountas A. P., Stouraitis T.: An RNS implementation of an F_p elliptic curve point multiplier. In: IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 56(6), pp. 1202-1213, 2008.

Wang W., Swamy M. N. S., Ahmad M. O.: RNS application for digital image processing. In: 4th IEEE international workshop on system-on-chip for real-time applications, pp. 77-80, 2004.

Bi S., Gross W. J.: The mixed-radix Chinese remainder theorem and its applications to residue comparison. In: IEEE Transactions on Computers, vol. 57(12), pp.1624-1632, 2008.

Torabi Z., Jaberipur G.: Low-power/cost RNS comparison via partitioning the dynamic range. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 24(5), pp. 1849-1857, 2015.

Gbolagade K. A., Voicu G. R., Cotofana S. D.: Memoryless RNS-to-Binary Converters for the Moduli set {2^(n+1)-1,2^n-1,2^n+1}, In: 21th IEEE Int. Conf. on Application-specific Systems Architectures and Processors (ASAP), pp. 301-304, 2010.

Gbolagade K. A., Chaves R., Sousa L., Cotofana S. D.: Residue-to-Binary Converters for the Moduli Set {2^(2n+1)-1,2^2n,2^n-1}, In: 2nd International Conference on Adaptive Science & Technology (ICAST), pp. 26-33, 2009.

Gbolagade K. A., Chaves R., Sousa L., Cotofana S. D.: An improved RNS reverse converter for the {2^(2n+1)- 1,2^n,2^n-1} moduli set. In: IEEE International Symposium on Circuits and Systems, pp. 2103-2106, 2010.

Mohan P. V. A.: RNS-to-binary converter for a new three-moduli set. In: IEEE Transactions on Circuits and System II, vol. 54(9), pp. 775-779, 2007.

Chaves R., Sousa L.: {2^n+1,2^(n+k),2^n-1}: a new RNS moduli set extension. In: Euromicro Symposium on Digital System Design, pp. 210-217, 2004.

Sousa L., and Martins P.: Sign Detection and Number Comparison on RNS 3-Moduli Sets {2^n-1,2^(n+ x),2^n+1}. In: Circuits, Systems, and Signal Processing, vol. 36(3), pp. 1224-1246, 2017.

Sousa L.: Efficient method for magnitude comparison in RNS based on two pairs of conjugate moduli. In: ARITH'07: 18th IEEE Symposium on Computer Arithmetic, pp. 240-250, 2007.

Dimauro G., Impedovo S., Pirlo G.: A new technique for fast number comparison in the residue number system. In: IEEE Transactions on computers, 42(5), pp. 608-612, 1993.

Wang Y., Song X., Aboulhamid M.: A new algorithm for RNS magnitude comparison based on new Chinese remainder theorem II. In: Ninth Great Lakes Symposium on VLSI, pp. 362-365, 1999.

Tay T. F., Chang C. H.: New algorithm for signed integer comparison in four-moduli {2^n,2^n-1,2^n+1,2^(n+1)-1}. In: APCCAS: IEEE Asia Pacific Conference on Circuits and Systems, pp. 519-522, 2014.

Szabo N. S., Tanaka R. I.: Residue arithmetic and its applications to computer technology, McGraw-Hill, 1967.

Torabi Z., Jaberipur G.: Fast low energy RNS comparators for 4-moduli sets {2^n±1,2^n,m} with m∈{2^(n+1)±1,2^(n-1)-1}. In: Integration, vol. 55, pp. 155-161, 2016.

Zarei B., Askarzadeh M., Derakhshanfard N., Hosseinzadeh M.: A high-speed Residue Number comparator For the 3-Moduli Set {2^n-1,2^n+1,2^n+3}. In: International Symposium on Signals, Systems and Electronics, vol. 1, pp. 1-4, 2010.

Torabi Z., Belghadr A.: Efficient RNS Comparator via Dynamic Range Partitioning: The Case of {2^n-1,2^n,2^(n+1)-1}. In: The CSI Journal on Computer Science and Engineering, vol. 14, pp. 38-43, 2019.

Miller D. D., Altschul R. E., King J. R., Polky J. N.: Analysis of the residue class core function of Akushskii, Burcev, and Pak. In: Residue number system arithmetic: modern applications in digital signal processing, pp. 390-401, 1986.

Dimauro G., Impedovo S., Pirlo G., Salzo A.: RNS architectures for the implementation of the diagonal function. In: Information processing letters, vol. 73(5-6), pp. 189-198, 2000.

Wang Y.: New Chinese remainder theorems. In: Conference Record of Thirty-Second Asilomar Conference on Signals, Systems and Computers, vol. 1, pp. 165-171, 1998.

Kalampoukas L., Nikolos D., Efstathiou C., Vergos H. T., Kalamatianos J.: High-speed parallel-prefix module 2n-1 adders. In: IEEE Trans. Comput., vol. 49(7), pp. 673–680, 2000.

Tyagi A.: A reduced-area scheme for carry-select adders. In: IEEE Transactions on Computers, vol. 42(11), pp. 63–70, 1993.