Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico

Un collegamento digitale sbaglia qualche bit: il demodulatore decide un simbolo (Regioni di decisione - criteri MAP, ML e minima distanzaLe regioni di decisione $\mathcal R_1,\dots,\mathcal R_M$ sono una partizione dello spazio $\mathbb R^I$: se il vettore ricevuto cade in $\mathcal R_m$ si decide $\hat a_0=m$. La probabilità di decisione corretta è $P[C]=\sum_m\int_{\mathcal R_m}D(\boldsymbol\rho;m),d\boldsymbol\rho$ con $D=P_{a_0}(m),p_{\mathbf r|a_0}(\boldsymbol\rho|m)$, ed è massima assegnando ogni $\boldsymbol\rho$ al $m$ che massimizza $D$: criterio MAP. Con simboli equiprobabili è il ML; con in più rumore AWGN diventa la minima distanza (MD), $\hat a_0=\arg\min_m\lVert\boldsymbol\rho-\mathbf s_m\rVert$, con confini che sono gli assi dei segmenti tra i punti. Con probabilità diverse i confini si spostano verso i punti meno probabili.Regioni di decisione - criteri MAP, ML e minima distanza →) e con probabilità piccola ma non nulla la decisione è sbagliata (Probabilità d'errore delle modulazioni binarie - funzione Q e coefficiente di correlazioneIn una modulazione binaria con rumore AWGN e decisione a minima distanza l'errore avviene solo se la componente di rumore lungo la congiungente dei due punti supera metà distanza: $P[E]=Q\left(\frac{d}{2\sigma_I}\right)$ con $d=\lVert\underline s_1-\underline s_2\rVert$. A parità di energia $E_s$ si ha $d^2=2E_s(1-\rho)$, quindi $P[E]=Q\left(\sqrt{\frac{E_s}{\sigma_I^2}}\sqrt{\frac{1-\rho}{2}}\right)$, con $\rho=\frac{\langle s_1,s_2\rangle}{\sqrt{E_{s_1}E_{s_2}}}$ coefficiente di correlazione. Antipodali ($\rho=-1$, BPSK): $Q\left(\sqrt{E_s/\sigma_I^2}\right)$; ortogonali ($\rho=0$): $Q\left(\sqrt{E_s/(2\sigma_I^2)}\right)$, 3 dB peggio; $\rho=1$: $P[E]=\frac12$. Per qualunque modulazione binaria basta un solo ramo del ricevitore, lungo $\phi_1'\propto s_1-s_2$.Probabilità d'errore delle modulazioni binarie - funzione Q e coefficiente di correlazione →). Se $P_{bit}$ è troppo alta per l'applicazione, aumentare l'energia o ridurre il rumore costa potenza, banda o distanza. La codifica di canale è l'altra strada: si aggiungono bit di ridondanza, scelti in modo che gli errori si possano riconoscere o correggere.

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 →. Versione per Ing. delle Telecomunicazioni: 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 →.

1. Tre strategie contro gli errori

1. Ritrasmissione, ARQ (ARQautomatic repeat request: il ricevitore controlla ogni messaggio e ne chiede la ripetizione se contiene errori). Serve un canale di ritorno su cui il ricevitore dice al trasmettitore "ricevuto bene" o "ricevuto male". La ridondanza serve solo a rivelare la presenza di errori: se ci sono, si rimanda il messaggio. Costa tempo (le ripetizioni) ma pochi bit di ridondanza.
2. Correzione diretta, FEC (FECforward error correction: la ridondanza permette al ricevitore di correggere gli errori da solo, senza ritrasmettere). Il ricevitore corregge da solo, nessun canale di ritorno. Costa più ridondanza (più bit per ogni bit di informazione) e non dà garanzie se gli errori sono più di quelli previsti.
3. ARQ ibrido, HARQ: si usa una FEC per correggere gli errori più comuni e la ritrasmissione quando la parola ricevuta non è accettabile.

Le sezioni 2-9 trattano la FEC con i codici a blocco; la sezione 10 tratta le prestazioni dell'ARQ.

2. Il codice a blocco: schema e notazione

Definizione. Un codice a blocco $(n,k)$ associa a ogni sequenza di $k$ bit di informazione $\mathbf b=[b_1,\dots,b_k]^T$ una parola di codice $\mathbf c=[c_1,\dots,c_n]^T$ di $n>k$ bit, in modo biunivoco. L'insieme delle parole è il codice $\mathcal C$.

La catena di trasmissione è

