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

49 Citations (Scopus)

Abstract

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
Volume53
Issue number3
DOIs
Publication statusPublished - 2004 Mar 1

All Science Journal Classification (ASJC) codes

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

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

Cite this