Algebraic Coding Theory Elwyn R Berlekamp

Algebraic Coding Theory (Revised Edition)

This is the revised edition of Berlekamp's famous book, 'Algebraic Coding Theory', originally published in 1968, wherein he introduced several algorithms which have subsequently dominated engineering practice in this field. One of these is an algorithm for decoding Reed-Solomon and Bose-Chaudhuri-Hocquenghem codes that subsequently became known as the Berlekamp-Massey Algorithm. Another is the Berlekamp algorithm for factoring polynomials over finite fields, whose later extensions and embellishments became widely used in symbolic manipulation systems. Other novel algorithms improved the basic methods for doing various arithmetic operations in finite fields of characteristic two. Other major research contributions in this book included a new class of Lee metric codes, and precise asymptotic results on the number of information symbols in long binary BCH codes.Selected chapters of the book became a standard graduate textbook.Both practicing engineers and scholars will find this book to be of great value.

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.

A Survey of Algebraic Coding Theory