Lezione 18Esercizi su codici e capacità

Appunti di riferimento: tlc_18 (soluzioni dei quattro esercizi della scheda "Channel coding").

Argomenti trattati

1. Cifra di controllo in base $10$: $11$ cifre per $10^{11}$ pacchi, $12$ con la cifra di parità modulo $10$ ($d_{min}=2$); l'esempio $12347891234\to6$.
2. Due codici $(4,2)$: costruzione delle parole, linearità ($\mu_1$ non lineare, $\mu_2$ lineare con matrice generatrice), probabilità di errore non rivelato contando le coppie a distanza minima ($2{,}24\cdot10^{-7}$ contro $9\cdot10^{-8}$).
3. Test del DNA: $16$ sospettati con $4$ provette come codice $(4,4)$; $18{,}6\,\%$ di accuse errate; con una provetta in più (parità, $2{,}1\,\%$ di errore non rivelato), con $3$ in più (Hamming $(7,4)$): rivelazione ($0{,}07\,\%$) contro correzione ($4{,}06\,\%$).
4. Capacità al crescere della banda: forma indeterminata e limite $\frac{M_{s_{rc}}}{N_0\ln2}$ (logaritmo in base $2$, quindi $\log(1+x)\sim x/\ln2$); andamento sublineare con saturazione.

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 →
• 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 →
• 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 →
• 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 →

Esercizi

• Esercizio - Codice di controllo per numeri di registro
• Esercizio - Codici (4,2) lineari o no e probabilità di errore non rivelato
• Esercizio - Test del DNA con 4, 5 e 7 provette
• Esercizio - Capacità al crescere della banda
• Esercizio - Entropia del bacio (teoria dell'informazione) — scheda correlata sull'entropia

Lezione precedente: Lezione 17 · Livello di collegamento, ARQ e accesso deterministico (TDMA e FDMA) · Lezione successiva: Lezione 19 · ALOHA, CSMA e persistenza