Introduzione ai codici LDPC e all'importazione di Distribuzioni di Laurea

I codici Parity-Check (LDPC) sono un punto cardine della correzione degli errori moderna, consentendo una trasmissione affidabile dei dati su canali rumorosi.

La performance di un codice LDPC è intrinsecamente legata alla sua distribuzione di grado, che definisce quante connessioni (edge) ogni nodo variabile (rappresentando bit) e ogni nodo di controllo (rappresentando vincoli di parità) possiede nel codice’ il grafico Tanner.

Comprensione dei codici e delle distribuzioni di laurea LDPC

La struttura del grafico del Tanner

Un codice LDPC è definito da una matrice di controllo di parità radi H, che può essere rappresentato come un grafo bipartito noto come un grafo Tanner. Il grafico è costituito da due set disgiunti di nodi: nodi variabili (uno per ogni bit di codice) e nodi di controllo (uno per ogni equazione di controllo di parità).

Il grado di un nodo è il numero di bordi che gli sono stati colpiti. La distribuzione di grado per nodi variabili, denotata da [λ(x)], e per nodi di controllo, denotati da ρ(x), sono solitamente espressi come polinomi:

  • & #955;(x) = ∑]]i] λ]i] xi-1, dove λ]
  • & n. 961;(x) = ∑]]j] ρ]j] xj-1, dove < 961;[FLT]

Questi polinomi soddisfano λ(1) = ρ(1) = 1 e sono definiti sulla prospettiva del bordo piuttosto che sulla prospettiva del nodo, che semplifica l'analisi dell'evoluzione della densità. Il tasso di progettazione del codice può essere calcolato come R = 1 – (∑ ρ]

Distribuzioni di laurea regolari vs. irregolare

I primi codici LDPC sono regolari: ogni nodo variabile ha lo stesso grado (ad esempio, 3) e ogni nodo di controllo ha lo stesso grado (ad esempio, 6). I codici regolari sono semplici da costruire ma spesso mostrano soglie suboptimali. I codici LDPC irregolari, introdotti da Luby, Mitzenmacher, Shokrollahi e Spielman alla fine degli anni '90, permettono di migliorare significativamente i gradi variabili e nodi di controllo.

Il ruolo dell'ottimizzazione della distribuzione di grado

L'obiettivo primario di ottimizzazione della distribuzione dei gradi è quello di massimizzare la soglia di decodifica, definita come il parametro più alto del canale (ad esempio, varianza del rumore & #963;2] per i canali AWGN, o la probabilità di crossover p per i canali simmetrici binari) a cui il decoder iterativo può ancora raggiungere probabilità di errore arbitrariamente bassa come la lunghezza del limite di blocco tende a infinity è la soglia fondamentale di ottimizzazione.

Oltre le soglie, la distribuzione dei gradi influenza anche altre metriche di prestazione:

  • Più piano:[ La regione ad alti rapporti segnale-rumore dove la probabilità di errore diminuisce lentamente a causa di piccoli set di trapping o set assorbenti.
  • Velocità di convergenza:[] Il numero di iterazioni di decodifica necessarie per raggiungere una corretta parola di codice. Le distribuzioni che forniscono messaggi più affidabili all'inizio possono ridurre la latenza.
  • Ddistanza minima:[] Il peso più piccolo di un codice non zero. Mentre i codici LDPC hanno in genere distanze minime relativamente piccole, la distribuzione dei gradi influisce sul tasso di crescita della distanza minima con lunghezza del blocco.
  • Complessità:[ I nodi di alto grado richiedono più calcoli per iterazione; l'ottimizzazione deve bilanciare il throughput e il consumo energetico.

Tecniche di ottimizzazione chiave

Densità Evoluzione

L'evoluzione della densità, pionieristica di Richardson e Urbanke, è lo strumento analitico più potente per prevedere le prestazioni di LDPC in codice di decodifica di propagazione delle convinzioni.

Analisi della tabella EXIT

I grafici Extrinsic Information Transfer (EXIT) introdotti da dieci Brink, forniscono un metodo grafico per visualizzare lo scambio di informazioni tra decodificatori a nodo variabile (VND) e controllare decodificatori a nodo (CND).

Algoritmi Genetici e Ricerca Evolutiva

Poiché lo spazio delle possibili distribuzioni di grado è di alta dimensione e non convessa, i metodi di ottimizzazione euristica come algoritmi genetici (GA) sono spesso impiegati. Una popolazione di distribuzioni di grado candidato è evoluta attraverso la selezione, crossover e mutazione, con il fitness valutato attraverso l'evoluzione della densità o l'analisi di grafico EXIT.

Metodi di programmazione lineari

Secondo l'ipotesi di un'approssimazione gaussiana per l'evoluzione della densità, il problema di ottimizzazione può essere trasformato in un programma lineare. Questo approccio sfrutta la convessità di certi vincoli (ad esempio, la condizione di stabilità) per trovare la distribuzione che massimizza la soglia per un dato tasso. La programmazione lineare è efficiente e garantisce l'ottimalità globale all'interno del ravvicinamento, ma la sua accuratezza dipende dalla validità del rumore gaus, che degrada a bassi tassi o canali.

ottimizzazione alternativa e regole euriche

Alcune opere hanno proposto alternarsi tra l'ottimizzazione delle distribuzioni variabili e dei nodi di controllo, tenendo l'altro fisso. Semplicemente regole euriste, come la concentrazione dei gradi di nodo di controllo a un unico valore o l'utilizzo di un & #8220; il controllo-regolare & #8221; il design, spesso produce buoni risultati. La combinazione di vincoli analitici (ad esempio, condizione di stabilità, vincolo) con la ricerca numerica rimane un approccio pratico comune.

Impatto su Sostegni e Prestazioni

Avvicinarsi al limite di Shannon

Uno dei risultati più sorprendenti dell'ottimizzazione della distribuzione dei gradi è la capacità di avvicinarsi arbitrariamente alla capacità di Shannon. Ad esempio, i codici LDPC irregolari con distribuzioni ottimizzate sono stati mostrati di operare entro 0,045 dB del limite di capacità per il canale di cancellazione binario (BEC). Per il canale AWGN, le soglie entro 0,1 dB di capacità sono regolarmente riportate per lunghezze di blocco moderate.

Saturazione di soglia con codici LDPC accoppiati Spazialmente

Un affascinante sviluppo recente è il fenomeno di ]saturazione di soglia in accoppiato spaziale (SC) codici LDP ShannonC. Con l'accoppiamento di una catena di LDPC ensembles, la soglia BP del codice SC può essere mostrata per avvicinare la soglia massima di accoppiamento a posteriori (MAP) dell'ensemble sottostante, che è spesso molto più alta.

Riduzione del pavimento di errore

Mentre i piani alti sono essenziali per il funzionamento nella regione cascata (moderate SNR), molte applicazioni (ad esempio, lo storage ottico, le comunicazioni a profondità) richiedono anche piani di errore estremamente bassi, spesso sotto 10-15] bit errore tasso.