$$\mathbf b\ (k\text{ bit})\ \longrightarrow\ \boxed{\text{COD. canale}}\ \longrightarrow\ \mathbf c\ (n\text{ bit})\ \longrightarrow\ \boxed{\text{MOD. dig.}}\ \longrightarrow\ \text{canale}\ \longrightarrow\ \boxed{\text{DEM. dig.}}\ \longrightarrow\ \tilde{\mathbf c}\ (n\text{ bit})\ \longrightarrow\ \boxed{\text{DEC. canale}}\ \longrightarrow\ \hat{\mathbf b}\ (k\text{ bit}).$$

Conviene contare e distinguere tre vettori che spesso si confondono.

• Le sequenze $\mathbf b$ possibili sono $2^k$, quindi le parole di codice sono $2^k$; le sequenze binarie di $n$ bit sono $2^n$, e $\mathcal C$ ne contiene solo una piccola parte (la frazione $2^{k-n}$). Per questo la ridondanza serve: una sequenza fuori dal codice è un errore riconoscibile.
• $\mathbf c$ è la parola trasmessa.
• $\tilde{\mathbf c}$ è la sequenza ricevuta all'uscita del demodulatore: ha $n$ bit, può essere una qualunque delle $2^n$ sequenze e non è detto che sia una parola di codice.
• $\hat{\mathbf c}$ è la parola decisa dal decodificatore e $\hat{\mathbf b}$ i $k$ bit a essa associati. In generale $\mathbf c\ne\tilde{\mathbf c}\ne\hat{\mathbf c}$; $\mathbf c$ e $\hat{\mathbf c}$ sono parole di codice, $\tilde{\mathbf c}$ no.

Esempio ($k=2$, $n=4$). La tabella

$\mathbf b$	$\mathbf c$
00	0001
01	0110
10	1010
11	1101

definisce il codice $\mathcal C=\{0001,\,0110,\,1010,\,1101\}$: $2^k=4$ parole tra le $2^4=16$ sequenze. Se si trasmette $0110$ con un errore sul primo bit si riceve $\tilde{\mathbf c}=1110$, che non appartiene a $\mathcal C$: l'errore è riconosciuto. Ma lo stesso $1110$ si ottiene anche da $1010$ con un errore sul secondo bit: il decodificatore vede una sequenza a un solo bit di distanza da due parole diverse e non può sapere quale fosse stata inviata. Se invece si riceve $0111$ la parola più vicina è $0110$ (un solo bit diverso, le altre ne hanno almeno 2), quindi $\hat{\mathbf c}=0110$.

Il canale binario. Il blocco "modulatore, canale analogico, demodulatore" riceve $n$ bit e restituisce $n$ bit: dal punto di vista della codifica è un canale binario, descritto da una probabilità d'errore sul bit $P_{bit}$ che si calcola con le formule dei capitoli sulle modulazioni, per esempio $P_{bit}=Q(\cdot)$ (Variabili aleatorie continue - uniforme, gaussiana, esponenziale e funzione QUna v.a. continua ha funzione di distribuzione F_x(a) = P(x ≤ a) e densità f_x(a) = dF_x/da ≥ 0 con integrale 1; P(A ≤ x ≤ B) = F_x(B) − F_x(A) = ∫A^B f_x e P(x = A) = 0. Uniforme U([a,b]): densità 1/(b−a), media (a+b)/2, varianza (b−a)²/12. Esponenziale unilatera di media m: (1/m)e^(−a/m), a ≥ 0. Gaussiana N(m, σ²): P(x ≥ A) = Q((A − m)/σ), con Q(A) coda della gaussiana standard. Somme di gaussiane indipendenti sono gaussiane (medie e varianze si sommano); teorema del limite centrale.Variabili aleatorie continue - uniforme, gaussiana, esponenziale e funzione Q →). Il codificatore e il decodificatore lavorano solo sui bit; la modulazione resta un blocco a parte (Modulazione digitale - trasmettitore, bit map e canale AWGNIl trasmettitore digitale ha due blocchi: la bit map raggruppa $\log_2M$ bit in un simbolo $a_m\in{1,\dots,M}$ (periodo $T=T_b\log_2M$) e il modulatore associa a ogni simbolo una forma d'onda $s{a_m}(t)$, così $s_{Tx}(t)=\sum_ms_{a_m}(t-mT)$; l'insieme delle $M$ forme d'onda è la segnalazione. Il canale ideale lascia il segnale com'è, il canale AWGN lo scala di $A$ e somma il rumore bianco gaussiano $w(t)$, il canale multipath somma echi ritardati: i suoi due effetti sono la deformazione delle forme d'onda ($s'_m$) e l'interferenza intersimbolica. Il ricevitore ha un demodulatore digitale che decide $\hat a_m$ e una bit demap.Modulazione digitale - trasmettitore, bit map e canale AWGN →).

3. Criteri di decodifica: MAP e ML

Il decodificatore è un ricevitore come quello della modulazione, con le parole di codice al posto dei simboli. La probabilità di decisione corretta è

