Esercizio - codice (5,3) lineare dalle parole di codice, sindrome e periodo di simbolo massimo (esame dell'8 febbraio 2024, es. 175)

---

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 e matrice generatrice sistematica

I bit entrano a gruppi di $k=3$ e le parole hanno $n=5$ bit: rate $R=\frac kn=\frac35$. Le parole sono $2^k=8$; ne sono date $4$, e le altre si ottengono per linearità.

Perché bastano le parole date. $\mathbf c_1+\mathbf c_2=01101+10111=11010=\mathbf c_3$: la terza parola è somma delle prime due, quindi la dimensione dello spazio generato da $\mathbf c_1,\mathbf c_2,\mathbf c_3,\mathbf c_4$ è al massimo $3$. Le tre parole $\mathbf c_1,\mathbf c_2,\mathbf c_4$ sono indipendenti (le somme di ogni loro sottoinsieme non vuoto sono tutte parole non nulle, come mostra l'elenco qui sotto), quindi lo spazio ha dimensione esattamente $3$ e il codice è $$\mathcal C=\{00000,\ 00110,\ 01011,\ 01101,\ 10001,\ 10111,\ 11010,\ 11100\}$$ (i $8$ vettori di tutte le somme di $\mathbf c_1,\mathbf c_2,\mathbf c_4$; controllato con Python).

Forma sistematica. Servono le tre parole che hanno come primi tre bit $100$, $010$, $001$: saranno le colonne di $G$ (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 →, ogni colonna è una parola).

• primi bit $100$: $\mathbf c_4=10001$ (già data);
• primi bit $010$: $\mathbf c_3+\mathbf c_4=11010+10001=01011$;
• primi bit $001$: $\mathbf c_2+\mathbf c_4=10111+10001=00110$.

Scrivendo queste tre parole come colonne: $$G=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\0&1&1\\1&1&0\end{bmatrix}=\begin{bmatrix}I_3\\A\end{bmatrix},\qquad A=\begin{bmatrix}0&1&1\\1&1&0\end{bmatrix}.$$

2. Matrice di controllo di parità, errori rivelati e corretti

$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&0&0&1\end{bmatrix}.$$ (Controllo: $HG=0$ e $H$ annulla tutte le $8$ parole.)

I pesi delle parole non nulle sono $00110\to2$, $01011\to3$, $01101\to3$, $10001\to2$, $10111\to4$, $11010\to3$, $11100\to3$. Quindi $d_{min}=w_{min}=2$ e il codice

• rivela sempre $d_{min}-1=1$ errore;
• corregge sempre $\lfloor\frac{2-1}2\rfloor=0$ errori.

(Dalle colonne di $H$: $[0,1]^T,[1,1]^T,[1,0]^T,[1,0]^T,[0,1]^T$; ci sono colonne uguali ($\mathbf h_3=\mathbf h_4$, $\mathbf h_1=\mathbf h_5$), quindi $d_{min}\le2$.)

3. Decodifica di $\boldsymbol\xi=[1,0,1,0,0]^T$

Sindrome: $$\boldsymbol\sigma=H\boldsymbol\xi=\begin{bmatrix}\xi_2+\xi_3+\xi_4\\\xi_1+\xi_2+\xi_5\end{bmatrix}=\begin{bmatrix}0+1+0\\1+0+0\end{bmatrix}=\begin{bmatrix}1\\1\end{bmatrix}.$$ È diversa da $\mathbf 0$. Nelle colonne di $H$ la sequenza $[1,1]^T$ compare una sola volta, alla colonna $2$: il coset leader di peso $1$ è unico, $\boldsymbol\varepsilon=[0,1,0,0,0]^T$ (le sindromi $[1,0]^T$ e $[0,1]^T$ invece hanno due leader ciascuna: sarebbero errori non correggibili in modo unico). La parola decodificata è $$\hat{\mathbf c}=\boldsymbol\xi+\boldsymbol\varepsilon=[1,0,1,0,0]^T+[0,1,0,0,0]^T=[1,1,1,0,0]^T,$$ che appartiene a $\mathcal C$: con $G$, $\mathbf b=[1,1,1]^T$ dà $\mathbf g_1+\mathbf g_2+\mathbf g_3=[1,0,0,0,1]^T+[0,1,0,1,1]^T+[0,0,1,1,0]^T=[1,1,1,0,0]^T$. Poiché $G$ è sistematica, i primi tre bit sono i bit decodificati: $\hat{\mathbf b}=[1,1,1]^T$.

4. Probabilità di ricevere $\boldsymbol\xi$ trasmettendo $\mathbf c_1$

$\mathbf c_1=01101$ e $\boldsymbol\xi=10100$ differiscono nelle posizioni $1$, $2$ e $5$ (nelle posizioni $3$ e $4$ coincidono: $1,1$ e $0,0$): $d_H=3$. Sul BSC senza memoria (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_1]=P_{bit}^{\,3}(1-P_{bit})^{\,2}=10^{-9}\cdot0{,}999^2=9{,}98\cdot10^{-10}.$$

5. Periodo di simbolo massimo sul canale

La sorgente emette un bit ogni $10^{-5}$ s: bit-rate di informazione $R_b=\frac{1}{10^{-5}}=100$ kbit/s (bit equiprobabili: $1$ bit di informazione per simbolo). 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 →) la probabilità d'errore residua può essere piccola a piacere se $R_b<C$, con $$C=\frac{1-h(P_{bit})}{T}\ \text{bit/s},\qquad h(10^{-3})=0{,}011408,$$ dove $T$ è il periodo di simbolo sul canale. La condizione è $$\frac{1-0{,}011408}{T}>10^5\ \Longrightarrow\ T<\frac{0{,}988592}{10^5}=9{,}886\cdot10^{-6}\ \text{s}.$$ Il periodo di simbolo massimo è circa $9{,}9\ \mu$s: poco meno dei $10\ \mu$s della sorgente, perché il canale sbaglia raramente e $1-h(P_{bit})=0{,}9886$ è vicino a $1$.

Osservazione. Con il codice $(5,3)$ di questo esercizio, per tenere il passo della sorgente basterebbe un periodo $T=\frac35\cdot10^{-5}=6\ \mu$s, ben dentro il limite; ma il codice $(5,3)$ non porta la probabilità d'errore a "piccola a piacere": la probabilità di parola errata, dalla tabella dei coset, è $P(E)=1-(1-p)^5-3p(1-p)^4=2{,}0\cdot10^{-3}$ a $p=10^{-3}$, contro $3\cdot10^{-3}$ per $3$ bit senza codice (Python). Serve un codice più lungo, come garantisce il teorema.

Errori comuni

• Prendere $\mathbf c_1,\dots,\mathbf c_4$ come le parole di un codice con $k=2$ perché sono quattro: sono dipendenti ($\mathbf c_3=\mathbf c_1+\mathbf c_2$) e il codice ha $2^3=8$ parole.
• Costruire $G$ con le righe uguali alle parole date: in questo corso le parole sono le colonne di $G$, che deve avere forma $\begin{bmatrix}I\\A\end{bmatrix}$.
• Dedurre dalla sindrome $[1,0]^T$ un errore preciso: con due colonne uguali non si può correggere.
• Usare $T=10^{-5}$ s come periodo del canale: è quello della sorgente; $T$ del canale è l'incognita.