Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Advances in Mathematics of Communications

A weight-based characterization of the set of correctable error patterns under list-of-2 decoding

Jonas Eriksson

Published Jan 1, 2007• 0 citations
Publisher

Abstract

List decoding of block codes is an alternative approach to thedecoding problem with appealing qualities. The fairly recent development of efficient algorithms for list decoding of Reed-Solomon codes spur new fuel to the study of this decoding strategy. In this paper we give a weight-based characterization of the set of correctable error patterns under list-of-2 ecodingof $(\tau, 2$)-list-decodable linear codes with known weight distribution. We apply our characterization of the set of correctable error patterns to a few codes in a family of low-rate list-of-2 decodable Reed-Solomon codes. We study the increase in error-correction performance obtained in a symmetric AWGN channel by using list-of-2 decoding instead of traditional decoding for these codes. Some simulation results for list-of-2 decoding on QAM channels using the Guruswami-Sudan algorithm for decoding of Reed-Solomon codes are alsopresented.

DOI
10.3934/amc.2007.1.331

Related papers

The Polynomial of correctable 2 Concatenated codes patterns of concatenated codes Let B(n

Nicolas Seiidrier

The polynomial of correctable patterns is defined In [l] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can be defined as well ([5] aid (61) These polynomials allow a compact representation of a decodiilg alient to compute the coriection probabillty and ability thiougli a memoryless symetric channel. Our purpose heie is to compute the polynomials of correctable patThese results are geneialised in [5] and [SI for erasure channels. terns of concatenated codes for dlffeient decoding algorithms. I) We give the weight distribution of the erior patterns correctable by the standard decoding algorithm. * We give bounds for the weight distribution of the error patterns correct able by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide to evaluate the standard algorithm. It will also give a with precision the performances of the Block-Zyablov decoding algorithm which needed, up to llow, a (much more expensive) simulation. ill compute the decoding performances of the rdstrom-Robinson ([4, p. 731) inlier code, and a Reed-Solomon (255,223,33) outer code over F2~6.

•Jan 1, 1992•0 citations

The Polynomial of correctable patterns of concatenated codes

Nicolas Sendrier

The polynomial of correctable patterns is defined in [1] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can redefined as well ([5] and [6]). These polynomials allow a compact representation of a decoding algorithm which is sufficient to compute the correction probability and the miscorrection probability through a memoryless symetric channel. These results are generalized in [5] and [6] for erasure channels. Our purpose here is to compute the polynomials of correctable patterns of concatenated codes for different decoding algorithms. We give the weight distribution of the error patterns correctable by the standard decoding algorithm. We give bounds for the weight distribution of the error patterns correctable by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide an efficient way to evaluate the standard algorithm. It will also give a way to evaluate with precision the performances of the Block- Zyablov decoding algorithm which needed, up to now, a (much more expensive) simulation. As an example, we will compute the decoding performances of the concatenation of the Nordstrom-Robinson ([4, p. 73]) inner code, and a Reed-Solomon (255,223,33) outer code over F/sub 256/.

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•0 citations

Optimization of List-Based Reed-Solomon Decoding via Deep Learning

Sergey L. Portnoy, Alexey M. Efremov, Andrey D. Voloshin

This paper presents a deep learning-based optimization of a list-decoding algorithm for a concatenated Hamming-Reed-Solomon code transmitted over an AWGN channel with BPSK modulation. The proposed method reformulates early termination of the erasure-pattern list as a weighted regression problem, addressing class imbalance through an asymmetric Weighted Mean Squared Error (WMSE) loss function that penalizes index underestimation more heavily than overestimation. Simulation results confirm that the neural network predictor reduces the average number of decoding iterations across the evaluated SNR range while maintaining error-correction performance comparable to the baseline list decoder.

2018Systems of Signal Synchronization, Generating and Processing in Telecommunications (SYNCHROINFO)•Jun 1, 2026•0 citations

List Decoding of 2-Interleaved Binary Alternant Codes

Chih‐Chiang Huang, Hedongliang Liu, Lukas Holzbaur +2 more

This paper is concerned with list decoding of 2-interleaved binary alternant codes. The principle of the proposed algorithm is based on a combination of a list decoding algorithm for (interleaved) Reed-Solomon codes and an algorithm for (non-interleaved) alternant codes. A new upper bound on the decoding radius is derived and the list size is shown to scale polynomially in the code parameters. While it remains an open problem whether this upper bound is achievable, the provided simulation results show that a decoding radius exceeding the binary Johnson radius can be achieved with a high probability of decoding success by the proposed algorithm.

arXiv:2201.11617•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•0 citations

Decoding concatenated codes using soft information

Venkatesan Guruswami, Madhu Sudan

We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.

IEEE Conference on Computational Complexity (CCC)•Jun 25, 2003•19 citations

On the computation of the probability of post-decoding error events for block codes (Corresp.)

Zelma McC. Huntoon, Arnold M. Michelson

The computation of the probability of certain post-decoding error events is formulated for block codes whose weight distributions are known. A bounded-distance decoder for group codes is assumed. Numerical examples included show post-decoding character error rates for the Golay code and for some Reed-Solomon codes and the distribution of post-decoding errors for the same Reed-Solomon codes. An extension to errors and erasures decoding is also given.

IEEE Transactions on Information Theory•May 1, 1977•46 citations
List decoding of block codes is an alternative approach to thedecoding problem with appealing qualities. The fairly recent development of efficient algorithms for list decoding of Reed-Solomon codes spur new fuel to the study of this decoding strategy. In this paper we give a weight-based characterization of the set of correctable error patterns under list-of-2 ecodingof (τ,2(\tau, 2(τ,2)-list-decodable linear codes with known weight distribution. We apply our characterization of the set of correctable error patterns to a few codes in a family of low-rate list-of-2 decodable Reed-Solomon codes. We study the increase in error-correction performance obtained in a symmetric AWGN channel by using list-of-2 decoding instead of traditional decoding for these codes. Some simulation results for list-of-2 decoding on QAM channels using the Guruswami-Sudan algorithm for decoding of Reed-Solomon codes are alsopresented.
The polynomial of correctable patterns is defined In [l] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can be defined as well ([5] aid (61) These polynomials allow a compact representation of a decodiilg alient to compute the coriection probabillty and ability thiougli a memoryless symetric channel. Our purpose heie is to compute the polynomials of correctable patThese results are geneialised in [5] and [SI for erasure channels. terns of concatenated codes for dlffeient decoding algorithms. I) We give the weight distribution of the erior patterns correctable by the standard decoding algorithm. * We give bounds for the weight distribution of the error patterns correct able by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide to evaluate the standard algorithm. It will also give a with precision the performances of the Block-Zyablov decoding algorithm which needed, up to llow, a (much more expensive) simulation. ill compute the decoding performances of the rdstrom-Robinson ([4, p. 731) inlier code, and a Reed-Solomon (255,223,33) outer code over F2~6.
The polynomial of correctable patterns is defined in [1] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can redefined as well ([5] and [6]). These polynomials allow a compact representation of a decoding algorithm which is sufficient to compute the correction probability and the miscorrection probability through a memoryless symetric channel. These results are generalized in [5] and [6] for erasure channels. Our purpose here is to compute the polynomials of correctable patterns of concatenated codes for different decoding algorithms. We give the weight distribution of the error patterns correctable by the standard decoding algorithm. We give bounds for the weight distribution of the error patterns correctable by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide an efficient way to evaluate the standard algorithm. It will also give a way to evaluate with precision the performances of the Block- Zyablov decoding algorithm which needed, up to now, a (much more expensive) simulation. As an example, we will compute the decoding performances of the concatenation of the Nordstrom-Robinson ([4, p. 73]) inner code, and a Reed-Solomon (255,223,33) outer code over F/sub 256/.
This paper presents a deep learning-based optimization of a list-decoding algorithm for a concatenated Hamming-Reed-Solomon code transmitted over an AWGN channel with BPSK modulation. The proposed method reformulates early termination of the erasure-pattern list as a weighted regression problem, addressing class imbalance through an asymmetric Weighted Mean Squared Error (WMSE) loss function that penalizes index underestimation more heavily than overestimation. Simulation results confirm that the neural network predictor reduces the average number of decoding iterations across the evaluated SNR range while maintaining error-correction performance comparable to the baseline list decoder.
This paper is concerned with list decoding of 2-interleaved binary alternant codes. The principle of the proposed algorithm is based on a combination of a list decoding algorithm for (interleaved) Reed-Solomon codes and an algorithm for (non-interleaved) alternant codes. A new upper bound on the decoding radius is derived and the list size is shown to scale polynomially in the code parameters. While it remains an open problem whether this upper bound is achievable, the provided simulation results show that a decoding radius exceeding the binary Johnson radius can be achieved with a high probability of decoding success by the proposed algorithm.
We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.