Page 183 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 165

⎛ d ⎞ ⎛ a 0 0 0 0 0 0 ⎞
0
⎜ ⎟ ⎜ a a 0 0 0 0 ⎟
⎜ d 1 ⎟ ⎜ 1 0 ⎟
⎜ d 2 ⎟ ⎜ a 2 a 1 1 a 0 0 0 0 ⎟ ⎛ b ⎞
⎜ ⎟ ⎜ ⎟ 0
⎜ ⎟ ⎜ a a a a a 0 ⎟ ⎜ b 1 ⎟
−
⎜ d m 2 ⎟ ⎜ m− 2 m− 3 m− 4 m− 5 0 ⎟ ⎜ ⎜ b ⎟
⎜ d m 1 ⎟ = a ⎜ ⎜ m− 1 a m− 2 a a m−3 a m− 4 a 1 a ⎟ ⎜ 2 ⎟ (7.3)
−
0
⎜ d ⎟ ⎜ ⎟ ⎜ ⎟
⎜
⎜ m ⎟ ⎜ 0 a m−1 a m−2 a m−3 a 2 a 1 ⎟ b ⎟
⎜ ⎜ d m 1 ⎟ ⎜ 0 0 a m−1 a m−2 a a 3 a ⎟ ⎜ b ⎜ m −2 ⎟ ⎟
+
2
⎜ ⎟ ⎜ ⎟ ⎝ m 1⎠
−
⎜ ⎟ ⎜ ⎟
⎜ d 2 − ⎜ 0 0 0 0 a m 1 a m 2 ⎟
m 3 ⎟
−
−
m 2⎠
⎝ d ⎜ 2 − ⎟ ⎜ ⎝ 0 0 0 0 0 a m 1⎠ ⎟
− .
The above equation is equal to Eq. (5.3) but with coefficients in
GF(2). From Eq. (7.3), the coefficients of d(x) are determined by the
following expressions:
⎧ ∑ k ab ; k = 0, ... , m−1
⎪
d = ⎨ i=0 ik i −
k 2m −2 (7.4)
⎪ ∑ a ki −+( m−1) b i−( m−1) ; k = m ... 2 , m −2
,
−
⎩ = ik
These expressions are equal to Eq. (5.4) along with addition and
multiplication in GF(2). Assume that the functions
function m2xor(x, y: bit) return bit
function m2and(x, y: bit) return bit
computing x XOR y (addition mod 2) and x AND y (multiplication
mod 2) have been defined. Then the function
function poly_multiplication(A,B: poly_vector) return
poly2_vector
performing the polynomial multiplication o f a(x) and b(x), d(x) =
a(x)b(x), can be implemented using Eq. (7.4) as follows

for i in 0 .. 2*m-2 loop d(i) := 0; end loop;
for k in 0 .. m-1 loop
for i in 0 .. k loop
d(k) := m2xor(d(k),m2and(a(i),b(k-i)));
end loop;
end loop;
for k in m .. 2*m-2 loop
for i in k .. 2*m-2 loop
d(k) := m2xor(d(k),m2and(a(k-i+(m-1)),b(i-(m-1))));
end loop;
end loop;
return d;