Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem |
| |
Authors: | NI Chervyakov P A Lyakhov M G Babenko M A Deryabin |
| |
Affiliation: | Department of Applied Mathematics and Mathematical Modelling, North-Caucasian Federal University, Stavropol, Russian Federation |
| |
Abstract: | The residue number system (RNS) is an unconventional number system which can lead to parallel and fault-tolerant arithmetic operations. However, the complexity of residue-to-binary conversion for large number of moduli reduces the overall RNS performance, and makes it inefficient for nowadays high-performance computation systems. In this paper, we present an improved approximate Chinese remainder theorem (CRT) with the aim of performing efficient residue-to-binary conversion for general RNS moduli sets. To achieve this aim, the required number of fraction bits for accurate residue-to-binary conversion is derived. Besides, a method is proposed to substitute fractional calculations by similar computations based on integer numbers to have a hardware amenable algorithm. The proposed approach results in high-speed and low-area residue-to-binary converters for general RNS moduli sets. Therefore, with this conversion method, high dynamic range residue number systems suitable for cryptography and digital signal processing can be designed. |
| |
Keywords: | Computer arithmetic residue number systems chinese remainder theorem residue-to-binary converter residue arithmetic |
|
|