A Division Algorithm in a Redundant Residue Number System Using Fractions
Open Access
- 18 January 2020
- journal article
- research article
- Published by MDPI AG in Applied Sciences
- Vol. 10 (2), 695
- https://doi.org/10.3390/app10020695
Abstract
The residue number system (RNS) is widely used for data processing. However, division in the RNS is a rather complicated arithmetic operation, since it requires expensive and complex operators at each iteration, which requires a lot of hardware and time. In this paper, we propose a new modular division algorithm based on the Chinese remainder theorem (CRT) with fractional numbers, which allows using only one shift operation by one digit and subtraction in each iteration of the RNS division. The proposed approach makes it possible to replace such expensive operations as reverse conversion based on CRT, mixed radix conversion, and base extension by subtraction. Besides, we optimized the operation of determining the most significant bit of divider with a single shift operation of the modular divider. The proposed enhancements make the algorithm simpler and faster in comparison with currently known algorithms. The experimental simulation using Kintex-7 showed that the proposed method is up to 7.6 times faster than the CRT-based approach and is up to 10.1 times faster than the mixed radix conversion approach.Funding Information
- Russian Science Foundation (19-19-00566)
This publication has 18 references indexed in Scilit:
- An FFT Circuit for a Spectrometer of a Radio Telescope using the Nested RNS including the Constant DivisionACM SIGARCH Computer Architecture News, 2017
- Binary-Ternary Plus-Minus Modular Inversion in RNSIEEE Transactions on Computers, 2016
- A comparative study on different moduli sets in residue number systemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Research challenges in next-generation residue number system architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- A general division algorithm for residue number systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Design and implementation of an RNS division algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fast RNS division algorithms for fixed divisors with application to RSA encryptionInformation Processing Letters, 1994
- An approximate sign detection method for residue numbers and its application to RNS divisionComputers & Mathematics with Applications, 1994
- A novel division algorithm for the residue number systemIEEE Transactions on Computers, 1992
- A new residue number system division algorithmComputers & Mathematics with Applications, 1990