Polar Complexity: A New Descriptive Complexity with Applications to Source and Joint Source-Channel Coding

Technische Samenvatting: Polaire Complexiteit en Adaptieve Dubbel-Polaire Coding

Probleemstelling
Het efficiënt beschrijven van individuele eindige binaire sequenties blijft een fundamentele uitdaging in de informatietheorie. Waar het Shannon-raamwerk de gemiddelde beschrijvingslengten optimaliseert voor stochastische bronnen met bekende statistieken, is het niet direct toepasbaar op individuele sequenties die geen probabilistisch model hebben. Omgekeerd is Kolmogorov-complexiteit, die de complexiteit van een sequentie definieert aan de hand van de lengte van het kortste programma dat deze genereert, theoretisch universeel maar onberekenbaar. Bestaande berekenbare benaderingen, zoals Lempel-Ziv (LZ)-complexiteit of lineaire complexiteit, vertrouwen op specifieke structurele aannames (bijvoorbeeld herhalende patronen of lineaire recurrenties) die mogelijk niet de volledige regelmaat van willekeurige sequenties vastleggen. Bovendien biedt conventionele polaire broncoding met vaste lengte, hoewel deze entropie bereikt voor stochastische bronnen, geen inherente mechanisme om de minimale compressielengte te bepalen die nodig is voor de exacte reconstructie van een specifieke individuele sequentie.

Methodologie
Dit artikel introduceert een nieuwe meting voor beschrijvende complexiteit, genaamd Polaire Complexiteit, gedefinieerd als de minimale Polaire-Compressielengte (PCL) die nodig is om de exacte reconstructie van een specifieke binaire sequentie te garanderen met Successive Cancellation Decoding (SCD). De methodologie is gebaseerd op het Binary Balanced Tree (BBT) polaire coderingsraamwerk, dat polaire transformaties generaliseert naar willekeurige bloklengtes.

