Citation
Abstract
It is shown that Reed-Solomon (RS) codes can be encoded and decoded by using a fast Fourier transform (FFT) algorithm over finite fields. A Fourier-like transform is defined over finite fields of type Ir,(°\/2), where F, is a Fermat prime forn <4. The field Iy,(*\/2) is used to extend the length of the original Fermat number transforms by a factor of 8. The arithmetic utilized to perform these transforms over the field of type Ip,(*\/2) requires only integer additions, circular shifts and a minimum number of integer multiplications by powers of *\/2. The computing time of this transform encoder-decoder for RS codes is less than the time of the standard method for RS codes. More generally, the field GF(q) is also considered, where q is a prime of the form K X 2" + 1 and K and n are integers. GF(q) can be used to decode very long RS codes by an efficient FFT algorithm with an improvement in the number of symbols. The arithmetic needed for these more general transforms requires only slightly modified binary integer additions and multiplications. Transforms can be defined also over the Galois field GF(q*), a finite field analogous to the complex number field, where q = 2? — 1 is a Mersenne prime. The arithmetic needed for this case requires integer complex multiplications mod q and additions mod q. It is shown in this paper that a radix-S FFT algorithm over GF(q?) can be utilized to encode and decode very long RS codes with a large number of symbols. For eight symbols in GF(q*), this transform over GF(q?) can be made simpler than any other known number theoretic transform with a similar capability. Of special interest is the decoding of a 16-tuple RS code with four errors.
Details
- Volume
- 42-35
- Published
- October 15, 1976
- Pages
- 64–78
- File Size
- 1.3 MB