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

IEEE International Symposium on Information Theory (ISIT)

On error correction with feedback under list decoding

Ofer Shayevitz

Published Jun 1, 2009• 1 citation
Publisher

Abstract

This work provides some preliminary results on the problem of error correction in the presence of noiseless feedback, where list-of-L decoding is allowed. The methods introduced by Berlekamp for the list-of-1 setting are generalized, and some basic finite-block constraints are described. These constraints are then combined to derive an upper bound on the asymptotically achievable rates for a large family of strategies, as a function of the maximal error fraction p and the list size L.

DOI
10.1109/isit.2009.5205965

Related papers

Error-correcting codes for list decoding

Peter Eliaš

In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p>

IEEE Transactions on Information Theory•Jan 1, 1991•180 citations

Non¿binary error correcting codes with noiseless feedback, localized errors, or both

Rudolf Ahlswede, Christian Deppe, Vladimir Lebedev

The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•22 citations

Zero-Error List Decoding for Classical-Quantum Channels

Marco Dalai, Filippo Girardi, Ludovico Lami

The aim of this work is to study the zero-error capacity of pure-state classical-quantum channels in the setting of list decoding. We provide an achievability bound for list-size two and a converse bound holding for every fixed list size. The two bounds coincide for channels whose pairwise absolute state overlaps form a positive semi-definite matrix. Finally, we discuss a remarkable peculiarity of the classical-quantum case: differently from the fully classical setting, the rate at which the sphere-packing bound diverges might not be achievable by zero-error list codes, even when we take the limit of fixed but arbitrarily large list size.

quant-pharXiv:2601.09786•IEEE International Symposium on Information Theory (ISIT)•Jan 16, 2026•0 citations

Improved Analysis of List Decoding and Its Application to Convolutional Codes and Turbo Codes

Chunlong Bai, Bartosz Mielczarek, Witold A. Krzymień +1 more

A list decoder generates a list of more than one codeword candidates, and decoding is erroneous if the transmitted codeword is not included in the list. This decoding strategy can be implemented in a system that employs an inner error correcting code and an outer error detecting code that is used to choose the correct codeword from the list. Probability of codeword error analysis for a linear block code with list decoding is typically based on the “worst case” lower bound on the effective weights of codewords for list decoding evaluated from the weight enumerating function of the code.

IEEE Transactions on Information Theory•Jan 23, 2007•10 citations

Conditional Correctness in List Decoding: How a Late Second Codeword Can Rescue Confidence in the First

Conrad Struss, Muriel Médard, Ken R. Duffy

In error correction, the difference between a codeword and a received word, a candidate noise sequence, carries information on the confidence of the codeword as a proposed decoding. For additive channels, it is known that if noise sequences are ranked in decreasing order of likelihood, a lower rank correlates with higher confidence in a decoding. Here we substantially expand considerations by exploring the relationship between the likelihood ranks arising in list decoding and the posterior probability of decoding correctness, establishing that the ranks associated with subsequent list entries carry reliability information that is not obtainable from the first rank alone. Building on the recent development of Soft-Output Guessing Random Additive Noise Decoding, we first show that, under a random codebook model, soft-output expressions for list decoding coincide with the exact finite-blocklength conditional probabilities of decoding correctness. For hard-decision maximum likelihood decoding, we characterize the asymptotic reliability of the first list entry. We identify a decision function whose sign determines whether the posterior correctness probability of the first entry in the list converges to one or zero and whose absolute value gives the exponential rate of convergence. Perhaps surprisingly, the asymptotic reliability of the first list entry depends only on the first, second and last ranks. For list size one, the result recovers the previously known likelihood-rank threshold for reliable decoding. For list size two, a sufficiently late second entry can imply that the first entry is asymptotically correct even when its rank, viewed in isolation, would indicate otherwise.

arXiv:2610.02458•Oct 1, 2026•0 citations

A criterion for decoding on the binary symmetric channel

Anup Rao, Oscar Sprumont

