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

Chien Hsing Wu, Chien Ming Wu, Ming Der Shieh, Yin Tsung Hwang

Research output: Contribution to journalArticlepeer-review

54 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)375-380
Number of pages6
JournalIEEE Transactions on Computers
Issue number3
Publication statusPublished - 2004 Mar

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'High-speed, low-complexity systolic designs of novel iterative division algorithms in GF(2m)'. Together they form a unique fingerprint.

Cite this