Page 233 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 213

end_inv <= ‘1’ when U = ONE else ‘0’;
control_unit: process(clk, reset, current_state, count)
begin
case current_state is
when 0 to 1 => first_step<=’0’; done<=’1’; ce_vc<=’0’;
ce_ub<=’0’;
when 2 => first_step <=’1’; done <=’0’; ce_vc <=’0’;
ce_ub <=’0’;
when 3 =>first_step <=’0’; done <=’0’; ce_vc <=U(0);
ce_ub <=’1’;
end case;
if reset = ‘1’ then current_state <= 0;
elsif clk’event and clk = ‘1’ then
case current_state is
when 0 => if start = ‘0’ then current_state <= 1;
end if;
when 1 => if start = ‘1’ then current_state <= 2;
end if;
when 2 => current_state <= 3;
when 3 => if end_inv = ‘1’ then current_state <= 0;
end if;
end case;
end if;
end process control_unit;

7.6 Important Irreducible Polynomials
The choice of the irreducible polynomial f(x) may ease the arithmetic
operations over GF(2 ), mainly the multiplication. Among the impor-
m
tant irreducible polynomials usually selected, trinomials, pentanomi-
als, ESPs (equally spaced polynomials), and AOPs (all-one polynomials)
can be considered.
7.6.1 Equally Spaced Polynomials (ESPs)
A polynomial in the form fx() = x + x n ( −1 s ) + + x + 1 over the
s
ns
binary field GF(2), with m = ns, is called an equally spaced polynomial
(also denoted as s-ESP) of degree m, where both n and s are integers
and 1 ≤ s ≤ m/2. When s = 1, a 1-ESP is obtained and it is the same as
the all-one polynomial (denoted as AOP). An AOP has the highest
Hamming weight (i.e., the number of 1s) among all the polynomials
of degree m. When s = m/2, then the least Hamming weight irreduc-
ible polynomial (i.e., trinomial) of degree m is obtained.
For an s-ESP, the following expression is obtained
⎧ x + x s i + + ... + x ( n− )1 s i + ; 0 ≤ i < s
i
x mi + = ⎨ is (7.47)
−
m
i
⎩ x ; s ≤≤ m − 2
Equation (7.47) can be used for the reduction of the complexity of
the arithmetic operations over GF(2 ) studied in previous sections.
m