Page 54 - Hardware Implementation of Finite-Field Arithmetic

mod m Reduction 37

q (n – k – 1..0) a (k – 1..0)

(n-k)-bit by k bits
multiplier
product (n – 1..0) r (k – 1..0)
–m
r (t – 1..0)
product (n – 1..k) product (k – 1..0)
(n – k)-bit register sign (k + 1)-
initially: x n–1 , ... , x k t-bit adder bit adder
after reload: r t–1 , ... , r k
sum (t – 1..0)
0 1
t-bit register
q (n – k – 1..0) initially: x k–1 , ... , x 0
after reload: r k–1 , ... , r 0
z (k – 1..0)
r (t – 1..0)
FIGURE 2.5 Datapath of a mod 2 − a reducer.
k

q (3)a (0) q (2)a (0) q (1)a (0) q (0)a (0)

product 0
q (3)a (1) q (2)a (1) q (1)a (1) q (0)a (1)

product
1
q (3)a (2) q (2)a (2) q (1)a (2) q (0)a (2)

product
2
HA FA FA HA
product 6 product 5 product 4 product 3
r 4 r 3 r 2 r 1 r 0
HA HA FA FA HA
sum 4 sum 3 sum 2 sum 1 sum 0

FIGURE 2.6 Carry-save multiplier and carry-ripple adder.

T ≈ snT ≤ (n − k + 1)nT (2.32)
MULT MULT
Obviously faster multipliers and/or adders could be used. A
VHDL file tpkma_reducer.vhd is available at www.arithmetic-
circuits.org. The corresponding entity declaration is