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)

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

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)