Page 195 - Hardware Implementation of Finite-Field Arithmetic

176 Cha pte r Se v e n

where p = f . It must be noted that the P matrix given by Eqs. (7.21)
0, j j
and (7.22) is equivalent to the reduction matrix R given in Eq. (7.6)
and (7.7) and used in the two-step classic multiplication. In fact, R =
T
P (transposed matrix).
2
The matrix-vector operation given in Eq. (7.19) requires m
modulo 2 multiplications. Therefore, it can be proven that the space
2
complexity of a bit-parallel Mastrovito multiplier is m AND gates
2
2
and more than (m – 1) XOR gates [the equality, i.e., (m – 1) XOR gates
m
correspond to the irreducible trinomial f(x) = x + x + 1] [Paa94]. The
delay of the bit-parallel Mastrovito multiplier can also be upper
⎤
bounded by T ≤ T + ⎡log m T .
2
AND ⎢ 2 ⎥ XOR
4
3
Example 7.1 Multiplication for f(x) = x + x + 1
3
4
Let f(x) = x + x + 1 be the generating irreducible polynomial for
4
4
5
6
GF(2 ). The polynomials x , x , and x are given as:
x = 1 + x mod f(x) = 1 + x 3
4
3
x = x + x mod f(x) = 1 + x + x 3
4
5
5
2
6
2
x = x + x mod f(x) = 1 + x + x + x 3
These equations can be rewritten in matrix form in order to obtain
the P matrix, also obtained using Eqs. (7.21) and (7.22), as follows:
⎛ 1⎞
x ⎛ ⎞ ⎛ 10 0 1⎞
4
⎜ 5⎟ = ⎜ 11 0 1 ⎟ ⎜ ⎜ x ⎟ 4 3
x
⎜ ⎟ ⎜ ⎟ ⎜ x 2 ⎟ mod x + x + 1 (7.23)
x ⎝ ⎠ ⎝ 11 11 ⎠ ⎜ ⎟
6
x ⎝ ⎠
3
The product matrix Z can be finally obtained using Eqs. (7.19)
and (7.20):
a ⎛ a a + a a + a + a ⎞ b ⎛ ⎞
0
⎜ a 0 a 3 2 a 3 1 a + 2 a 3 ⎟ ⎜ ⎟
b
1
C = Z B = ⎜ 1 0 3 2 3 ⎟ ⎜ ⎟ (7.24)
⎜ a 2 a 1 a 0 a 3 ⎟ ⎜ b 2⎟
⎟ ⎜ ⎟
⎜ a ⎝ a a + a a + a + a a + a + a + ⎠ b ⎝ ⎠
b
a
3 2 3 1 2 3 0 1 2 3 3
Assume that the function
function matrix_P (f: poly_vector) return poly_matrix_
m2m1
computing the P matrix is implemented using Eq. (7.22) as follows
for j in 0 .. m-1 loop P(0,j) := f(j); end loop;
for i in 1 .. m-2 loop
for j in 0 .. m-1 loop P(i,j) := 0; end loop;
end loop;