11 Hardware Realization of Arithmetic Operations
241
11.3.1 Approach Based on Reducing the Input Bit-by-Bit
In [2], the authors proposed a sequence made by a chain of homogeneous arithmetic
blocks, and combinational architectures for pseudorandom number generator. This
yields a modulus function architecture based on the following representation:
X = P · Q + R
= P · 2
δ
· q δ + P · 2
δ−1
· q δ−1 + . . . + P · 2
0
· q 0 + R
(11.2)
and X(mod P ) = R, where X = (x ψ , x ψ−1 , . . . , x 1 ) and δ is defined by the
inequality P · 2 δ+1 < 2 ψ − 1 ≤ P · 2 δ . Notice that P can be an arbitrary number.
Every computational block executes comparison, multiplexing, multiplication by a
constant, and subtraction.
For instance, X = (x 10 , x 9 , . . . , x 1 ) and P = 21, hence δ = 5. In this case (11.2)
takes the following form:
X = 21 · Q + R
= 21 · 2
5
· q 5 + 21 · 2
4
· q 4 + 21 · 2
3
· q 3
+ 21 · 2
2
· q 2 + 21 · 2
1
· q 1 + 21 · 2
0
· q 0 + R.
This representation consists of seven addends, where the last R is the result
of a modulus function computation and the remaining six addends represent an
arithmetic unit. We assign X = X 5 as input of the first unit; X 4 is the output of
the first unit and the input of the second unit; X 3 is the output of the second unit
and the input of the third unit; X 2 is the output of the third unit and the input of the
fourth unit; X 1 is the output of the fourth unit and the input of the fifth unit; X 0 is
the output of the fifth unit and input of the sixth unit; R is the output of the sixth
unit and the result of the X(mod 21) computation.
Assume that X = 888. Thus X = 888 (mod 21) will be computed by the
following six steps:
– as X 5 ≥ 21 · 2 5 , i.e., 888 ≥ 672, then X 4 = 888 − 21 · 2 5 = 216;
– as X 4 < 21 · 2 4 , i.e., 216 < 336, then X 3 = 216;
– as X 3 ≥ 21 · 2 3 , i.e., 216 ≥ 168, then X 2 = 216 − 21 · 2 3 = 48;
– as X 2 < 21 · 2 2 , i.e., 48 < 84, then X 1 = 48;
– as X 1 ≥ 21 · 2 1 , i.e., 48 ≥ 42, then X 0 = 48 − 21 · 2 1 = 6;
– as X 0 < 21 · 2 0 , i.e., 6 < 21, then R = 6.
This approach can be pipelined (1-dimensional) very efficiently by including
triggers between homogeneous blocks; moreover, it can be simplified by optimizing
the arithmetic operations in every block [7] and organizing a 2-dimensional systolic
matrix.
241
11.3.1 Approach Based on Reducing the Input Bit-by-Bit
In [2], the authors proposed a sequence made by a chain of homogeneous arithmetic
blocks, and combinational architectures for pseudorandom number generator. This
yields a modulus function architecture based on the following representation:
X = P · Q + R
= P · 2
δ
· q δ + P · 2
δ−1
· q δ−1 + . . . + P · 2
0
· q 0 + R
(11.2)
and X(mod P ) = R, where X = (x ψ , x ψ−1 , . . . , x 1 ) and δ is defined by the
inequality P · 2 δ+1 < 2 ψ − 1 ≤ P · 2 δ . Notice that P can be an arbitrary number.
Every computational block executes comparison, multiplexing, multiplication by a
constant, and subtraction.
For instance, X = (x 10 , x 9 , . . . , x 1 ) and P = 21, hence δ = 5. In this case (11.2)
takes the following form:
X = 21 · Q + R
= 21 · 2
5
· q 5 + 21 · 2
4
· q 4 + 21 · 2
3
· q 3
+ 21 · 2
2
· q 2 + 21 · 2
1
· q 1 + 21 · 2
0
· q 0 + R.
This representation consists of seven addends, where the last R is the result
of a modulus function computation and the remaining six addends represent an
arithmetic unit. We assign X = X 5 as input of the first unit; X 4 is the output of
the first unit and the input of the second unit; X 3 is the output of the second unit
and the input of the third unit; X 2 is the output of the third unit and the input of the
fourth unit; X 1 is the output of the fourth unit and the input of the fifth unit; X 0 is
the output of the fifth unit and input of the sixth unit; R is the output of the sixth
unit and the result of the X(mod 21) computation.
Assume that X = 888. Thus X = 888 (mod 21) will be computed by the
following six steps:
– as X 5 ≥ 21 · 2 5 , i.e., 888 ≥ 672, then X 4 = 888 − 21 · 2 5 = 216;
– as X 4 < 21 · 2 4 , i.e., 216 < 336, then X 3 = 216;
– as X 3 ≥ 21 · 2 3 , i.e., 216 ≥ 168, then X 2 = 216 − 21 · 2 3 = 48;
– as X 2 < 21 · 2 2 , i.e., 48 < 84, then X 1 = 48;
– as X 1 ≥ 21 · 2 1 , i.e., 48 ≥ 42, then X 0 = 48 − 21 · 2 1 = 6;
– as X 0 < 21 · 2 0 , i.e., 6 < 21, then R = 6.
This approach can be pipelined (1-dimensional) very efficiently by including
triggers between homogeneous blocks; moreover, it can be simplified by optimizing
the arithmetic operations in every block [7] and organizing a 2-dimensional systolic
matrix.