article · 2007

Decoding error-correcting codes with Grobner bases

Cited by 2Abstract and details only

Abstract

The decoding of arbitrary linear block codes is accomplished by solving a system of quadratic equations by means of Buchberger’s algorithm for finding a Gröbner basis. This generalizes the algorithm of Berlekamp-Massey for decoding Reed-Solomon, Goppa and cyclic codes up to half the true minimum distance by intro-ducing the unknown syndromes as variables. The complexity of this algorithm is exponential and the complexity coefficient is measured under the assumption that the over-determined system of quadratic equations is semi-regular using the results of Bardet et al. [5]. The complexity is compared to existing bounded distance decoding algorithms. Our method can be extended to complete and generic decoding, and to finding the minimum distance and the complete weight distribution. 1

Cite this paper

APA 7

Bulygin, S., & Pellikaan, G. (2007). Decoding error-correcting codes with Grobner bases.

MLA 9

Bulygin, Stanislav, and G.R. Pellikaan. “Decoding error-correcting codes with Grobner bases.” 2007, pp. 3–10.

Chicago

Bulygin, Stanislav, and G.R. Pellikaan. 2007. “Decoding error-correcting codes with Grobner bases.”

Harvard

Bulygin, S. and Pellikaan, G. (2007) ‘Decoding error-correcting codes with Grobner bases’.

BibTeX

@article{bulygin2007decoding,
  title = {{Decoding error-correcting codes with Grobner bases}},
  author = {Bulygin, Stanislav and Pellikaan, G.R.},
  pages = {3--10},
  year = {2007}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.