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

Technische Samenvatting: Low-Pathwidth GRAND (LP-GRAND)

Probleemstelling
Het artikel behandelt de uitdaging van Maximum-Likelihood (ML) decodering voor Binary Phase-Shift Keying (BPSK) transmissie over kanalen met gecorreleerde Gaussische ruis. Standaard soft-input Guessing Random Additive Noise Decoding (GRAND) bereikt eindige-blok ML-garanties door kandidaat-ruiseffectpatronen op te vragen in een niet-toenemende volgorde van hun conditionele waarschijnlijkheid. Echter, onder gecorreleerde ruis factoriseert de bijbehorende conditionele waarschijnlijkheid niet over coördinaten; het bevat interactietermen tussen coördinaten.

Bestaande GRAND-varianten, zoals ORBGRAND en de blokgebaseerde uitbreidingen (ORBGRAND-AI), vertrouwen op additieve betrouwbaarheidsmetrieken of blok-onafhankelijkheidsbenaderingen. Deze methoden falen in het behouden van de exacte waarschijnlijkheidsvolgorde die vereist is voor ML-decodering, omdat ze de interacties tussen coördinaten weglaten die inherent zijn aan de bijbehorende negatieve log-waarschijnlijkheidsmetriek. Bijgevolg is de eerste gevonden codeboek-hit door deze benaderingen niet gegarandeerd de ML-codewoord. Hoewel exacte ordening mogelijk is voor specifieke modellen zoals intersymboolinterferentie (ISI) via SGRAND-ISI, ontbrak er een algemene oplossing voor willekeurige ijle precisiematrices.

Methodologie
De auteurs stellen Low-Pathwidth GRAND (LP-GRAND) voor, een decoder die kandidaat-ruiseffectpatronen genereert in de exacte volgorde geïnduceerd door de bijbehorende Gaussische waarschijnlijkheid voor elke gespecificeerde symmetrische positief-definiete precisie-matrix $Q = \Sigma^{-1}$.

1. Kwadratische Pseudo-Booleaanse Formulering:
   Het kandidaat-afhankelijke deel van de Gaussische negatieve log-waarschijnlijkheid wordt afgeleid als een observatie-afhankelijke kwadratische pseudo-Booleaanse energiefunctie, $W_r(z)$. Voor een kandidaat-ruispatroon $z \in \{0, 1\}^n$ is de energie:
   $$W_r(z) = \sum_{i=1}^n \alpha_i z_i + \sum_{1 \le i < j \le n} \beta_{ij} z_i z_j$$
   De interactiegraaf van deze energie bevat een zijde $\{i, j\}$ indien en slechts indien de overeenkomstige waarde in de precisie-matrix $Q_{ij} \neq 0$. De ijle structuur van $Q$ bepaalt dus de structuur van de energiefunctie.

2. Grafische Representatie via Paddecompositie:
   Om patronen in een niet-afnemende energievolgorde te enumereren, construeert LP-GRAND een gelaagde grafische representatie (een trellis of DAG) gebaseerd op een paddecompositie van de interactiegraaf.

   • Als de precisie-matrix een halve bandbreedte heeft van maximaal $\nu$, staat de interactiegraaf een paddecompositie toe met breedte $w \le \nu$.
   • Deze decompositie levert een gelaagde graaf op met maximaal $2^{w+1}$ toestanden (bag assignments) per laag.
   • Voor banded matrices reduceert dit tot een standaard trellis met $2^\nu$ toestanden per laag.

3. Exacte Enumeratie-algoritme:
   De decoder maakt gebruik van suffix dynamic programming gecombineerd met best-first complete-path enumeratie (met behulp van een priority queue) op de geconstrueerde gelaagde graaf.

   • Suffix dynamic programming berekent vooraf de minimale kosten om de sink te bereiken vanaf elke toestand, wat efficiënte branch-and-bound pruning mogelijk maakt.
   • De best-first enumerator extraheert paden in een niet-afnemende totale kostenvolgorde.
   • Het algoritme vraagt de codeboek-lidmaatschapstest $\Phi(y \oplus z)$ op voor elk uitgegeven patroon $z$. Het eerste patroon dat voldoet aan $\Phi(y \oplus z) = 1$ wordt geretourneerd.

Belangrijkste Bijdragen

