Fast algorithm for the Fourier transform over finite fields and its VLSI implementation

Yao Wang, Xuelong Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Summary form only given. An algorithm for computing the Fourier transform over any finite field GF(pm) has been developed. It requires only O(n log n)2/4) additions and the same number of multiplications for an n-point transform, and allows in some fields a further reduction of the number of multiplications to O(n log n). Unlike most other fast algorithms that are generalizations of the FFT algorithms over the complex field, the proposed algorithm is unique in that it makes use of the special algebraic properties of the finite field and has the same implementation structure over any field. Due to its high regularity and low computational complexity when both multiplications and additions are considered, the algorithm is very attractive when VLSI realization is intended.

Original languageEnglish (US)
Title of host publicationIEEE 1988 Int Symp on Inf Theory Abstr of Pap
PublisherPubl by IEEE
Number of pages1
Volume25 n 13
StatePublished - 1988

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Fast algorithm for the Fourier transform over finite fields and its VLSI implementation'. Together they form a unique fingerprint.

Cite this