Improved decoding of affine-variety codes

DOI10.1016/J.JPAA.2012.01.002zbMATH Open1262.94027arXiv1102.4186OpenAlexW2108793748MaRDI QIDQ714109FDOQ714109

Authors: Chiara Marcolla, Emmanuela Orsini, Massimiliano Sala 

Publication date: 19 October 2012

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Abstract: General error locator polynomials are polynomials able to decode any correctable syndrome for a given linear code. Such polynomials are known to exist for all cyclic codes and for a large class of linear codes. We provide some decoding techniques for affine-variety codes using some multidimensional extensions of general error locator polynomials. We prove the existence of such polynomials for any correctable affine-variety code and hence for any linear code. We propose two main different approaches, that depend on the underlying geometry. We compute some interesting cases, including Hermitian codes. To prove our coding theory results, we develop a theory for special classes of zero-dimensional ideals, that can be considered generalizations of stratified ideals. Our improvement with respect to stratified ideals is twofold: we generalize from one variable to many variables and we introduce points with multiplicities.

Full work available at URL: https://arxiv.org/abs/1102.4186

Recommendations

• Decoding affine variety codes using Gröbner bases
• Correcting errors and erasures via the syndrome variety
• A code decomposition approach for decoding cyclic and algebraic-geometric codes
• Heuristic decoding of linear codes using commutative algebra
• General principles for the algebraic decoding of cyclic codes

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Cites Work

• Title not available (Why is that?)
• Use of Grobner bases to decode binary cyclic codes up to the true minimum distance
• On the decoding of binary cyclic codes with the Newton identities
• On codes from norm-trace curves
• Decoding affine variety codes using Gröbner bases
• Title not available (Why is that?)
• Title not available (Why is that?)
• The FGLM problem and Möller's algorithm on zero-dimensional ideals
• Finding BCH error locator polynomials in one step
• Properties of Gröbner bases under specializations
• Generic interpolation polynomial for list decoding
• An improvement of the Feng-Rao bound on minimum distance
• FGLM-Like Decoding: from Fitzpatrick’s Approach to Recent Developments
• Decoding cyclic codes: the Cooper philosophy
• Bounded distance decoding of linear error-correcting codes with Gröbner bases
• On the decoding of cyclic codes using Gröbner bases
• The Chen-Reed-Helleseth-Truong decoding algorithm and the Gianni-Kalkbrenner Gröbner shape theorem
• General Error Locator Polynomials for Binary Cyclic Codes With <formula formulatype="inline"><tex>$t \le 2$</tex></formula> and <formula formulatype="inline"> <tex>$n &lt; 63$</tex></formula>
• Title not available (Why is that?)
• Correcting errors and erasures via the syndrome variety
• Solving systems of algebraic equations by using Gröbner bases
• A commutative algebra approach to linear codes
• Gröbner technology
• Algebraic Decoding of a Class of Binary Cyclic Codes Via Lagrange Interpolation Formula
• Invited Talk: Decoding Cyclic Codes: The Cooper Philosophy

Cited In (6)

• On the small-weight codewords of some Hermitian codes
• Minimum-weight codewords of the Hermitian codes are supported on complete intersections
• Hilbert quasi-polynomial for order domains and application to coding theory
• Hermitian codes and complete intersections
• Stabilizer quantum codes from \(J\)-affine variety codes and a new Steane-like enlargement
• On the evaluation codes given by simple \(\delta \)-sequences

This page was built for publication: Improved decoding of affine-variety codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714109)