2026/07/30 by Behrooz Razeghi
Computer Science · Mathematics · #cs.IT #math.IT
arxiv created 2026/07/30 · arxiv updated 2026/07/31
The finite-block maximum-likelihood (ML) guarantee of soft-input GRAND requires querying noise-effect patterns in nonincreasing conditional-likelihood order. Under correlated Gaussian noise, additive reliability metrics and independent-block approximations need not preserve this order because the matched metric contains cross-coordinate interactions; the first codebook hit need not induce an ML codeword. We develop Low-Pathwidth GRAND (LP-GRAND) for binary phase-shift keying (BPSK) with precision matrix Q. The candidate-dependent part of the Gaussian negative log-likelihood is an observation-dependent quadratic pseudo-Boolean energy whose interaction graph has edge \i,j\ exactly when Qij≠0. If Q has half-bandwidth at most ν, this energy admits a trellis with at most 2ν states per layer; a path decomposition of width w yields at most 2w+1 bag assignments per layer. In real arithmetic, suffix dynamic programming and best-first complete-path enumeration enumerate patterns in nondecreasing energy. With complete enumeration and no abandonment, the first codebook hit induces an ML codeword for any nonempty binary codebook with equiprobable codewords. LP-GRAND agreed with exhaustive codeword ML in all 10,000 frames for two [20,12] codes. At nominal Eb/N0=2 dB, its empirical BLER was lower than that of each block-based approximation for six [64,52] codes.