🔢 mathematics

Tail-Calibrated Soft-Output GRAND for Finite-Memory Noise-Effect Posteriors

This paper introduces Tail-Calibrated SOGRAND, a decoding algorithm for finite-memory noise channels that enumerates candidate noise effects by posterior energy and utilizes finite-state recursions to compute exact posterior weights and tail masses, thereby enabling unbiased soft-output estimates and maximum-likelihood decoding with rigorous abandonment bounds.

Original authors: Behrooz Razeghi

Published 2026-08-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Behrooz Razeghi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Noise Hunt: Why Decoding Needs a Memory

Imagine you are trying to listen to a friend's voice across a crowded, windy stadium. Sometimes the wind blows in a steady stream, but other times it gusts in sudden, chaotic bursts that make words sound garbled. In the world of digital communication, this "wind" is called noise. When you send a message (like a text or a video) over the internet or a satellite link, the signal gets battered by this noise. To fix it, computers use decoders—smart algorithms that guess what the original message was, even when parts of it are missing or distorted.

For a long time, engineers treated this noise as if it were completely random, like rolling a die for every single letter of the message. If the noise on the first letter had nothing to do with the noise on the second, the math was simple. But in the real world, noise often has a "memory." A burst of static might last for several seconds, or a fading signal might linger. This means the noise on one letter is often related to the noise on the next. When decoders ignore this memory, they get confused, leading to dropped calls or corrupted files. The challenge is to build a decoder that doesn't just look at the current letter but remembers the recent past to make a better guess. This paper tackles exactly that problem, offering a new way to hunt down the right message even when the noise is acting like a sneaky, remembering ghost.

The Paper's Story: Teaching the Decoder to Remember

This paper introduces a new, smarter way to decode messages called Tail-Calibrated Soft-Output GRAND. To understand what makes it special, let's look at how the old way worked. Imagine you are trying to find a specific key in a giant, messy pile of junk. The old method, called GRAND (Guessing Random Additive Noise Decoding), works by guessing what the "noise" (the junk) might look like. It starts by guessing the most likely junk first, checks if removing that junk reveals a valid message, and if not, moves to the next most likely guess. It's like a detective who checks the most probable suspects first.

However, when the noise has a "memory" (like a burst of static), the old detective gets confused. It might guess the noise on the first letter correctly but fail to realize that the noise on the second letter is likely to be similar. The paper points out that previous methods tried to fix this by shuffling the letters (a process called interleaving) to break the connection between them. But shuffling is like taking a puzzle apart and mixing the pieces before you start; it adds delay and makes the puzzle harder to solve quickly. Other methods tried to guess the noise in small, independent blocks, but they missed the bigger picture of how the noise flows from one letter to the next.

What this paper does:
The author proposes a decoder that acts like a detective with a perfect memory of the noise's recent history. Instead of shuffling the puzzle pieces or guessing in small, isolated blocks, this new decoder understands that the noise is a continuous, flowing story. It uses a concept called finite-memory energy, which is a fancy way of saying the decoder calculates how "likely" a specific pattern of noise is, based on how it fits with the noise that came just before it.

The paper introduces a clever trick called Tail-Calibration. Imagine the detective is searching the junk pile. As they check items, they keep a running tally of how much "junk" they have already looked at. They also need to guess how much "junk" is left in the pile that they haven't looked at yet. If they stop too early, they might miss the right key. If they search forever, they waste time. The new method calculates a precise "tail" of the remaining junk. It uses a mathematical estimate to say, "We have checked 99% of the likely junk, and the remaining 1% is so unlikely that we can safely stop." This allows the decoder to stop searching at the exact right moment, saving time without losing accuracy.

What the paper finds:
Through computer simulations, the author shows that this new method works better than the old ones when the noise has memory.

