Page 143 - Hardware Implementation of Finite-Field Arithmetic

126 Cha pte r F i v e

The Least Significant Element (LSE) first multiplication starts with
the lowest coefficient b of the multiplier polynomial and continues
0
with the remaining coefficients one at the time in ascending order.
Hence, multiplication according to this scheme can be performed in
the following way:

2
a(x)b(x) = b a(x) + b (a(x)x) + b (a(x)x ) + . . . + b (a(x)x m − 1 ) (5.11)
0 1 1 m − 1
where all coefficient arithmetic is done modulo p.

Algorithm 5.7—LSE-first multiplier

for i in 0 .. m -1 loop
c := addition_mod_f_poly(product(a,b(i)),c);
a := multiply_by_x_zp(a,f);
end loop;

An executable Ada file LSEfirst.adb, including Algorithm 5.7, is
available at www.arithmetic-circuits.org. It can be noted that the
implementation of the LSE-first multiplier presented in Algorithm 5.7
is slightly more complex than the implementation given for the MSE-
first multiplier (Algorithm 5.6), because the LSE-first multiplier
requires one register for c(x) and another one for a(x). However, LSE-
first multipliers are faster than MSE-first ones, because c(x) and a(x)
can be updated in parallel. In general, LSE-first scheme is faster than
MSE-first.
A VHDL model has been generated for p = 239. It uses two
components described in Chap. 3 (mod_239_reducer.vhd and subtractor_
mod_p.vhd). The complete VHDL file LSE_first_mod_f_multiplier.vhd
is available at www.arithmetic-circuits.org. The datapath is given in
Fig. 5.3. The entity declaration is the following:

entity LSE_first_mod_f_multiplier is
port(
a, b: in polynomial;
clk, reset, start: in std_logic;
z: out polynomial;
done: out std_logic
);
end LSE_first_mod_f_multiplier;

The VHDL architecture is the following:

next_c_calc: for i in 0 to m-1 generate
mult_add(i) <= ( int_b(0) * int_a(i) ) + c(i);
comp1: mod_239_reducer port map(mult_add(i),
next_c(i));
end generate;