Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem

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

2010 AMS SUBJECT CLASSIFICATIONS:

• 65Y04
• 65Y05
• 65Y20
• 65Y10

ORCID

N.I. Chervyakov http://orcid.org/0000-0002-4355-085X

A.S. Molahosseini http://orcid.org/0000-0003-3603-9401

P.A. Lyakhov http://orcid.org/0000-0003-0487-4779

M.G. Babenko http://orcid.org/0000-0002-1892-8232

M.A. Deryabin http://orcid.org/0000-0002-6761-3667