Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione

A che cosa serve

Il canale numerico (Canale numerico, ISI e codifica di GrayNella catena bit $\to$ BMAP $\to$ modulatore $\to$ canale $\to$ proiezione $\to$ rivelatore $\to$ IMAP, un simbolo da $b=\log_2M$ bit dura $T=T_b\log_2M$. Per non avere interferenza intersimbolo (ISI) le forme d'onda devono essere ortogonali alle loro traslate di $kT$: $\langle\phi_i(t),\phi_j(t-kT)\rangle=0$ per $k\ne0$ (per esempio un impulso che dura al più $T$). Il canale numerico equivalente (bit in ingresso, bit decisi in uscita) è un canale binario simmetrico di probabilità $P_{bit}$; con la codifica di Gray simboli adiacenti differiscono in un solo bit e $P_{bit}\approx\frac{P[E]}{\log_2M}$.Canale numerico, ISI e codifica di Gray →) sbaglia ogni tanto un bit: con la modulazione si può scendere a $P_{bit}=10^{-3}$ o $10^{-5}$, ma alcuni servizi richiedono $10^{-9}$ o meno, e alzare ancora la potenza costa. La codifica di canale (channel coding) aggiunge ridondanzabit aggiunti che non portano informazione nuova ma permettono di controllare la parola ai bit di informazione in modo che il ricevitore possa:

• rivelare che una parola ricevuta contiene errori (e, per esempio, chiederne la ritrasmissione: Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →);
• correggere gli errori senza ritrasmissione (forward error correction, FECcorrezione degli errori fatta dal solo ricevitore, senza chiedere ritrasmissioni).

Non va confusa con la codifica di sorgente (Codifica di sorgente - codici a prefisso e teorema di ShannonLa codifica di sorgente riduce il numero di bit mappando le parole della sorgente in parole di lunghezza variabile (più corte per le più probabili), senza perdere informazione. Il codice deve essere decodificabile; i codici a prefisso (nessuna parola è prefisso di un'altra) lo sono. Kraft-McMillan: se il codice è decodificabile $\sum M_y^{-L(b)}\le1$. Teorema di Shannon: $L_y\ge\frac{H(x)}{\log_2M_y}$ e esiste un codice a prefisso con $L_y\le\frac{H(x)}{\log_2M_y}+1$; l'efficienza è $\eta=\frac{H(x)}{L_y\log_2M_y}$.Codifica di sorgente - codici a prefisso e teorema di Shannon →), che toglie ridondanza per risparmiare bit: la codifica di canale la mette, in modo controllato. Nella catena trasmissiva si trova dopo la codifica di sorgente e prima del modulatore.

Codice a blocco $(n,k)$

Si raggruppano i bit di informazione in blocchi di $k$ bit, detti parole di informazione (ce ne sono $2^k$), e a ciascuna si associa una parola di codicesequenza di $n$ bit associata a una parola di informazione di $n>k$ bit (la mappa deve essere iniettiva). L'insieme delle $2^k$ parole di codice è il codice $\mathcal C\subset\{0,1\}^n$. Grandezze:

$$R_c=\frac kn\ \ (\text{rendimento}),\qquad n-k\ \ (\text{bit di ridondanza}),\qquad\frac1{R_c}=\frac nk\ \ (\text{espansione di banda}).$$

Se il canale sostiene un bit-rate $R_b$ di bit trasmessi, i bit utili sono $R_bR_c$. Il codice è sistematico se i primi $k$ bit della parola di codice coincidono con la parola di informazione (gli altri $n-k$ sono i bit di parità).

Esempi. Ripetizione $(n,1)$: ogni bit è ripetuto $n$ volte, $R_c=\frac1n$. Singolo bit di parità $(n,n-1)$: si aggiunge un bit che rende pari il numero di uni, $R_c=\frac{n-1}n$. Hamming $(7,4)$: $R_c=\frac47$ (Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di HammingUn codice a blocco è lineare se la somma (bit a bit, modulo 2) di due parole di codice è una parola di codice. Si descrive con la matrice generatrice $G$ ($k\times n$, $\mathbf c=\mathbf mG$) e con la matrice di controllo di parità $H$ ($(n-k)\times n$, $G H^T=0$); in forma sistematica $G=[I_k\mid P]$ e $H=[P^T\mid I_{n-k}]$. La distanza minima è il peso minimo delle parole non nulle. La sindrome $\mathbf s=\mathbf rH^T$ dipende solo dall'errore: se è nulla la parola è valida, altrimenti identifica l'errore (un solo errore ha per sindrome la colonna di $H$ corrispondente). I codici di Hamming $(2^m-1,,2^m-1-m)$ hanno $d_{min}=3$.Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di Hamming →).

Distanza di Hamming e distanza minima

Il peso di Hammingnumero di uni di una parola $w_H(\mathbf c)$ è il numero di uni di $\mathbf c$; la distanza di Hammingnumero di posizioni in cui due parole hanno bit diversi tra due parole è il numero di posizioni in cui differiscono: $$d_H(\mathbf c,\mathbf c')=\sum_{j=1}^n\left(1-\delta_{c_jc'_j}\right)=w_H(\mathbf c\oplus\mathbf c')$$ (con $\oplus$ somma bit a bit modulo 2). La distanza minima del codice è la più piccola distanza tra due parole distinte: $$d_{min}=\min_{\mathbf c\ne\mathbf c'\in\mathcal C}d_H(\mathbf c,\mathbf c').$$ È l'analogo discreto della distanza minima della costellazione (Introduzione alla modulazione digitale e spazio dei segnaliLa modulazione digitale associa a ognuna delle $M=2^b$ parole di $b$ bit un segnale $s_m(t)$ di energia finita; il demodulatore deve capire quale segnale è stato trasmesso da $r(t)=s_m(t)+w(t)$. Per studiarlo i segnali si vedono come vettori: con il prodotto scalare $\langle x,y\rangle=\int xy^*dt$ e una base ortonormale ${\phi_i}$ ogni segnale è $\mathbf s_m=[\langle s_m,\phi_i\rangle]$ e l'insieme dei punti è la costellazione. La base si trova con il procedimento di Gram-Schmidt; distanze ed energie dei punti dicono le prestazioni.Introduzione alla modulazione digitale e spazio dei segnali →): più le parole sono lontane, più errori servono per trasformarne una in un'altra.

Esempio. Codice $(4,2)$ con $00\to0000$, $01\to0111$, $10\to1011$, $11\to1110$. Distanze: $0000$–$0111$: $3$; $0000$–$1011$: $3$; $0000$–$1110$: $3$; $0111$–$1011$: $2$; $0111$–$1110$: $2$; $1011$–$1110$: $2$. Quindi $d_{min}=2$.

Rivelazione e correzione degli errori

Un errore di $e$ bit sposta la parola trasmessa a distanza $e$.

• Rivelazione: se $e<d_{min}$ la parola ricevuta non è una parola di codice (è a distanza $e<d_{min}$ dalla trasmessa, quindi non può coincidere con un'altra parola di codice): l'errore è visibile. Il codice rivela con certezza fino a $d_{min}-1$ errori. (Con $e\ge d_{min}$ può accadere che la parola ricevuta sia un'altra parola valida: errore non rivelato.)
• Correzione con decodifica a minima distanzail ricevitore sceglie la parola di codice più vicina, in distanza di Hamming, a quella ricevuta (minimum distance decoding): il ricevitore sceglie la parola di codice più vicina alla ricevuta (equivale al criterio ML per un canale binario simmetricoogni bit viene invertito con probabilità $p$, indipendentemente dagli altri con $p<\frac12$, come la minima distanza euclidea nel caso AWGN: Teoria della decisione - criteri MAP, ML e MDLe regioni di decisione che massimizzano la probabilità di decisione corretta sono $\mathcal R_m={\boldsymbol\rho:\ m=\arg\max_mP_m,p_{\mathbf r|m}(\boldsymbol\rho|m)}$: criterio MAP (ottimo). Il criterio ML ignora le probabilità a priori; se i simboli sono equiprobabili coincide con il MAP. Il criterio MD sceglie il punto più vicino, $\hat m=\arg\min_m\lVert\boldsymbol\rho-\mathbf s_m\rVert$; con canale AWGN coincide con il ML. Quindi con simboli equiprobabili e AWGN la distanza minima è ottima; con probabilità diverse le soglie si spostano verso il punto meno probabile.Teoria della decisione - criteri MAP, ML e MD →). Le sfere di Hamminginsiemi delle parole a distanza al più $t$ da una parola di codice di raggio $t$ attorno alle parole di codice sono disgiunte se $2t+1\le d_{min}$, quindi si correggono con certezza fino a $$\boxed{t=\left\lfloor\frac{d_{min}-1}2\right\rfloor\ \text{errori}.}$$
• Correzione e rivelazione insieme: si possono correggere $t$ errori e rivelarne fino a $e\ge t$ se $d_{min}\ge t+e+1$.
• Cancellazioniposizioni in cui si sa che il bit è andato perso, senza conoscerne il valore (posizioni note ma con valore incerto): se ne correggono fino a $d_{min}-1$.

Esempio. Ripetizione $(3,1)$: parole $000$ e $111$, $d_{min}=3$: corregge $t=1$ errore (si decide a maggioranza: $010\to0$). Singolo bit di parità: $d_{min}=2$, rivela $1$ errore ma non lo corregge. Un codice che deve correggere almeno $3$ errori ha $d_{min}\ge7$ (per esempio il $(63,45)$ dell'esercizio Esercizio 27 · TDMA, codice a blocco (63,45) e PAM a quattro livelli (tema d'esame luglio 2021)).

Limiti sui codici

Con un codice $(n,k)$ e distanza $d_{min}$:

• Limite di Singleton$d_{min}\le n-k+1$: la distanza non supera i bit di ridondanza più uno: $d_{min}\le n-k+1$ (togliendo $d_{min}-1$ posizioni le parole restano distinte). I codici che lo raggiungono sono detti a massima distanza (MDS). Serve per trovare il $k$ massimo con $n$ e $t$ dati: $k\le n-d_{min}+1$, con $d_{min}=2t+1$.
• Limite di Hammingle $2^k$ sfere di raggio $t$ non si sovrappongono, quindi non possono occupare più dello spazio disponibile (impacchettamento di sfere): le $2^k$ sfere di raggio $t$ non si sovrappongono nello spazio di $2^n$ parole, quindi $2^{n-k}\ge\sum_{i=0}^t\binom ni$. Se vale l'uguaglianza il codice è perfettovale l'uguaglianza nel limite di Hamming: le sfere ricoprono tutto lo spazio (Hamming $(7,4)$: $2^3=1+7$; Golay $(23,12)$: $2^{11}=1+23+253+1771$).

Prestazioni su un canale binario simmetrico

Il canale numerico è un BSC con probabilità di errore sul bit $p$ (per esempio $p=P_{bit}$ della modulazione). Con decodifica di un codice che corregge $t$ errori:

• la parola è decodificata correttamente se ci sono al più $t$ errori (la probabilità di avere $i$ errori su $n$ bit è binomialela probabilità di $i$ errori su $n$ bit è $\binom ni p^i(1-p)^{n-i}$): $$P_w\le\sum_{i=t+1}^n\binom ni\,p^i(1-p)^{n-i}\approx\binom n{t+1}p^{t+1}\quad(p\ll1);$$ (con uguaglianza per i codici perfetti);
• la probabilità d'errore sul bit dopo la decodifica: quando c'è un errore di parola, la parola decodificata è a distanza almeno $d_{min}$ dalla trasmessa, quindi sbaglia in media circa $d_{min}$ bit su $n$ (e la parola più probabile decodificata è a distanza $d_{min}$): $$P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}(1-p)^{n-t-1}.$$

Esempi (calcolati e controllati con Python).

• Ripetizione $(3,1)$, $p=10^{-2}$: errore se almeno $2$ bit su $3$ sono sbagliati: $P_b=3p^2(1-p)+p^3=2{,}98\cdot10^{-4}$ (circa $34$ volte meno, al prezzo di triplicare i bit). Ripetizione $(5,1)$ ($t=2$): $9{,}9\cdot10^{-6}$.
• Hamming $(7,4)$, $t=1$, $p=10^{-2}$: $P_w=\sum_{i\ge2}\binom7ip^i(1-p)^{7-i}=2{,}03\cdot10^{-3}\approx21p^2$ (simulazione su $4\cdot10^5$ parole: $2{,}06\cdot10^{-3}$), contro la probabilità $1-(1-p)^4=3{,}9\cdot10^{-2}$ di sbagliare almeno uno dei $4$ bit senza codice.
• Codice $(63,45)$ con $t=3$ ($d_{min}\ge7$) e $p=2{,}9\cdot10^{-5}$: $P_w=4{,}2\cdot10^{-13}$ e $P_{bit}\approx\frac7{63}\binom{63}4p^4=4{,}6\cdot10^{-14}$.

Il prezzo della ridondanza. Se il bit-rate del canale resta fisso, i bit utilibit di informazione effettivamente trasportati, esclusa la ridondanza calano di $R_c$; se invece si vuole mantenere il rate utile, il tempo di bit si riduce di $R_c$ e, a potenza fissa, l'energia per bit trasmesso cala (e quindi $p$ cresce): il guadagno di codificariduzione della potenza necessaria, a parità di probabilità d'errore, grazie al codice va confrontato con questa perdita. Per $p$ molto piccola il guadagno è grande; per $p$ vicino a $\frac12$ la codifica non conviene. Il limite teorico a cui un codice può arrivare è dato dalla capacità del canale (Capacità di canale - canale binario simmetrico, a cancellazione e AWGNLa capacità $C=\max_{p_x}I(x;y)$ è il massimo di informazione mutua tra ingresso e uscita del canale; per il teorema di Shannon si può comunicare con probabilità d'errore arbitrariamente piccola se e solo se il rate è minore di $C$. Per il canale binario simmetrico $C=1-H_2(p)$ bit per uso (ingresso uniforme), per il canale a cancellazione $C=1-\varepsilon$, per l'AWGN $C=\frac12\log_2(1+\text{SNR})$ per uso reale, cioè $C=B\log_2(1+\text{SNR})$ bit/s su una banda $B$. Il limite $R_b<C$ dà il minimo $\frac{E_b}{N_0}\ge\frac{2^\nu-1}\nu$ ($-1{,}59$ dB per $\nu\to0$).Capacità di canale - canale binario simmetrico, a cancellazione e AWGN →).

Errori comuni

• Dire che $d_{min}$ errori sono rivelati: se ne rivelano $d_{min}-1$ (con $d_{min}$ errori si può finire in un'altra parola di codice).
• Correggere $\frac{d_{min}}2$ errori: sono $\left\lfloor\frac{d_{min}-1}2\right\rfloor$ ($d_{min}=4$ corregge solo $1$).
• Usare $d_{min}\ge2t$ al posto di $2t+1$ per correggere $t$ errori (per $t=8$: $d_{min}\ge17$, non $16$).
• Dimenticare che il rendimento $\frac kn$ riduce il rate utile.
• Confondere la probabilità di parola con quella di bit dopo la decodifica (differiscono di circa $\frac{d_{min}}n$).