Better Accuracy: In tests with a specific type of noisy channel (called a Gauss–Markov channel), the new decoder made fewer mistakes. For example, at a signal quality of 3 dB, the new method had a block error rate (the chance of getting the whole message wrong) of about 0.0099 (less than 1%), while the best previous method (ORBGRAND-AI with block size 8) had an error rate of 0.0285 (nearly 3%).
Fewer Guesses: The new decoder also needed to check fewer "junk" patterns to find the right message. In the same test, it only needed to make about 42 membership checks (guesses) on average, whereas the previous best method needed 130.
The Trade-off: The paper is honest about a catch. While the new decoder is more accurate and checks fewer items, the math it uses to calculate the "memory" of the noise is more complex. In their software simulation, the new method did more "mental work" (calculating probabilities) per guess than the simpler methods. The author suggests that while it is currently heavier on the computer's brain, it is much more efficient at finding the answer.

What the paper rules out:
The paper explicitly argues against the idea that interleaving (shuffling the data) is the best solution for low-latency (fast) communication. They show that shuffling adds delay and hides the structure of the noise, making it harder for the decoder to use its "memory" effectively. They also show that guessing noise in small, independent blocks (like the ORBGRAND-AI method) is not as good as using the full memory of the noise, because the noise often flows across those block boundaries.

How sure are they?
The author is very confident in their mathematical proofs. They have proved that if the decoder guesses the noise in the exact right order, it will find the best possible answer (the "Maximum Likelihood" solution). They have also proved that their method for estimating the "tail" of the remaining junk is statistically sound for random codebooks. However, their claims about the performance improvements (like the lower error rates) are based on computer simulations, not real-world hardware tests. They tested their ideas on simulated random codes and specific noise models (like Gauss–Markov and binary Markov noise). The results are strong and consistent across many different tests, but they are currently limited to these simulations.

In short, this paper gives us a new tool for decoding messages in a noisy world. It teaches the decoder to remember the past, stop searching at the perfect moment, and find the right message faster and more accurately than before, provided we can handle the extra math required to keep that memory alive.

Technical Summary: Tail-Calibrated Soft-Output GRAND for Finite-Memory Noise-Effect Posteriors

Problem Statement
Guessing Random Additive Noise Decoding (GRAND) reformulates maximum-likelihood (ML) decoding as a search over candidate noise effects rather than codewords. While standard GRAND and its soft-output variants (SOGRAND) perform well on memoryless channels, they face challenges when the effective noise exhibits temporal correlation (memory). Existing correlation-aware GRAND methods, such as ORBGRAND-AI, incorporate local dependence into the noise-effect ordering but rely on interleaving or approximate independence models. Crucially, these methods lack a rigorous framework for computing finite-memory posterior tail masses and bitwise tail marginals required for accurate soft-output reliability estimation (APP and LLRs) in correlated noise environments. Furthermore, standard soft-output rules are not derived from the finite-memory posterior tails, leading to a gap in estimating the probability that the transmitted codeword is missing from the current query list (the "missing-list" probability).

Methodology
The paper introduces Tail-Calibrated SOGRAND, a decoder designed for binary additive channels where the ambient hard-decision noise-effect posterior, conditioned on received soft information, is modeled by a finite-memory energy.

Finite-Memory Posterior Modeling:
The decoder assumes the ambient full-space posterior weights $\pi_{r^n}(z^n)$ are defined by a finite-range energy function $E_{r^n}(z^n)$ . This includes memoryless models, first-order Markov models, and finite-state burst models. The partition function $Z(r^n)$ and posterior weights are computed efficiently using finite-state forward recursions, avoiding explicit summation over the entire $2^n$ space.
Tail-Calibrated Stopping and Missing-List Estimation:
Unlike GRANDAB, which uses a fixed query threshold, Tail-Calibrated SOGRAND stops based on a plug-in estimate of the missing-list probability.
- The decoder enumerates noise effects in nondecreasing posterior energy.
- It maintains the accumulated ambient posterior mass of queried prefixes ( $S_q$ ) and the remaining ambient tail mass ( $T_q$ ).
- Under a fixed-size random-codebook ensemble, the unqueried codebook-restricted denominator contribution ( $U_q$ ) is estimated as $\hat{U}_q = p_q T_q$ , where $p_q = (M - |L_q|) / (2^n - q)$ is the remaining occupancy probability.
- The stopping rule halts when the estimated missing-list probability $\hat{P}_{miss}(q) = \hat{U}_q / (S_q + \hat{U}_q)$ falls below a tolerance $\eta$ .
Soft-Output Generation:
The same posterior-tail decomposition yields blockwise and bitwise APP estimates. Bitwise APP log-likelihood ratios (LLRs) are derived by decomposing the unqueried tail mass according to bit values (0 or 1) and combining them with the listed codeword contributions.
Enumeration:
For first-order energies, noise patterns are enumerated by decomposing them into maximal runs of ones (burst atoms) and ordering these atoms by their excess energy. This allows for exact energy-ordered enumeration without interleaving.

