HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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
Inria Paris-Rocquencourt
2 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:17:58 PM
Last modification on : Thursday, February 3, 2022 - 11:13:51 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:45:12 PM


  • HAL Id : inria-00071933, version 1



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⟩



Record views


Files downloads