Details:
Title  On the decoding of binary cyclic codes with the Newton identities  Author(s)  Daniel Augot, Magali Bardet, JeanCharles Faugère  Type  Article in Journal  Abstract  We revisit in this paper the concept of decoding binary cyclic codes with Gröbner bases. These ideas were first introduced by Cooper, then Chen, Reed, Helleseth and Truong, and eventually by Orsini and Sala. We discuss here another way of putting the decoding problem into equations: the Newton identities. Although these identities have been extensively used for decoding, the work was done manually, to provide formulas for the coefficients of the locator polynomial. This was achieved by Reed, Chen, Truong and others in a long series of papers, for decoding quadratic residue codes, on a casebycase basis. It is tempting to automate these computations, using elimination theory and Gröbner bases. Thus, we study in this paper the properties of the system defined by the Newton identities, for decoding binary cyclic codes. This is done in two steps, first we prove some facts about the variety associated with this system, then we prove that the ideal itself contains relevant equations for decoding, which lead to formulas. Then we consider the socalled online Gröbner basis decoding, where the work of computing a Gröbner basis is done for each received word. It is much more efficient for practical purposes than preprocessing and substituting into the formulas. Finally, we conclude with some computational results, for codes of interesting length (about one hundred).  Keywords  Cyclic codes, Quadratic residue codes, Elimination theory, Gröbner bases, F 4 algorithm  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717108001764 
Language  English  Journal  Journal of Symbolic Computation  Volume  44  Number  12  Pages  1608  1625  Year  2009  Note  Gröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics  Edition  0  Translation 
No  Refereed 
No 
