11 Hardware Realization of Arithmetic Operations
251
a s s i g n temp_R_2 = temp_R_1 [ 3 : 1 ] + r 5 + r 6 ;
always @( temp_R_2 )
begin
i f ( temp_R_2 >= 4 7 )
temp_R <= temp_R_2 − 4 7 ;
e l s e
temp_R <= temp_R_2 ;
end
a s s i g n R = temp_R ;
endmodule
There are six external blocks in Listing 11.2: mult 3x3, two mult 3x38, mult 3x317,
mult 38, and mult 217. All these blocks consist of Boolean functions with hundreds
of product terms (which we do not represent to save space). In the next section
we discuss the impact of Boolean function minimization in modular computations.
11.5 Boolean Minimization in Modular Operations
The result of any arithmetic computation can be represented as sum-of-products
(SOPs). However the original representation given by truth tables may be unmanageable by synthesis tools, e.g., the truth table of the product of two 16-bit input
operands requires 64 columns (16 columns for each operand and 32 columns for the
result) and more than four billions rows.
For a pair of δ-bit tuples, consider 2 i (mod P ) X i ·
2 δ·(i−1) (mod P ), where
i = 1, 2, . . . , k, are the corresponding factors of the multiplication. Then
2 i (mod P ) is a constant whose bits are redundant in the minimization, because
all rows in the truth table corresponding to this constant have the same value
2 i (mod P ).
The initial truth table for X(mod P ) consists of P rows and 2 · δ columns, where
the left δ columns correspond to all integers from 0 up to P − 1, and the right
columns correspond to X · 2 i (mod P ).
Example Consider 2 8 (mod 13) = 9(mod 13) = 1001 2 . In this case (Table 11.1),
subtable 1 represents the truth table for X · 9(mod 13) before minimization and
subtable 2 represents the SOP after minimization (it can obtained by tools like [8]
or ELS [1]). So the first four bits in the last row of the truth table in subtable 1
represent 12 10 , and the right four bits represent 12 · 9(mod 13) = 4 10 . For the 18-bit
input X and P = 47, all pairs of corresponding factors are represented as a SOP:
with 12 columns (6 inputs and 6 outputs) X 2 · 17(mod 47) and X 3 · 7(mod 47);
with 11 columns (5 inputs and 6 outputs) X 1
2 · 17(mod 47); with 9 columns (3
251
a s s i g n temp_R_2 = temp_R_1 [ 3 : 1 ] + r 5 + r 6 ;
always @( temp_R_2 )
begin
i f ( temp_R_2 >= 4 7 )
temp_R <= temp_R_2 − 4 7 ;
e l s e
temp_R <= temp_R_2 ;
end
a s s i g n R = temp_R ;
endmodule
There are six external blocks in Listing 11.2: mult 3x3, two mult 3x38, mult 3x317,
mult 38, and mult 217. All these blocks consist of Boolean functions with hundreds
of product terms (which we do not represent to save space). In the next section
we discuss the impact of Boolean function minimization in modular computations.
11.5 Boolean Minimization in Modular Operations
The result of any arithmetic computation can be represented as sum-of-products
(SOPs). However the original representation given by truth tables may be unmanageable by synthesis tools, e.g., the truth table of the product of two 16-bit input
operands requires 64 columns (16 columns for each operand and 32 columns for the
result) and more than four billions rows.
For a pair of δ-bit tuples, consider 2 i (mod P ) X i ·
2 δ·(i−1) (mod P ), where
i = 1, 2, . . . , k, are the corresponding factors of the multiplication. Then
2 i (mod P ) is a constant whose bits are redundant in the minimization, because
all rows in the truth table corresponding to this constant have the same value
2 i (mod P ).
The initial truth table for X(mod P ) consists of P rows and 2 · δ columns, where
the left δ columns correspond to all integers from 0 up to P − 1, and the right
columns correspond to X · 2 i (mod P ).
Example Consider 2 8 (mod 13) = 9(mod 13) = 1001 2 . In this case (Table 11.1),
subtable 1 represents the truth table for X · 9(mod 13) before minimization and
subtable 2 represents the SOP after minimization (it can obtained by tools like [8]
or ELS [1]). So the first four bits in the last row of the truth table in subtable 1
represent 12 10 , and the right four bits represent 12 · 9(mod 13) = 4 10 . For the 18-bit
input X and P = 47, all pairs of corresponding factors are represented as a SOP:
with 12 columns (6 inputs and 6 outputs) X 2 · 17(mod 47) and X 3 · 7(mod 47);
with 11 columns (5 inputs and 6 outputs) X 1
2 · 17(mod 47); with 9 columns (3