$$P(C)=\sum_{l=1}^{2^k}P(\hat{\mathbf c}=\mathbf c_l\mid\mathbf c=\mathbf c_l)\,P(\mathbf c=\mathbf c_l).$$

(è la stessa formula $\sum_mP(\hat a_0=m\mid a_0=m)P(m)$ della modulazione, con $2^k$ "simboli".) Come nella modulazione, si massimizza $P(C)$ scegliendo, per ogni sequenza ricevuta $\boldsymbol\beta$, la parola con probabilità a posteriori massima:

$$\hat{\mathbf c}(\boldsymbol\beta)=\arg\max_{\boldsymbol\alpha\in\mathcal C}\ P(\tilde{\mathbf c}=\boldsymbol\beta\mid\mathbf c=\boldsymbol\alpha)\,P(\mathbf c=\boldsymbol\alpha)\qquad\text{(criterio MAP)}.$$

Il primo fattore è la probabilità di transizione del canale da $\boldsymbol\alpha$ a $\boldsymbol\beta$; il secondo è la probabilità a priori della parola. Se tutte le parole hanno la stessa probabilità a priori il secondo fattore è costante e rimane

$$\hat{\mathbf c}(\boldsymbol\beta)=\arg\max_{\boldsymbol\alpha\in\mathcal C}\ P(\tilde{\mathbf c}=\boldsymbol\beta\mid\mathbf c=\boldsymbol\alpha)\qquad\text{(criterio ML, massima verosimiglianza)}.$$

I bit di informazione equiprobabili e indipendenti danno $2^k$ parole equiprobabili, perché la corrispondenza $\mathbf b\leftrightarrow\mathbf c$ è biunivoca: nei problemi si usa quasi sempre ML. Per il confronto con la modulazione: Regioni di decisione - criteri MAP, ML e minima distanzaLe regioni di decisione $\mathcal R_1,\dots,\mathcal R_M$ sono una partizione dello spazio $\mathbb R^I$: se il vettore ricevuto cade in $\mathcal R_m$ si decide $\hat a_0=m$. La probabilità di decisione corretta è $P[C]=\sum_m\int_{\mathcal R_m}D(\boldsymbol\rho;m),d\boldsymbol\rho$ con $D=P_{a_0}(m),p_{\mathbf r|a_0}(\boldsymbol\rho|m)$, ed è massima assegnando ogni $\boldsymbol\rho$ al $m$ che massimizza $D$: criterio MAP. Con simboli equiprobabili è il ML; con in più rumore AWGN diventa la minima distanza (MD), $\hat a_0=\arg\min_m\lVert\boldsymbol\rho-\mathbf s_m\rVert$, con confini che sono gli assi dei segmenti tra i punti. Con probabilità diverse i confini si spostano verso i punti meno probabili.Regioni di decisione - criteri MAP, ML e minima distanza →; versione per Ing. Elettronica: 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 →.

4. Il canale binario simmetrico senza memoria (BSC)

Definizione. Un canale binario simmetrico senza memoria (BSC, binary symmetric channel) ha ingresso $x$ e uscita $y$ in $\{0,1\}$ e $$P(y=1\mid x=0)=P(y=0\mid x=1)=P_{bit},\qquad y_i=x_i\oplus\varepsilon_i,$$ con gli errori $\varepsilon_i\in\{0,1\}$ indipendenti nel tempo, $P(\varepsilon_i=1)=P_{bit}$.

"Simmetrico" vuol dire che si sbaglia con la stessa probabilità sia mandando 0 sia mandando 1; "senza memoria" che l'errore su un bit non dice nulla sugli altri. Se queste due ipotesi mancano il canale non è un BSC: per esempio un canale che con probabilità $0{,}2$ dà $y=1$ qualunque sia $x$, con probabilità $0{,}1$ dà $y=0$ e altrimenti $y=x$ ha $P(0\mid0)=0{,}1+0{,}7=0{,}8$ ma $P(1\mid1)=1-0{,}1=0{,}9$: è binario e senza memoria ma non simmetrico.

Poiché gli errori sono indipendenti, la probabilità di ricevere $\boldsymbol\beta$ avendo trasmesso $\boldsymbol\alpha$ è il prodotto dei $n$ fattori, uno per bit: $1-P_{bit}$ nelle posizioni dove i due vettori coincidono, $P_{bit}$ dove differiscono. Se i due vettori differiscono in $d_H(\boldsymbol\alpha,\boldsymbol\beta)$ posizioni (distanza di Hamming, sezione 5):

$$P(\tilde{\mathbf c}=\boldsymbol\beta\mid\mathbf c=\boldsymbol\alpha)=\prod_{i=1}^nP(\tilde c_i=\beta_i\mid c_i=\alpha_i)=P_{bit}^{\,d_H(\boldsymbol\alpha,\boldsymbol\beta)}\,(1-P_{bit})^{\,n-d_H(\boldsymbol\alpha,\boldsymbol\beta)}.$$

