The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)
I.S. Reed, Treiu-Kien Truong, Lloyd R. Welch · IEEE Transactions on Information Theory · 1978
It is shown that\sqrt\[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Since\sqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, where\sqrt{2}is inGF(F_{2})=GF(17), is given.