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

arXiv:2610.02458

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

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

Published Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2610.02458

Related papers

Guessing Random Additive Noise Decoding With Symbol Reliability Information (SRGRAND)

Ken R. Duffy, Muriel Médard, Wei An

The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon’s 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg’s 1978 theorem on the NP-completeness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes.

arXiv:1902.03796•IEEE Transactions on Communications•Sep 20, 2021•59 citations

The Approximate Maximum-Likelihood Certificate

Idan Goldenberg, David Burshtein

The confidence in the reliability of a codeword output by some (not necessarily optimal) decoding algorithm is discussed. A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced to address this issue as follows. First, the channel output vector is decoded by some symmetric decoder D, e.g., belief propagation or min-sum algorithm decoding. Second, the channel output vector is decoded by LP decoding. Third, if the decoding result of D is a codeword, its LP value is compared to the LP value of the LP decoding result (the latter need not be a codeword). If these two values are close, the AMLC holds. Using upper bounding techniques, we show that the conditional frame error probability given that the AMLC holds, is with some degree of confidence below a threshold. In channels with low noise, this threshold is orders of magnitude lower than the simulated frame error rate, and our bound holds with a very high degree of confidence. This is in stark contrast with standard Monte Carlo simulation, which would require excessively long runs to demonstrate like performance. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

IEEE Transactions on Information Theory•May 16, 2013•2 citations

On the determination of GRAND noise sequences by employing integer compositions

Steven Jones, A. Brinton Cooper

Guessing Random Additive Noise Decoding (GRAND) has been proposed as an efficient and universal decoding technique for linear block codes [1]. A necessary element of the GRAND decoder is a set of noise sequences of length$n$equal to the code length. The decoded codeword is taken as the first valid codeword that results from the binary addition of the noise sequences, in order of likelihood, with the received word. For a binary code of length$\boldsymbol{n}$there are$2^{n}$such noise sequences. When$\boldsymbol{n}$is large, it will typically be intractable to add every noise sequence during decoding. Moreover, these sequences exhibit a number of error bursts$(\boldsymbol{m})$and a total number of bit flips$(\boldsymbol{l})$. In [1] the authors provide expressions to determine the probability of each error burst sequence for a two-state Markov channel model. The resulting decoder is called GRAND-Markov Order (GRAND-MO). The authors of [1] describe a GRAND-MO error pattern generator for the two-state Markov channel based upon sequential transition between$(\boldsymbol{m},\boldsymbol{l})$pairs, incrementing$\boldsymbol{m}$first, and then treating each value of l. In this paper we address a method of constructing the n-length noise sequences based upon integer compositions on the required$l$bit flips as well as the$\boldsymbol{n}-\boldsymbol{l}$non-errors in the sequence. This method allows one to construct noise sequences in order of probability without the need to construct less likely noise sequences. A GRAND decoder may employ a limited number of noise sequences and abandon decoding upon finding a valid code word, or upon reaching an abandonment threshold without decoding success. In this way the most likely noise sequences can be prioritized in decoding.

Conference on Information Sciences and Systems•Mar 22, 2023•2 citations

Leveraging Code Structure to Improve Soft Output for GRAND, GCD, OSD, and SCL

Jiewei Feng, Ken R. Duffy, Muriel Médard

In addition to a codeword, error correction decoders that provide blockwise soft output (SO) return an estimate of the likelihood that the decoding is correct. Following Forney, such estimates have traditionally only been possible for list decoders with the approximate soft output being the likelihood that a decoding is correct given it is assumed to be in the list. Recently, it has been established that Guessing Random Additive Noise Decoding (GRAND), Guessing Codeword Decoding (GCD), Ordered Statistics Decoding (OSD), and Successive Cancellation List (SCL) decoding can provide accurate soft output without the need for list decoding. Central to the improvement is the evaluation of an estimate of the likelihood that the correct decoding has not been found. We explore how binary linear codebook constraints can be leveraged to further enhance SO precision. We evaluate performance by adapting a forecasting statistic called the Brier Score. Results indicate that the SO generated by the approach is essentially as accurate as the maximum a posteriori estimate.

arXiv:2503.16677•Mar 20, 2025•0 citations

Low-Complexity Ordered Reliability Direct Error Pattern Testing (ORDEPT) Decoding with Likelihood Thresholding

Reza Hadavian, Dmitri V. Truhachev

We propose a reduced complexity approach to pattern-based soft decoding of block codes. We start from the ORDEPT decoding algorithm which tests a list of partial error patterns organized in the order of their likelihood and attempts to complete the patterns creating candidate codewords. We then propose an early termination criterion. Once a candidate codeword is found, its log-likelihood difference to the received sequence is compared to a preset threshold and the decoding decision is instantly made in case the likelihood deviation is below the threshold. We demonstrate that while keeping the same block error rate (BLER) performance, the proposed algorithm's latency and complexity is multiple times smaller than that of the state-of-the art competitors including the Chase II, ORBGRAND, GCD, and the very recent ORDEPT with Soft-Output GRAND termination which necessitates several multiplications in each query processing.

arXiv:2506.20079•Jun 25, 2025•0 citations

Sort-and-match algorithm for soft-decision decoding

Ilya I. Dumer

