Algebraic Coding Theory

In 1948, Claude Shannon showed the existence of codes which could correct errors. Over the next two decades, he and others explored the theoretical limits of the performance of long block codes, resulting in curves such as the one shown above. In the 1960s, mathematicians introduced the notion that the sophisticated algebra of finite fields might be used to design and implement such codes. When the first edition of this book appeared in 1968, it immediately became a landmark in the field. It introduced a novel algorithm for factoring polynomials, the crux of which is the top formula on the left of the cover. It also introduced a new algorithm for determining the polynomial that needs to be factored in order to decode Reed-Solomon codes. The crux of this algorithm, which appears on the bottom left of the cover, became widely known as the Berlekamp-Massey algorithm. These advances made algebraic error-correcting codes feasible for a wide range of applications in both computer memories and in digital communications. Building on the foundations of this book a subsequent breakthrough in the 1970s reduced the complexity of nonbinary Reed-Solomon encoders to that of much simpler binary codes of comparable redundancies. A circuit diagram for such an encoder appears on the right of the cover. It became a NASA standard for deep space communications.