How a second codeword can improve confidence in decoding errors
Conditional Correctness in List Decoding: How a Late Second Codeword Can Rescue Confidence in the First
Information Theory
Summary
When trying to fix errors in digital messages, the first guess for the correct message can sometimes be wrong or uncertain. The authors show that looking at the position of a second possible guess in the list can actually help determine if the first guess is more likely to be right. They also establish mathematical rules that tell when the first guess will almost certainly be correct or incorrect, depending on the rankings of the guesses in the decoding process. This insight can make error-correcting methods more reliable by using information beyond just the top guess.
What this means in practice
- •For communication engineers: Improve decoding algorithms by using the rank of the second codeword to increase confidence in the first guess under noisy conditions.
- •For network system designers: Design more reliable error correction schemes in digital communication by incorporating conditional correctness from later list entries in decoding.
Authors
Conrad Struss, Muriel Medard, Ken R. Duffy
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.