We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive and doubly transitive codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.1. We give a tight bound on the weight distribution of every transitive linear code $ C \subseteq \mathbb{F}_2^N $:$ \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \mathsf{dim}(C)}. $2. We give a criterion that certifies that a linear code $ C $ can be decoded on the binary symmetric channel. Let $ K_s(x) $ denote the Krawtchouk polynomial of degree $ s $, and let $ C^\perp $ denote the dual code of $ C $. We show that bounds on $ \mathbb{E}_{c \in C^{\perp}}[ K_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $ C^\perp $ is sufficiently close to the binomial distribution in some interval around $ \frac{N}{2} $, $ C $ is resilient to $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.

Advances in Mathematics of Communications•Feb 28, 2024•2 citations
This work provides some preliminary results on the problem of error correction in the presence of noiseless feedback, where list-of-L decoding is allowed. The methods introduced by Berlekamp for the list-of-1 setting are generalized, and some basic finite-block constraints are described. These constraints are then combined to derive an upper bound on the asymptotically achievable rates for a large family of strategies, as a function of the maximal error fraction p and the list size L.
In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p>
The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors
The aim of this work is to study the zero-error capacity of pure-state classical-quantum channels in the setting of list decoding. We provide an achievability bound for list-size two and a converse bound holding for every fixed list size. The two bounds coincide for channels whose pairwise absolute state overlaps form a positive semi-definite matrix. Finally, we discuss a remarkable peculiarity of the classical-quantum case: differently from the fully classical setting, the rate at which the sphere-packing bound diverges might not be achievable by zero-error list codes, even when we take the limit of fixed but arbitrarily large list size.
A list decoder generates a list of more than one codeword candidates, and decoding is erroneous if the transmitted codeword is not included in the list. This decoding strategy can be implemented in a system that employs an inner error correcting code and an outer error detecting code that is used to choose the correct codeword from the list. Probability of codeword error analysis for a linear block code with list decoding is typically based on the “worst case” lower bound on the effective weights of codewords for list decoding evaluated from the weight enumerating function of the code.
In error correction, the difference between a codeword and a received word, a candidate noise sequence, carries information on the confidence of the codeword as a proposed decoding. For additive channels, it is known that if noise sequences are ranked in decreasing order of likelihood, a lower rank correlates with higher confidence in a decoding. Here we substantially expand considerations by exploring the relationship between the likelihood ranks arising in list decoding and the posterior probability of decoding correctness, establishing that the ranks associated with subsequent list entries carry reliability information that is not obtainable from the first rank alone. Building on the recent development of Soft-Output Guessing Random Additive Noise Decoding, we first show that, under a random codebook model, soft-output expressions for list decoding coincide with the exact finite-blocklength conditional probabilities of decoding correctness. For hard-decision maximum likelihood decoding, we characterize the asymptotic reliability of the first list entry. We identify a decision function whose sign determines whether the posterior correctness probability of the first entry in the list converges to one or zero and whose absolute value gives the exponential rate of convergence. Perhaps surprisingly, the asymptotic reliability of the first list entry depends only on the first, second and last ranks. For list size one, the result recovers the previously known likelihood-rank threshold for reliable decoding. For list size two, a sufficiently late second entry can imply that the first entry is asymptotically correct even when its rank, viewed in isolation, would indicate otherwise.
We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive and doubly transitive codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.1. We give a tight bound on the weight distribution of every transitive linear code $ C \subseteq \mathbb{F}_2^N ::: \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \mathsf{dim}(C)}. $2. We give a criterion that certifies that a linear code $ C $ can be decoded on the binary symmetric channel. Let $ K_s(x) $ denote the Krawtchouk polynomial of degree $ s $, and let $ C^\perp $ denote the dual code of $ C $. We show that bounds on $ \mathbb{E}_{c \in C^{\perp}}[ K_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $ C^\perp $ is sufficiently close to the binomial distribution in some interval around $ \frac{N}{2} $, $ C $ is resilient to $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.