Let a q-ary linear (n, k) code C be used over a memoryless channel. We design a decoding algorithm /spl Psi//sub N/ that splits the received block into two halves in n different ways. First, about /spl radic/N error patterns are found on either half. Then the left- and right-hand lists are sorted out and matched to form codewords. Finally, the most probable codeword is chosen among at most n/spl radic/N codewords obtained in all n trials. The algorithm can be applied to any linear code C and has complexity order of n/sup 3//spl radic/N. For any N/spl ges/q/sup n-k/, the decoding error probability P/sub N/ exceeds at most 1+q/sup n-k//N times the probability P/sub /spl Psi//(C) of maximum-likelihood decoding. For code rates R/spl ges/1/2, the complexity order q/sup n-k/2/ grows as square root of general trellis complexity q/sup min{n-k,k}/. When used on quantized additive white Gaussian noise (AWGN) channels, the algorithm /spl Psi//sub N/ can provide maximum-likelihood decoding for most binary linear codes even when N has an exponential order of q/sup n-k/.

IEEE Transactions on Information Theory•Jan 1, 1999•13 citations
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.
The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon’s 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg’s 1978 theorem on the NP-completeness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes.
The confidence in the reliability of a codeword output by some (not necessarily optimal) decoding algorithm is discussed. A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced to address this issue as follows. First, the channel output vector is decoded by some symmetric decoder D, e.g., belief propagation or min-sum algorithm decoding. Second, the channel output vector is decoded by LP decoding. Third, if the decoding result of D is a codeword, its LP value is compared to the LP value of the LP decoding result (the latter need not be a codeword). If these two values are close, the AMLC holds. Using upper bounding techniques, we show that the conditional frame error probability given that the AMLC holds, is with some degree of confidence below a threshold. In channels with low noise, this threshold is orders of magnitude lower than the simulated frame error rate, and our bound holds with a very high degree of confidence. This is in stark contrast with standard Monte Carlo simulation, which would require excessively long runs to demonstrate like performance. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.
Guessing Random Additive Noise Decoding (GRAND) has been proposed as an efficient and universal decoding technique for linear block codes [1]. A necessary element of the GRAND decoder is a set of noise sequences of lengthnnnequal to the code length. The decoded codeword is taken as the first valid codeword that results from the binary addition of the noise sequences, in order of likelihood, with the received word. For a binary code of lengthn\boldsymbol{n}nthere are2n2^{n}2nsuch noise sequences. Whenn\boldsymbol{n}nis large, it will typically be intractable to add every noise sequence during decoding. Moreover, these sequences exhibit a number of error bursts(m)(\boldsymbol{m})(m)and a total number of bit flips(l)(\boldsymbol{l})(l). In [1] the authors provide expressions to determine the probability of each error burst sequence for a two-state Markov channel model. The resulting decoder is called GRAND-Markov Order (GRAND-MO). The authors of [1] describe a GRAND-MO error pattern generator for the two-state Markov channel based upon sequential transition between(m,l)(\boldsymbol{m},\boldsymbol{l})(m,l)pairs, incrementingm\boldsymbol{m}mfirst, and then treating each value of l. In this paper we address a method of constructing the n-length noise sequences based upon integer compositions on the requiredlllbit flips as well as then−l\boldsymbol{n}-\boldsymbol{l}n−lnon-errors in the sequence. This method allows one to construct noise sequences in order of probability without the need to construct less likely noise sequences. A GRAND decoder may employ a limited number of noise sequences and abandon decoding upon finding a valid code word, or upon reaching an abandonment threshold without decoding success. In this way the most likely noise sequences can be prioritized in decoding.
In addition to a codeword, error correction decoders that provide blockwise soft output (SO) return an estimate of the likelihood that the decoding is correct. Following Forney, such estimates have traditionally only been possible for list decoders with the approximate soft output being the likelihood that a decoding is correct given it is assumed to be in the list. Recently, it has been established that Guessing Random Additive Noise Decoding (GRAND), Guessing Codeword Decoding (GCD), Ordered Statistics Decoding (OSD), and Successive Cancellation List (SCL) decoding can provide accurate soft output without the need for list decoding. Central to the improvement is the evaluation of an estimate of the likelihood that the correct decoding has not been found. We explore how binary linear codebook constraints can be leveraged to further enhance SO precision. We evaluate performance by adapting a forecasting statistic called the Brier Score. Results indicate that the SO generated by the approach is essentially as accurate as the maximum a posteriori estimate.
We propose a reduced complexity approach to pattern-based soft decoding of block codes. We start from the ORDEPT decoding algorithm which tests a list of partial error patterns organized in the order of their likelihood and attempts to complete the patterns creating candidate codewords. We then propose an early termination criterion. Once a candidate codeword is found, its log-likelihood difference to the received sequence is compared to a preset threshold and the decoding decision is instantly made in case the likelihood deviation is below the threshold. We demonstrate that while keeping the same block error rate (BLER) performance, the proposed algorithm's latency and complexity is multiple times smaller than that of the state-of-the art competitors including the Chase II, ORBGRAND, GCD, and the very recent ORDEPT with Soft-Output GRAND termination which necessitates several multiplications in each query processing.
Let a q-ary linear (n, k) code C be used over a memoryless channel. We design a decoding algorithm /spl Psi//sub N/ that splits the received block into two halves in n different ways. First, about /spl radic/N error patterns are found on either half. Then the left- and right-hand lists are sorted out and matched to form codewords. Finally, the most probable codeword is chosen among at most n/spl radic/N codewords obtained in all n trials. The algorithm can be applied to any linear code C and has complexity order of n/sup 3//spl radic/N. For any N/spl ges/q/sup n-k/, the decoding error probability P/sub N/ exceeds at most 1+q/sup n-k//N times the probability P/sub /spl Psi//(C) of maximum-likelihood decoding. For code rates R/spl ges/1/2, the complexity order q/sup n-k/2/ grows as square root of general trellis complexity q/sup min{n-k,k}/. When used on quantized additive white Gaussian noise (AWGN) channels, the algorithm /spl Psi//sub N/ can provide maximum-likelihood decoding for most binary linear codes even when N has an exponential order of q/sup n-k/.