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

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²loglogm) and O(m²), respectively. Compared to the systolic designs based on the extended Euclid´s algorithm, our circuits exhibit significant speed and area advantages.