Codici a parità di controllo a bassa densità (LDPC)
- Introdotto da
- Robert Gallager
- Anno
- 1962
- Tipo
- linear error-correcting code
- Famiglia
- Coding theory
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
I codici LDPC, inventati da Robert Gallager nel 1962 e riscoperti negli anni '90 da MacKay, sono codici lineari correttori di errori definiti da matrici di parità sparse.
Raggiungono prestazioni entro 0,4 dB dal limite di Shannon con decodifica iterativa a propagazione di credenza e sono diventati lo standard per le moderne comunicazioni wireless (WiFi-6, 5G NR, Digital Video Broadcasting). A differenza dei codici turbo, i codici LDPC hanno una struttura più elegante dal punto di vista della teoria dei grafi e un'analisi teorica più matura.
L’intuizione alla base del metodo
I codici lineari standard utilizzano matrici di parità dense, rendendo la decodifica computazionalmente intensiva. I codici LDPC invertono questo approccio: la matrice di parità è sparsa (la maggior parte delle voci sono zero), quindi ogni controllo di parità coinvolge solo una manciata di bit. Al ricevitore, viene costruito un grafo bipartito in cui i nodi variabili rappresentano i bit trasmessi e i nodi di controllo rappresentano i vincoli di parità. La decodifica diventa un passaggio iterativo di messaggi su questo grafo: ogni nodo variabile raccoglie informazioni dai suoi vicini, aggiorna la sua credenza sul valore del bit e invia stime raffinate indietro. La sparsità garantisce una convergenza rapida e prestazioni quasi-Shannon.
Storia
Gallager inventò i codici LDPC nel 1962, ma la teoria rimase indietro rispetto all'implementazione pratica. Nel 1995, MacKay li riscoprì e ne dimostrò le prestazioni quasi-Shannon tramite simulazioni. Ricerche estese negli anni 2000 svilupparono algoritmi efficienti di codifica, decodifica e costruzione di grafi. I codici LDPC sono stati adottati in WiFi-6 (802.11ax, 2021) e nello standard 5G NR (2018). Sono diventati più diffusi dei codici turbo nei nuovi sistemi grazie a prestazioni migliori e a una struttura più pulita.
Quando usarlo
I codici LDPC sono preferiti ai codici turbo nei sistemi moderni per prestazioni migliori e architettura più semplice. Utilizzare LDPC per ampi intervalli di SNR (nessun cliff di soglia); funzionano bene da SNR bassi ad alti. LDPC è lo standard per WiFi-6, comunicazioni satellitari e 5G NR. Evitare LDPC solo se la compatibilità legacy richiede codici turbo. LDPC è adatto anche per pacchetti molto corti (>30 bit) poiché la struttura del codice è separabile.
Limiti e considerazioni
- La costruzione del grafo e l'archiviazione della matrice diventano complesse per codici molto lunghi (>10k bit)
- Le prestazioni sono sensibili a strutture del grafo su piccola scala (girth, insiemi assorbenti); richiede un'attenta progettazione
- La propagazione di credenza assume un grafo con anelli (loopy), ma i grafi hanno cicli; la convergenza alla soluzione ottimale non è garantita
- La latenza di decodifica (iterazioni) cresce logaritmicamente con l'SNR; non è a latenza zero come alcuni codici classici
- La quantizzazione dei messaggi (in hardware a punto fisso) influisce sulle prestazioni; è necessaria un'attenta allocazione dei bit
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Prestazioni entro 0,4 dB dal limite di Shannon (leggermente migliori dei codici turbo)
- Struttura più semplice dal punto di vista della teoria dei grafi; analisi teorica più pulita rispetto ai codici turbo
- La decodifica iterativa evita comportamenti di soglia a cliff (a differenza dei turbo)
- Progettazione flessibile del codice tramite costruzione del grafo; facile da adattare ad applicazioni specifiche
- Hardware di decodifica parallela efficiente; il passaggio di messaggi si adatta all'implementazione VLSI/GPU
- Funziona bene sia per parole in codice lunghe che moderatamente corte
Applicazioni
- WiFi-6 (802.11ax): reti locali wireless ad alta velocità di trasmissione dati con LDPC che forniscono una consegna dati affidabile
- 5G NR: codifica di canale sia per canali dati che di controllo, sostituendo i codici turbo del 4G
- Comunicazioni satellitari: trasmissione video digitale (DVB-S2) e missioni nello spazio profondo che utilizzano LDPC a parola in codice lunga
- Comunicazioni su linea elettrica (PLC): trasmissione dati robusta su reti elettriche rumorose
- Sistemi di memoria Flash: correzione degli errori per lo storage NAND flash senza usura dovuta a frequenti aggiornamenti
Come funziona
Come funziona
I bit di informazione vengono codificati utilizzando una matrice di parità sparsa H; i bit codificati sono la soluzione di H*c = 0 (mod 2), dove c è la parola in codice.
La matrice di parità H è strutturata per essere sparsa (ad esempio, ogni riga/colonna ha un peso costante basso di 3-5). Questa struttura viene sfruttata per una codifica efficiente.
I bit codificati vengono trasmessi attraverso un canale rumoroso; i bit ricevuti sono valori morbidi (rapporti di verosimiglianza o rapporti di log-verosimiglianza).
Viene costruito un grafo bipartito: nodi sinistri = nodi variabili (bit), nodi destri = nodi di controllo (equazioni di parità). Gli spigoli collegano le variabili ai controlli in cui appaiono.
Propagazione iterativa di credenza: i nodi variabili aggregano messaggi dai nodi di controllo, aggiornano le stime dei bit e inviano messaggi raffinati indietro. Dopo le iterazioni, vengono prese decisioni dure; se i controlli di parità sono soddisfatti, la decodifica ha successo.
Errori comuni
- Utilizzo di un grafo sparso mal progettato con cicli corti; i cicli corti causano oscillazioni nella propagazione di credenza
- Iterazioni eccessive oltre la convergenza; iterazioni non necessarie sprecano energia senza miglioramenti
- Assunzione che la decodifica min-sum sia valida quanto la sum-product; le approssimazioni comportano perdite di prestazioni, specialmente a basso SNR
- Trascurare gli effetti di lunghezza finita; i grafi progettati per l'analisi asintotica possono sottoperformare su pacchetti corti
- Non tenere conto della quantizzazione nell'implementazione hardware; la simulazione in virgola mobile differisce dalla realtà a punto fisso
Domande frequenti
Cosa rende la decodifica LDPC così efficiente rispetto ai codici lineari generali?
La sparsità della matrice di parità implica che ogni bit partecipa solo a pochi controlli di parità. In decodifica, il passaggio di messaggi sul grafo bipartito è lineare nel numero di spigoli, non nella lunghezza del codice. Per codici densi, la decodifica richiederebbe l'inversione di matrici, che è cubica nella lunghezza del codice. La sparsità rende la decodifica quasi-lineare e pratica per codici lunghi.
Cos'è un insieme assorbente e perché è importante?
Un insieme assorbente è un piccolo sottoinsieme del grafo che può intrappolare la decodifica a propagazione di credenza, impedendo la convergenza alla soluzione corretta. Sono una fonte primaria di errore (la diminuzione non esponenziale del BER a basso SNR). I progettisti di codici evitano insiemi assorbenti corti attraverso un'attenta costruzione del grafo; strumenti di analisi (ad esempio, analisi degli insiemi di arresto) identificano strutture problematiche.
Come si confrontano gli LDPC con i codici polari?
Entrambi raggiungono prestazioni quasi-Shannon. I codici polari hanno una struttura ricorsiva e un'ottimalità dimostrabile sotto decodifica a cancellazione successiva a lunghezza di codice infinita. I codici LDPC sono più flessibili e hanno empiricamente prestazioni migliori a lunghezza finita. Il 5G NR utilizza codici polari per i canali di controllo (pacchetti corti) e LDPC per i canali dati (pacchetti lunghi), sfruttando i punti di forza di ciascun codice.
Perché il girth del grafo è importante nei codici LDPC?
Il girth è la lunghezza del ciclo più corto nel grafo bipartito. Cicli corti (girth < 6) fanno sì che la propagazione di credenza utilizzi informazioni correlate (i messaggi ritornano indietro), degradando le prestazioni. I codici ad alto girth (girth ≥ 6) rompono meglio le correlazioni. I codici sono spesso progettati per massimizzare il girth soggetto a vincoli di sparsità.
Metodi correlati
Fonti
Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
Apri il riferimento DOICopiato.Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.
Apri il riferimento DOICopiato.