Page 126 - Hardware Implementation of Finite-Field Arithmetic

Operations over GF ( p ) 109

The minimum clock period is determined by the adders, that is,
about (k + 4)T if ripple adders are used. Let t be the number of
FA
executions of the main loop of Algorithm 4.5 or 4.6. The total
computation time T is approximately equal to

T ≈ tkT (4.33)
FA
As α + β = 2k > α + β > . . . > α + β > α + β with α > 0,
1
0
i − 1
0
i
i
i − 1
1
i − 1
β > 0, and β ≤ 0, an upper bound of t is 2k, so that an upper bound
i − 1 i
of the computation time is
T < 2k T (4.34)
2
FA
A complete VHDL file plus_minus.vhd is available at www.
arithmetic-circuits.org. The entity declaration is
entity plus_minus is
port(
x, y: in std_logic_vector(K-1 downto 0);
clk, reset, start: in std_logic;
z: out std_logic_vector(K-1 downto 0);
done: out std_logic
);
end plus_minus;
The VHDL architecture corresponding to the circuit of Fig. 4.5 is
the following:
half_b <= b(K)& b(K downto 1);
half_a <= a(K)& a(K downto 1);
gates1: for i in 0 to K generate
aa(i) <= (oper(1) and (oper(0) xor half_a(i)));
end generate;
sum_ab <= half_b + aa + oper(1);
half_sum_ab <= sum_ab(K)& sum_ab(K downto 1);
with sel_bd select next_b <= ‘0’ & y when “00”,
sum_ab when “01”, half_sum_ab when others;
gates2: for i in 0 to k generate
dd(i) <= lastb and d(i); cc(i) <= (oper(1) and (oper(0)
xor c(i)));
end generate;
sum_cd <= (dd(k)&dd) + (cc(k)&cc) + oper(0);
with sel_correction select pp <= ‘0’ & ZERO when “00”,
pp1 when “01”, TWO_P when “10”, pp3 when others;
corrected_sum <= (sum_cd(K+1) & sum_cd) + (pp(K+1) & pp);
z <= corrected_sum(K-1 downto 0);
with sel_bd select next_d <= ‘0’&x when “00”,
corrected_sum(K+1 downto 1) when “01”,
corrected_sum(K+2 downto 2) when others;
with sel_ac select next_a <= p when ‘0’, b when others;