Conta solo quanti bit sono diversi, non quali. Versione per Ing. delle Telecomunicazioni: Canale binario simmetrico, codifica di Gray e probabilità di bitIl canale numerico equivalente a modulatore, canale e demodulatore è un canale binario simmetrico senza memoria (BSC): ogni bit è sbagliato con probabilità $P_{bit}$, indipendentemente dagli altri. Per una modulazione $M$-aria con $n=\log_2M$ bit per simbolo, la probabilità di errore sul simbolo è $P[E]=1-(1-P_{bit})^n\approx nP_{bit}$ e $P_{bit}\le P[E]$. Il legame inverso passa dalla distanza di Hamming tra le parole di bit: $P_{bit}=\sum_k\sum_{j\ne k}p_kP_{j|k}\frac{d_H(\mathbf c_j,\mathbf c_k)}{\log_2M}$. Con la codifica di Gray (simboli adiacenti differiscono per un solo bit) e SNR non troppo basso gli errori più probabili, verso i vicini, sbagliano un solo bit, quindi $P_{bit}\approx\frac{P[E]}{\log_2M}$.Canale binario simmetrico, codifica di Gray e probabilità di bit →.

Esempio. Con $P_{bit}=0{,}1$ si riceve $0111$ dal codice $\{0001,0110,1010,1101\}$. Le distanze sono $2,1,3,2$, quindi le verosimiglianze sono $$0{,}1^2\cdot0{,}9^2=0{,}0081,\quad0{,}1\cdot0{,}9^3=0{,}0729,\quad0{,}1^3\cdot0{,}9=0{,}0009,\quad0{,}0081.$$ La più alta è quella di $0110$: ML decide $0110$. Con $1110$ invece $0110$ e $1010$ sono entrambe a distanza $1$ e hanno la stessa verosimiglianza $0{,}0729$: ML è in parità. Se le parole non sono equiprobabili, per esempio con probabilità a priori $0{,}1,\ 0{,}4,\ 0{,}2,\ 0{,}3$, si moltiplica per il prior: $0{,}0729\cdot0{,}4=0{,}02916$ contro $0{,}0729\cdot0{,}2=0{,}01458$, e MAP sceglie $0110$.

5. ML sul BSC significa minima distanza di Hamming

Definizione. La distanza di Hamming tra due sequenze binarie $\boldsymbol\alpha,\boldsymbol\beta$ di $n$ bit è il numero di posizioni in cui sono diverse: $$d_H(\boldsymbol\alpha,\boldsymbol\beta)=\sum_{i=1}^n(\alpha_i\oplus\beta_i),$$ dove $\alpha_i\oplus\beta_i$ vale $1$ se i bit sono diversi e $0$ se sono uguali ("differenza binaria").

Sul BSC con parole equiprobabili, il criterio ML diventa

$$\hat{\mathbf c}(\boldsymbol\beta)=\arg\max_{\boldsymbol\alpha\in\mathcal C}P_{bit}^{d_H}(1-P_{bit})^{n-d_H}=\arg\max_{\boldsymbol\alpha\in\mathcal C}\ (1-P_{bit})^n\left(\frac{P_{bit}}{1-P_{bit}}\right)^{d_H(\boldsymbol\alpha,\boldsymbol\beta)}.$$

Il fattore $(1-P_{bit})^n$ non dipende da $\boldsymbol\alpha$ e si può togliere. Se $P_{bit}<\frac12$ il rapporto $\frac{P_{bit}}{1-P_{bit}}$ è minore di 1, quindi elevato a una potenza decrescente: la verosimiglianza è massima quando l'esponente $d_H$ è minimo.

$$\boxed{P_{bit}<\tfrac12\ \Longrightarrow\ \hat{\mathbf c}(\boldsymbol\beta)=\arg\min_{\boldsymbol\alpha\in\mathcal C}d_H(\boldsymbol\alpha,\boldsymbol\beta)}\qquad\text{(decodifica a minima distanza).}$$

