AT2-Optimal Galois Field Multiplier for VLSI

Martin Fürer, Kurt Mehlhorn

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Finite or Galois field arithmetic is central in many encoding and decoding procedures for error detecting and error correcting codes. In this paper, VLSI designs for Galois field multipliers are presented. For every prime p, these designs (for GF(pn) multiplication in standard representation) are asymptotically optimal with respect to area A and time T. In fact, the lower bound AT2 = ω(n2) is matched for every computation time T in the range [ω(log n), O[formula omitted]]. Analogous results hold for variable primes p too. The designs are based on the DFT on a structure similar to Fermat rings. For p = 2 the DFT uses 3'th instead of 2'th roots of unity.

Original languageEnglish (US)
Pages (from-to)1333-1336
Number of pages4
JournalIEEE Transactions on Computers
Issue number9
StatePublished - Sep 1989

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'AT2-Optimal Galois Field Multiplier for VLSI'. Together they form a unique fingerprint.

Cite this