🔢 mathematics

Low-Pathwidth GRAND: Exact Likelihood-Ordered Enumeration for BPSK Transmission over Correlated Gaussian Noise

This paper introduces Low-Pathwidth GRAND (LP-GRAND), an exact maximum-likelihood decoding algorithm for BPSK over correlated Gaussian noise that leverages the low-pathwidth structure of the noise precision matrix to enumerate noise patterns in likelihood order via dynamic programming, thereby guaranteeing optimal decoding performance where traditional approximations fail.

Original authors: Behrooz Razeghi

Published 2026-07-31

📖 7 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

Imagine you are trying to send a secret message across a noisy, crowded room. You shout a series of words, but the wind, the chatter, and the echo distort your voice. The person listening has to guess which words you actually meant. In the world of digital communication, this "room" is a channel, the "words" are bits of data, and the "noise" is a random interference that scrambles the signal. The goal of a decoder is to figure out the original message despite this chaos.

For decades, engineers have used a clever strategy called "Guessing Random Additive Noise Decoding" (GRAND). Instead of trying to guess the message directly, GRAND works backward: it guesses what the noise might have been. It starts with the most likely noise patterns (like a gentle breeze) and works its way down to the unlikely ones (like a hurricane). If it subtracts a guessed noise pattern from the received signal and the result is a valid message, it stops and declares victory. The trick is that for this to work perfectly, the decoder must guess the noise patterns in the exact right order, from most probable to least probable.

However, things get messy when the noise isn't just random static but is "correlated." Imagine the wind doesn't just blow randomly; if it gusts at one moment, it's likely to gust a split second later. This creates a complex web of connections between the bits, making it incredibly hard to rank the noise patterns correctly. Previous methods tried to simplify this by ignoring the connections or breaking the message into small, independent chunks, but these shortcuts often led to wrong guesses.

This paper introduces a new, highly precise decoder called Low-Pathwidth GRAND (LP-GRAND). Think of it as a master detective who doesn't just guess the noise; they map out the entire "interaction graph" of the noise to find the perfect order to check possibilities. The authors show that by treating the noise as a specific mathematical shape (a quadratic energy landscape) and using a clever "trellis" (a step-by-step map), they can list every possible noise pattern in the exact order of likelihood, even when the noise is highly correlated. They proved mathematically that if you follow this list without skipping anything, the very first valid message you find is guaranteed to be the best possible answer. In simulations with specific codes, this new method found the correct message more often and faster than previous "chunk-based" shortcuts, proving that taking the time to map the complex connections pays off.

The Core Idea: Mapping the Noise Maze

To understand how LP-GRAND works, let's imagine the noise as a giant, multi-dimensional maze. In a simple, "memoryless" world, every path in the maze is independent; you can choose the left or right turn at any point without worrying about the previous turn. But in a "correlated" world, the maze is twisted. Turning left at step 5 might force you to turn right at step 6. This twisting is what makes the math hard.

The authors realized that for a specific type of noise (Gaussian noise with a known "precision matrix"), this twisted maze can be flattened into a structured, layered map called a trellis. If the noise connections are "sparse" (meaning they only link nearby bits, like neighbors talking to each other), this map doesn't get infinitely huge. Instead, it stays manageable, like a ladder with a limited number of rungs.

LP-GRAND uses this ladder to perform a "best-first" search. It doesn't just walk down the ladder; it calculates the "energy cost" of every possible path. The lower the energy, the more likely that noise pattern is. By using a technique called suffix dynamic programming, the decoder can look ahead and know exactly which paths are the cheapest to explore next. It's like having a GPS that tells you not just the distance to the exit, but the exact order in which to visit every possible route to ensure you find the shortest one first.

Why the Old Shortcuts Failed

Before this paper, engineers often tried to simplify the problem by breaking the message into small blocks and assuming the noise in one block didn't affect the next. This is like trying to solve a jigsaw puzzle by ignoring the fact that the picture on one piece might connect to the picture on the piece next to it.

The paper explicitly argues against these "block-based approximations." The authors show that when noise is correlated, these shortcuts miss the "cross-coordinate interactions"—the subtle ways one part of the noise influences another. In their tests, these shortcuts often guessed the wrong noise pattern first, leading to decoding errors. The paper demonstrates that while these shortcuts are faster to compute, they are not "Maximum Likelihood" (ML) optimal, meaning they don't guarantee finding the absolute best answer. LP-GRAND, by contrast, refuses to cut corners; it calculates the exact energy of the full, correlated noise, ensuring that the first valid message it finds is mathematically the most likely one.

