Chapter 11
Efficient Hardware Operations
for the Residue Number System
by Boolean Minimization
Danila Gorodecky and Tiziano Villa
11.1 Introduction
The idea of the residue number system (RNS) goes back to an ancient Chinese
source showing how to convert residues into numbers, and was later formalized
by C.F. Gauss in the nineteenth century. Since the advent of digital computers,
there have been many papers proposing algorithms to implement efficiently RNS
on computers.
The main advantage of RNS is the speed and reliability of arithmetic computations [3, 21, 23]. The first application of RNS was in the search of prime numbers.
Nowadays implementations of RNS can be found in anti-aircraft systems [12],
neural computations [3], real-time signal processing (pattern recognition) [6], and
cryptography [17]. Modular arithmetic (MA) is effective for processing large data
flows (with several hundreds or thousands bits) [15]. So RNS allows to increase
significantly hardware performance and to upgrade reliability and noise immunity
in signal processing and data transferring. A conference was held in 2005 in Russia
on the 50th anniversary of the introduction of RNS in scientific computations [9],
and it was reported on the key role of RNS in radars, in space and military aircraft
(e.g., Sukhoi) data transferring, and in other important technologies.
This contribution describes an efficient combinational hardware computation of
modular multiplication and of the modulus function (X(mod P )) for an arbitrary
modulo. We report also experimental results and compare with industrial tools.
D. Gorodecky ()
National Academy of Science of Belarus, Minsk, Belarus
e-mail: danila.gorodecky@gmail.com
T. Villa
University of Verona, Verona, Italy
e-mail: tiziano.villa@univr.it
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_11
237
Efficient Hardware Operations
for the Residue Number System
by Boolean Minimization
Danila Gorodecky and Tiziano Villa
11.1 Introduction
The idea of the residue number system (RNS) goes back to an ancient Chinese
source showing how to convert residues into numbers, and was later formalized
by C.F. Gauss in the nineteenth century. Since the advent of digital computers,
there have been many papers proposing algorithms to implement efficiently RNS
on computers.
The main advantage of RNS is the speed and reliability of arithmetic computations [3, 21, 23]. The first application of RNS was in the search of prime numbers.
Nowadays implementations of RNS can be found in anti-aircraft systems [12],
neural computations [3], real-time signal processing (pattern recognition) [6], and
cryptography [17]. Modular arithmetic (MA) is effective for processing large data
flows (with several hundreds or thousands bits) [15]. So RNS allows to increase
significantly hardware performance and to upgrade reliability and noise immunity
in signal processing and data transferring. A conference was held in 2005 in Russia
on the 50th anniversary of the introduction of RNS in scientific computations [9],
and it was reported on the key role of RNS in radars, in space and military aircraft
(e.g., Sukhoi) data transferring, and in other important technologies.
This contribution describes an efficient combinational hardware computation of
modular multiplication and of the modulus function (X(mod P )) for an arbitrary
modulo. We report also experimental results and compare with industrial tools.
D. Gorodecky ()
National Academy of Science of Belarus, Minsk, Belarus
e-mail: danila.gorodecky@gmail.com
T. Villa
University of Verona, Verona, Italy
e-mail: tiziano.villa@univr.it
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_11
237