The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes

DOI10.1109/TIT.2010.2096034MaRDI QIDQ5281066zbMATH OpenOpenAlexFDO

Authors R. Kötter, Jun Ma, Alexander Vardy

Publication date 27 July 2017

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

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

Mathematics Subject Classification ID

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Abstract: The main computational steps in algebraic soft-decoding, as well as Sudan-type list-decoding, of Reed-Solomon codes are bivariate polynomial interpolation and factorization. We introduce a computational technique, based upon re-encoding and coordinate transformation, that significantly reduces the complexity of the bivariate interpolation procedure. This re-encoding and coordinate transformation converts the original interpolation problem into another reduced interpolation problem, which is orders of magnitude smaller than the original one. A rigorous proof is presented to show that the two interpolation problems are indeed equivalent. An efficient factorization procedure that applies directly to the reduced interpolation problem is also given.

Cited in

(6)

• A Hensel lifting to replace factorization in list-decoding of algebraic-geometric and Reed-Solomon codes
• A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes
• Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes
• An encoder to match Reed-Solomon codes over GF(q) to a subalphabet of GF(q)
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• Key equations for list decoding of Reed-Solomon codes and how to solve them

This page was built for publication: The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes

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