A Fast Algorithm for the Fourier Transform Over Finite Fields and Its VLSI Implementation

Yao Wang, Xuelong Zhu

Research output: Contribution to journalArticle

Abstract

The Fourier transform over finite fields is mainly required in the encoding and decoding of Reed-Solomon and BCH codes. A new algorithm for computing the Fourier transform over any finite field GF(pm) is introduced. It requires only [formula omitted] additions and the same number of multiplications for an n-point transform, and allows, in some fields, such as GF(22'), a further reduction of the number of multiplications to [formula omitted]. Because of its highly regular structure, this algorithm can be easily implemented by VLSI technology.

Original languageEnglish (US)
Pages (from-to)572-577
Number of pages6
JournalIEEE Journal on Selected Areas in Communications
Volume6
Issue number3
DOIs
StatePublished - Apr 1988

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A Fast Algorithm for the Fourier Transform Over Finite Fields and Its VLSI Implementation'. Together they form a unique fingerprint.

  • Cite this