Esercizio - porta parallela a 8 pin, Hamming (7,4), coset e canale con pin guasto (esame del 15 febbraio 2023, es. 157)

---

Teoria usata: 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 →, 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 →, 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. Il codice di Hamming per otto pin

Una parola di codice deve entrare intera nella porta: la lunghezza è $n\le8$. I codici di Hamming hanno $n=2^m-1$ con $m=n-k$ bit di parità (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 →): $n=3$ ($m=2$), $n=7$ ($m=3$), $n=15$ ($m=4$), ... Con $n\le8$ restano $n=3$ e $n=7$. Il numero di parole è $2^k$, quindi si prende il $k$ più grande, quello di $n=7$: $$n=7,\qquad k=n-m=7-3=4,\qquad 2^4=16\ \text{parole}.$$ (Con $n=3$, $k=1$, si avrebbero solo $2$ parole.) Ogni codice di Hamming ha $d_{min}=3$, quindi rivela sempre $d_{min}-1=2$ errori (e ne corregge $1$). Il bound di Hamming con $t=1$ vale con l'uguaglianza: $2^4\cdot(1+7)=2^7$.

2. Un coset e il numero di parole sulla porta

Il coset ha $4$ vettori di lunghezza $4$. I vettori di un coset sono $\boldsymbol\varepsilon_0+\mathbf c$ al variare di $\mathbf c\in\mathcal C$ (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 →), quindi i vettori di un coset sono tanti quanti le parole: $2^k=4$, cioè $k=2$, con $n=4$ (lunghezza dei vettori). Il codice è un $(4,2)$ e le sue parole sono le differenze dei vettori del coset (per esempio $0010+1000=1010$, $0010+0111=0101$, $0010+1101=1111$): $\mathcal C=\{0000,\ 1010,\ 0101,\ 1111\}$.

Coset leader. Sono i vettori di peso minimo del coset. I pesi sono $0010\to1$, $1000\to1$, $0111\to3$, $1101\to3$: i leader sono $0010$ e $1000$ (due leader, perché la sindrome è ripetuta tra due colonne di $H$).

Parole in parallelo. Ogni parola ha $n=4$ bit; la porta ha $8$ pin, quindi si possono trasmettere $\frac84=2$ parole di codice contemporaneamente (una su $4$ pin, una sugli altri $4$).

3. Rilevare il guasto di un pin

Se un pin non funziona, al ricevitore su quel pin si osserva $0$ o $1$ a caso: per quel bit la sequenza ricevuta ha un errore con probabilità $\frac12$ oppure no. In ogni caso al più un bit è sbagliato. Per rivelare sempre al più un errore serve $d_{min}\ge2$ (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 →).

Con $n=8$ si vuole il massimo $k$. Il bound di Singleton (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 →) dà $d_{min}\le n-k+1$, quindi $d_{min}\ge2$ richiede $n-k\ge1$: basta un solo bit di parità, $k=7$. Il bit di parità è la somma di tutti i bit di informazione: $c_8=c_1+\dots+c_7$, cioè la somma di tutti i bit della parola vale zero. La matrice di controllo ha una riga: $$H=\begin{bmatrix}1&1&1&1&1&1&1&1\end{bmatrix}.$$ Le colonne sono tutte uguali a $[1]$ (non nulle): $d_{min}=2$ (due $1$ in qualunque posizione sommano a zero), rivela $1$ errore, ne corregge $0$.

4. La capacità con il pin difettato

Il primo pin si comporta come un canale a cancellazione: con probabilità $0{,}2$ l'uscita è una cancellazione (non si sa se era $0$ o $1$) e con probabilità $0{,}8$ è esatta. Un canale binario a cancellazione con probabilità di cancellazione $\epsilon$ ha capacità $1-\epsilon$ bit per uso (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 →; per Ing. Elettronica Capacità di canale - canale binario simmetrico, a cancellazione e AWGNLa capacità $C=\max_{p_x}I(x;y)$ è il massimo di informazione mutua tra ingresso e uscita del canale; per il teorema di Shannon si può comunicare con probabilità d'errore arbitrariamente piccola se e solo se il rate è minore di $C$. Per il canale binario simmetrico $C=1-H_2(p)$ bit per uso (ingresso uniforme), per il canale a cancellazione $C=1-\varepsilon$, per l'AWGN $C=\frac12\log_2(1+\text{SNR})$ per uso reale, cioè $C=B\log_2(1+\text{SNR})$ bit/s su una banda $B$. Il limite $R_b<C$ dà il minimo $\frac{E_b}{N_0}\ge\frac{2^\nu-1}\nu$ ($-1{,}59$ dB per $\nu\to0$).Capacità di canale - canale binario simmetrico, a cancellazione e AWGN →): $$C_1=1-0{,}2=0{,}8\ \text{bit per uso}.$$ Gli altri $7$ pin sono senza errore: ciascuno ha capacità $1$ bit per uso. I pin sono indipendenti e l'informazione mutua tra ingresso e uscita dell'intera porta è la somma di quelle dei singoli pin (l'uscita di ogni pin dipende solo dal suo ingresso), quindi si massimizza ciascuna e si sommano: $$C=7\cdot1+0{,}8=7{,}8\ \text{bit per uso della porta}.$$ Con $10^3$ usi al secondo per pin: $$C=10^3\cdot7{,}8=7{,}8\ \text{kbit/s}.$$ (Per confronto, senza guasto la capacità è $8$ kbit/s.)

Errori comuni

• Trasmettere una parola di Hamming su più di un ciclo della porta: la lunghezza $n$ deve essere $\le8$; $n=15$ non entra.
• Confondere i vettori del coset (lunghi $n$) con i bit di informazione: la lunghezza di un vettore del coset è $n$, e il numero di vettori è $2^k$.
• Per un pin "casuale" chiedere $d_{min}\ge3$: un solo bit sbagliato si rivela con $d_{min}=2$; serve $d_{min}=3$ solo per correggerlo.
• Calcolare la capacità del pin difettato come $1-h(0{,}2)$ (canale binario simmetrico): qui l'errore è una cancellazione e vale $1-0{,}2$.