Syndrome Decoding of Reed–Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis

DOI10.1109/TIT.2010.2060130MaRDI QIDQ5281273zbMATH OpenFDO

Authors Georg Schmidt, V. R. Sidorenko, Martin Bossert

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/cs/0702130

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cyclic codes (94B15) Decoding (94B35)

Abstract: In this paper, a new approach for decoding low-rate Reed-Solomon codes beyond half the minimum distance is considered and analyzed. Unlike the Sudan algorithm published in 1997, this new approach is based on multi-sequence shift-register synthesis, which makes it easy to understand and simple to implement. The computational complexity of this shift-register based algorithm is of the same order as the complexity of the well-known Berlekamp-Massey algorithm. Moreover, the error correcting radius coincides with the error correcting radius of the original Sudan algorithm, and the practical decoding performance observed on a q-ary symmetric channel (QSC) is virtually identical to the decoding performance of the Sudan algorithm. Bounds for the failure and error probability as well as for the QSC decoding performance of the new algorithm are derived, and the performance is illustrated by means of examples.

Cited in

(15)

• Distinguishing and recovering generalized linearized Reed-Solomon codes
• Bounds on collaborative decoding of interleaved Hermitian codes and virtual extension
• Power Decoding of Reed–Solomon Codes Revisited
• Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability
• Structural properties of self-dual monomial codes with application to code-based cryptography
• A linear algebraic approach to multisequence shift-register synthesis
• Fast skew-feedback shift-register synthesis
• Algorithms for simultaneous Hermite-Padé approximations
• A Syndrome Formulation of the Interpolation Step in the Guruswami-Sudan Algorithm
• Power error locating pairs
• scientific article; zbMATH DE number 1792628 (Why is no real title available?)
• A lattice-based minimal partial realization algorithm for matrix sequences of varying length
• Polynomial linear system solving with random errors. New bounds and early termination technique
• Improved power decoding of interleaved one-point Hermitian codes
• Power decoding Reed-Solomon codes up to the Johnson radius

This page was built for publication: Syndrome Decoding of Reed–Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis

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