Page 191 - Hardware Implementation of Finite-Field Arithmetic

172 Cha pte r Se v e n

implementing Eq. (7.14) according to Eqs. (7.15) and (7.16) and therefore,
the polynomial xa(x) mod f(x) has been defined, where poly_vector is a
bit vector from 0 to m – 1. Assume also that the functions
function m2abv(x: bit; y: poly_vector) return poly_vector
function m2xvv(x, y: poly_vector) return poly_vector

returning the multiplication of a bit x by a bit vector y (x AND y , x AND
0
y , . . . , x AND y ), and the bit-wise XOR of two bit vectors (x XOR y ,
1 m − 1 0 0
x XOR y , . . . , x XOR y ), respectively, have also been defined.
1 1 m − 1 m − 1
When the bits of b(x) are processed from the most-significant bit
to the least-significant bit, then the shift-and-add method receives the
name of most-significant bit-serial (MSB) multiplier.
Algorithm 7.2—MSB-first multiplier

for i in 0 . . m-1 loop c(i) := 0; end loop;
for i in reverse 0 .. m-1 loop
c := m2xvv(Product_alpha_A(c,f), m2abv(b(i),a));
end loop;
An executable Ada file MSBfirst.adb, including Algorithm 7.2, is
available at www.arithmetic-circuits.org. It is important to note that
Algorithm 7.2 is the binary version of the MSE-first multiplier given
in Algorithm 5.6.
Notice that in Algorithm 7.2, the computation of ba(x) and xc(x)
i
mod f(x) can be performed in parallel as they are independent of each
other. However, the value of c in each iteration depends on both the
value of c at the previous iteration and on the value of ba(x). This
i
dependency has the effect of making the MSB multiplier have a longer
critical path than that of the least-significant-bit (LSB) multiplier.
In a least-significant-bit (LSB) multiplier, the coeffic ients of b(x) are
processed starting from the least-significant bit b and continue with the
0
remaining coefficients one at a time in ascending order. Thus multiplication
according to this scheme is performed in the following way:
c(x) = a(x)b(x) mod f(x)

= (b a(x) + b a(x)x + b a(x)x + . . . + b a(x)x m - 1 ) mod f(x)
2
0 1 2 m - 1
2
= (b a(x) + b (a(x)x) + b (a(x)x ) + . . . + b (a(x)x m - 1 )) mod f(x) (7.17)
0 1 2 m - 1
= (b a(x) + b (a(x)x) + b (a(x)x)x + . . . + b (a(x)x m - 2 )x) mod f(x)
0 1 2 m - 1
Algorithm 7.3—LSB-first multiplier
for i in 0 . . m-1 loop c(i) := 0; end loop;
for i in 0 .. m-1 loop
c := m2xvv(m2abv(b(i),a),c);
a := Product_alpha_A(a,f);
end loop;