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 Transactions on Information Theory

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

Chunlong Bai, Bartosz Mielczarek, Witold A. Krzymień, I.J. Fair

Published Jan 23, 2007• 10 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2006.889464

Related papers

On the theory of list decoding of convolutional codes

Rolf Johannesson, Kamil Sh. Zigangirov

Lower bounds on the list minimum weight and list weight are obtained for ensembles of systematic and nonsystematic encoders. >From these bounds it follows that the necessary list size grows exponentially with the number of corrected errors. We obtain an expurgated upper bound on the probability of the correct path loss for the ensemble of time-invariant binary convolutional codes. The notion of an l-list weight enumerator is introduced and used to obtain an upper bound on the probability of the correct path loss for list decoding of a fixed convolutional code.

Problems of Information Transmission•Jan 1, 1996•3 citations

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

List decoding of concatenated codes: improved performance estimates

Alexander Barg, Andrew McGregor

An improved bound is proved on the list-decoding radius of a concatenated code relying upon a combination of (soft-decision) algebraic list decoding and generalized minimum distance (GMD) decoding in the outer level. This bound is further improved if the inner code is a random linear code.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•0 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

Reverse PAC Codes: Look-Ahead List Decoding

Xinyi Gu, Mohammad Rowshan, Jinhong Yuan

Convolutional precoding in polarization-adjusted convolutional (PAC) codes is a recently introduced variant of polar codes. It has demonstrated an effective reduction in the number of minimum weight codewords (a.k.a error coefficient) of polar codes. This reduction has the potential to significantly improve the error correction performance. From a codeword formation perspective, this reduction has limitations. Capitalizing on the understanding of the decomposition of minimum-weight codewords, this paper studies reverse precoding that can effectively reduce minimum-weight codewords more than in PAC codes. We propose a look-ahead list decoding for the reverse PAC codes, which has the same order of complexity as list decoding in PAC codes. Through numerical analysis, we demonstrate a notable reduction in error coefficients compared to PAC codes and polar codes, resulting in a remarkable improvement in the block error rate, in particular at high code rates.

arXiv:2406.01903•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•7 citations

Analysis of List Decoding for Convolutional Codes

Kamil Sh. Zigangirov, Harro Osthoff

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•4 citations
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.
Lower bounds on the list minimum weight and list weight are obtained for ensembles of systematic and nonsystematic encoders. >From these bounds it follows that the necessary list size grows exponentially with the number of corrected errors. We obtain an expurgated upper bound on the probability of the correct path loss for the ensemble of time-invariant binary convolutional codes. The notion of an l-list weight enumerator is introduced and used to obtain an upper bound on the probability of the correct path loss for list decoding of a fixed convolutional code.
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>
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.
Convolutional precoding in polarization-adjusted convolutional (PAC) codes is a recently introduced variant of polar codes. It has demonstrated an effective reduction in the number of minimum weight codewords (a.k.a error coefficient) of polar codes. This reduction has the potential to significantly improve the error correction performance. From a codeword formation perspective, this reduction has limitations. Capitalizing on the understanding of the decomposition of minimum-weight codewords, this paper studies reverse precoding that can effectively reduce minimum-weight codewords more than in PAC codes. We propose a look-ahead list decoding for the reverse PAC codes, which has the same order of complexity as list decoding in PAC codes. Through numerical analysis, we demonstrate a notable reduction in error coefficients compared to PAC codes and polar codes, resulting in a remarkable improvement in the block error rate, in particular at high code rates.