11 Hardware Realization of Arithmetic Operations
247
For illustration, consider the following example. Suppose that X is an 18-bit
input and P = 47. Then modulo P is a 6-bit number, and the input X is split
into three 6-bit tuples X = (X 3 , X 2 , X 1 ), where X 1 = (x 6 , x 5 , . . . , x 1 ), X 2 =
(x 12 , x 11 , . . . , x 7 ), and X 3 = (x 18 , x 17 , . . . , x 13 ). Then 2 6 (mod 47) = 17(mod 47)
and 2 12 (mod 47) = 7(mod 47). Hence, in the first iteration Eq. (11.3) takes the
following form:
X(mod 47) = X 1 + X 2 · 2
6 (mod 47) + X 3 · 2
12 (mod 47)
= X 1 + X 2 · 17(mod 47) + X 3 · 7(mod 47) = S 1
If input X = 2 18 −1, then its binary representation requires 18 bits, i.e., X 1 = X 2 =
X 3 = 63 10 = 111111 2 . Then S 1 ≤ 63 + 63 · 17 + 63 · 7 = 1575 10 = 11000100111 2 .
In this case Eq. (11.3) takes the following form:
S 1 (mod 47) = S
1
1 + S
1
2 · 2
6 (mod 47)
= S
1
1 + S
1
2 · 17(mod 47) = S 2 ≤ 447.
If S 1
1 = 1001110 2 and S 1
2 = 11000 2 , it follows S 2 = 447. The second iteration splits
the 9-bit S 2 number into two 6-bit and 3-bit tuples: S 2 =
S 2
2 , S 2
1
, where S 2
2 =
s 2
9 , s 2
8 , s 2
7
and S 2
1 =
s 2
6 , s 2
5 , . . . , s 2
1
. In this case Eq. (11.3) takes the following
form:
S 2 (mod 47) = S
2
1 + S
2
2 · 17(mod 47) = S 3 ≤ 148.
If S 2
1 = 111111 2 and S 2
2 = 101 2 , it follows S 3 = 148. The third iteration
splits the 8-bit number S 3 into two 6-bit and 2-bit tuples: S 3 =
S 3
2 , S 3
1
, where
S 3
2 =
s 3
8 , s 3
7
and S 3
1 =
s 3
6 , s 3
5 , . . . , s 3
1
. In this case Eq. (11.3) takes the following
form:
S 3 (mod 47) = S
3
1 + S
3
2 · 17(mod 47) = S 4 ≤ 54.
If S 3
1 = 010100 2 and S 3
2 = 10 2 , it follows S 4 = 54. Since S 4 < 2 · P = 94,
S 4 is compared with P = 47: if S 4 > 47, then X(mod 47) = S 4 − 47, else
X(mod 47) = S 4 .
We provide a Verilog functional representation of this example in Listing 11.1
for X(mod 47), where X is a 100−bit number.