Lagrange Codes
Martin Tomlinson, Cen Jung Tjhai, Marcel Ambroze, Mohammed Ahmed, Mubarak Jibril · Signals and communication technology · 2017
Interpolation plays an important, mostly hidden role in algebraic coding theory. Reed–Solomon codes, BCH codes, and Goppa codes are all codes that may be constructed via interpolation. It is shown that all of these codes form part of a large family of generalised MDS codes. Also in this chapter, we discuss the encoding of BCH and Goppa codes using classical Lagrange interpolation. It is shown in detail how Goppa codes are designed and constructed starting from first principles. The parity check matrix of a BCH code is derived as a Goppa code proving that BCH codes are a subset of Goppa codes. Following on from this and using properties of the cyclotomic cosets it is explained why the minimum Hamming distance of some BCH codes exceeds the BCH bound. It is shown how these outstanding BCH codes can be identified and constructed. A little known paper by Goppa is discussed and as a result it is shown how Goppa codes and BCH codes may be extended in length with additional parity check bits resulting in increased minimum Hamming distance of the code. Several examples are given of the technique which results in some exceptional codes. Reed–Solomon codes are explored as a means of constructing binary codes resulting in some best known codes.