Esercizio - canale binario con errori diversi sui bit pari e dispari (compito del 25 giugno 2024, es. 179)

---

Teoria usata: 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-4, capacità del BSC e canali in parallelo), 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 → (entropia binaria), 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 → (punto 5). Altre capacità: Esercizio 32 · capacità di canali gaussiano, binario simmetrico e a cancellazione (esercizio del corso).

(1) Quando il canale è binario simmetrico senza memoria

Un canale binario simmetrico senza memoria è descritto, per ogni bit, dalla stessa matrice di transizione $$\begin{bmatrix}1-P_{bit}&P_{bit}\\P_{bit}&1-P_{bit}\end{bmatrix},$$ con una sola probabilità d'errore $P_{bit}$, uguale per l'ingresso $0$ e per l'ingresso $1$ (simmetria) e costante nel tempo (il canale è sempre lo stesso a ogni uso, senza memoria).

Qui l'errore non dipende dal bit trasmesso (il canale è simmetrico a ogni istante), ma dipende dal tempo: $P_P$ per $n$ pari, $P_D$ per $n$ dispari. Il canale complessivo è un BSC senza memoria se e solo se $P_P=P_D$, per qualunque valore comune ($0\le P_P=P_D\le1$). Se $P_P\ne P_D$ la matrice cambia da un istante al successivo, quindi non è un BSC stazionario (è un canale periodico a due fasi).

(2) Capacità con $P_P=P_D=0{,}1$

Con $P_P=P_D=0{,}1$ si ha un BSC con $P_{bit}=0{,}1$ e $T_b=1$ ms. La capacità è (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=\frac{1-h(P_{bit})}{T_b},\qquad h(0{,}1)=0{,}1\log_2\tfrac1{0{,}1}+0{,}9\log_2\tfrac1{0{,}9}=0{,}3322+0{,}1368=0{,}4690,$$ $$C=\frac{1-0{,}4690}{10^{-3}\ \text{s}}=531\ \text{bit/s}.$$ (Calcolata anche massimizzando numericamente $I(b;\hat b)$ su $P_b(0)$: il massimo è in $P_b(0)=0{,}5$ e vale $0{,}5310$ bit per uso.)

(3) Probabilità d'errore media con $P_P=0{,}1$ e $P_D=0{,}2$

Metà dei bit (quelli ai tempi pari) è sbagliata con probabilità $0{,}1$ e metà (quelli ai tempi dispari) con probabilità $0{,}2$, quindi la probabilità d'errore media su un bit qualsiasi è $$P(E)=\frac12\cdot0{,}1+\frac12\cdot0{,}2=0{,}15.$$ La media si fa con pesi uguali ($\frac12$ e $\frac12$) perché pari e dispari sono ugualmente frequenti.

Osservazione. La capacità di questo canale non è quella del BSC con $P_{bit}=0{,}15$. Con i risultati del punto 4 (canali paralleli): $C=\frac1{2T_b}\left[(1-h(0{,}1))+(1-h(0{,}2))\right]=500\cdot(0{,}5310+0{,}2781)=404{,}5$ bit/s, mentre il BSC con $0{,}15$ avrebbe $1000\cdot(1-h(0{,}15))=1000\cdot0{,}3902=390{,}2$ bit/s. La differenza viene dal fatto che $h$ è concava: la media delle entropie è minore dell'entropia della media, quindi conoscere quali bit sono più affidabili vale qualcosa.

(4) Capacità con $P_P=0{,}1$ e $P_D=0$: canali paralleli

Si divide il canale in due canali indipendenti, uno per i bit pari e uno per i dispari, ciascuno usato una volta ogni $2T_b$:

• canale dei bit pari: BSC con $P_{bit}=0{,}1$ e periodo di simbolo $T_b'=2T_b=2$ ms. La sua capacità è la metà di quella del punto 2: $$C_P=\frac{1-h(0{,}1)}{2T_b}=\frac{0{,}5310}{2\cdot10^{-3}\ \text{s}}=265{,}5\ \text{bit/s};$$
• canale dei bit dispari: senza errori ($P_D=0$), quindi ogni uso trasporta $1$ bit: $$C_D=\frac{1}{2T_b}=500\ \text{bit/s}.$$

La capacità del canale complessivo è la somma: le informazioni mutue dei due canali si sommano quando gli ingressi sono scelti in modo indipendente, e il massimo si raggiunge massimizzando ciascuna separatamente (ingresso uniforme per il canale pari, qualunque ingresso uniforme per il dispari): $$C_{\text{tot}}=C_P+C_D=265{,}5+500=765{,}5\ \text{bit/s}.$$ Si usano un codificatore e un decodificatore separati per i due canali. Il risultato sta tra la capacità del BSC con $0{,}1$ su tutti i bit ($531$ bit/s) e quella del canale ideale ($1000$ bit/s).

(5) Hamming $(7,4)$ con $m$ bit nei tempi pari

Un codice di Hamming ha distanza minima $d_{\min}=3$ e corregge sempre $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 →). I bit nei tempi dispari non sono mai in errore ($P_D=0$). Gli errori possono quindi colpire solo gli $m$ bit della parola di codice trasmessi nei tempi pari.

• Con $m\le1$ la parola ha al più un errore: il decodificatore lo corregge sempre, quindi la parola decodificata è sempre esatta, qualunque sia la realizzazione degli errori.
• Con $m=2$ i due bit pari possono essere entrambi sbagliati (con probabilità $0{,}1^2=0{,}01$). Con due errori la sindrome è non nulla (perché $d_{\min}=3>2$) e coincide con la colonna di un terzo bit, che il decodificatore inverte per errore: la parola decodificata è sbagliata. Quindi non c'è garanzia.

Il massimo è $m=1$: un solo bit della parola di $7$ deve passare dai tempi pari, e gli altri $6$ dai dispari.

(Verificato con Python: $1-h(0{,}1)=0{,}53100$, massimo di $I$ in $P_b(0)=0{,}5$, $C_{\text{tot}}=265{,}5+500=765{,}5$ bit/s, $C$ del canale con $0{,}1$ e $0{,}2$ $=404{,}5$ bit/s contro $390{,}2$ del BSC con $0{,}15$. La soluzione del corso riporta gli stessi valori.)

Errori comuni

• Dire che il canale è BSC per qualunque $(P_P,P_D)$: serve $P_P=P_D$.
• Per i canali paralleli, dimenticare di dividere per $2$ il periodo di simbolo: ciascun canale è usato una volta ogni $2T_b$.
• Prendere come capacità del canale alternato quella del BSC con probabilità media: per la concavità di $h$ il risultato è diverso (maggiore).
• Al punto 5 pensare che basti la probabilità: serve una garanzia sempre, cioè il caso peggiore, che è il massimo numero di errori possibile in una parola.
• Dimenticare che con $2$ errori un Hamming non rileva solo ma corregge male.