Key Contributions

Formulation: The paper formulates Tail-Calibrated SOGRAND for binary additive channels with finite-memory noise-effect posteriors, explicitly separating the ambient posterior law from the codebook-restricted APP denominator.
Theoretical Derivation: It derives a tail-calibrated soft-output rule for GRAND searches under a fixed-size random-codebook ensemble, proving that the conditional mean of the unqueried denominator contribution is $p_q T_q$ .
Finite-Block Guarantees:
- ML Property: With exact energy ordering and no abandonment, the first listed codeword is guaranteed to be ML under the defining likelihood model.
- Abandonment Bounds: An ambient-tail abandonment bound is proven, showing that the error probability of an abandoned decoder is bounded by the abandoned ambient posterior tail mass.
- Estimator Bounds: Conditional unbiasedness, variance, and concentration bounds are derived for the random-codebook missing-list estimator.
Soft-Output Decomposition: The method provides a unified procedure to compute blockwise APPs, missing-list probabilities, and bitwise APP LLRs for correlated noise-effect posteriors.
Empirical Evaluation: The decoder is evaluated on random linear codes over Gauss-Markov and hard-decision correlated noise models.

Results
Numerical evaluations compare Tail-Calibrated SOGRAND (specifically the "Exact-Markov" variant) against random-interleaved ORBGRAND, ORBGRAND-AI (with local block orderings), and ExactBlockProduct ablations.

Performance: In Gauss-Markov channels ( $\rho=0.5$ ), the Exact-Markov decoder achieves lower Block Error Rate (BLER) point estimates and smaller average membership-query counts compared to memoryless, rank-weighted approximate-independence, and block-product approximate-independence orderings.
Correlation Sensitivity: As the correlation coefficient $\rho$ increases, the performance gap between the correlation-aware Exact-Markov decoder and memoryless baselines widens significantly.
Model Mismatch: The decoder is sensitive to model mismatch; using a memoryless model ( $\rho_{model}=0$ ) on a correlated channel ( $\rho=0.5$ ) results in significant BLER degradation compared to a matched model.
Calibration: Reliability diagrams demonstrate that the plug-in missing-list estimate is well-calibrated, with small expected calibration errors (ECE) in populated probability ranges.
Complexity Trade-off: While the Exact-Markov decoder minimizes the number of codebook membership queries (the primary GRAND metric), its "software-work proxy" (counting metric evaluations and priority queue operations) is higher at low SNR compared to approximate methods, reflecting the cost of exact finite-memory enumeration.

Significance
The paper claims to address a critical gap in GRAND-based decoding: the lack of finite-block posterior-tail computations for correlated noise. By deriving exact finite-memory posterior weights, tail masses, and bitwise marginals, the work enables GRAND to function as a soft-output component decoder in iterative schemes (e.g., for product codes and GLDPC codes) without relying on interleaving. The proposed method provides a rigorous theoretical foundation for stopping criteria and reliability estimation in memory channels, offering improved error rates and query efficiency over existing correlation-aware approximations, albeit with a trade-off in enumeration complexity. The author positions this as a step toward integrating GRAND into full iterative decoding systems for channels with memory.

The Great Noise Hunt: Why Decoding Needs a Memory

The Paper's Story: Teaching the Decoder to Remember

Technical Summary: Tail-Calibrated Soft-Output GRAND for Finite-Memory Noise-Effect Posteriors

More like this