Velocità di convergenza e latenza

Nelle applicazioni in tempo reale, come lo streaming o il controllo video, il numero di iterazioni di decodifica è fondamentale. Le distribuzioni di grado ottimizzate che rendono più rapida la convergenza possono ridurre la la latenza media di decodifica. Ad esempio, le distribuzioni con una frazione più elevata di nodi variabili ad alto grado tendono a convergere più velocemente perché ricevono informazioni estrinseche più diverse presto.

Applicazioni pratiche e direzioni future

5G NR e Oltre

Lo standard 5G New Radio utilizza due codici LDPC a base di grafo con distribuzioni predeterminate su misura per diversi regimi di lunghezza del blocco e di tasso di codice. I grafici base sono stati selezionati dopo una vasta ottimizzazione della soglia di equilibrio, del piano di errore e della complessità dell'implementazione.

Comunicazioni satellitari e Deep-Space

Nei collegamenti satellitari dove il rapporto segnale-rumore è spesso molto basso, i codici LDPC ottimizzati con distribuzioni di grado a bassa velocità (ad esempio, tasso 1/3 o 1/4) sono utilizzati. Il CCSDS (Comitato consultivo per i sistemi di dati spaziali) ha standardizzato i codici LDPC a bassa capacità per la telemetria e il telecomando.

Sistemi di comunicazione ottici

Tuttavia, i canali ottici hanno spesso vincoli di quantizzazione di soft-decision e distribuzioni di rumore asimmetriche. L'ottimizzazione delle distribuzioni di gradi per tali canali richiede la modifica del contesto di evoluzione della densità (ad esempio, utilizzando distribuzioni discrete o modelli di miscela Gaussiana).

Memoria flash NAND e storage dati

I codici LDPC con distribuzioni di grado ottimizzate sono ora standard in SSD di fascia alta (Solid-State Drives). Il canale è altamente asimmetrico con un quantizzatore di soft-output; l'ottimizzazione della distribuzione dei gradi deve tenere conto della varianza non uniforme tra i livelli di memoria.

Codici LDPC quantistici

I codici Quantum LDPC (QLDPC) utilizzano generatori di stabilizzanti radi e richiedono distribuzioni di grado che soddisfano le relazioni di commutazione degli operatori Pauli. L'ottimizzazione delle distribuzioni di grado per i codici QLDPC è nella sua infanzia, ma i risultati iniziali mostrano che le buone distribuzioni LDPC classiche possono essere adattate all'impostazione quantistica, potenzialmente portando a un canale di evoluzione difetto-to.

Ottimizzazione adattiva e azionata da macchine

Tuttavia, con l'aumento di apprendimento profondo, i ricercatori hanno iniziato a utilizzare reti neurali per imparare le distribuzioni di grado che massimizzano il throughput o minimizzano la latenza sotto vincoli pratici di decoder (ad esempio, aritmetici a punto fisso, canali di iterazione limitati).

Conclusioni

L'ottimizzazione della distribuzione dei gradi non è solo un esercizio accademico; è la chiave per sbloccare il pieno potenziale dei codici LDPC attraverso un ampio spettro di tecnologie di comunicazione e storage. Selezionando attentamente i collegamenti dei bordi tra nodi variabili e di controllo, gli ingegneri possono spingere le soglie del codice arbitrariamente vicino al limite di Shannon, ridurre i livelli di errore a livelli trascurabili, e personalizzare il comportamento di convergenza a vincoli di latenza e complessità specifici delle applicazioni.

Prima lettura