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.
ASJC Scopus subject areas
- Computer Networks and Communications
- Electrical and Electronic Engineering