List decoding of Reed-Solomon codes from a Gröbner basis perspective
From MaRDI portal
Abstract: The interpolation step of Guruswami and Sudan's list decoding of Reed-Solomon codes poses the problem of finding the minimal polynomial of an ideal with respect to a certain monomial order. An efficient algorithm that solves the problem is presented based on the theory of Groebner bases of modules. In a special case, this algorithm reduces to a simple Berlekamp-Massey-like decoding algorithm.
Recommendations
- Gröbner basis approach to list decoding of algebraic geometry codes
- List decoding codes on Garcia-Stichtenoth tower using Gröbner basis
- List decoding of Hermitian codes using Gröbner bases
- List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
- List Decoding of Generalized Reed–Solomon Codes Over Commutative Rings
- List-Decodability With Large Radius for Reed-Solomon Codes
- Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
- List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes
- Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
- Limits to List Decoding Reed–Solomon Codes
Cites work
- scientific article; zbMATH DE number 1461545 (Why is no real title available?)
- scientific article; zbMATH DE number 2222667 (Why is no real title available?)
- Decoding of Reed Solomon codes beyond the error-correction bound
- Gröbner bases of ideals defined by functionals with an application to ideals of projective points
- Gröbner basis solutions of constrained interpolation problems
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
- List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
- On the key equation
- Using Algebraic Geometry
Cited in
(30)- A Syndrome Formulation of the Interpolation Step in the Guruswami-Sudan Algorithm
- List Decoding of Generalized Reed–Solomon Codes Over Commutative Rings
- Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
- Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
- A tutorial on AG code decoding from a Gröbner basis perspective
- A Gröbner-Bases Approach to Syndrome-Based Fast Chase Decoding of Reed–Solomon Codes
- A Hensel lifting to replace factorization in list-decoding of algebraic-geometric and Reed-Solomon codes
- A matrix based list decoding algorithm for linear codes over integer residue rings
- Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes
- Efficient list decoding of a class of algebraic-geometry codes
- List decoding of repeated codes
- A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes
- Key equations for list decoding of Reed-Solomon codes and how to solve them
- Behavioral Models for List Decoding
- Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
- Computing minimal interpolation bases
- Improved List Decoding of Generalized Reed–Solomon and Alternant Codes Over Galois Rings
- Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
- Generic interpolation polynomial for list decoding
- Minimal Gröbner bases and the predictable leading monomial property
- List decoding algorithm based on voting in Gröbner bases for general one-point AG codes
- List decoding of Hermitian codes using Gröbner bases
- A module minimization approach to Gabidulin decoding via interpolation
- Power decoding Reed-Solomon codes up to the Johnson radius
- An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings
- Gröbner basis approach to list decoding of algebraic geometry codes
- Row reduction applied to decoding of rank-metric and subspace codes
- List decoding codes on Garcia-Stichtenoth tower using Gröbner basis
- List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes
- Interpolation in list decoding of Reed-Solomon codes
This page was built for publication: List decoding of Reed-Solomon codes from a Gröbner basis perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q931140)