È la stessa regola del ricevitore a minima distanza della modulazione, con la distanza di Hamming al posto di quella euclidea. Per $P_{bit}>\frac12$ il rapporto sarebbe maggiore di 1 e si sceglierebbe la parola più lontana (un canale che sbaglia più di metà dei bit si può "rovesciare" invertendo l'uscita); $P_{bit}=\frac12$ non porta informazione.

6. Distanza minima, rivelazione e correzione

Definizione. La distanza minima del codice è la minima distanza di Hamming tra due parole diverse: $$d_{min}=\min_{\boldsymbol\alpha,\boldsymbol\beta\in\mathcal C,\ \boldsymbol\alpha\ne\boldsymbol\beta}d_H(\boldsymbol\alpha,\boldsymbol\beta).$$

Rivelazione. Un errore non viene riconosciuto solo se trasforma una parola di codice in un'altra parola di codice, e per farlo deve cambiare almeno $d_{min}$ bit. Quindi qualunque combinazione di al più $d_{min}-1$ errori porta fuori dal codice e si riconosce: il codice rivela sempre $d_{min}-1$ errori.

Correzione. Si disegnano attorno a ogni parola le "sfere" di Hamming di raggio $t$: tutte le sequenze a distanza $\le t$ da essa. Se le sfere sono disgiunte, ogni sequenza ricevuta con al più $t$ errori sta nella sfera della parola trasmessa e solo in quella: la decodifica a minima distanza la riconduce alla parola giusta. Due sfere di raggio $t$ centrate in parole a distanza $d_{min}$ sono disgiunte se $2t<d_{min}$, cioè

$$t=\left\lfloor\frac{d_{min}-1}{2}\right\rfloor\qquad\text{(errori corretti sempre).}$$

"Sempre" significa in qualunque posizione cadano gli errori. Con più di $t$ errori la decodifica può ancora riuscire per fortuna, ma non c'è garanzia.

Esempio ($d_{min}$ pari). Il codice $\{0000,\,1111\}$ ha $d_{min}=4$: rivela $3$ errori e corregge $t=\lfloor3/2\rfloor=1$. Ricevendo $0001$ si decide $0000$ (distanza $1$ contro $3$). Ricevendo $0011$ le due parole sono entrambe a distanza $2$: l'errore (doppio) è rivelato ma non correggibile. Il disegno della distanza $4$ ha un punto di decisione esattamente a metà strada, quindi con $d_{min}$ pari c'è un punto di parità.

Si possono anche combinare i due scopi: un codice con $d_{min}\ge t+s+1$ corregge $t$ errori e ne rivela fino a $s\ge t$. Per $d_{min}=4$: corregge $1$ e rivela $2$ allo stesso tempo.

Come limitare $d_{min}$ dall'alto: il bound di Hamming (sezione 8 e nota Codici di Hamming e bound di HammingIl bound di Hamming (sphere packing) lega tasso e capacità di correzione: $2^k\sum_{r=0}^t\binom nr\le2^n$, cioè $\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$, perché le $2^k$ sfere di raggio $t$ attorno alle parole sono disgiunte. Un codice di Hamming ha per colonne di $H$ tutte le sequenze non nulle di $n-k$ bit, ciascuna una volta, quindi $n=2^{n-k}-1$ (parametri $(2^m-1,,2^m-1-m)$: $(7,4)$, $(15,11)$, $(63,57)$, $(255,247)$). Non ha colonne nulle né ripetute e tre colonne sommano a zero: $d_{min}=3$, corregge $1$ errore e ne rivela $2$. Rispetta il bound di Hamming con l'uguaglianza ($t=1$): è un codice perfetto, per cui la probabilità d'errore di parola sul BSC è esattamente $P(\text{almeno 2 errori})$.Codici di Hamming e bound di Hamming →) e il bound di Singleton (Codici a blocco lineari - matrice generatrice, forma sistematica e bound di SingletonUn codice a blocco è lineare se le sue $2^k$ parole formano un sottospazio dello spazio delle sequenze binarie di $n$ bit, con la somma modulo 2 (XOR) senza riporto: contiene la parola nulla ed è chiuso rispetto alla somma. Si descrive con la matrice generatrice $G$ ($n\times k$, rango $k$, $\mathbf c=G\mathbf b$, le colonne sono parole di codice); le operazioni sulle colonne non cambiano il codice, le permutazioni delle righe permutano i bit e non cambiano le prestazioni sul canale senza memoria. In forma sistematica $G=\begin{bmatrix}I_k\A\end{bmatrix}$ e $\mathbf c=[\mathbf b;A\mathbf b]$. Per i codici lineari la distanza minima è il peso di Hamming minimo delle parole non nulle e vale il bound di Singleton $d_{min}\le n-k+1$.Codici a blocco lineari - matrice generatrice, forma sistematica e bound di Singleton →).

7. Tasso del codice e bit-rate

Definizione. Il tasso (rate) del codice è $R=\dfrac kn\le1$.

Se $n\gg k$ il tasso tende a $0$: quasi tutti i bit trasmessi sono ridondanza. Se il canale trasporta un bit ogni $T_b$ secondi ($T_b$ è il tempo per trasmettere un bit sul canale), ogni parola occupa $nT_b$ secondi e porta $k$ bit di informazione. Il codificatore riceve quindi

$$\frac{k}{nT_b}=\frac{R}{T_b}\ \text{bit/s}$$

di informazione, mentre sul canale passano $\frac1{T_b}$ bit/s. Viceversa, per trasportare un'informazione di $R_{info}$ bit/s occorre un canale da $R_{info}\cdot\frac nk=\frac{R_{info}}{R}$ bit/s: per esempio con un codice $(7,4)$ e $R_{info}=1$ Mbit/s servono $\frac74=1{,}75$ Mbit/s sul canale (più banda, o più energia per bit se si vuole la stessa $P_{bit}$). La codifica "costa" sempre almeno questo fattore.

8. Probabilità d'errore di parola e bound di Hamming

Sul BSC, il numero di errori in una parola di $n$ bit ha distribuzione 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 →): la probabilità di $j$ errori in posizioni qualsiasi è $\binom nj P_{bit}^j(1-P_{bit})^{n-j}$. Un codice con $t$ errori corretti sempre decodifica bene almeno quando gli errori sono al più $t$. Quindi, per la probabilità d'errore di parola $P(E)=P(\hat{\mathbf c}\ne\mathbf c)$:

