Page 231 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 211

m
Algorithm 7.23—Modified Almost Inverse Algorithm for inversion in GF(2 )
for i in 0 .. m loop
v(i) := f(i); u(i) := a(i); b(i) := 0;
c(i) := 0; auxm(i) := 0; inv(i) := 0;
end loop;
b(0) := 1;
degree_v := degreem(v);
degree_u := degreem(u);
aux := 0; ext := 0;
while ext = 0 loop
while u(0) /= 1 loop
u := lshiftm(u);
degree_u := degree_u - 1;
if b(0) /= 1 then b := lshiftm(b);
else auxm := b; b := lshiftm(m2xvvm(b,f));
end if;
end loop;
ext := unitym(u);
if ext = 1 then inv := b; end if;
if degree_u < degree_v then
auxm := v; v := u; u := auxm;
aux := degree_u; degree_u := degree_v; degree_v := aux;
auxm := c; c := b; b := auxm;
end if;
u := m2xvvm(u,v);
degree_u := degreem(u);
b := m2xvvm(b,c);
end loop;
An executable Ada file MAIA_inversion.adb, including Algorithm
7.23, is available at www.arithmetic-circuits.org. The corresponding
VHDL model MAIA_inversion.vhd has been generated. The entity
declaration is
entity maia_inversion is
port (
A: in std_logic_vector (M-1 downto 0);
clk, reset, start: in std_logic;
Z: out std_logic_vector (M-1 downto 0);
done: out std_logic
);
end maia_inversion;
The VHDL architecture corresponding to the MAIA_inversion
follows:
vb_comp: process(b,c,u,v,degree_u)
variable d: natural;
begin
if U(0) = ‘0’ then
new_u <= ‘0’ & u(M downto 1);new_degree_u <= degree_u
- 1;