Esercizio 31codice a blocco non lineare, distanza minima e decodifica su un canale binario simmetrico (tema d'esame giugno 2017)

---

Teoria usata: 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 →, 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 →, Informazione ed entropiaL'informazione di un evento di probabilità $p$ è $\log_2\frac1p$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza della sorgente: $0\le H\le\log_2M$, con il massimo quando i simboli sono equiprobabili. Per più simboli: $H(x,y)\le H(x)+H(y)$ (uguaglianza se indipendenti), $H(x|y)=H(x,y)-H(y)$. Per una sorgente con $F_s$ simboli al secondo il rate di informazione è $F_sH_s$, il rate nominale $F_s\log_2M$ e l'efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione ed entropia →.

(1) Blocco, lineare, sistematico

• a) A blocco: sì. A ogni blocco di $k=2$ bit di informazione si associa una parola di $n=4$ bit: codice $(4,2)$, rendimento $R_c=\frac12$.
• b) Lineare: no. Un codice è lineare se la somma di due parole è una parola. $01\oplus10=11$, che dovrebbe corrispondere alla somma delle parole $0111\oplus1011=1100$, ma la parola associata a $11$ è $1110\ne1100$. La somma di due parole valide non è una parola valida: non è lineare. (Per questo la minima distanza non si ottiene dal peso minimo, ma da tutte le coppie.)
• c) Sistematico: sì. I primi $2$ bit della parola di codice coincidono con i bit di informazione ($00\to\mathbf{00}00$, $01\to\mathbf{01}11$, $10\to\mathbf{10}11$, $11\to\mathbf{11}10$); gli ultimi $2$ sono le parità. (Un codice può essere sistematico senza essere lineare.)

(2) Errori rivelabili

Distanze di Hamming tra le $4$ parole ($d_H=w_H(\mathbf c\oplus\mathbf c')$):

$d_{min}=2$. Il codice rivela con certezza $d_{min}-1=\mathbf1$ errore (e ne corregge $\lfloor\frac{2-1}2\rfloor=0$): con un solo bit sbagliato la parola ricevuta è a distanza $1$ dalla trasmessa, quindi non è una parola di codice (tutte le parole distano almeno $2$).

(3) Efficienza della sorgente

La sorgente binaria ha entropia $H(b)=\frac14\log_24+\frac34\log_2\frac43=0{,}5+0{,}311=0{,}811$ bit/simbolo, contro il massimo $\log_22=1$ bit (Informazione ed entropiaL'informazione di un evento di probabilità $p$ è $\log_2\frac1p$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza della sorgente: $0\le H\le\log_2M$, con il massimo quando i simboli sono equiprobabili. Per più simboli: $H(x,y)\le H(x)+H(y)$ (uguaglianza se indipendenti), $H(x|y)=H(x,y)-H(y)$. Per una sorgente con $F_s$ simboli al secondo il rate di informazione è $F_sH_s$, il rate nominale $F_s\log_2M$ e l'efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione ed entropia →): $$\eta=\frac{H(b)}{\log_2M}=0{,}811.$$ (Si noti che questa è l'efficienza della sorgente prima della codifica di canale; il codice $(4,2)$ ha rendimento $\frac12$ e aggiunge ridondanza, riducendo il rate di informazione per bit trasmesso.)

(4) Probabilità d'errore di decodifica per $\mathbf b=[00]$

Si trasmette la parola $0000$. Il canale inverte ciascun bit con probabilità $0{,}1$ in modo indipendente: la ricevuta $\mathbf r$ ha probabilità $0{,}1^{w}\,0{,}9^{4-w}$, con $w$ il peso di $\mathbf r$. Decodifica a minima distanza: si sceglie la parola di codice più vicina a $\mathbf r$. Si analizzano le $16$ possibili $\mathbf r$:

• $w=0$ ($0000$): distanza $0$ da $0000$: corretta; probabilità $0{,}9^4=0{,}6561$.
• $w=1$ ($0001,0010,0100,1000$): distanza $1$ da $0000$ e almeno $2$ da tutte le altre: corretta; probabilità $4\cdot0{,}1\cdot0{,}9^3=0{,}2916$.
• $w=2$ ($0011,0101,0110,1001,1010,1100$): ognuna è a distanza $1$ da una delle altre parole ($0011$ da $0111$, $0101$ da $0111$, $0110$ da $0111$, $1001$, $1010$ da $1011$, $1100$ da $1110$) e a distanza $2$ da $0000$: si decide un'altra parola, errore; probabilità $6\cdot0{,}1^2\cdot0{,}9^2=0{,}0486$.
• $w=3,4$ ($0111,1011,1101,1110,1111$): $0111,1011,1110$ sono parole di codice diverse da $0000$; $1101$ e $1111$ sono a distanza $\ge2$ da $0000$ e più vicine ad altre: errore; probabilità $4\cdot0{,}1^3\cdot0{,}9+0{,}1^4=0{,}0037$.

$$P[\text{corretta}\mid\mathbf b=00]=0{,}6561+0{,}2916=0{,}9477,\qquad P[\text{errore di parola}\mid\mathbf b=00]=1-0{,}9477=0{,}0523.$$ (Nessuna ricevuta è a pari distanza da $0000$ e da un'altra parola, quindi il risultato non dipende dalla regola sui pareggi.) Con la parola $0000$ trasmessa gli errori singoli vengono corretti, perché $0000$ dista $3$ da tutte le altre parole; per le altre parole (a distanza $2$ tra loro) un errore singolo può cadere a metà strada tra due parole e la decisione è ambigua. Il valore calcolato è dunque condizionato a $\mathbf b=[00]$: mediando sulle quattro parole (con scelta casuale nei pareggi) l'errore di parola vale $0{,}141$: $0{,}052$ per $0000$ e $0{,}171$ per ciascuna delle altre tre. Senza codifica, per confronto, la probabilità di sbagliare almeno uno dei $2$ bit è $1-0{,}9^2=0{,}19$.

(Verificato con Python: enumerazione delle $16$ ricevute, $P[\text{corretta}]=0{,}9477$, $\eta=0{,}8113$.)

Errori comuni

• Dire che il codice è lineare perché contiene la parola nulla: serve la chiusura per la somma.
• Dire che è sistematico $\Rightarrow$ lineare (non è vero).
• Rispondere $2$ errori rivelati ($d_{min}$ al posto di $d_{min}-1$).
• Calcolare la probabilità di errore con la formula di un codice correttore ($t=1$): qui $d_{min}=2$ non garantisce la correzione.