24.9 Reed-Solomon Codes

The Reed-Solomon codes, constructed in 1960, are an example of BCH codes. Because they work well for certain types of errors, they have been used in spacecraft communications and in compact discs.

Let F be a finite field with q elements and let n=q1. A basic fact from the theory of finite fields is that F contains a primitive nth root of unity α. Choose d with 1d<n and let

g(X)=(Xα)(Xα2)(Xαd1).

This is a polynomial with coefficients in F. It generates a BCH code C over F of length n, called a Reed-Solomon code.

Since g(α)==g(αd1)=0, the BCH bound implies that the minimum distance for C is at least d. Since g(X) is a polynomial of degree d1, it has at most d nonzero coefficients. Therefore, the codeword corresponding ...

Get Introduction to Cryptography with Coding Theory, 3rd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.