Esercizio - codice (5,3) non sistematico, matrice di parità e sindrome su BSC (secondo compitino del 9 gennaio 2026, es. 195)

---

Teoria usata: 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 →, 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 →, 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 →, 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 →.

1. Rate, linearità, forma sistematica

Rate. Entrano $k=3$ bit e escono $n=5$ bit: $R=\frac kn=\frac35$.

Linearità. Un codice è lineare se ogni bit di parola è una somma modulo 2 di bit di informazione, senza costanti e senza prodotti. $c_1,c_2,c_3,c_5$ lo sono già. Resta $c_4=\|\mathbf b\|_H\bmod2$: il peso di Hamming $\|\mathbf b\|_H$ è il numero di $1$ in $\mathbf b$, cioè $b_1+b_2+b_3$ calcolato in $\mathbb Z$; prenderlo modulo $2$ dà la parità di quel numero, che è proprio la somma modulo $2$ dei tre bit. Quindi $$c_4=b_1+b_2+b_3\pmod 2$$ e il codice è lineare. La matrice generatrice $G'$ ($5\times3$) ha per righe i coefficienti delle equazioni: $$G'=\begin{bmatrix}1&0&0\\1&1&0\\0&0&1\\1&1&1\\0&1&1\end{bmatrix}\qquad(\text{riga }1:\ c_1=b_1;\ \text{riga }2:\ c_2=b_1+b_2;\ \dots).$$

Sistematico? No: in un codice sistematico i primi tre bit della parola sono $b_1,b_2,b_3$, qui $c_2=b_1+b_2\ne b_2$.

Forma sistematica con sole operazioni sulle colonne. Le operazioni sulle colonne di $G'$ non cambiano il codice, solo la corrispondenza $\mathbf b\to\mathbf c$ (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 →). Servono le prime tre righe uguali all'identità. Le prime due righe sono $[1,0,0]$ e $[1,1,0]$: per far diventare la seconda $[0,1,0]$ occorre togliere un "$1$" in prima colonna. Si sostituisce la prima colonna con la somma della prima e della seconda: $$\text{col}_1\leftarrow\text{col}_1+\text{col}_2=\begin{bmatrix}1\\1\\0\\1\\0\end{bmatrix}+\begin{bmatrix}0\\1\\0\\1\\1\end{bmatrix}=\begin{bmatrix}1\\0\\0\\0\\1\end{bmatrix}.$$ Si ottiene $$G=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\0&1&1\\1&1&1\end{bmatrix}=\begin{bmatrix}I_3\\A\end{bmatrix},\qquad A=\begin{bmatrix}0&1&1\\1&1&1\end{bmatrix}.$$

Controllo (Python): le $8$ parole di $G'$ e di $G$ sono le stesse.

