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

DOI10.1109/TIT.2010.2060130zbMATH Open1366.94722arXivcs/0702130MaRDI QIDQ5281273FDOQ5281273

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)

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.

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)

Cited In (15)

• 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
• Title not available (Why is that?)
• Polynomial linear system solving with random errors. New bounds and early termination technique
• A lattice-based minimal partial realization algorithm for matrix sequences of varying length
• Improved power decoding of interleaved one-point Hermitian codes
• Power decoding Reed-Solomon codes up to the Johnson radius
• Distinguishing and recovering generalized linearized Reed-Solomon codes

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)