New VLSI circuit architectures for addition and multiplication
modulo (2
n
1) and (2
n + 1) are proposed that
allow the implementation of highly efficient combinational
and pipelined circuits for modular arithmetic. It is shown
that the parallel-prefix adder architecture is well suited to
realize fast end-around-carry adders used for modulo addition.
Existing modulo multiplier architectures are improved
for higher speed and regularity. These allow the use of
common multiplier speed-up techniques like Wallace-tree
addition and Booth recoding, resulting in the fastest known
modulo multipliers. Finally, a high-performance modulo
multiplier-adder for the IDEA block cipher is presented.
The resulting circuits are compared qualitatively and quantitatively,
i.e., in a standard-cell technology, with existing
solutions and ordinary integer adders and multipliers.
Arithmetic modulo 2n+1 has found applicability in a variety of fields ranging from pseudorandom
number generation and cryptography up to convolution computations without round-off errors. Also modulo
2
n+1 operator are commonly included in residue number system (RNS) applications. The RNS is an arithmetic
system which decomposes a number into parts (residues) and performs arithmetic operations in parallel for each
residue without the need of carry propagation among them, leading to significant speedup over the
corresponding binary operations. RNS is well suited to applications that are rich of addition/subtraction and
multiplication operations and has been adopted in the design of digital signal processors FIR filters and
communication components offering in several cases apart from enhanced operation speed, low-power
characteristics We shall also briery discuss one other unconventional number system that has found some
practical use in computer arithmetic; this is the redundant 1 signed-digit number system. We have two
objectives in these preliminary discussions. The first is to facilitate a contrast between RNS and commonly used
number systems. The second is to to recall a few basic properties of the conventional number systems, as
ultimately, it is these that form the basis of implementations of residue arithmetic. The sub sequent introduction
to RNS consists of some basic definitions, a discussion of certain desirable features of a residue number system,
and a discussion of the basic arithmetic operations.
For reducing the area complexity of the parallel-prefix solutions, select-prefix and circular carry select
IEAC adders have been proposed. Unfortunately, both these proposals achieve a smaller operating speed than
the parallel-prefix ones. Recently, very fast IEAC adders that use the Ling carry formulation of parallel-prefix
addition have appeared in that also suffer from the requirement of a double parallel-prefix computation tree.