Cambia solo quale $\mathbf b$ produce quale parola (per $\mathbf b=100$: $11010$ con $G'$, $10001$ con $G$), l'insieme $\mathcal C$ è lo stesso.

2. Distanza minima, peso minimo, errori rivelati e corretti

I pesi delle $7$ parole non nulle sono $3,3,2,3,4,2,3$ (dalla tabella: $00111\to3$, $01011\to3$, $01100\to2$, $11010\to3$, $11101\to4$, $10001\to2$, $10110\to3$). Il peso minimo è $w_H(\mathcal C)=2$ e, essendo il codice lineare, la distanza minima è $d_{min}=2$ (due parole sono $01100$ e $10001$).

• Errori rivelati sempre: $d_{min}-1=1$.
• Errori corretti sempre: $\left\lfloor\frac{d_{min}-1}{2}\right\rfloor=\left\lfloor\frac12\right\rfloor=0$.

3. Due sequenze ricevute

Si trasmette $\mathbf b=[0,0,0]^T$, quindi la parola è $\mathbf c=\mathbf 0=[0,0,0,0,0]^T$. Su un BSC la probabilità di ricevere una sequenza dipende solo da quanti bit sono diversi, non da quali (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[\boldsymbol\xi\mid\mathbf c]=P_{bit}^{\,d_H}(1-P_{bit})^{\,5-d_H}.$$ $\boldsymbol\xi_1=10100$ ha due $1$ (posizioni $1$ e $3$) e $\boldsymbol\xi_2=00110$ ha due $1$ (posizioni $3$ e $4$): in entrambi i casi $d_H(\boldsymbol\xi,\mathbf 0)=2$. Quindi le due sequenze sono equiprobabili, con $$P[\boldsymbol\xi_1]=P[\boldsymbol\xi_2]=P_{bit}^2(1-P_{bit})^3=10^{-6}\cdot0{,}999^3=9{,}97\cdot10^{-7}.$$

4. Matrice di controllo di parità e decodifica

Dalla $G$ sistematica si legge $H=[A\mid I_2]$ (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 →): $$H=\begin{bmatrix}0&1&1&1&0\\1&1&1&0&1\end{bmatrix}.$$ Verifica $HG=0$, riga per colonna (le colonne di $G$ sono $[1,0,0,0,1]^T$, $[0,1,0,1,1]^T$, $[0,0,1,1,1]^T$):

• riga $[0,1,1,1,0]$: $0+0+0+0+0=0$, $\ 0+1+0+1+0=2\equiv0$, $\ 0+0+1+1+0=2\equiv0$;
• riga $[1,1,1,0,1]$: $1+0+0+0+1=2\equiv0$, $\ 0+1+0+0+1=2\equiv0$, $\ 0+0+1+0+1=2\equiv0$.

Il prodotto è la matrice nulla $2\times3$ (controllato anche con Python).

Sindrome. Per $\boldsymbol\xi=[1,1,1,1,1]^T$: $$\boldsymbol\sigma=H\boldsymbol\xi=\begin{bmatrix}0+1+1+1+0\\1+1+1+0+1\end{bmatrix}=\begin{bmatrix}3\\4\end{bmatrix}=\begin{bmatrix}1\\0\end{bmatrix}\pmod2.$$ È diversa da $\mathbf 0$: $\boldsymbol\xi$ non è una parola. La sindrome $[1,0]^T$ è la colonna $4$ di $H$ e nessun'altra colonna le è uguale (le colonne sono $[0,1],[1,1],[1,1],[1,0],[0,1]$): il coset leader è unico, $\boldsymbol\varepsilon_{min}=[0,0,0,1,0]^T$.

Parola e bit decodificati. $$\hat{\mathbf c}=\boldsymbol\xi+\boldsymbol\varepsilon_{min}=[1,1,1,1,1]^T+[0,0,0,1,0]^T=[1,1,1,0,1]^T.$$ È una parola di codice ($\mathbf b=111$ con $G$ dà proprio $11101$). Poiché $G$ è sistematica, $\hat{\mathbf b}$ sono i primi $k=3$ bit: $$\hat{\mathbf b}=[1,1,1]^T.$$

5. Probabilità d'errore residua 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 →) esiste una codifica a errore residuo piccolo a piacere se il bit-rate di informazione della sorgente è minore della capacità del canale.

Sorgente. Emette un simbolo ogni $20\ \mu$s da un alfabeto di $3$ simboli. Il massimo dell'informazione per simbolo è $\log_2 3=1{,}585$ bit (a simboli equiprobabili): bit-rate al più $$R_b=\frac{\log_23}{20\cdot10^{-6}}=79{,}25\ \text{kbit/s}.$$ (Se i simboli non fossero equiprobabili l'entropia sarebbe minore, e la condizione ancora più facile.)

Canale. BSC con $P_{bit}=10^{-3}$ e un bit ogni $T=10\ \mu$s: $$h(10^{-3})=-10^{-3}\log_210^{-3}-0{,}999\log_20{,}999=0{,}01141,\qquad C=\frac1T[1-h(P_{bit})]=\frac{1-0{,}01141}{10^{-5}}=98{,}86\ \text{kbit/s}.$$

$R_b=79{,}25<C=98{,}86$ kbit/s: sì, è possibile (con un codice molto più lungo di questo $(5,3)$; il $(5,3)$ non lo fa, perché non corregge nessun errore).

Errori comuni

• Trattare $\|\mathbf b\|_H$ come termine non lineare: modulo $2$ vale $b_1+b_2+b_3$.
• Per ottenere la forma sistematica scambiare righe di $G'$: qui servirebbe una riga $[0,1,0]$ che non c'è; si usa la somma di colonne.
• Dedurre dalla distanza minima $2$ che il codice "corregge un errore": $\lfloor\frac{2-1}2\rfloor=0$.
• Confrontare la capacità con il rate del codice invece che con il bit-rate dell'informazione della sorgente.