On the Error Probability of RPA Decoding of Reed-Muller Codes over BMS Channels

Technische Samenvatting: Over de foutkans van RPA-decodering van Reed-Muller-codes over BMS-kanalen

Probleemstelling
Reed-Muller (RM) codes zijn een fundamentele familie van binaire lineaire codes die bekend staan om het bereiken van de kanaalcapaciteit over Binary Memoryless Symmetric (BMS) kanalen. Hoewel de theoretische capaciteitsbereikende eigenschap is vastgesteld, blijft praktische decodering een uitdaging. De Recursive Projection-Aggregation (RPA) decoder, geïntroduceerd door Ye en Abbe, heeft een prestatie geleverd die nabij de maximum-likelihood (ML) prestatie ligt voor RM-codes over de Binary Symmetric Channel (BSC). Echter, rigoureuze analytische prestatiegaranties voor RPA-decodering over algemene BMS-kanalen ontbraken voorheen. Hoewel recent werk door Rameshwar en Lalitha (2025) dergelijke garanties bood voor de BSC, is het uitbreiden van deze resultaten naar willekeurige BMS-kanalen niet triviaal; een directe generalisatie van hun bewijsstrategie vereist restrictieve aannames over het kanaal (bijv. een begrensde output-alfabetgrootte en begrensde log-likelihood ratio's). Dit artikel adresseert de kloof door expliciete foutkansgrenzen af te leiden voor RPA-decodering over algemene BMS-kanalen zonder dergelijke restrictieve aannames.

Methodologie
De auteurs ontwikkelen een bewijsstrategie die de aanpak gebruikt voor de BSC door gebruik te maken van een specifieke structurele equivalentie tussen de RPA-decoder en de polar code constructie.

1. Kanaalequivalentie: Het kerninzicht op technisch gebied is het identificeren van een equivalentie tussen de projectie-operatie in RPA-decodering en de "kanaalcombinatie"-fase in de constructie van polar codes. Specifiek induceert het projecteren van een RM-code langs een eendimensionale subruimte een nieuw kanaal, aangeduid als $W^-$, dat identiek is aan het kanaal dat voortkomt uit het combineren van twee onafhankelijke toepassingen van het oorspronkelijke BMS-kanaal $W$.
2. Bhattacharyya-parameteranalyse: Gebruikmakend van deze equivalentie, analyseren de auteurs de evolutie van de Bhattacharyya-parameter ($Z$) door de recursieboom van de RPA-decoder. Zij stellen vast dat de Bhattacharyya-parameter van het geïnduceerde kanaal in elke stap voldoet aan $Z(W^-) \leq 1 - (1 - Z(W))^2$. Dit maakt het mogelijk om de kanaalkwaliteit bij de "bladeren" van de recursieboom (waar eerste-orde RM-codes worden gedecodeerd) te begrenzen in termen van de initiële kanaalparameter.
3. Recursieve foutgrenzen: De analyse richt zich op het geval waarin één iteratie van de RPA-decoder volstaat voor convergentie. De auteurs leiden de recessie-relaties af voor de foutkans bij elk knooppunt van de RPA-recursieboom.
   • Basisgeval: Voor de bladknopen (eerste-orde RM-codes) hanteren zij een generieke union bound op de ML-foutkans. Cruciaal is dat deze grens geldt voor elk BMS-kanaal, waardoor de noodzaak voor specifieke kanaalbeperkingen wordt vermeden.
   • Recursieve stap: Voor hogere-orde knopen wordt de foutkans begrensd door de kans op fouten in de kind-knooppunten en de kans op een fout in de aggregatie-stap, geconditioneerd op correcte decodering van de kind-knooppunten.
4. Het uitrollen van de recursie: Door deze recessie-relaties uit te rollen, leiden de auteurs een gesloten vorm van een bovengrens voor de totale blokfoutkans, $P_{err}(RM(m, r))$, af als functie van de bloklengte $n = 2^m$ en de code-orde $r$.

Belangrijkste bijdragen en resultaten
De primaire bijdrage is Theorem 4, die een analytische garantie biedt voor de verdwijnende foutkans van de RPA-decoder over algemene BMS-kanalen.

• Hoofdresultaat: Het artikel bewijst dat voor een BMS-kanaal met Bhattacharyya-parameter $Z$, de RPA-decoder een verdwijnende foutkans bereikt naarmate de bloklengte $n \to \infty$ (of equivalent aan $m \to \infty$) mits de RM-orde $r$ ongeveer schaalt als:
  $$r < \log_2 m - \log_2 \lambda$$
  waarbij $\lambda = -\ln(1-Z)$.
• Asymptotische schaling: Deze schaling impliceert dat $r$ logaritmisch groeit met $m$ (d.w.z. $r \sim \log \log n$). Dit asymptotische gedrag is identiek aan het resultaat dat eerder is vastgesteld voor de BSC in [19].
• Generaliteit: In tegen tegenstelling tot eerdere pogingen om de BSC-bewijsvoering te generaliseren, vereist deze techniek geen aanvullende aannames voor het BMS-kanaal (zoals begrensde log-likelihood ratio's). Het bewijs steunt uitsluitend op de eigenschappen van de Bhattachya-parameter en de structurele equivalentie met polar code combinatie.

Betekenis en Claims
Het artikel claimt dat hun werk een significante generalisatie is van het resultaat van 2025 door Rameshwar en Lalitha. Door vast te stellen dat de RPA-decoder aantoonbaar een verdwijnende foutkans bereikt voor "low-rate" RM-codes (waarbij de orde schaalt als $\log \log n$) over alle BMS-kanalen, breiden de auteurs het theoretische begrip van RPA-decodering uit voorbij de BSC.

De auteurs merken op dat hoewel hun afgeleide grens voor de BSC iets zwakker is dan de specifieke grens in [19] (vanwege de vereiste algemeenheid voor willekeurige BMS-kanalen), de asymptotische groeivoet van de code-orde $r$ hetzelfde blijft. Zij stellen expliciet dat hun analyse zich beperkt tot het regime waar een enkele iteratie van de decoder volstaat. Bijgevolg suggereren zij dat het versoepelen van deze restrictie om de correlaties die door meerdere iteraties worden geïntroduceerd te analyseren, een belangrijke richting is voor het verkrijgen van verdere asymptotische verbeteringen in de foutkans, hoewel dit niet wordt bereikt in het huidige werk.

Samenvattend biedt het artikel het eerste rigoureuze, aannamevrije analytische bewijs dat de RPA-decoder effectief is voor RM-codes over de brede klasse van BMS-kanalen, waarmee bevestigd wordt dat de prestaties van de decoder gunstig schalen met de bloklengte, zelfs in de afwezigheid van specifieke kanaalbeperkingen.