We extend the binary algorithm invented by Stein and propose novel iterative division algorithms over GF(2m) 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(m2 log log m) and O(m2), respectively. Compared to the systolic designs based on the extended Euclid's algorithm, our circuits exhibit significant speed and area advantages.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics