A Parallel Implementation of the Reverse Converter for the Moduli Set {2n, 2n–1, 2n–1–1}

Authors: Mehdi Hosseinzadeh, Amir Sabbagh Molahosseini, Keivan Navi

Abstract:

In this paper, a new reverse converter for the moduli set {2n, 2n–1, 2n–1–1} is presented. We improved a previously introduced conversion algorithm for deriving an efficient hardware design for reverse converter. Hardware architecture of the proposed converter is based on carry-save adders and regular binary adders, without the requirement for modular adders. The presented design is faster than the latest introduced reverse converter for moduli set {2n, 2n–1, 2n–1–1}. Also, it has better performance than the reverse converters for the recently introduced moduli set {2n+1–1, 2n, 2n–1}

Keywords: Residue arithmetic, Residue number system, Residue-to-Binary converter, Reverse converter

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332428

References:

[1] N. S. Szabo and R. I. Tanaka, Residue Arithmetic and its Applications to Computer Technology. New York: McGraw Hill, 1967.
[2] Y. Wang, X. Song, M. Aboulhamid, and H. Shen, "Adder based residue to binary numbers converters for (2n-1, 2n, 2n+1)," IEEE Trans. Signal Processing, vol. 50, no. 7, pp. 1772-1779, 2002.
[3] Z. Wang, G. Jullien, and W. Miller, "An Improved Residue to Binary Converter," IEEE Trans. Circuits Syst.-I, vol. 45, no. 9, pp. 998-1002, 2000.
[4] A. Hariri, K. Navi, and R. Rastegar, "A new high dynamic range moduli set with efficient reverse converter," Elsevier Journal of Computers and Mathematics with Applications, vol. 55, no. 4, pp. 660-668, 2008.
[5] A. Hiasat and H. S. Abdel-Aty-Zohdy, "Residue-to-binary arithmetic converter for the moduli set (2k, 2k-1, 2k-1-1)," IEEE Trans. Circuits Syst.-II, vol. 45, no. 2, pp. 204-208, 1998.
[6] W.Wang, M. N. S. Swamy, M. O. Ahmad, and Y.Wang, "A high-speed residue-to-binary converter and a scheme of its VLSI implementation," IEEE Trans. Circuits Syst.-II, vol. 47, no. 12, pp. 1576-1581, 2000.
[7] P.V.A. Mohan,. "RNS-To-Binary converter for a new three-moduli set {2n+1-1, 2n, 2n-1}," IEEE Trans. Circuits Syst.-II, vol. 54, pp. 775-779, 2007.
[8] M. Hosseinzadeh, A.S. Molahosseini, and K. Navi, "An improved reverse converter for the moduli set {2n-1, 2n, 2n+1, 2n+1-1}," IEICE Electronics Express, In Press, 2008.
[9] C.H. Chang, S. Menon, B. Cao, and T. Srikanthan , "A configurable dual moduli multi-operand modulo adder," Proc. IEEE Symp. Circuits Syst., vol. 2, pp. 1630-1633, 2005.
[10] Y. Wang, "Residue-to-Binary Converters Based on New Chinese remainder theorems," IEEE Trans. Circuits Syst.-II, vol. 47, no. 3, pp. 197-205, 2000.
[11] A.S. Molahosseini, K. Navi, O. Hashemipour, and A. Jalali, "An efficient architecture for designing reverse converters based on a general three-moduli set, Elsevier Journal of Systems Architecture, In Press, 2008.
[12] C. Efstathiou, D. Nikolos, and J. Kalamatianos, "Area-time efficient modulo 2n-1 adder design," IEEE Trans. Circuits Syst.-II, vol. 41, pp. 463-467, 1994.