A Parametric Approach to List Decoding of Reed-Solomon Codes Using Interpolation

DOI10.1109/TIT.2011.2165803MaRDI QIDQ5272298zbMATH OpenOpenAlexFDO

Authors Mortuza Ali, Margreta Kuijper

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Linear codes (general theory) (94B05)

Abstract: In this paper we present a minimal list decoding algorithm for Reed-Solomon (RS) codes. Minimal list decoding for a code $C$ refers to list decoding with radius $L$, where $L$ is the minimum of the distances between the received word $mathbfr$ and any codeword in $C$. We consider the problem of determining the value of $L$ as well as determining all the codewords at distance $L$. Our approach involves a parametrization of interpolating polynomials of a minimal Gr"obner basis $G$. We present two efficient ways to compute $G$. We also show that so-called re-encoding can be used to further reduce the complexity. We then demonstrate how our parametric approach can be solved by a computationally feasible rational curve fitting solution from a recent paper by Wu. Besides, we present an algorithm to compute the minimum multiplicity as well as the optimal values of the parameters associated with this multiplicity which results in overall savings in both memory and computation.

Cited in

(6)

• scientific article; zbMATH DE number 2081134 (Why is no real title available?)
• Using Lagrange's interpolation formula to construct Reed-Solomon codes over GF(p)
• List decoding algorithm based on voting in Gröbner bases for general one-point AG codes
• An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings
• A module minimization approach to Gabidulin decoding via interpolation
• Key equations for list decoding of Reed-Solomon codes and how to solve them

This page was built for publication: A Parametric Approach to List Decoding of Reed-Solomon Codes Using Interpolation

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