Page 131 - Hardware Implementation of Finite-Field Arithmetic

114 Cha pte r F o u r

4.6.2 Binary Algorithm
The divider of Fig. 4.4, based on the binary algorithm, has been impl-
emented. The number of cycles depends on the value of the oper-
ands. The cost and period of several dividers are shown in Table 4.7.

k FFs LUTs Slices Period
8 34 145 78 6.9
32 130 510 285 8.9
64 259 1,069 590 11.6
128 515 2,198 1,364 15.8
192 771 3,401 2,091 19.9
256 1,027 4,164 2,754 26.5

TABLE 4.7 Cost and Period of Dividers Based on the
Binary Algorithm

In order to get an estimation of the computation time, 1,000 pairs
(x, y) have been generated for several values of k, and the correspond-
ing numbers of cycles have been observed by simulation. Then, the
minimum (MinCycles), maximum (MaxCycles), and average (Aver-
Cycles) numbers of cycles have been obtained, and the average com-
putation time AverTime has been computed (Table 4.8).

k Period MinCycles MaxCycles AverCycles AverTime
8 6.9 3 19 14.2 98
32 8.9 41 77 65.3 582
64 11.6 112 149 132.8 1,541
128 15.8 243 287 268.8 4,247
192 19.9 376 425 404.3 8,046
256 26.5 509 568 539.6 14,299

TABLE 4.8 Average Delay of Dividers Based on the Binary Algorithm

4.6.3 Plus-Minus Algorithm
The divider of Fig. 4.5, based on the plus-minus algorithm, has been
implemented. The number of cycles depends on the value of the
operands. The cost and period of several dividers are shown in
Table 4.9.
In order to get an estimation of the computation time, 1,000 pairs
(x, y) have been generated for several values of k, and the correspond-
ing numbers of cycles have been observed by simulation. Then, the