Abstract
In this paper, we propose a reverse converter from the balanced Residue Number System (RNS) with low-cost moduli set {2^n, 2^n−1, 2^(n + 1)−1} to the Binary Number System (BNS). The proposed method is based on the Chinese remainder theorem with fractions (CRTf) for the reverse conversion device. Constant coefficients are calculated in detail, where the bit width depends only on the value of n. Proposed a device architecture using parallel adders to speed up calculations. Hardware modeling of a reverse converter from balanced RNS with moduli set {2^n, 2^n−1, 2^(n + 1)−1} to the positional number system (PNS) was carried out using the field-programmable gate arrays (FPGA) in the VHDL. The results show that the proposed method achieves a faster performance by an average of 8.5% and lower hardware costs by an average of 10.5% compared to the state-of-the-art method. The proposed development can find wide applications in both digital signal and image processing based on RNS.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Parhami B (2010) Computer arithmetic Oxford University Press, 2nd edn. New York, Oxford University Press
Kumar CS, Prathiba A, Bhaskaran VSK (2016) Implementation of RNS and LNS based addition and subtraction units for cryptography. In: International conference on VLSI systems, architectures, technology and applications (VLSI-SATA), pp 1–5
Hiasat A (2019) A reverse converter for three-moduli set (2k, 2n-1, 2n+1), k < n. In: IEEE Jordan international joint conference on electrical engineering and information technology (JEEIT), pp 548–553
Hiasat A, Sousa L, Anta AF (2019) On the design of RNS inter-modulo processing units for the arithmetic-friendly moduli sets {2n+k, 2n–1, 2n+1−1}. Comput J 62(2):292–300
Hiasat A (2017) An efficient reverse converter for the three-moduli set (2n+1-1, 2n, 2n–1). IEEE Trans Circ Syst II Express Briefs 64(8):962–966
Muralidharan R, Chang C (2012) Area-power efficient modulo 2n–1 and modulo 2n+1 multipliers for 2n–1, 2n, 2n+1 based RNS. IEEE Trans Circuits Syst I Regul Pap 59(10):2263–2274
Chervyakov NI, Lyakhov PA, Deryabin MA, Nagornov NN, Valueva MV, Valuev GV (2020) Residue number system-based solution for reducing the hardware cost of a convolutional neural network. Neurocomputing 407:439–453
Boyvalenkov P, Chervyakov NI, Lyakhov P, Semyonova N, Nazarov A, Valueva M, Boyvalenkov G, Bogaevskiy D, Kaplun D (2020) Classification of moduli sets for residue number system with special diagonal functions. IEEE Access 8:156104–156116
Lyakhov P, Bergerman M, Semyonova N, Kaplun D Voznesensky A (2021) Design reverse converter for balanced rns with three low-cost modules. In: 2021 10th mediterranean conference on embedded computing (MECO), pp 1–7
Chervyakov NI, Molahosseini AS, Lyakhov PA, Babenko MG, Deryabin MA (2017) Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem. Int J Comput Math 94:1833–1849
Acknowledgements
The work of P.A. Lyakhov was supported by the Presidential Council for grants (project no. MК-3918.2021.1.6). The work of D.I. Kaplun was supported by the Russian Science Foundation, project no.19-19-00566. The work of M.V. Bergerman is supported by North-Caucasus Center for Mathematical Research under agreement №. 075-02-2021-1749 with the Ministry of Science and Higher Education of the Russian Federation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bergerman, M., Lyakhov, P., Semyonova, N., Bogaevskiy, D., Kaplun, D. (2022). CRTf-Based Reverse Converter for RNS with Low-Cost Modules \(\{{2}^{n},{2}^{n}-1,{2}^{n+1}-1\}\). In: Tchernykh, A., Alikhanov, A., Babenko, M., Samoylenko, I. (eds) Mathematics and its Applications in New Computer Systems. MANCS 2021. Lecture Notes in Networks and Systems, vol 424. Springer, Cham. https://doi.org/10.1007/978-3-030-97020-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-97020-8_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-97019-2
Online ISBN: 978-3-030-97020-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)