The Results: A Perfect Match

The authors didn't just theorize; they tested their decoder rigorously. They ran simulations on two different types of codes: a small [20, 12] code and a larger [64, 52] code.

In the small code tests, they compared LP-GRAND against an "exhaustive" search—a method that checks every single possible message one by one to find the best one. This exhaustive method is the gold standard but is usually too slow for real use. Over 10,000 frames of data, LP-GRAND agreed with the exhaustive search 100% of the time. It found the exact same "best" message every single time, proving that its ordering of noise patterns was mathematically perfect.

For the larger [64, 52] codes, they compared LP-GRAND against the popular block-based shortcuts (like ORBGRAND-AI and ExactBlockProduct). At a signal quality of 2 dB, LP-GRAND achieved a lower "Block Error Rate" (BLER) than all the other methods. In simple terms, it made fewer mistakes. For example, with a specific random code, LP-GRAND had an error rate of about 0.022, while the best block-based approximation had an error rate of 0.040. This means LP-GRAND was nearly twice as reliable in these tests.

The "Pathwidth" Magic

The secret sauce of this decoder is a concept called pathwidth. Imagine the noise connections as a graph where dots (bits) are connected by lines. If the graph is a long, straight line, the pathwidth is small. If it's a tangled ball of yarn, the pathwidth is huge. The authors showed that if the noise matrix has a "half-bandwidth" (meaning it only connects bits that are close to each other), the pathwidth is small enough to build a manageable trellis.

They tested this on graphs with different shapes, like paths, ladders, and binary trees. For the "path" and "ladder" shapes, which represent the kind of noise found in many real-world channels, the decoder worked perfectly. They even tested a scenario where the noise connections were shuffled (permuted) so they weren't in a neat order. By using a clever reordering trick called Reverse Cuthill–McKee (RCM), they could still find a low pathwidth and run the decoder efficiently. In one test with a shuffled 64-bit code, LP-GRAND found the correct message in all 50 frames tested, while the block-based methods made errors in 17 to 25 frames.

The Bottom Line

This paper presents a decoder that is both exact and efficient for a specific, important class of noisy channels. It proves that you don't have to choose between speed and accuracy if you are willing to use the right mathematical map. By treating the noise as a structured energy landscape and using a "low-pathwidth" approach to navigate it, LP-GRAND guarantees that the first valid message it finds is the best possible one. While it requires more complex setup than the old shortcuts, the simulations show that for correlated noise, this extra effort results in significantly fewer errors, making it a powerful tool for future high-reliability communication systems.

Technical Summary: Low-Pathwidth GRAND (LP-GRAND)

Problem Statement
The paper addresses the challenge of Maximum-Likelihood (ML) decoding for Binary Phase-Shift Keying (BPSK) transmission over channels with correlated Gaussian noise. Standard soft-input Guessing Random Additive Noise Decoding (GRAND) achieves finite-block ML guarantees by querying candidate noise-effect patterns in nonincreasing order of their conditional likelihoods. However, under correlated noise, the matched conditional likelihood does not factorize across coordinates; it contains cross-coordinate interaction terms.

Existing GRAND variants, such as ORBGRAND and its block-based extensions (ORBGRAND-AI), rely on additive reliability metrics or block-independence approximations. These methods fail to preserve the exact likelihood ordering required for ML decoding because they omit the cross-coordinate interactions inherent in the matched negative log-likelihood metric. Consequently, the first codebook hit found by these approximations is not guaranteed to be the ML codeword. While exact ordering is possible for specific models like intersymbol interference (ISI) via SGRAND-ISI, a general solution for arbitrary sparse precision matrices has been lacking.

Methodology
The authors propose Low-Pathwidth GRAND (LP-GRAND), a decoder that generates candidate noise-effect patterns in the exact order induced by the matched Gaussian likelihood for any specified symmetric positive-definite precision matrix $Q = \Sigma^{-1}$ .

