High-speed, low-complexity systolic designs of novel iterative division algorithms in GF(2^m)

We extend the binary algorithm invented by Stein and propose novel iterative division algorithms over GF(2^m) for systolic VLSI realization. While Algorithm EBg is a basic prototype with guaranteed convergence in at most 2m - 1 iterations, its variants, Algorithms EBd and EBdf, are designed for reduced complexity and fixed critical path delay, respectively. We show that Algorithms EBd and EBdf can be mapped to parallel-in parallel-out systolic circuits with low area-time complexities of O(m² log log m) and O(m²), respectively. Compared to the systolic designs based on the extended Euclid's algorithm, our circuits exhibit significant speed and area advantages.