4 - Reed–Solomon codes and their decoding

Summary

Introduction

Reed–Solomon codes are error-correcting codes defined over large alphabets. They were among the early constructions of good codes (1959), and are now one of the most important classes of error-correcting codes for many applications. At the same time these codes constitute a natural starting point for studying algebraic coding theory, i.e. methods of correcting errors by solving systems of equations.

Finite fields

To describe the codes and the decoding methods, the symbol alphabet is given a structure that allows computations similar to those used for rational numbers. The structure is that of a field. In a field there are two compositions, addition and multiplication, satisfying the usual associative and distributive rules. The compositions have neutral elements 0 and 1, every element has an additive inverse (a negative), and nonzero elements have a multiplicative inverse.

Well-known examples of fields include the rational, the real, and the complex numbers. The integers are not a field because only ±1 have multiplicative inverses. However, there are also fields with a finite number of elements, and we actually used the binary field in the previous chapter to construct binary codes. A finite field with q elements is referred to as F(q). Having the alphabet given this structure allows us to use concepts of matrices, vector spaces, and polynomials, which concepts are essential to the construction of codes and decoding algorithms.

The simplest examples of finite fields are sets of integers, [0, 1, 2, …, p − 1], with addition and multiplication modulo p.