$$\boxed{P(E)\le P(\text{più di }t\text{ errori})=\sum_{j=t+1}^n\binom nj P_{bit}^j(1-P_{bit})^{n-j}=1-\sum_{j=0}^{t}\binom nj P_{bit}^j(1-P_{bit})^{n-j}}$$

(è una limitazione superiore: con più di $t$ errori la decodifica può ancora riuscire). Vale l'uguaglianza per i codici perfetti (Codici di Hamming e bound di HammingIl bound di Hamming (sphere packing) lega tasso e capacità di correzione: $2^k\sum_{r=0}^t\binom nr\le2^n$, cioè $\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$, perché le $2^k$ sfere di raggio $t$ attorno alle parole sono disgiunte. Un codice di Hamming ha per colonne di $H$ tutte le sequenze non nulle di $n-k$ bit, ciascuna una volta, quindi $n=2^{n-k}-1$ (parametri $(2^m-1,,2^m-1-m)$: $(7,4)$, $(15,11)$, $(63,57)$, $(255,247)$). Non ha colonne nulle né ripetute e tre colonne sommano a zero: $d_{min}=3$, corregge $1$ errore e ne rivela $2$. Rispetta il bound di Hamming con l'uguaglianza ($t=1$): è un codice perfetto, per cui la probabilità d'errore di parola sul BSC è esattamente $P(\text{almeno 2 errori})$.Codici di Hamming e bound di Hamming →). Il valore vale per qualunque mappa $\mathbf b\to\mathbf c$: la probabilità d'errore di parola dipende solo dall'insieme $\mathcal C$, non da quale $\mathbf b$ corrisponde a quale $\mathbf c$ (permutare le associazioni non cambia le parole né le distanze).

Esempio (codice $(5,2)$ con $d_{min}=3$, $P_{bit}=10^{-2}$). Il codice corregge $t=1$ errore. Allora $$P(E)\le1-\left[(1-P_{bit})^5+5P_{bit}(1-P_{bit})^4\right]=1-[0{,}95099+0{,}04803]=9{,}8\cdot10^{-4}.$$ Senza codice, i due bit di informazione arrivano corretti con probabilità $(1-P_{bit})^2$ e la probabilità che almeno uno sia sbagliato è $1-0{,}99^2=1{,}99\cdot10^{-2}$: il codice la riduce di un fattore circa $20$. Con $P_{bit}=10^{-3}$ si passa da $2{,}0\cdot10^{-3}$ a $1{,}0\cdot10^{-5}$.

