Page 292 - Hardware Implementation of Finite-Field Arithmetic

272 Cha pte r Ni ne

h Aβα
h Cβα
m
For GF(2 ), if a = ( j ), j = , ,01 ... ,2 m − 2 and c = ( j ),
j j
01
1
j = ,,... , m − , then Eq. (9.7) can be rewritten as follows [FBT96a]:
⎛ a a a − ⎞ ⎛ b ⎞ ⎛ c ⎞
⎜ 0 1 m 1 ⎟ ⎜ 0 ⎟ ⎜ 0 ⎟
⎜ a 1 a 2 a m ⎟ ⎜ b 1 ⎟ = ⎜ c 1 ⎟ (9.8)
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎟
⎟ ⎟ ⎜b
⎝ a ⎜ m 1 a m a 2 m − 2⎠ ⎝ m 1 ⎟ ⎠ ⎜c − ⎟ ⎠
−
−
⎝ m 1

If h and β are taken as in Eq. (9.5), a and c ( j = 0, 1, . . . , m – 1) in
j j
Eq. (9.8) are the dual basis coefficients of A and C, respectively.
Therefore, if the terms a (with j = m, m + 1, . . . , 2m – 2) can be generated,
j
then Eq. (9.8) represents a dual basis multiplication algorithm. If f(x)
is the generating irreducible polynomial for GF(2 ), then
m
⎛ ⎛ m−1 ⎞⎞ m−1 m−1
i (
i ⎟⎟ = ∑
h Aβα
h A β
i
a = ( m ) = ⎜ ⎜ ∑ f α i f h Aβα ) = ∑ f a (9.9)
A
m ⎜ ⎝ ⎝ ⎠⎠ ⎟ ii
i=0 i=0 i=0
where f ’s are the coefficients of f(x). In general, it can be proven that
i
[FBT96a]
m−1
mk ∑
=
a + f a + , k = 01, ,... , m − 2 (9.10)
i i k
i=0
where a ’s, with i = 0, 1, . . . , m – 1, are the dual basis coefficients of A.
i
Therefore, the above equations compute the product C of the field
elements A and B, where A and C are represented in dual basis, and B
is represented in polynomial basis.
Using the above equations, the following algorithm implements
the dual-basis multiplication.
Algorithm 9.1—Dual basis multiplication
for k in 0 .. m-2 loop
for i in 0 .. m-1 loop
A(m + k) := m2xor(A(m + k),m2and(F(i),A(i + k)));
end loop;
end loop;
for j in 0 .. m-1 loop
for i in 0 .. m-1 loop
C(j) := m2xor(C(j),m2and(A(j + i),B(i)));
end loop;
end loop;
In Algorithm 9.1, A has been defined as a bit vector from 0 to 2m – 2.
An executable Ada file dual_mult.adb, including Algorithm 9.1, is
available at www.arithmetic-circuits.org.