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 language||English (US)|
|Title of host publication||IEEE 1988 Int Symp on Inf Theory Abstr of Pap|
|Publisher||Publ by IEEE|
|Number of pages||1|
|Volume||25 n 13|
|State||Published - 1988|
ASJC Scopus subject areas