Quadratic Pseudo-Boolean Formulation:
The candidate-dependent part of the Gaussian negative log-likelihood is derived as an observation-dependent quadratic pseudo-Boolean energy function, $W_r(z)$ . For a candidate noise pattern $z \in \{0, 1\}^n$ , the energy is:
$W_r(z) = \sum_{i=1}^n \alpha_i z_i + \sum_{1 \le i < j \le n} \beta_{ij} z_i z_j$
The interaction graph of this energy contains an edge $\{i, j\}$ if and only if the corresponding entry in the precision matrix $Q_{ij} \neq 0$ . Thus, the sparsity pattern of $Q$ dictates the structure of the energy function.
Graphical Representation via Path Decomposition:
To enumerate patterns in nondecreasing energy order, LP-GRAND constructs a layered graphical representation (a trellis or DAG) based on a path decomposition of the interaction graph.
- If the precision matrix has a half-bandwidth of at most $\nu$ , the interaction graph admits a path decomposition of width $w \le \nu$ .
- This decomposition yields a layered graph with at most $2^{w+1}$ states (bag assignments) per layer.
- For banded matrices, this reduces to a standard trellis with $2^\nu$ states per layer.
Exact Enumeration Algorithm:
The decoder employs suffix dynamic programming combined with best-first complete-path enumeration (using a priority queue) on the constructed layered graph.
- Suffix dynamic programming precomputes the minimum cost to reach the sink from any state, enabling efficient branch-and-bound pruning.
- The best-first enumerator extracts paths in nondecreasing total cost.
- The algorithm queries the codebook membership test $\Phi(y \oplus z)$ for each emitted pattern $z$ . The first pattern satisfying $\Phi(y \oplus z) = 1$ is returned.

Key Contributions

Exact ML Ordering: The paper proves that for any nonempty binary codebook with equiprobable codewords, enumerating noise-effect patterns in nondecreasing order of $W_r(z)$ ensures that the first codebook hit is an ML codeword. This holds in real arithmetic without abandoning the search.
General Sparse Precision Handling: Unlike previous methods restricted to specific channel models (e.g., memoryless or specific ISI), LP-GRAND constructs the exact ordering directly from a supplied sparse precision matrix, provided the matrix's interaction graph admits a bounded-width path decomposition.
Algorithmic Construction: The authors provide a constructive method to build the layered graphical representation from a validated path decomposition. They demonstrate that for a path decomposition of width $w$ , the graphical representation has at most $2^{w+1}$ states per layer, growing linearly with blocklength $n$ for fixed $w$ .
Robustness Analysis: The paper establishes conditions under which the strict pairwise ordering of candidates is preserved under coefficient quantization and precision matrix mismatch, ensuring that the exact order is maintained for the modified metric.

Experimental Results
The authors validate LP-GRAND through extensive numerical evaluations:

Exactness Verification: For small blocklengths ( $n \in \{8, 10, 12\}$ ) and various topologies (banded, path, ladder, binary tree), LP-GRAND's output sequence matched exhaustive sorting of all $2^n$ candidates in nondecreasing energy. The maximum absolute difference between graphical path costs and direct quadratic evaluation was on the order of $10^{-16}$ .
ML Agreement: For two fixed $[20, 12]$ codes (a random linear code and a CRC-8 code) over 10,000 frames, LP-GRAND agreed perfectly with exhaustive codeword ML decoding.
Performance vs. Approximations: For six fixed $[64, 52]$ codes at nominal $E_b/N_0 = 2$ dB with correlated noise ( $\rho=0.5$ ), LP-GRAND achieved a lower empirical Block Error Rate (BLER) than both ExactBlockProduct (a block-based independence approximation) and ORBGRAND-AI.
Efficiency: LP-GRAND required significantly fewer valid membership queries to find the first codeword compared to the approximations. For example, at $R_c = 0.75$ , LP-GRAND averaged 132.3 queries versus 227.5 for ExactBlockProduct and 350.6 for ORBGRAND-AI.
Non-Banded Graphs: The method successfully handled a permuted Gauss-Markov channel where the coordinate-order half-bandwidth was 56, but the Reverse Cuthill-McKee (RCM) ordering reduced the induced frontier width to 1, allowing efficient enumeration.

Significance and Claims
The paper claims that LP-GRAND provides the first exact, code-agnostic soft-input decoder for BPSK over correlated Gaussian noise that guarantees ML decoding under complete enumeration. By leveraging path decompositions of the precision-induced interaction graph, it avoids the independence approximations that compromise the ML guarantee in existing GRAND variants. The work demonstrates that exact likelihood-ordered enumeration is computationally feasible for sparse precision matrices with low pathwidth, offering a rigorous alternative to heuristic or approximate decoders in correlated noise environments. The authors emphasize that while the graphical size is bounded by the pathwidth, the number of queries required to reach the first hit depends on the specific codebook and channel realization, not just the graph width.