Page 225 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 205

The computation primitives are
b(x)/x and c(x)x − 1 mod f(x) if b = 0
0
(a(x) + b(x))/x and (c(x) + d(x))x − 1 mod f(x) if b = 1
0
Given a polynomial α(x), the computation of α(x)x − 1 mod f(x),
with

m
f(x) = x + f x m − 1 + f x m − 2 + . . . + f x + 1
m − 1 m − 2 1
is performed as follows:
α(x) ≡ α(x) + α f(x)
0
= α x m − 1 + α x m − 2 + . . . + α x + α + α x + α f x m − 1
m
m − 1 m − 2 1 0 0 0 m − 1
+ α f x m − 2 + . . . + α f x + α
0 m − 2 0 1 0
= α x + (α + α f )x m − 1 + (α + α f )x m − 2 + . . . + (α + α f )x
m
0 m − 1 0 m − 1 m − 2 0 m − 2 1 0 1
so that
− 1
α(x)x mod f(x) = α x m − 1 + (α + α f )x m − 2 + (α + α f )x m − 3
0 m − 1 0 m − 1 m − 2 0 m − 2
+ . . . + (α + α f )
1 0 1
The corresponding datapath is shown in Fig. 7.8.
A generic VHDL model binary_algorithm_polynomials.vhd has been
generated. The complete VHDL file is available at www.arithmetic-
circuits.org. The entity declaration is

d
a b a b a b a d c m–2 c d c d c
m m–1 m–1 m–2 m–2 1 1 m–1 m–1 m–2 1 1 0 0

0
0 1 0 1 0 1 ... 0 1 b 0 0 1 0 1 ... 0 1 0 1 b 0
initially: h(x) ce_bd
f f f
0 b m–1 b m–2 b m–3 ... b 0 m–1 m–2 1
initially: f(x) ce_ac
...
a a a a a
m m–1 m–2 m–3 0
initially: g(x) ce_bd
d d d ... d
m–1 m–2 m–3 0
initially: 0 ce_ac
...
c m–1 c m–2 c m–3 c 0

FIGURE 7.8 Binary algorithm: datapath.