Efficient decoding of (binary) cyclic codes above the correction capacity of the code using Gröbner bases

Daniel Augot; Magali Bardet; Jean Charles Faugère

doi:10.1109/isit.2003.1228378

Efficient decoding of (binary) cyclic codes above the correction capacity of the code using Gröbner bases

Daniel Augot
, Magali Bardet
, Jean Charles Faugère

INRIA Rocquencourt
LIP6, UPMC Sorbonne Universités - Paris 6

Research output: Contribution to journal › Conference article › peer-review

11 Citations (Scopus)

Abstract

This paper revisits the topic of decoding cyclic codes with Gröbner bases. We introduce new algebraic systems, for which the Gröbner basis computation is easier. We show that formal decoding formulas are too huge to be useful, and that the most efficient technique seems to be to recompute a Gröbner basis for each word (online decoding). We use new Gröbner basis algorithms and "trace preprocessing" to gain in efficiency.

Original language	English
Pages (from-to)	362
Number of pages	1
Journal	IEEE International Symposium on Information Theory-Proceedings
DOIs	https://doi.org/10.1109/isit.2003.1228378
Publication status	Published - 1 Jan 2003
Event	Proceedings 2003 IEEE International Symposium on Information Theory (ISIT) - Yokohama, Japan Duration: 29 Jun 2003 → 4 Jul 2003

Access to Document

10.1109/isit.2003.1228378

Cite this

@article{175b08b562f44b328218a2460f5951da,

title = "Efficient decoding of (binary) cyclic codes above the correction capacity of the code using Gr{\"o}bner bases",

abstract = "This paper revisits the topic of decoding cyclic codes with Gr{\"o}bner bases. We introduce new algebraic systems, for which the Gr{\"o}bner basis computation is easier. We show that formal decoding formulas are too huge to be useful, and that the most efficient technique seems to be to recompute a Gr{\"o}bner basis for each word (online decoding). We use new Gr{\"o}bner basis algorithms and {"}trace preprocessing{"} to gain in efficiency.",

author = "Daniel Augot and Magali Bardet and Faug{\`e}re, \{Jean Charles\}",

year = "2003",

month = jan,

day = "1",

doi = "10.1109/isit.2003.1228378",

language = "English",

pages = "362",

journal = "IEEE International Symposium on Information Theory-Proceedings",

issn = "2157-8095",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "Proceedings 2003 IEEE International Symposium on Information Theory (ISIT) ; Conference date: 29-06-2003 Through 04-07-2003",

}

TY - JOUR

T1 - Efficient decoding of (binary) cyclic codes above the correction capacity of the code using Gröbner bases

AU - Augot, Daniel

AU - Bardet, Magali

AU - Faugère, Jean Charles

PY - 2003/1/1

Y1 - 2003/1/1

N2 - This paper revisits the topic of decoding cyclic codes with Gröbner bases. We introduce new algebraic systems, for which the Gröbner basis computation is easier. We show that formal decoding formulas are too huge to be useful, and that the most efficient technique seems to be to recompute a Gröbner basis for each word (online decoding). We use new Gröbner basis algorithms and "trace preprocessing" to gain in efficiency.

AB - This paper revisits the topic of decoding cyclic codes with Gröbner bases. We introduce new algebraic systems, for which the Gröbner basis computation is easier. We show that formal decoding formulas are too huge to be useful, and that the most efficient technique seems to be to recompute a Gröbner basis for each word (online decoding). We use new Gröbner basis algorithms and "trace preprocessing" to gain in efficiency.

U2 - 10.1109/isit.2003.1228378

DO - 10.1109/isit.2003.1228378

M3 - Conference article

AN - SCOPUS:0142008226

SN - 2157-8095

SP - 362

JO - IEEE International Symposium on Information Theory-Proceedings

JF - IEEE International Symposium on Information Theory-Proceedings

T2 - Proceedings 2003 IEEE International Symposium on Information Theory (ISIT)

Y2 - 29 June 2003 through 4 July 2003

ER -

Efficient decoding of (binary) cyclic codes above the correction capacity of the code using Gröbner bases

Abstract

Access to Document

Fingerprint

Cite this