BCH and Reed-Solomon Codes

Corresponds to Lecture topic 6. Cyclic codes are linear codes closed under cyclic shifts of coordinates, which lets every codeword be represented as a multiple of a fixed generator polynomial over $\mathbb F_q[x]/(x^n-1)$ — turning coding-theoretic questions into polynomial algebra. BCH codes specialize this to guarantee a designed minimum distance by choosing the generator polynomial’s roots carefully (worked through concretely for the double-error-correcting case), and Reed-Solomon codes are the extreme case where the alphabet size equals the code length, giving MDS (maximum-distance-separable) codes with the best possible distance for their rate — see explicit-constructions-of-biased-distributions-and-codes for Reed- Solomon codes, the Singleton bound, and list decoding treated again in a pseudorandomness/derandomization context. Decoding is covered via three increasingly powerful algorithms: the classical PGZ algorithm and the Euclidean algorithm approach (both solving for the error locator polynomial, up to the unique-decoding radius), and Sudan’s list-decoding algorithm, which corrects more errors than any unique decoder could by giving up uniqueness — returning a short list guaranteed to contain the true codeword.

Outline (TODO — flesh out each)

• Cyclic codes
• BCH codes — construction, designed distance
• Double-error-correcting BCH codes, worked out
• Reed-Solomon codes
• Decoding RS codes — the PGZ algorithm
• Decoding RS codes — Euclid’s algorithm
• List decoding of RS codes — Sudan’s algorithm