1. Definitie en Berekening van Polaire Complexiteit:

   • De auteurs definiëren de polaire complexiteit $L^\star(\mathbf{s})$ van een sequentie $\mathbf{s}$ als de kleinste PCL $L$ zodat de sequentie perfect kan worden hersteld uit zijn polair gecomprimeerde representatie onder een canonieke configuratie (met gebruik van de Polarization-Weight-methode voor selectie van bevroren knopen en een deterministische SCD-parameter $\tau=0$).
   • Exacte Berekening: Door gebruik te maken van de monotonie van herstelbaarheid (als een sequentie herstelbaar is bij lengte $L$, is deze herstelbaar bij elke $L' > L$), stelt het artikel een bisektie-zoekalgoritme voor om $L^\star(\mathbf{s})$ efficiënt te berekenen, waardoor het aantal SCD-proeven wordt gereduceerd van lineair naar logaritmisch in de sequentielengte.
   • Complexiteitsarme Schatting: Om herhaalde decodeerproeven te vermijden, wordt een voorspelde polaire complexiteit geïntroduceerd. Deze methode maakt gebruik van Genie-Aided SCD (GA-SCD) om een "kritieke set" van bladknopen te identificeren die lokaal dubbelzinnig zijn of gevoelig voor fouten. De voorspelde complexiteit wordt bepaald door de selectieprioriteit van de knoop met de hoogste prioriteit in deze kritieke set, en biedt een conservatieve bovengrens voor de ware polaire complexiteit.

2. Polargebaseerde Twee-Staps Broncoding:

   • Er wordt een nieuw broncoderingsschema voorgesteld waarbij elke bronsequentie wordt gecodeerd als een paar: een vaste lengte header die de binaire representatie van de polaire complexiteit bevat, gevolgd door de variabele lengte polair gecomprimeerde sequentie.
   • Het schema is strikt verliesvrij en prefix-vrij.
   • Theoretische analyse bewijst dat voor Binaire Geheugenloze Bronnen (BMS) met bloklengtes als machten van twee, de genormaliseerde gemiddelde compressielengte van dit schema asymptotisch de bronentropie benadert, mits de selectie van bevroren knopen en SCD-parameters zijn geoptimaliseerd voor de bronverdeling.

3. Adaptieve Dubbel-Polaire Gezamenlijke Bron- en Kanaalcoding (JSCC):

   • De auteurs integreren de voorgestelde broncoding met polaire kanaalcoding om een adaptief JSCC-schema te creëren.
   • Mechanisme: De encoder en decoder delen een vooraf gedefinieerde eindige set van kandidaat-PCL's. Voor een gegeven bronsequentie selecteert de encoder de kleinste kandidaat-PCL die groter dan of gelijk is aan de voorspelde polaire complexiteit van de sequentie. Deze geselecteerde PCL bepaalt de toewijzing van actieve en bevroren knopen in de kanaalencoder.
   • Decoding: De decoder voert hypothese-toetsing uit over de set van kandidaat-PCL's. Het reconstrueert kandidaat-bronsequenties voor elke hypothese en selecteert de uiteindelijke schatting op basis van het Maximum A Posteriori (MAP)-criterium, waarbij CRC-controles worden gebruikt om ongeldige kandidaten te filteren.
   • Optimalisatie: Het ontwerp van de set kandidaat-PCL's wordt geformuleerd als een optimalisatieprobleem om de Frame Error Rate (FER) te minimaliseren. Dit wordt efficiënt opgelost met dynamische programmering, waarbij de afweging tussen prestaties (finere granulariteit) en complexiteit (grootte van de kandidaatset) wordt gebalanceerd.

Belangrijkste Bijdragen

• Polaire Complexiteit: De introductie van een nieuwe, berekenbare meting voor beschrijvende complexiteit gebaseerd op de minimale PCL voor exacte SCD-reconstructie.
• Efficiënte Algoritmen: Ontwikkeling van een bisektie-zoekalgoritme voor exacte berekening en een complexiteitsarme GA-SCD-gebaseerde voorspellingsmethode voor het schatten van polaire complexiteit.
• Twee-Staps Broncoding: Een strikt verliesvrij, prefix-vrij coderingsschema dat asymptotisch bronentropie bereikt zonder voorafgaande kennis van bronstatistieken te vereisen voor de werking (hoewel entropie-bereikende beweringen kennis van statistieken aannemen voor parameterafstelling).
• Adaptieve JSCC: Een unificerend dubbel-polaire JSCC-raamwerk dat de kanaalcoderingsrate aanpast aan de comprimeerbaarheid van individuele bronrealisaties. Het schema omvat een methode op basis van dynamische programmering om de kandidaat-PCL-set te optimaliseren voor afwegingen tussen prestaties en complexiteit.

Resultaten

• Prestaties Broncoding: Simulaties tonen aan dat het voorgestelde twee-staps schema compressieprestaties bereikt die vergelijkbaar zijn met enumeratieve coding voor korte bloklengtes ($K=64$), maar met aanzienlijk lagere rekencomplexiteit ($O(K \log K)$ versus $O(K^2)$). Het schema blijft robuust over verschillende bronverdelingen en vereist geen voorafgaande statistische kennis.
• Complexiteitsschatting: De bisektie-zoekmethode reduceert de rekenkosten voor het bepalen van polaire complexiteit aanzienlijk in vergelijking met sequentiële zoekopdrachten. De voorspelde polaire complexiteit biedt consequent een bovengrens voor de ware complexiteit met een kleine kloof, wat de bruikbaarheid voor JSCC-ontwerp valideert.
• JSCC-prestaties: In simulaties van adaptieve dubbel-polaire JSCC (voor bloklengtes $N=128$ en $N=1024$) presteert het voorgestelde schema beter dan bestaande JSCC-baselines op basis van polaire codes (inclusief double-CRC-polaire en gezamenlijke SCLD-schema's). De Frame Error Rate (FER) neemt monotoon af naarmate de kardinaliteit van de kandidaat-PCL-set toeneemt, en nadert een theoretische ondergrens waarbij de ware PCL bekend is bij de decoder.

Betekenis
Het artikel stelt dat door de focus te verschuiven van stochastische bronkenmerken naar het herstelgedrag van individuele sequenties onder polaire coding, het een praktische en berekenbare maatstaf voor beschrijvende complexiteit biedt. Deze "polaire complexiteit" maakt een nieuwe klasse coderingsschema's mogelijk die strikt verliesvrij en adaptief zijn. Het voorgestelde adaptieve dubbel-polaire JSCC-schema biedt een flexibele afweging tussen prestaties en complexiteit, en toont aan dat het afstemmen van kanaalbescherming op de specifieke comprimeerbaarheid van individuele bronrealisaties superieure foutkansprestaties kan opleveren in vergelijking met statische of niet-adaptieve gezamenlijke coderingsbenaderingen. Het werk overbrugt de kloof tussen concepten van algoritmische complexiteit en praktische, capaciteitsbenaderende coderingstechnieken.