Esercizio - rate di informazione, codice di Hamming (7,4) e capacità del canale binario simmetrico (compito del 6 luglio 2026, es. 204)

---

Nota sul testo. I punti 4 e 5 usano parole di $4$ bit ($\mathbf b$) e di $7$ bit ($\xi$): il codice di Hamming è quindi il $(7,4)$, che codifica gruppi di $4$ bit, cioè due simboli di $L=2$ bit. Non esiste un codice di Hamming con $k=2$ ($k=1,4,11,\dots$), quindi "gruppo di $L$ bit" va letto come "gruppo di bit" (qui $4$).

Teoria usata: Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo → e 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 → (punti 1 e 6), 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 →, 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 →, Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset → (punti 2-5), Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P_{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico → (punto 4). Un esercizio del corso sulla capacità del BSC: Esercizio 32 · capacità di canali gaussiano, binario simmetrico e a cancellazione (esercizio del corso).

(1) Rate di informazione e $L$

L'alfabeto ha $4$ simboli, di cui uno ($d$) ha probabilità $0$. L'entropia è $$H=\frac12\log_22+\frac14\log_24+\frac14\log_24=\frac12+\frac12+\frac12=\frac32=1{,}5\ \text{bit per simbolo}$$ (il simbolo $d$ non contribuisce: $0\cdot\log_2\frac10=0$). Il rate di informazione è l'entropia per simbolo divisa per il periodo di simbolo (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 →): $$R=\frac{H}{T_s}=\frac{1{,}5\ \text{bit}}{2\cdot10^{-6}\ \text{s}}=750\ \text{kbit/s}.$$ La codifica di sorgente a lunghezza fissa deve distinguere tutti i simboli dell'alfabeto: $\lceil\log_24\rceil=2$ bit, quindi $L=2$. (Anche considerando solo i $3$ simboli di probabilità non nulla servirebbero $\lceil\log_23\rceil=2$ bit.) Il flusso binario che esce dal codificatore di sorgente è $\frac{2\ \text{bit}}{2\ \mu\text{s}}=1$ Mbit/s, maggiore dei $750$ kbit/s di informazione: l'efficienza è $\eta=\frac{1{,}5}{2}=0{,}75$.

(2) Matrici generatrice e di controllo di parità

Un codice di Hamming $(n,k)$ ha $n=2^m-1$ e $k=n-m$. Con $k=4$ si ha $m=3$, $n=7$: il codice è il $(7,4)$. La matrice di controllo di parità $H$ ($3\times7$) ha come colonne tutte le $7$ sequenze non nulle di $3$ bit; in forma sistematica $H=[\,P\,|\,I_3\,]$: le ultime $3$ colonne sono l'identità e le prime $4$ sono le sequenze di peso $\ge2$, $$H=\begin{bmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{bmatrix},\qquad P=\begin{bmatrix}1&1&0&1\\1&0&1&1\\0&1&1&1\end{bmatrix}.$$ La matrice generatrice sistematica ($7\times4$, $\mathbf c=G\mathbf b$) è $G=\begin{bmatrix}I_4\\P\end{bmatrix}$, cioè $$G=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&0&1\\1&0&1&1\\0&1&1&1\end{bmatrix}.$$ I primi $4$ bit della parola sono i bit di informazione e gli ultimi $3$ sono di parità: $c_5=b_1+b_2+b_4$, $c_6=b_1+b_3+b_4$, $c_7=b_2+b_3+b_4$ (somme modulo $2$). Controllo: $HG=0$ (verificato con Python). I $16$ parole di codice sono le $G\mathbf b$ al variare di $\mathbf b\in\{0,1\}^4$.

(3) Errori rilevati e corretti

La parola di peso minimo non nulla ha peso $3$ (per esempio $\mathbf b=[1,0,0,0]$ dà $[1,0,0,0,1,1,0]$): $d_{\min}=3$, uguale al peso minimo perché il codice è lineare. Il codice rileva $d_{\min}-1=2$ errori e corregge $\left\lfloor\frac{d_{\min}-1}2\right\rfloor=1$ errore (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 →).

(4) Probabilità di ricevere $\xi$ se si trasmette $\mathbf b=[1,0,1,0]^T$

Si codifica $\mathbf b$: $c_5=1+0+0=1$, $c_6=1+1+0=0$, $c_7=0+1+0=1$, quindi $$\mathbf c=G\mathbf b=[1\ 0\ 1\ 0\ 1\ 0\ 1]^T.$$ Si confronta con $\xi=[1\ 0\ 1\ 0\ 0\ 1\ 1]^T$: i bit uguali sono quelli in posizione $1,2,3,4,7$ (cinque) e i bit diversi quelli in posizione $5$ e $6$ (due). Sul canale binario simmetrico senza memoria gli errori sono indipendenti, quindi la probabilità è il prodotto: $P_{bit}$ per ogni bit invertito e $1-P_{bit}$ per ogni bit corretto (Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P_{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico →): $$P[\xi|\mathbf b]=P_{bit}^2(1-P_{bit})^5=10^{-8}\cdot(1-10^{-4})^5=9{,}995\cdot10^{-9}.$$

(5) Parola decodificata

La sindrome di $\xi$ è $s=H\xi$ (somme modulo $2$). Le tre righe di $H$ danno $$s_1=\xi_1+\xi_2+\xi_4+\xi_5=1+0+0+0=1,\quad s_2=\xi_1+\xi_3+\xi_4+\xi_6=1+1+0+1=1,\quad s_3=\xi_2+\xi_3+\xi_4+\xi_7=0+1+0+1=0,$$ cioè $s=[1\ 1\ 0]^T$. Non è nulla, quindi $\xi$ non è una parola di codice, e coincide con la prima colonna di $H$: l'errore di peso minimo (coset leader, Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset →) è sul primo bit, $\mathbf e=[1\ 0\ 0\ 0\ 0\ 0\ 0]^T$. La parola decodificata è $$\hat{\mathbf c}=\xi+\mathbf e=[0\ 0\ 1\ 0\ 0\ 1\ 1]^T,$$ che corrisponde ai bit di informazione $[0,0,1,0]^T$. Controllo: con $\mathbf b=[0,0,1,0]$ si ha $c_5=b_1+b_2+b_4=0$, $c_6=b_1+b_3+b_4=1$, $c_7=b_2+b_3+b_4=1$, quindi $\mathbf c=[0,0,1,0,0,1,1]$, uguale a $\hat{\mathbf c}$: è una parola di codice, a distanza $1$ da $\xi$. La parola effettivamente trasmessa, $[1,0,1,0,1,0,1]$, dista invece $2$ da $\xi$: il decodificatore sbaglia perché sono avvenuti $2$ errori e il codice ne corregge uno solo. È il comportamento atteso.

(6) Periodo di bit massimo per una probabilità d'errore piccola a piacere

Per il teorema di Shannon (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 →) una codifica di canale con probabilità d'errore residua piccola a piacere esiste se il rate dei bit da proteggere è al più la capacità del canale. I bit da proteggere sono quelli all'uscita del codificatore di sorgente: $R_b=1$ Mbit/s (un bit ogni $T_b=1\ \mu$s). La capacità del BSC con $P_{bit}=10^{-4}$ è $$C=\frac{1-h(10^{-4})}{T_c},\qquad h(10^{-4})=10^{-4}\log_2\tfrac1{10^{-4}}+0{,}9999\log_2\tfrac1{0{,}9999}=0{,}0013288+0{,}0001443=0{,}001473,$$ dove $T_c$ è il periodo di bit sul canale (dopo il codificatore di canale). Per un codice di rate $\frac kn$ si ha $R_b=\frac kn\cdot\frac1{T_c}$, cioè $\frac kn=R_bT_c$, e la condizione $\frac kn\le1-h$ dà $$R_bT_c\le1-h(10^{-4})=0{,}998527\ \Rightarrow\ T_c\le\frac{0{,}998527}{10^{6}\ \text{bit/s}}=0{,}9985\ \mu\text{s}\simeq9{,}99\cdot10^{-7}\ \text{s}.$$ Il periodo massimo è quindi circa $0{,}9985\ \mu$s (la soluzione del corso lo riporta come $9{,}99\cdot10^{-7}$ s, con un'entropia scritta $h(10^{-3})=0{,}0015$ invece di $h(10^{-4})=0{,}00147$: il valore è lo stesso).

Per un confronto: il codice di Hamming $(7,4)$ ha rate $\frac47$, quindi i bit sul canale hanno periodo $T_c=\frac47\cdot1\ \mu\text{s}=0{,}571\ \mu$s (sotto il massimo, come deve essere), ma la sua probabilità d'errore sulla parola, $1-(1-10^{-4})^7-7\cdot10^{-4}(1-10^{-4})^6\simeq21\cdot10^{-8}=2{,}1\cdot10^{-7}$, non è piccola a piacere: è fissata dal codice. Il teorema dice solo che esistono codici più lunghi (con $T_c$ fino a $0{,}9985\ \mu$s) che portano la probabilità d'errore sotto qualsiasi soglia.

(Verificato con Python: $H=1{,}5$ bit, $R=750$ kbit/s, $HG=0$, $d_{\min}=3$, $\mathbf c=[1,0,1,0,1,0,1]$, $P[\xi|\mathbf b]=9{,}995\cdot10^{-9}$, sindrome $[1,1,0]^T$, parola più vicina a $\xi$ a distanza $1$, $1-h(10^{-4})=0{,}998527$, probabilità d'errore sulla parola di Hamming $2{,}099\cdot10^{-7}$.)

Errori comuni

• Usare $\log_23$ per $L$: con una lunghezza fissa i bit sono un numero intero, $\lceil\log_2M\rceil=2$.
• Confondere il rate di informazione ($750$ kbit/s, entropia) con quello nominale ($1$ Mbit/s, lunghezza fissa).
• Per il punto 4, dimenticare di codificare $\mathbf b$ (la sequenza trasmessa è $\mathbf c=G\mathbf b$, di $7$ bit) o contare male le posizioni diverse.
• Nel calcolare la sindrome sbagliare le somme (sono modulo $2$) o confrontare con la colonna sbagliata di $H$.
• Al punto 6 usare $T_c=\frac47T_b$ (periodo del Hamming) al posto del massimo periodo permesso dal teorema.
• Dimenticare che la sindrome corregge un solo errore: con $2$ errori si decodifica la parola sbagliata.