Lezione 16Codici lineari, sindrome, capacità di canale e teorema di Shannon

Appunti di riferimento: tlc_16.

Argomenti trattati

1. Rappresentazione matriciale di una codifica lineare: $\mathbf c=G\mathbf b$ con $G$ di tipo $n\times k$ (convenzione a colonna); matrice generatrice come base del codice; non unicità.
2. Codici sistematici: $G=\binom{I_k}{A}$; ripetizione e bit di parità come esempi; codice di Hamming $(7,4)$ con le sue $16$ parole e $d_{min}=3$.
3. Permutazioni elementari $H_{ij}$, $K_{ij}$: stesso codice (colonne) o codice equivalente (righe); ogni codice lineare ha un equivalente sistematico; limite di Singleton $d_{min}\le n-k+1$.
4. Matrice di controllo di parità $H$: $H\mathbf c=\mathbf0\iff\mathbf c\in\mathcal C$; $HG=O$ e $\mathrm{rank}\,H=n-k$; $H=[A\mid I_{n-k}]$; sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$; analogia della prova del nove.
5. Decodifica a sindrome: $2^{n-k}$ coset, coset leader, $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, tabella dei leader.
6. Prestazioni di un codice: energia per bit, $P[\mathbf c\ne\hat{\mathbf c}]$ e $P[b_\ell\ne\hat b_\ell]$ con le ipotesi del corso, confronto tra tassi e bit errati prima e dopo la codifica.
7. Informazione mutua e capacità: richiamo, velocità di informazione $R=F\,I_s$, capacità di Shannon, esempio del BSC, teorema di Shannon (parte diretta e inversa), analogia fluidica, accenni a LDPC e codici turbo.
8. Capacità del canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con la derivazione, commenti (logaritmo in base $2$).

Teoria

• Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome → — punti 1-5
• Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC → — l'Hamming $(7,4)$ in dettaglio e prestazioni; CRC
• Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione → — punto 6
• Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale → — punti 7-8

Esercizi

• Esercizio - Test del DNA con 4, 5 e 7 provette — codici e probabilità d'errore
• Esercizio - Capacità al crescere della banda

Lezione precedente: Lezione 15 · Codifica di canale, distanza minima e limite di Hamming · Lezione successiva: Lezione 17 · Livello di collegamento, ARQ e accesso deterministico (TDMA e FDMA)