Solo rivelazione. Se il codice si usa solo per rivelare (come nell'ARQ), l'errore non rivelato è quello che trasforma $\mathbf c$ in un'altra parola. Con un solo bit di parità $(8,7)$ ($d_{min}=2$) è un numero pari di errori: $P=\sum_{j\ \text{pari}\ge2}\binom8jP_{bit}^j(1-P_{bit})^{8-j}=2{,}8\cdot10^{-5}$ a $P_{bit}=10^{-3}$ (circa $\binom82P_{bit}^2=28\cdot10^{-6}$), contro una probabilità di avere un errore tra i $7$ bit di informazione senza codice pari a $7\cdot10^{-3}$.

Il bound di Hamming dà un limite al tasso a parità di errori corretti $t$. Il numero di sequenze a distanza esattamente $r$ da una sequenza di $n$ bit è $\binom nr$ (si scelgono le $r$ posizioni da cambiare); le sequenze nella sfera di raggio $t$ sono $\sum_{r=0}^t\binom nr$. Le $2^k$ sfere sono disgiunte e stanno tutte tra le $2^n$ sequenze:

$$2^k\sum_{r=0}^t\binom nr\le2^n\quad\Longleftrightarrow\quad\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr.$$

La dimostrazione e le conseguenze (codici perfetti) sono nella nota Codici di Hamming e bound di HammingIl bound di Hamming (sphere packing) lega tasso e capacità di correzione: $2^k\sum_{r=0}^t\binom nr\le2^n$, cioè $\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$, perché le $2^k$ sfere di raggio $t$ attorno alle parole sono disgiunte. Un codice di Hamming ha per colonne di $H$ tutte le sequenze non nulle di $n-k$ bit, ciascuna una volta, quindi $n=2^{n-k}-1$ (parametri $(2^m-1,,2^m-1-m)$: $(7,4)$, $(15,11)$, $(63,57)$, $(255,247)$). Non ha colonne nulle né ripetute e tre colonne sommano a zero: $d_{min}=3$, corregge $1$ errore e ne rivela $2$. Rispetta il bound di Hamming con l'uguaglianza ($t=1$): è un codice perfetto, per cui la probabilità d'errore di parola sul BSC è esattamente $P(\text{almeno 2 errori})$.Codici di Hamming e bound di Hamming →.

9. Quando basta un codice: il teorema di Shannon sul BSC

La codifica non può portare a zero gli errori a qualunque bit-rate. Per il BSC la capacità di canale (Tasso d'informazione, capacità di canale e teorema di ShannonUna sorgente che emette un simbolo ogni $T$ secondi ha tasso d'informazione $R=\frac{H_s}T$ [bit/s] ($H_s$ entropia per simbolo); un canale ha tasso $R(g)=\frac{I_s(x;y)}T\le R(x)$. La capacità è il massimo del tasso del canale su tutte le statistiche d'ingresso, $C=\max_{p_x}\frac{I(x;y)}T$ per un canale senza memoria. Teorema di Shannon: se il tasso nominale della sorgente è $R\le C$ esiste un codice di canale con probabilità d'errore piccola a piacere, se $R>C$ no. Capacità: BSC $C=\frac1T[1-h(P_{bit})]$, canale a cancellazione $C=\frac{1-\alpha}T$, AWGN reale $C=\frac1{2T}\log_2\left(1+\frac{E_s}{\sigma^2}\right)$; canali in parallelo sommano le capacità.Tasso d'informazione, capacità di canale e teorema di Shannon →) è $$C=\frac1{T}\,[1-h(P_{bit})]\ \text{bit/s},\qquad h(p)=-p\log_2p-(1-p)\log_2(1-p),$$ con $T$ il periodo di un bit sul canale. Se il bit-rate di informazione della sorgente è minore di $C$ esiste (per $n$ grande) un codice con probabilità d'errore residua piccola a piacere; se è maggiore, nessun codice ci riesce. Il teorema non dice come costruire il codice: i codici a blocco di queste note sono esempi concreti, lontani dal limite.

Esempio. Con $P_{bit}=10^{-3}$ e $T=10\ \mu$s: $h(10^{-3})=0{,}0114$, $C=\frac{1-0{,}0114}{10^{-5}}=98{,}86$ kbit/s. Una sorgente da $79$ kbit/s si può proteggere (rate minore di $C$), una da $100$ kbit/s no.

Nei temi d'esame la domanda "è possibile trovare una codifica di canale con probabilità d'errore residua piccola a piacere?" si risolve confrontando il bit-rate di informazione (entropia della sorgente divisa per il periodo di simbolo) con $C$: vedi gli esercizi Esercizio - codice (5,3) non sistematico, matrice di parità e sindrome su BSC (secondo compitino del 9 gennaio 2026, es. 195) e Esercizio - codice (5,3) lineare dalle parole di codice, sindrome e periodo di simbolo massimo (esame dell'8 febbraio 2024, es. 175). Versione per Ing. Elettronica: 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 →.

10. ARQ: ritrasmissione dei pacchetti

Con l'ARQ i dati sono divisi in pacchetti (PDU) di $L$ bit. Il ricevitore controlla ogni pacchetto con un codice a rivelazione (per esempio il bit di parità o un CRC) e risponde con un ACK (corretto) o un NACK (errato); si ritrasmette quello errato. Si assume il canale di ritorno affidabile. Il pacchetto è errato se almeno un bit è errato:

$$p=1-(1-P_{bit})^L\ \approx\ L\,P_{bit}\quad(LP_{bit}\ll1).$$

Si definiscono $t_P$ il tempo per trasmettere un pacchetto, $t_A$ quello dell'ACK/NACK, $\tau_P$ il ritardo di propagazione (andata; andata e ritorno $2\tau_P$). Il numero di trasmissioni di un pacchetto fino al successo è geometrico, con media $\frac1{1-p}$. Si chiama throughput normalizzato $S$ la frazione di tempo in cui il canale trasporta pacchetti nuovi e corretti.

• Stop-and-wait (SW). Si manda un pacchetto e si aspetta la conferma prima del successivo. Un ciclo dura $t_P+t_A+2\tau_P$ e porta $t_P$ di tempo utile con probabilità $1-p$: $$S_{SW}=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}.$$
• Go-back-N (GBN). Il trasmettitore manda pacchetti senza aspettare, con una finestra di $N$ pacchetti in volo, con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$ (la finestra copre l'andata e ritorno). Se un pacchetto è errato, il ricevitore scarta anche i successivi e il trasmettitore li rimanda tutti: ogni errore costa $N-1$ trasmissioni inutili in più. Il numero medio di trasmissioni per pacchetto utile è $\frac{1+(N-1)p}{1-p}$ e $$S_{GBN}=\frac{(1-p)\,t_P}{\left[(N-1)p+1\right](t_P+t_A)}.$$
• Selective repeat (SR). Come GBN ma il ricevitore conserva i pacchetti corretti arrivati dopo uno errato e si rimanda solo l'errato: $$S_{SR}=(1-p)\,\frac{t_P}{t_P+t_A}.$$

Valori tipici: con $\tau_P=525$ ms, $t_P=200$ ms, $t_A=10$ ms e $p=10^{-2}$ (esercizio Esercizio - throughput di stop-and-wait, go-back-N e selective repeat (esercizi del corso, cap. 4)) si ottiene $S_{SW}=0{,}157$, $S_{GBN}=0{,}898$ con $N=6$, $S_{SR}=0{,}943$: sul collegamento lungo lo stop-and-wait aspetta quasi sempre. Versione per Ing. Elettronica: 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 →; per Ing. delle Telecomunicazioni: 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 →.

L'ARQ ha bisogno del canale di ritorno e porta un ritardo variabile, ma con pochi bit di parità raggiunge $S\approx1-p$ (SR); la FEC non ha ritardi di ritrasmissione ma spende ridondanza a ogni parola. L'HARQ combina i due vantaggi.

Errori comuni

• Confondere $\tilde{\mathbf c}$ (ricevuta, di solito non è una parola) con $\hat{\mathbf c}$ (decisa, è sempre una parola).
• Usare la decodifica a minima distanza con $P_{bit}\ge\frac12$, o con parole non equiprobabili: allora serve la verosimiglianza o il criterio MAP.
• Dire che il codice corregge "$\frac{d_{min}-1}{2}$ errori" senza la parte intera: con $d_{min}=4$ si correggono $1$ errore, non $1{,}5$.
• Calcolare $p$ del pacchetto come $P_{bit}$ nell'ARQ: $p=1-(1-P_{bit})^L$.
• Confrontare la capacità $C$ con il bit-rate del canale invece del bit-rate di informazione della sorgente, o dimenticare che $T$ è il periodo di un bit sul canale.

Domande d'esame

1. Un codice a blocco ha $d_{min}=5$. Quanti errori rivela e quanti ne corregge sempre? Rivela $d_{min}-1=4$ errori e corregge $t=\lfloor\frac{5-1}2\rfloor=2$. Con tre errori può decodificare male; con quattro li rivela se non corregge.
2. Perché sul BSC la decodifica ML è a minima distanza di Hamming? La verosimiglianza di $\boldsymbol\alpha$ è $P_{bit}^{d_H}(1-P_{bit})^{n-d_H}$ e per $P_{bit}<\frac12$ decresce con $d_H$; il fattore $(1-P_{bit})^n$ è lo stesso per tutte le parole.
3. Un codice $(5,2)$ con $d_{min}=3$ è usato su un BSC con $P_{bit}=10^{-2}$: limite superiore alla probabilità d'errore di parola. $t=1$; $P(E)\le1-(1-p)^5-5p(1-p)^4=9{,}8\cdot10^{-4}$.

Esercizi svolti

• Esercizio - throughput di stop-and-wait, go-back-N e selective repeat (esercizi del corso, cap. 4): throughput di stop-and-wait, go-back-N e selective repeat con i dati del corso.
• Esercizio - stop-and-wait con canale a cancellazione e informazione mutua (secondo compitino del 12 gennaio 2018, es. 73): stop-and-wait su un canale a cancellazione, sistema senza ACK per alcuni simboli, informazione mutua e capacità.
• Esercizio - codice non lineare a quattro parole, distanza 2 e bound di Singleton (esame del 21 giugno 2023, es. 159): codice non lineare a quattro parole, distanza minima, bound di Singleton e un bit inutile.
• Esercizio - codice (5,3) lineare dalle parole di codice, sindrome e periodo di simbolo massimo (esame dell'8 febbraio 2024, es. 175): probabilità di una sequenza ricevuta sul BSC e periodo di simbolo massimo secondo Shannon.