Lezione 15Codifica di canale, distanza minima e limite di Hamming

Appunti di riferimento: tlc_15 (slide TLC9). Controllo d'errore, capitolo 6.

Argomenti trattati

1. Dalla codifica di sorgente alla codifica di canale: si toglieva ridondanza, ora la si aggiunge per proteggere la trasmissione (analogia del tubo e della pluriball); rivelazione contro correzione d'errore.
2. Schema generale: parola di informazione $\mathbf b\in\mathbb Z_2^k$, parola di codice $\mathbf c\in\mathbb Z_2^n$, mappa $\mu_C$, ricevuto $\tilde{\mathbf c}$, stimato $\hat{\mathbf c}$; probabilità residue su parola e su bit; errore non rivelato.
3. ARQ, FEC e HARQ.
4. Codici a blocco $(n,k)$: tasso $k/n$, conversioni di velocità $R_c=R_b\,n/k$, energia per bit con e senza codifica; codici sistematici.
5. Distanza di Hamming e distanza minima (lo stagno delle rane); teorema sul potere di rivelazione ($d_{min}-1$ errori).
6. Decisione ottima sul BSC: regioni di decisione, MAP, ML, minima distanza; ML = MD se $P_{bit}<\frac12$; canale inutile.
7. Potere di correzione $t<d_{min}/2$ (dimostrazione per assurdo); rivelare e correggere non insieme.
8. Esempi: ripetizione, bit di parità, parità a righe e colonne $(25,16)$, cifre di controllo (carte, ISBN, codice fiscale).
9. Limite di Hamming con dimostrazione.
10. Inizio dei codici lineari: $\mathbb Z_2^n$ come spazio vettoriale, peso di Hamming, chiusura rispetto alla somma, $\mathbf 0\in\mathcal C$, $d_{min}$ come peso minimo.

Teoria

• 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 → — punti 1-9
• 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 → — punto 10 e la lezione seguente
• Tecniche ARQ e loro prestazioniARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore risponde a ogni pacchetto con ACK (corretto) o NACK (errato), e il trasmettitore ritrasmette. Con probabilità di pacchetto errato $p$, $t_{RTT}=t_P+t_A+2\tau_P$ e coda sempre piena, il throughput massimo (frazione di tempo d'aria) è: Stop-and-Wait $S=\frac{t_P(1-p)}{t_{RTT}}$; Go-Back-N con $N=t_{RTT}/t_P$ $S=\frac{1-p}{(N-1)p+1}$; Selective Repeat $S=1-p$. Il ritardo medio è $m_{delay}=t_P+\tau_P+\frac p{1-p}t_{RTT}$ (a coda vuota). Sono solo valori massimi: la coda ARQ è stabile solo se $\lambda$ è minore della velocità di servizio, $\lambda<1/m_y$; altrimenti il throughput è $\min(\lambda,\mu)$. L'efficienza (payload) è $\eta=S,L_D/L$.Tecniche ARQ e loro prestazioni → — ARQ e FEC a livello di collegamento

Esercizi

• Esercizio - Codice di controllo per numeri di registro — cifre di controllo, $d_{min}=2$
• Esercizio - Codici (4,2) lineari o no e probabilità di errore non rivelato

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