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

Sintesi Tecnica: Complessità Polare e Codifica Doppia Polare Adattiva

Enunciato del Problema
Descrivere efficientemente singole sequenze binarie di lunghezza finita rimane una sfida fondamentale nella teoria dell'informazione. Mentre il quadro di Shannon ottimizza le lunghezze medie di descrizione per sorgenti stocastiche con statistiche note, non si applica direttamente a sequenze individuali prive di un modello probabilistico. Al contrario, la complessità di Kolmogorov, che definisce la complessità di una sequenza attraverso la lunghezza del programma più breve che la genera, è teoricamente universale ma non calcolabile. Gli approcci calcolabili esistenti, come la complessità di Lempel-Ziv (LZ) o la complessità lineare, si basano su ipotesi strutturali specifiche (ad esempio, pattern ripetuti o ricorrenze lineari) che potrebbero non catturare la piena regolarità di sequenze arbitrarie. Inoltre, la codifica sorgente polare convenzionale a lunghezza fissa, pur raggiungendo l'entropia per sorgenti stocastiche, non fornisce intrinsecamente un meccanismo per determinare la lunghezza minima di compressione richiesta per la ricostruzione esatta di una specifica sequenza individuale.

Metodologia
Questo articolo introduce una nuova metrica di complessità descrittiva denominata Complessità Polare, definita come la minima Lunghezza di Compressione Polare (PCL) necessaria per garantire la ricostruzione esatta di una specifica sequenza binaria utilizzando la Decodifica a Cancellazione Successiva (SCD). La metodologia si fonda sul quadro di codifica polare ad Albero Bilanciato Binario (BBT), che generalizza le trasformate polari a lunghezze di blocco arbitrarie.

1. Definizione e Calcolo della Complessità Polare:

   • Gli autori definiscono la complessità polare $L^\star(\mathbf{s})$ di una sequenza $\mathbf{s}$ come la più piccola PCL $L$ tale che la sequenza possa essere perfettamente recuperata dalla sua rappresentazione compressa polare in una configurazione canonica (utilizzando il metodo Polarization-Weight per la selezione dei nodi congelati e un parametro SCD deterministico $\tau=0$).
   • Calcolo Esatto: Sfruttando la monotonia della recuperabilità (se una sequenza è recuperabile alla lunghezza $L$, è recuperabile a qualsiasi $L' > L$), l'articolo propone un algoritmo di ricerca per bisezione per calcolare $L^\star(\mathbf{s})$ in modo efficiente, riducendo il numero di tentativi di SCD da lineare a logaritmico rispetto alla lunghezza della sequenza.
   • Stima a Bassa Complessità: Per evitare ripetuti tentativi di decodifica, viene introdotta una complessità polare predetta. Questo metodo utilizza la SCD assistita da Genio (GA-SCD) per identificare un "insieme critico" di nodi foglia che sono localmente ambigui o soggetti a errori. La complessità predetta è determinata dalla priorità di selezione del nodo di priorità più alta in questo insieme critico, fornendo un limite superiore conservativo alla vera complessità polare.

2. Codifica Sorgente in Due Stadi Basata su Polarità:

   • Viene proposto un nuovo schema di codifica sorgente in cui ogni sequenza sorgente è codificata come una coppia: un'intestazione a lunghezza fissa contenente la rappresentazione binaria della sua complessità polare, seguita dalla sequenza compressa polare a lunghezza variabile.
   • Lo schema è rigorosamente senza perdita e privo di prefissi.
   • L'analisi teorica dimostra che per Sorgenti Senza Memoria Binaria (BMS) con lunghezze di blocco potenze di due, la lunghezza media di compressione normalizzata di questo schema converge asintoticamente all'entropia della sorgente, a condizione che la selezione dei nodi congelati e i parametri SCD siano ottimizzati per la distribuzione della sorgente.

3. Codifica Congiunta Sorgente-Canale (JSCC) Doppia Polare Adattiva:

   • Gli autori integrano la codifica sorgente proposta con la codifica canale polare per creare uno schema JSCC adattivo.
   • Meccanismo: Il codificatore e il decodificatore condividono un insieme finito predefinito di PCL candidate. Per una data sequenza sorgente, il codificatore seleziona la PCL candidata più piccola che sia maggiore o uguale alla complessità polare predetta della sequenza. Questa PCL selezionata determina l'allocazione dei nodi attivi e congelati nel codificatore di canale.
   • Decodifica: Il decodificatore esegue un test di ipotesi sull'insieme delle PCL candidate. Ricostruisce le sequenze sorgente candidate per ogni ipotesi e seleziona la stima finale basandosi sul criterio della Massima A Posteriori (MAP), utilizzando controlli CRC per filtrare i candidati non validi.
   • Ottimizzazione: La progettazione dell'insieme delle PCL candidate è formulata come un problema di ottimizzazione per minimizzare il Tasso di Errore del Frame (FER). Questo viene risolto in modo efficiente utilizzando la programmazione dinamica, bilanciando il compromesso tra prestazioni (maggiore granularità) e complessità (dimensione dell'insieme candidato).

