Page 112 - Hardware Implementation of Finite-Field Arithmetic

Operations over GF ( p ) 95

acc := 0; for i in 0 .. k-2 loop acc := acc + (q(i)*(2**i));
end loop;
acc := acc - (q(k-1)*(2**(k-1)));
if remainder < 0 then quotient := acc -1;
remainder := remainder + b;
else quotient := acc; end if;
An executable Ada file nr_divider.adb, including Algorithm 4.2,
is available at www.arithmetic-circuits.org.
The datapath corresponding to Algorithm 4.2 is shown in Fig. 4.1.
The minimum clock period is about kT if a carry-ripple adder-
FA
subtractor is used for computing r at each step. The number of clock
cycles is equal to k − 1 plus the cycles corresponding to the initial and
final operations, so that the computation time is about

2
T ≈ k T (4.16)
FA
s (2k – 2..k – 2) b
s (2k – 1) s (k – 3..0)

(k + 1)-bit adder-subtractor
oper
(0: add,1: subtract)
r (2k – 2..k – 2) r (k – 3..0)
a
r (2k – 2..0) & 0 load clear in s (2k – 1)
k-bit shift register
shift update
1 0 1
load
q (k – 1) q (k – 2..1) q (0)

(2k – 1)-bit parallel register
ce load + update

s (2k – 1..0)
q (k – 1..0) 1 s (2k – 2..k – 1) b

k-bit subtractor k-bit adder

0 1 0 1
s (2k – 1)

quotient remainder

FIGURE 4.1 Nonrestoring divider datapath.