1. Exacte ML-volgorde: Het artikel bewijst dat voor elke niet-lege binaire codeboek met even waarschijnlijke codewoorden, het enumereren van ruiseffectpatronen in een niet-afnemende volgorde van $W_r(z)$ garandeert dat de eerste codeboek-hit een ML-codewoord is. Dit geldt in reële rekenkunde zonder de zoektocht te verlaten.
2. Algemene Afhandeling van IJle Precisie: In tegenstelling tot eerdere methoden die beperkt zijn tot specifieke kanaalmodellen (bijv. geheugenloos of specifieke ISI), construeert LP-GRAND de exacte ordening direct vanuit een meegeleverde ijle precisie-matrix, mits de interactiegraaf van de matrix een paddecompositie met een begrensde breedte toestaat.
3. Algoritmische Constructie: De auteurs bieden een constructieve methode om de gelaagde grafische representatie te bouwen vanuit een gevalideerde paddecompositie. Ze tonen aan dat voor een paddecompositie van breedte $w$, de grafische representatie maximaal $2^{w+1}$ toestanden per laag heeft, wat lineair groeit met de bloklengte $n$ voor een vaste $w$.
4. Robuustheidsanalyse: Het artikel stelt voorwaarden vast waaronder de strikte paarwijze ordening van kandidaten behouden blijft onder coëfficiënt-kwantisatie en precisie-matrix mismatch, waardoor wordt gegarandeerd dat de exacte volgorde behouden blijft voor de gewijzigde metriek.

Experimentele Resultaten
De auteurs valideren LP-GRAND via uitgebreide numerieke evaluaties:

• Exactheid Verificatie: Voor kleine bloklengtes ($n \in \{8, 10, 12\}$) en diverse topologieën (banded, path, ladder, binary tree), kwam de outputsequentie van LP-GRAND exact overeen met de exhaustieve sortering van alle $2^n$ kandidaten in niet-afnemende energie. Het maximale absolute verschil tussen grafische padkosten en directe kwadratische evaluatie was van de orde $10^{-16}$.
• ML-Overeenkomst: Voor twee vaste $[20, 12]$ codes (een willekeurige lineaire code en een CRC-8 code) over 10.000 frames, kwam LP-GRAND perfect overeen met exhaustieve codewoord ML-decodering.
• Prestaties vs. Benaderingen: Voor zes vaste $[64, 52]$ codes bij een nominale $E_b/N_0 = 2$ dB met gecorreleerde ruis ($\rho=0.5$), bereikte LP-GRAND een lagere empirische Block Error Rate (BLER) dan zowel ExactBlockProduct (een blokgebaseerde onafhankelijkheidsbenadering) als ORBGRAND-AI.
• Efficiëntie: LP-GRAND vereiste aanzienlijk minder geldige lidmaatschapsvragen om de eerste codewoord te vinden vergeleken met de benaderingen. Bijvoorbeeld, voor $R_c = 0.75$, vroeg LP-GRAND gemiddeld 132,3 queries, versus 227,5 voor ExactBlockProduct en 350,6 voor ORBGRAND-AI.
• Niet-Banded Grafen: De methode verwerkte succesvol een gepermuteerd Gauss-Markov kanaal waarbij de coördinaat-volgorde halve bandbreedte 56 was, maar de Reverse Cuthill-McKee (RCM) ordening de geïnduceerde frontier breedte reduceerde naar 1, wat efficiënte enumeratie mogelijk maakte.

Betekenis en Claims
Het artikel claimt dat LP-GRAND de eerste exacte, code-agnostische soft-input decoder is voor BPSK over gecorreleerde Gaussische ruis die ML-decodering garandeert onder volledige enumeratie. Door gebruik te maken van paddecomposities van de door precisie geïnduceerde interactiegraaf, vermijdt het de onafhankelijkheidsbenaderingen die de ML-garantie in bestaande GRAND-varianten ondermijnen. Het werk demonstreert dat exacte waarschijnlijkheidsgeordende enumeratie computationeel haalbaar is voor ijle precisie-matrices met een lage pathwidth, wat een rigoureuze alternatief biedt voor heuristische of benaderende decoders in omgevingen met gecorreleerde ruis. De auteurs benadrukken dat hoewel de grootte van de graaf begrensd wordt door de pathwidth, het aantal queries dat nodig is om de eerste hit te vinden afhangt van de specifieke codeboek en kanaalrealisatie, en niet alleen van de grafische breedte.