Page 49 - Hardware Implementation of Finite-Field Arithmetic

32 Cha pte r T w o

s s,n+1 s c,n+1 w k+1 s s,n s c,n w k s s,n–k+2 s c,n–k+2 w 2 s s,n–k+1 w 1 s s,n–k w 0 s s,n–k–1 s s,1 s s,0

...
FA FA ... FA FA FA
r r s,n–k r r r
s,n–k+1
r s,n+1 r c,n+1 r s,n r c,n r s,n–k+2 r c,n–k+2 r c,n–k+1 s,n–k–1 s,1 s,0
0
... ...
(n – k + 3)-bit register
initially: s = x, s = 0
c
s
... ...
s s,n+2 s c,n+2 s s,n+1 s c,n+1 s s,n s c,n s s,n–k+2 s c,n–k+2 s s,n–k+1 s s,n–k s s,n–k–1 s s,1 s s,0

0 m –m
s s,n+2 , s s,n+1 , s s,n , s s,n–1 4-bit t two 4-input quotient
s c,n+2 , s c,n+1 , s c,n , s c,n–1 adder Boolean 0 1 –1
functions
r c,n , r c,n–1 , ...,r c,n–k+1 w
r s,n , r s,n–1 , ...,r s,n–k+1 r s,n–k r k–1 k–2 , ... , r 0 m
,r

k-bit adder
k-bit adder

r , r , ... ,r 1 r 0 r k
k k–1
(sign) 0 1

z

FIGURE 2.4 SRT reducer datapath.

A complete VHDL file srt_reducer.vhd is available at www.
arithmetic-circuits.org. The corresponding entity declaration is

entity srt_reducer is
port (
x: in std_logic_vector (N downto 0);
m: 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 srt_reducer;
The VHDL architecture corresponding to the circuit of Fig. 2.4 is
the following: