Codici a blocco - distanza minima, rivelazione e correzione

Questa nota apre il capitolo del controllo d'errore. Fino a qui, con la Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →, si è tolta ridondanza alla sorgente per mandare meno dati; adesso si fa il contrario, ma con uno scopo preciso: aggiungere ridondanza scelta ad arte per proteggere la trasmissione dagli errori introdotti dal canale (il canale è stato "domato" nei capitoli sul livello fisico: Probabilità d'errore e funzione QPer due segnali di energie $E_1,E_2$ con coefficiente di correlazione $\rho=\frac{\langle s_1,s_2\rangle}{\sqrt{E_1E_2}}$ la distanza è $d_{12}=\sqrt{E_1+E_2-2\rho\sqrt{E_1E_2}}$ e, con rumore AWGN, simboli equiprobabili e criterio MD, $P[E]=Q\left(\frac{d_{12}}{2\sigma_I}\right)=Q\left(\sqrt{\frac{E_s(1-\rho)}{N_0}}\right)$ con $\sigma_I^2=\frac{N_0}2$ e $Q$ la coda della gaussiana. Il caso antipodale ($\rho=-1$) dà $Q\left(\sqrt{\frac{2E_s}{N_0}}\right)$, l'ortogonale ($\rho=0$) $Q\left(\sqrt{\frac{E_s}{N_0}}\right)$: 3 dB peggio. Con $M>2$ segnali si usano limiti: $\frac{N^*}M Q\left(\frac{d_{min}}{2\sigma_I}\right)\le P[E]\le(M-1)Q\left(\frac{d_{min}}{2\sigma_I}\right)$ (union bound); la probabilità dipende solo da $\frac{E_s}{N_0}$, cioè dall'SNR.Probabilità d'errore e funzione Q →, Link budgetIl sistema di trasmissione si modella con un canale che attenua ($a_{ch}$) e filtra il segnale, un rumore additivo bianco gaussiano (AWGN) che si somma dopo il canale, e un ricevitore con cifra di rumore $F_{rc}$. Il link budget è il bilancio che dà l'SNR in ricezione, $\text{SNR}=\frac{P_{tx}}{a_{ch},kT_0F_{rc},B}=\frac{M_{tx}}{a_{ch}N_0B}$, che deve superare una soglia; in dB (banda stretta) $\text{SNR}{dB}=(P{tx}){dBm}+114-(a{ch}){dB}-(F{rc}){dB}-10\log{10}B_{MHz}$. Lo si usa per ricavare la potenza minima, la banda massima o la distanza massima di un collegamento.Link budget →, 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 →). Il corso usa l'analogia del tubo: la sorgente è un fluido comprimibile, il canale un tubo con perdite; la ridondanza è come la pluriball con cui si imballa il fluido.

Vedi anche la versione per Ing. Elettronica: Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →.

Perché la ridondanza aiuta

Una frase in italiano con qualche lettera sbagliata si capisce lo stesso: la lingua è ridondante (non tutte le sequenze di lettere sono parole). Qui la ridondanza naturale è già presente; nei sistemi reali invece la si aggiunge artificialmente, dopo aver tolto con la codifica di sorgente quella naturale. L'esempio suggerisce due modi di sfruttarla:

• rivelazione d'errore (error detection): ci si accorge che c'è un errore;
• correzione d'errore (error correction): si cerca di capire anche quale era il messaggio giusto.

Schema generale e codici a blocco

Definizione (codice a blocco binario $(n,k)$). Una sequenza di $k$ bit di informazione $\mathbf b=(b_1,\dots,b_k)\in\mathcal A^k$ (parola di informazione, $\mathcal A=\mathbb Z_2=\{0,1\}$), che sono $2^k$ possibili, viene trasformata dalla mappa di codifica $\mu_C$ in una parola di codice (codeword) $\mathbf c=\mu_C(\mathbf b)=(c_1,\dots,c_n)\in\mathcal A^n$ di $n>k$ bit. Le parole di codice sono ancora $2^k$ ma stanno in uno spazio più grande, di $2^n$ elementi: l'insieme $\mathcal C=\mu_C(\mathcal A^k)\subset\mathcal A^n$ è il codice. Si chiama tasso di codifica (coding rate) il rapporto $k/n<1$.

Esempio. Il codice a ripetizione con $k=1$, $n=3$ ha $2^1=2$ parole di codice, $\mathcal C=\{000,111\}$, dentro uno spazio di $2^3=8$ sequenze: le altre sei ($001,010,\dots$) non sono parole di codice; sono quelle che si ricevono quando il canale sbaglia. Il tasso è $1/3$.

Il percorso completo è: trasmetto $\mathbf c$; ricevo $\tilde{\mathbf c}$ (che può non essere una parola di codice); decido una stima $\hat{\mathbf c}\in\mathcal C$; ricavo $\hat{\mathbf b}=\mu_C^{-1}(\hat{\mathbf c})$. In pratica la decisione su $\hat{\mathbf c}$ e la decodifica in $\hat{\mathbf b}$ si fanno insieme. (Il corso scrive vettori e simboli senza freccia per non appesantire; li si distingue dall'indice: $\mathbf c=(c_1\ c_2\ \dots\ c_n)$.)

Si assume che il canale (modulatore, canale fisico, demodulatore) si riassuma in un canale binario simmetrico senza memoria (BSC: ogni bit si inverte con probabilità $P_{bit}$, indipendentemente dagli altri). Allora, senza e con codifica: $$P[\mathbf b=\hat{\mathbf b}]=(1-P_{bit})^k\ \ (\text{senza codice}),\qquad P[\mathbf c=\tilde{\mathbf c}]=(1-P_{bit})^n\ \ (\text{con codice, nessun bit sbagliato}).$$ Esempio. Con $P_{bit}=10^{-2}$: $k=4$ bit non codificati arrivano tutti giusti con probabilità $0{,}99^4=0{,}9606$; la parola di $n=7$ bit di un codice $(7,4)$ arriva senza errori con $0{,}99^7=0{,}9321$. Più bit si mandano, più occasioni di sbagliare: la codifica funziona solo se il suo sistema di recupero compensa questa perdita (vedi il confronto in fondo).

Conversioni di velocità

La sorgente produce un bit ogni $T_b$ (velocità $R_b=1/T_b$); dopo il codificatore escono bit ogni $T_c$ (velocità $R_c=1/T_c$). Per ogni $k$ bit informativi ne escono $n$ codificati nello stesso tempo $kT_b=nT_c$: $$R_c=R_b\,\frac nk,\qquad T_c=T_b\,\frac kn.$$ Viceversa, la velocità informativa di un canale che trasporta $R_c$ bit codificati al secondo è $R_c\cdot\frac kn=R_b$: la velocità sul canale moltiplicata per il tasso di codifica. Nel tempo di simbolo $T$ della modulazione digitale prima si trasmettevano $\log_2M$ bit (Modulazioni PAM, PSK, QAM e FSKLe modulazioni pratiche usano un solo impulso base $h(t)$ (energia $E_h$) e coefficienti scelti in un insieme regolare. PAM: $s_n=\alpha_nh(t)$, $\alpha_n\in{-M+1,\dots,M-1}$, punti su una retta, $d_{min}=2\sqrt{E_h}$, $E_s=\frac{M^2-1}3E_h$, $P[E]=2\left(1-\frac1M\right)Q\left(\sqrt{\frac{6E_s}{(M^2-1)N_0}}\right)$. QAM: coefficienti complessi su due portanti in quadratura, base di dimensione 2, per $M=L^2$ $E_s=\frac{M-1}3E_h$ e $P[E]\approx4\left(1-\frac1{\sqrt M}\right)Q\left(\sqrt{\frac{3E_s}{(M-1)N_0}}\right)$. PSK: ampiezza costante, fasi $\theta_n=\frac{(2n-1)\pi}M$, punti su una circonferenza, $E_s=\frac{E_h}2$, $P[E]\approx2Q\left(\sqrt{\frac{2E_s}{N_0}}\sin\frac\pi M\right)$. FSK: due sinusoidi a frequenze diverse, $\rho\approx\operatorname{sinc}(4f_dT)$. Con la codifica di Gray $P_{bit}\approx\frac{P[E]}{\log_2M}$.Modulazioni PAM, PSK, QAM e FSK →), che ora diventano $\log_2M$ bit codificati (ne servono $n/k$ volte di più per la stessa informazione). Lo stesso vale per l'energia: l'energia per simbolo $E_s$ resta quella, ma

• se $E_b$ è l'energia per ogni bit trasmesso (codificato) allora $E_b=\dfrac kn\dfrac{E_s}{\log_2M}$: scende;
• se $E_b$ è l'energia per bit di informazione e $E_s$ resta costante, $E_b=\dfrac nk\dfrac{E_s}{\log_2M}$: sale.

Non esiste una formula universale: bisogna dire a quale bit ci si riferisce. (La scelta si usa nel confronto delle prestazioni: Probabilità d'errore e funzione QPer due segnali di energie $E_1,E_2$ con coefficiente di correlazione $\rho=\frac{\langle s_1,s_2\rangle}{\sqrt{E_1E_2}}$ la distanza è $d_{12}=\sqrt{E_1+E_2-2\rho\sqrt{E_1E_2}}$ e, con rumore AWGN, simboli equiprobabili e criterio MD, $P[E]=Q\left(\frac{d_{12}}{2\sigma_I}\right)=Q\left(\sqrt{\frac{E_s(1-\rho)}{N_0}}\right)$ con $\sigma_I^2=\frac{N_0}2$ e $Q$ la coda della gaussiana. Il caso antipodale ($\rho=-1$) dà $Q\left(\sqrt{\frac{2E_s}{N_0}}\right)$, l'ortogonale ($\rho=0$) $Q\left(\sqrt{\frac{E_s}{N_0}}\right)$: 3 dB peggio. Con $M>2$ segnali si usano limiti: $\frac{N^*}M Q\left(\frac{d_{min}}{2\sigma_I}\right)\le P[E]\le(M-1)Q\left(\frac{d_{min}}{2\sigma_I}\right)$ (union bound); la probabilità dipende solo da $\frac{E_s}{N_0}$, cioè dall'SNR.Probabilità d'errore e funzione Q →.)

Esempio. $R_b=1$ Mbit/s con codice $(7,4)$: i bit informativi sono $4$ ogni $7$ trasmessi, quindi $R_c=\frac74\cdot 1=1{,}75$ Mbit/s e $T_c=\frac47T_b=0{,}571\ \mu$s (contro $T_b=1\ \mu$s).

Che cosa può succedere alla ricezione

L'errore non rivelato non si può evitare: è il caso sfortunato in cui il canale trasforma una parola di codice in un'altra parola di codice. Si cerca solo che accada con probabilità $P_{undetected}$ molto piccola, e questo succede quando le parole di codice sono ben distanziate. Si distinguono due probabilità d'errore residue:

• $P[\mathbf c\neq\hat{\mathbf c}]$: errore sulla parola di codice (o di informazione, $P[\mathbf b\neq\hat{\mathbf b}]$);
• $P[b_\ell\neq\hat b_\ell]$: errore residuo sui singoli bit di informazione, da non confondere con $P_{bit}$ (la probabilità del canale prima della codifica).

A livello più alto queste due strade diventano due tecniche:

I sistemi reali (anche il 5G) usano l'approccio ibrido Hybrid ARQ: pochi errori $\to$ FEC, tanti $\to$ ARQ. Le prestazioni dell'ARQ sono in 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 →.

Codici sistematici

Definizione (codice sistematico). Un codice è sistematico se la parola di informazione $\mathbf b$ compare come prefisso della parola di codice: $\mathbf c=(\,\mathbf b\mid c_{k+1}\dots c_n\,)$. Gli altri $n-k$ bit sono i bit di ridondanza (o di parità).

È utile per le applicazioni "a lettura lenta" (si ha subito l'informazione mentre si aspetta il controllo) e per un utente umano che guarda la parola; con i calcolatori di oggi è un dettaglio.

Distanza di Hamming e distanza minima

L'insieme $\mathcal A^n$ è uno spazio discreto: sequenze di $n$ bit come $001001$ o $001011$, e niente "di intermedio". Per visualizzarlo il corso usa lo stagno delle rane: le sequenze sono sassi, le parole di codice sono sassi colorati; ogni salto di rana inverte un bit (da $0$ a $1$ o viceversa), e due sassi adiacenti hanno distanza $1$.

Definizione (distanza di Hamming). $d_H(\mathbf x,\mathbf y)$ è il numero di posizioni in cui $\mathbf x$ e $\mathbf y$ differiscono, cioè il numero minimo di salti per passare dall'una all'altra. È una vera distanza (simmetrica, $\ge0$, nulla solo se uguali, vale la disuguaglianza triangolare). Esempio. $d_H(001001,001011)=1$; $d_H(1011,0110)=3$ (differiscono nei bit $1,2,4$).

Definizione (distanza minima di un codice). $$d_{min}=\min_{\substack{\boldsymbol\gamma_1,\boldsymbol\gamma_2\in\mathcal C\\ \boldsymbol\gamma_1\ne\boldsymbol\gamma_2}}d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2).$$ È il minimo numero di salti per andare da un sasso colorato a un altro sasso colorato.

Esempio. Ripetizione $m=3$: $d_H(000,111)=3=d_{min}$. Codice $\{00,11\}$ ($m=2$): $d_{min}=2$.

Teorema (potere di rivelazione). Un codice a blocco con distanza minima $d_{min}$ usato per rivelare garantisce la rivelazione di ogni situazione con al più $d_{min}-1$ bit sbagliati, cioè con $\#errori<d_{min}$. Dimostrazione. Si parte da un sasso colorato (la parola trasmessa) e si fanno meno di $d_{min}$ salti (gli errori): non si può arrivare a un altro sasso colorato, perché ogni altro sasso colorato dista almeno $d_{min}$. Quindi la parola ricevuta non è di codice: nessun errore non rivelato è possibile.

Esempio. Un codice con $d_{min}=3$ rivela ogni pattern di $1$ o $2$ errori; con $3$ errori potrebbe finire su un'altra parola di codice (a distanza $3$), e l'errore non verrebbe visto.

Probabilità di avere $d$ errori

Se si trasmette $\mathbf c$ su un BSC senza memoria, la probabilità di ricevere una specifica parola $\tilde{\mathbf c}$ a distanza $d_H(\tilde{\mathbf c},\mathbf c)=d$ è $$P[\mathbf c\to\tilde{\mathbf c}]=P_{bit}^{\,d}(1-P_{bit})^{n-d}$$ ($d$ bit sbagliati, ciascuno con probabilità $P_{bit}$, e $n-d$ giusti: il prodotto va bene perché i bit sono indipendenti, e non conta l'ordine). La probabilità che ci siano esattamente $d$ errori in una posizione qualsiasi è la binomiale (Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →, Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →): $$P[d\text{ errori}]=\binom nd\,P_{bit}^{\,d}(1-P_{bit})^{n-d}.$$ Esempio. $n=7$, $P_{bit}=10^{-2}$: $P[0]=0{,}9321$, $P[1]=7\cdot10^{-2}\cdot0{,}99^6=0{,}0659$, $P[2]=21\cdot10^{-4}\cdot0{,}99^5=1{,}997\cdot10^{-3}$, $P[3]=35\cdot10^{-6}\cdot0{,}99^4=3{,}36\cdot10^{-5}$: ogni errore in più costa circa un fattore $10^{-2}\cdot\frac{n-d}{d+1}$.

Correzione d'errore: decisione ottima

Il problema è quello già visto nella Decisione ottima - criteri MAP e MLIl ricevitore osserva il vettore $\mathbf r$ e deve stimare il simbolo trasmesso $a_0$: lo spazio $\mathbb R^I$ si divide in $M$ regioni di decisione $\mathcal R_j$. La probabilità di decisione corretta è $P[C]=\sum_j\int_{\mathcal R_j}D_j(\boldsymbol\rho),d\boldsymbol\rho$ con $D_j=p_{\mathbf r|a_0}(\boldsymbol\rho|j),p_j$ e si massimizza assegnando ogni $\boldsymbol\rho$ alla regione con $D_j$ più alto: criterio MAP (massimo a posteriori, ottimo). Il criterio ML ($\arg\max_jp_{\mathbf r|a_0}(\boldsymbol\rho|j)$) ignora le probabilità a priori e coincide con MAP per simboli equiprobabili. Il criterio MD (minima distanza, $\arg\min\lVert\boldsymbol\rho-\mathbf s_j\rVert$) coincide con ML se il rumore è AWGN, quindi con simboli equiprobabili e AWGN è ottimo.Decisione ottima - criteri MAP e ML →: si è inviato $\mathbf c=\mu_C(\mathbf b)$, si è ricevuto $\tilde{\mathbf c}$, e bisogna decidere. Là si inviava $s$, si riceveva $r$ e si cercava $\hat a_0$. L'idea è la stessa: si partiziona l'insieme in cui può cadere $\tilde{\mathbf c}$ in regioni di decisione $\mathcal R_{\boldsymbol\beta}$, una per ogni parola di informazione $\boldsymbol\beta\in\mathcal A^k$: $$\bigcup_{\boldsymbol\beta\in\mathcal A^k}\mathcal R_{\boldsymbol\beta}=\mathcal A^n,\qquad\mathcal R_{\boldsymbol\beta_1}\cap\mathcal R_{\boldsymbol\beta_2}=\emptyset\ (\boldsymbol\beta_1\ne\boldsymbol\beta_2)$$ (se $\tilde{\mathbf c}\in\mathcal R_{\boldsymbol\beta}$ si decide $\hat{\mathbf b}=\boldsymbol\beta$). La bontà della decodifica dipende da come si disegnano queste regioni.

Ragionando in termini di errore sulla parola ($P[\mathbf b\ne\hat{\mathbf b}]$, da non confondere con la probabilità sul singolo bit) si vuole minimizzare $$P[\mathbf b\neq\hat{\mathbf b}]=1-P[\mathbf b=\hat{\mathbf b}]=1-\sum_{\boldsymbol\beta}P[\tilde{\mathbf c}\in\mathcal R_{\boldsymbol\beta}\mid\mathbf b=\boldsymbol\beta]\,p_{\boldsymbol\beta}=1-\sum_{\boldsymbol\beta}p_{\boldsymbol\beta}\sum_{\boldsymbol\xi\in\mathcal R_{\boldsymbol\beta}}p_{\tilde{\mathbf c}|\mathbf b}(\boldsymbol\xi\mid\boldsymbol\beta)$$ (probabilità totali: si somma sulle parole di informazione $\boldsymbol\beta$ pesate con la loro probabilità $p_{\boldsymbol\beta}$, e dentro la regione si sommano le probabilità dei vettori ricevuti). Per minimizzare l'errore ogni vettore $\boldsymbol\xi$ va assegnato alla regione per cui è massimo $p_{\boldsymbol\beta}\,p_{\tilde{\mathbf c}|\mathbf b}(\boldsymbol\xi|\boldsymbol\beta)$: è il criterio MAP (massima probabilità a posteriori), perché per Bayes (Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →) $$p_{\mathbf b|\tilde{\mathbf c}}(\boldsymbol\beta|\boldsymbol\xi)=\frac{p_{\tilde{\mathbf c}|\mathbf b}(\boldsymbol\xi|\boldsymbol\beta)\,p_{\boldsymbol\beta}}{p_{\tilde{\mathbf c}}(\boldsymbol\xi)},$$ e il denominatore non dipende da $\mathbf b$. Per parole di informazione equiprobabili (sempre il nostro caso) il fattore $p_{\boldsymbol\beta}$ è costante e si ottiene il criterio ML (massima verosimiglianza): si massimizza $p_{\tilde{\mathbf c}|\mathbf b}(\boldsymbol\xi|\boldsymbol\beta)$ (la likelihood).

Come in modulazione si vorrebbe poi passare al criterio a distanza minima (MD, qui a minima distanza di Hamming). Là con il rumore AWGN ML e MD coincidevano; qui gli insiemi sono discreti, quindi serve una condizione.

Teorema (condizione sufficiente per ML = MD). Su un BSC senza memoria con $P_{bit}<1/2$, la decisione ML coincide con quella a distanza minima di Hamming. Dimostrazione. Sia $d=d_H(\boldsymbol\gamma,\tilde{\mathbf c})$ con $\boldsymbol\gamma=\mu_C(\boldsymbol\beta)$. Allora $$p_{\tilde{\mathbf c}|\mathbf b}(\boldsymbol\xi|\boldsymbol\beta)=P_{bit}^{\,d}(1-P_{bit})^{n-d}=\Big(\frac{P_{bit}}{1-P_{bit}}\Big)^{d}(1-P_{bit})^{n}.$$ Il fattore $(1-P_{bit})^n$ è costante. Se $P_{bit}<\frac12$ allora $\frac{P_{bit}}{1-P_{bit}}<1$, e una potenza di un numero minore di $1$ è tanto più grande quanto più piccolo è l'esponente $d$. Massimizzare la likelihood equivale quindi a minimizzare $d$. $\square$

Osservazioni sul BSC. La condizione è in realtà più larga. Con $P_{bit}=1$ il canale sbaglia sempre, ma è soltanto un canale invertente: basta fare un NOT logico e lo si vede come privo di errori, quindi anche per $P_{bit}>\frac12$ è tutto equivalente (si inverte). Il caso davvero brutto è $P_{bit}=\frac12$, il canale inutile: i bit in uscita sono indipendenti ed equiprobabili e non hanno niente a che fare con quelli trasmessi (capacità nulla: 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 →).

Teorema (potere di correzione). Un codice con distanza minima $d_{min}$ usato con decodifica a distanza minima garantisce di correggere ogni caso con meno di $d_{min}/2$ bit sbagliati: la correzione è buona se $t<d_{min}/2$ errori, cioè $$t\le\frac{d_{min}-2}{2}\ (d_{min}\text{ pari}),\qquad t\le\frac{d_{min}-1}{2}\ (d_{min}\text{ dispari}).$$ Dimostrazione (per assurdo). Si invia $\boldsymbol\gamma_1$ e si riceve $\tilde{\mathbf c}$ con $d_H(\boldsymbol\gamma_1,\tilde{\mathbf c})=t<d_{min}/2$. Supponiamo che si decodifichi un'altra parola $\boldsymbol\gamma_2\in\mathcal C$, $\boldsymbol\gamma_2\neq\boldsymbol\gamma_1$. Poiché MD sceglie la parola più vicina, $d_H(\boldsymbol\gamma_2,\tilde{\mathbf c})\le d_H(\boldsymbol\gamma_1,\tilde{\mathbf c})=t<d_{min}/2$. Ma per la disuguaglianza triangolare $$d_H(\boldsymbol\gamma_2,\tilde{\mathbf c})\ \ge\ d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2)-d_H(\boldsymbol\gamma_1,\tilde{\mathbf c})\ >\ d_{min}-\frac{d_{min}}2=\frac{d_{min}}2,$$ contraddizione. $\square$

Rivelare o correggere: non insieme. Con distanza minima $d_{min}$ si rivelano fino a $d_{min}-1$ errori e se ne correggono fino a $\approx d_{min}/2$, ma non nello stesso momento: le regioni di decisione ($\mathcal R_1,\mathcal R_2,\dots$ intorno ai sassi colorati) toccano più o meno a metà strada tra due parole; se si decide di correggere, un pattern di molti errori può finire dentro la regione di un'altra parola e produrre una correzione sbagliata che non si vede.

Esempio. $d_{min}=3$: o si rivelano $2$ errori, o se ne corregge $1$. $d_{min}=4$: o si rivelano $3$ errori, o se ne corregge $1$ (la condizione $t<2$ dà $t=1$); in quest'ultimo caso si possono ancora rivelare, ma non correggere, i pattern con $2$ errori (a metà strada tra due parole di codice).

Esempi di codici

Codice a ripetizione. Blocco $(n,k)$ con $n=mk$: si ripete la parola di informazione $m$ volte, $\mathbf b\to\mathbf c=(\mathbf b\,|\,\mathbf b\,|\dots)$. È sistematico, $d_{min}=m$ (cambiando un solo bit di informazione cambiano $m$ bit). Con $k=1$, $m=2$: $\mathcal C=\{00,11\}$, rivela $1$ errore. Con $m=3$: $\mathcal C=\{000,111\}$, $d_{min}=3$, corregge $1$ errore; la decodifica a distanza minima è il voto a maggioranza ($010\to000$). Il prezzo è un tasso $1/3$.

Codice a bit di parità. Blocco $(k+1,k)$ sistematico: si aggiunge un solo bit $p=b_1\oplus b_2\oplus\dots\oplus b_k=\sum_jb_j\ (\mathrm{mod}\ 2)$, che vale $0$ se $\mathbf b$ ha un numero pari di uni e $1$ se dispari; dopo l'aggiunta il numero di uni è sempre pari. Si vede subito $d_{min}=2$: due parole di informazione che differiscono in un bit hanno parità opposta, quindi le parole di codice differiscono in $2$ bit. Rivela sempre $1$ errore, non ne corregge nessuno, e con due errori la rivelazione fallisce sempre (lo stesso vale per qualunque numero pari di errori).

Esempio. $\mathbf b=1011$ ha tre uni: $p=1$, $\mathbf c=10111$. Se arriva $10101$ (un bit sbagliato) il numero di uni è $3$, dispari: errore rivelato. Se ne sbagliano due ($10001$): uni $=2$, pari: errore non rivelato.

Parità a righe e colonne. Controlli di parità parziali aumentano $d_{min}$ e permettono la correzione. Il corso presenta un codice $(25,16)$: i $16$ bit sono disposti in un quadrato $4\times4$, si calcola un bit di parità per ogni riga ($c_{17}=b_1\oplus b_2\oplus b_3\oplus b_4,\ c_{18},c_{19},c_{20}$), uno per ogni colonna ($c_{21}=b_1\oplus b_5\oplus b_9\oplus b_{13},\dots,c_{24}$) e un'ultima parità $p$ di controllo ($c_{25}$, la parità dei bit di riga): $16+4+4+1=25$. Ha $d_{min}=4$ (verificato enumerando tutte le $2^{16}$ parole). Un errore singolo fa fallire una riga e una colonna: il loro incrocio individua il bit sbagliato e lo si corregge.

Codici nella vita reale. Numeri di carta di credito (l'ultima cifra è di controllo), ISBN-10 (ultima cifra modulo $11$, $0$–$9$ o X), codice fiscale (l'ultima lettera è un carattere di controllo), assegni, codici a barre. In tutti i casi le cifre di controllo sono ridondanza che permette di rivelare errori di trascrizione. Un caso svolto è nell'Esercizio - Codice di controllo per numeri di registro.

Il limite di Hamming

Si vorrebbe un tasso $k/n$ vicino a $1$ (poca ridondanza), ma la capacità di correzione lo limita.

Teorema (limite di Hamming). Se un codice a blocco $(n,k)$ garantisce di correggere fino a $t$ errori, allora $$\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr\quad\Longleftrightarrow\quad k\le n-\log_2\sum_{r=0}^t\binom nr.$$ Dimostrazione. Si ricorda che $\mathbf b\in\mathcal A^k$ ha $2^k$ valori, $\mathbf c\in\mathcal C\subseteq\mathcal A^n$ ha $2^k$ valori scelti in un insieme di $2^n$ elementi. Garantire la correzione di $t$ errori significa che se $d_H(\mathbf c,\tilde{\mathbf c})=r\le t$ allora $\tilde{\mathbf c}\in\mathcal R_{\mathbf b}$ con $\mathbf b=\mu_C^{-1}(\mathbf c)$. Quindi $\mathcal R_{\mathbf b}$ contiene almeno tutte le $n$-uple che differiscono da $\mathbf c$ in al più $t$ posizioni, che sono $\sum_{r=0}^t\binom nr$ (c'è $1$ parola con $0$ errori, $n$ con $1$ errore, $\binom n2$ con $2$, …): $$|\mathcal R_{\mathbf b}|\ \ge\ \sum_{r=0}^t\binom nr$$ (disuguaglianza e non uguaglianza: la regione può contenere altri elementi). La proprietà vale per ogni regione; sommando su tutte le $2^k$ parole di informazione $\mathbf b$, $$\sum_{\mathbf b}|\mathcal R_{\mathbf b}|\ \ge\ 2^k\sum_{r=0}^t\binom nr.$$ Ma le $\mathcal R_{\mathbf b}$ sono disgiunte e ricoprono tutto $\mathcal A^n$, quindi la somma vale $|\mathcal A^n|=2^n$. Allora $2^n\ge2^k\sum_{r=0}^t\binom nr$ e, prendendo $\log_2$, $n\ge k+\log_2\sum_{r=0}^t\binom nr$. $\square$

Esempio. Hamming $(7,4)$ con $t=1$: $\sum=\binom70+\binom71=8$, $2^4\cdot8=128=2^7$: uguaglianza, le regioni ricoprono lo spazio senza avanzi (codice perfetto, 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 →). Per un codice con $n=15$ e $t=1$: $k\le15-\log_2(16)=11$ (è l'Hamming $(15,11)$). Per $n=25$, $t=1$: $\sum=26$, $k\le25-\log_2 26=20{,}30$, quindi $k\le20$: il $(25,16)$ del corso, che corregge $1$ errore, ha tasso $0{,}64$ contro un massimo teorico $20/25=0{,}8$. Per $n=23$, $t=3$ il limite dà $k\le12$ (il codice di Golay $(23,12)$ lo raggiunge).

Prestazioni di un codice: stima delle probabilità residue

Dire "corregge fino a $t_C$ errori" è troppo vago per calcolare una probabilità, quindi si fanno ipotesi esplicite, che sono approssimazioni:

1. se ci sono $t_C+1$ errori la parola decodificata è sicuramente sbagliata (caso peggiore);
2. si ignorano i casi con $t_C+2,\ t_C+3,\dots$ errori perché improbabili (ottimistico).

Allora, per un BSC con probabilità $P_{bit}$ (prima della codifica) e $n$ bit per parola, $$P[\mathbf c\ne\hat{\mathbf c}]\ \simeq\ \binom n{t_C+1}P_{bit}^{\,t_C+1}(1-P_{bit})^{\,n-t_C-1}.$$ Ma per i bit di informazione si vuole $P[b_\ell\ne\hat b_\ell]$. Altre due ipotesi: 3) se la parola decodificata è sbagliata contiene esattamente $d_{min}$ bit errati (è finita su una parola di codice vicina); 4) i bit sbagliati si distribuiscono uniformemente sulla parola (tra informazione e ridondanza). Quindi una frazione $d_{min}/n$ di bit sbagliati: $$P[b_\ell\ne\hat b_\ell]\ \simeq\ \frac{d_{min}}n\binom n{t_C+1}P_{bit}^{\,t_C+1}(1-P_{bit})^{\,n-t_C-1}.$$

Esempio. Hamming $(7,4)$ ($d_{min}=3$, $t_C=1$) con $P_{bit}=10^{-2}$: $P[\mathbf c\neq\hat{\mathbf c}]\simeq\binom72(10^{-2})^2(0{,}99)^5=1{,}997\cdot10^{-3}$ e $P[b_\ell\ne\hat b_\ell]\simeq\frac37\cdot1{,}997\cdot10^{-3}=8{,}56\cdot10^{-4}$. Il valore esatto (enumerando tutti i $128$ pattern d'errore) è $P[\mathbf c\ne\hat{\mathbf c}]=2{,}031\cdot10^{-3}$ e $P[b_\ell\ne\hat b_\ell]=8{,}74\cdot10^{-4}$: la stima è buona al $2\,\%$. La codifica ha ridotto l'errore sul bit da $10^{-2}$ a circa $8{,}7\cdot10^{-4}$, un fattore $11$.

Il grafico confronta l'errore sul bit senza codice ($P_{bit}$) e con Hamming $(7,4)$ (stima $\frac37\binom72P^2(1-P)^5=9P^2(1-P)^5$): per $P_{bit}$ piccolo il guadagno è enorme perché la curva scende come $P^2$, mentre per $P_{bit}$ grande le due si avvicinano (ipotesi 2 non più vera).

Una nota importante sul confronto equo: l'$E_s$ per simbolo è fissato, quindi con la codifica il rapporto $E_b/N_0$ cambia secondo la convenzione scelta sopra, e $P_{bit}$ (la probabilità di errore sul bit del canale) peggiora un po' (si trasmettono più bit nella stessa energia). Il guadagno finale di codifica va valutato con lo stesso $E_b/N_0$ per bit di informazione.

Errori comuni

• Dire che il codice "corregge $d_{min}/2$ errori" senza il segno stretto: la condizione è $t<d_{min}/2$ (con $d_{min}=4$ si corregge $1$ errore, non $2$).
• Pensare di poter usare insieme tutto il potere di rivelazione e tutto quello di correzione.
• Confondere $P_{bit}$ del canale con la probabilità di errore sui bit dopo la decodifica, $P[b_\ell\neq\hat b_\ell]$, e con quella sulla parola $P[\mathbf c\ne\hat{\mathbf c}]$.
• Credere che l'errore non rivelato si possa eliminare: si può solo renderlo improbabile.

Collegamenti

Il caso dei codici lineari, con matrice generatrice e sindrome, è in 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 →; il codice di Hamming e il CRC in 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 →; i limiti teorici per la probabilità d'errore piccola a piacere in 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 - Codici (4,2) lineari o no e probabilità di errore non rivelato, Esercizio - Test del DNA con 4, 5 e 7 provette.