Contributi Chiave

• Complessità Polare: L'introduzione di una nuova metrica di complessità descrittiva calcolabile basata sulla PCL minima per la ricostruzione esatta tramite SCD.
• Algoritmi Efficienti: Sviluppo di un algoritmo di ricerca per bisezione per il calcolo esatto e di un metodo di previsione basato su GA-SCD a bassa complessità per la stima della complessità polare.
• Codifica Sorgente in Due Stadi: Uno schema di codifica rigorosamente senza perdita e privo di prefissi che raggiunge l'entropia della sorgente asintoticamente senza richiedere conoscenze preliminari delle statistiche della sorgente per il funzionamento (sebbene le prove di raggiungimento dell'entropia assumano la conoscenza delle statistiche per la sintonizzazione dei parametri).
• JSCC Adattiva: Un quadro unificato JSCC doppio polare che adatta il tasso di codifica del canale alla comprimibilità delle singole realizzazioni della sorgente. Lo schema include un metodo basato sulla programmazione dinamica per ottimizzare l'insieme delle PCL candidate per i compromessi prestazioni-complessità.

Risultati

• Prestazioni di Codifica Sorgente: Le simulazioni dimostrano che lo schema in due stadi proposto raggiunge prestazioni di compressione paragonabili alla codifica enumerativa per brevi lunghezze di blocco ($K=64$) ma con una complessità computazionale significativamente inferiore ($O(K \log K)$ contro $O(K^2)$). Lo schema rimane robusto attraverso varie distribuzioni della sorgente e non richiede conoscenze statistiche preliminari.
• Stima della Complessità: Il metodo di ricerca per bisezione riduce significativamente il costo computazionale della determinazione della complessità polare rispetto alla ricerca sequenziale. La complessità polare predetta limita costantemente superiormente la vera complessità con un piccolo scarto, validando la sua utilità per la progettazione JSCC.
• Prestazioni JSCC: Nelle simulazioni JSCC doppia polare adattiva (per lunghezze di blocco $N=128$ e $N=1024$), lo schema proposto supera le baseline JSCC esistenti basate su codici polari (inclusi schemi double-CRC-polar e joint SCLD). Il Tasso di Errore del Frame (FER) diminuisce monotonicamente all'aumentare della cardinalità dell'insieme delle PCL candidate, avvicinandosi a un limite inferiore teorico dove la vera PCL è nota al decodificatore.

Significato
L'articolo afferma che, spostando l'attenzione dalle proprietà stocastiche della sorgente al comportamento di recupero delle sequenze individuali sotto codifica polare, fornisce una misura pratica e calcolabile della complessità descrittiva. Questa "complessità polare" abilita una nuova classe di schemi di codifica che sono rigorosamente senza perdita e adattivi. Lo schema proposto di JSCC doppia polare adattiva offre un compromesso flessibile tra prestazioni e complessità, dimostrando che l'adattamento della protezione del canale alla specifica comprimibilità delle singole realizzazioni della sorgente può produrre prestazioni di tasso di errore superiori rispetto agli approcci di codifica congiunta statici o non adattivi. Il lavoro colma il divario tra i concetti di complessità algoritmica e le tecniche di codifica pratiche che si avvicinano alla capacità.