Algebraic Decoding

[alg graphic]

The "Berlekamp algorithm" best known to coding theorists is a fast way to invert matrices with constant diagonals. It works over any field, with the finite fields that occur in coding theory being the most popular. Massey's variation on the algorithm, used to synthesize linear feedback shift registers having a specified output sequence, became known as the "Berlekamp-Massey algorithm". The algorithm is also helpful for decoding various classes of algebraic codes. Since the goal is an algorithm whose work and storage requirements will be comparable to or better than n², the crucial step is to reformulate the problem in a way that avoids thinking about n by n matrices explicitly. This is done via this congruence:

(1 + S(z)) (z) (z) mod z²ⁿ⁺¹.

Here S(z) is the generating function for the terms along the successive diagonals of the traditional matrix. Its coefficients are the known inputs to the problem. (z) and (z) are the two polynomials (each of degree at most n) that will become the algorithm's outputs. The challenge was to find a faster algorithm to find the coefficients of these polynomials. The crux is an iterative procedure which successively computes polynomials that satisfy the "key equation". See Chapters 7 and 10 of Algebraic Coding Theory, McGraw-Hill, 1968; Revised edition, Aegean Park Press, Laguna Hills, CA, 1984.

This was the first of a long sequence of many algorithms and techniques for encoding and decoding algebraic codes which were invented and implemented by Berlekamp and his colleagues at Cyclotomics, including Earl Cohen, Steve Pope, Gadiel Seroussi, Po Tong, Lloyd Welch, and others. They led to many publications and over 12 patented inventions, which formed the core of Cyclotomics' successful business for about 15 years, including applications in space and satellite communications, military communications, optical disk memories, magnetic disk memories, floppy disk memories, compact disks, and techniques for optically encoding digital sound tracks on movie film, called "Cinema Digital Sound".

Because of the business implications, some competitors' decoders carefully avoided using any of the patented "Berlekamp Decoding algorithms", sticking instead with the less efficient but better-known public-domain algorithms that first appeared in Berlekamp's 1968 book, or with other public-domain variations thereof.

For most applications with high code rates, the algebraic decoding algorithms patented by Berlekamp and Welch in the early 1980s are still the fastest known. Refinements are presented in Berlekamp's 1996 paper, "Soft Decision + 1 Reed-Solomon Decoding".

These algorithms were subsequently applied to probabilistic checking of proofs by Madhu Sudan and his colleagues, who also devised ingenious algorithms to implement list decoding in a way which discovers all codewords that lie within some multiple of half the minimum distance. Although significantly slower than Welch-Berlekamp, Sudan's enhanced methods also attain significantly improved performance when the code rate is low.

	Home / Algebraic Decoding
Home Publications Research Interests Algorithms Polynomial Factorization Algebraic Decoding Bit-Serial Encoding Applied Analysis Games Cyclotomics Logo Finance Information Theory Recent Classes Thesis Students Awards Board Memberships K-12 Outreach Education Employment Contact Information and Site Credits	The "Berlekamp algorithm" best known to coding theorists is a fast way to invert matrices with constant diagonals. It works over any field, with the finite fields that occur in coding theory being the most popular. Massey's variation on the algorithm, used to synthesize linear feedback shift registers having a specified output sequence, became known as the "Berlekamp-Massey algorithm". The algorithm is also helpful for decoding various classes of algebraic codes. Since the goal is an algorithm whose work and storage requirements will be comparable to or better than n², the crucial step is to reformulate the problem in a way that avoids thinking about n by n matrices explicitly. This is done via this congruence: (1 + S(z)) (z) (z) mod z²ⁿ⁺¹. Here S(z) is the generating function for the terms along the successive diagonals of the traditional matrix. Its coefficients are the known inputs to the problem. (z) and (z) are the two polynomials (each of degree at most n) that will become the algorithm's outputs. The challenge was to find a faster algorithm to find the coefficients of these polynomials. The crux is an iterative procedure which successively computes polynomials that satisfy the "key equation". See Chapters 7 and 10 of Algebraic Coding Theory, McGraw-Hill, 1968; Revised edition, Aegean Park Press, Laguna Hills, CA, 1984. This was the first of a long sequence of many algorithms and techniques for encoding and decoding algebraic codes which were invented and implemented by Berlekamp and his colleagues at Cyclotomics, including Earl Cohen, Steve Pope, Gadiel Seroussi, Po Tong, Lloyd Welch, and others. They led to many publications and over 12 patented inventions, which formed the core of Cyclotomics' successful business for about 15 years, including applications in space and satellite communications, military communications, optical disk memories, magnetic disk memories, floppy disk memories, compact disks, and techniques for optically encoding digital sound tracks on movie film, called "Cinema Digital Sound". Because of the business implications, some competitors' decoders carefully avoided using any of the patented "Berlekamp Decoding algorithms", sticking instead with the less efficient but better-known public-domain algorithms that first appeared in Berlekamp's 1968 book, or with other public-domain variations thereof. For most applications with high code rates, the algebraic decoding algorithms patented by Berlekamp and Welch in the early 1980s are still the fastest known. Refinements are presented in Berlekamp's 1996 paper, "Soft Decision + 1 Reed-Solomon Decoding". These algorithms were subsequently applied to probabilistic checking of proofs by Madhu Sudan and his colleagues, who also devised ingenious algorithms to implement list decoding in a way which discovers all codewords that lie within some multiple of half the minimum distance. Although significantly slower than Welch-Berlekamp, Sudan's enhanced methods also attain significantly improved performance when the code rate is low.