Efficient Decoding of (binary) Cyclic Codes beyond the correction capacity of the code using Gröbner bases

Daniel Augot (1) , Magali Bardet (1) , Jean-Charles Faugère (2)

1 CODES - Coding and cryptography
2 SPACES - Solving problems through algebraic computation and efficient software

The problem of decoding cyclic codes can be rewritten into an algebraic system of equations, whose solutions are closely related to the error that occured. Extensive work has been done previously, where it has been shown that the computation of a Gröbner basis of this algebraic system enables to decode up to the true minimum distance. The Gröbner basis computation can be done either as a preprocessing (formal decoding), with the parameters taken as variables, or for each word to be decoded (online decoding), with the parameters computed from the word and substituted into the system. For the formal decoding, it has been shown that decoding formulas for the coefficients of the locator polynomial are obtained from the formal Gröbner basis. Unfortunately, it becomes quickly impossible to compute this formal Gröbner basis even for codes of small length. Motivated by the problem of decoding quadratic residue (QR) codes, for which no general decoding algorithm is known, we improve on several points. First we introduce modified systems, without high degree equations, for which the Gröbner basis computation is easier. This enables to compute the formal Gröbner basis for longer codes. We show on the example of the [41,21,9] QR code that the formulas become quickly of large size, thus being useless for decoding. This indicates that the effort on the algebraic decoding of cyclic codes by formulas hits a wall. The other approach (online decoding) is more efficient from a computational point of view. Using general compilation methods for systems with parameters, we improve the efficiency of the computation. Many examples are given (for BCH codes of length 75, 511, for QR codes of length 41, 73, 89, 113 and for a code of length 75 which does not belong to a known class of codes). This method for decoding cyclic codes with Gröbner basis works for any cyclic codes, is automatic and enables to decode beyond the true minimum distance.

Mots clés: DECODING; CYCLIC CODES; IDEAL THEORY; GRÖBNER BASES; ERROR-LOCATOR POLYNOMIAL; NEWTON IDENTITIES

Domaines: Autre [cs.OH]

Daniel Augot, Magali Bardet, Jean-Charles Faugère. Efficient Decoding of (binary) Cyclic Codes beyond the correction capacity of the code using Gröbner bases. [Research Report] RR-4652, INRIA. 2002. ⟨inria-00071933⟩