Esercizio - codice non lineare a quattro parole, distanza 2 e bound di Singleton (esame del 21 giugno 2023, es. 159)

---

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

1. Una parola a distanza 2 da tutte

Le parole hanno lunghezza $4$, quindi la nuova parola $\mathbf w=[w_1,w_2,w_3,w_4]$ deve avere $4$ bit. Le tre parole di $\mathcal C$ sono tra loro a distanza $2$ ($d_H(0011,0101)=2$ nelle posizioni $2,3$; $d_H(0011,1001)=2$ nelle posizioni $1,3$; $d_H(0101,1001)=2$ nelle posizioni $1,2$), e hanno tutte l'ultimo bit uguale a $1$ e un solo $1$ nei primi tre bit ($001$, $010$, $100$).

Caso $w_4=1$. L'ultimo bit coincide con quello di tutte le parole: la distanza è quella dei primi tre bit. Servono $w_1w_2w_3$ a distanza $2$ da $001$, $010$ e $100$. Il vettore $000$ è a distanza $1$ da tutti: no. Il vettore $111$ è a distanza $2$ da tutti ($111$ contro $001$ differisce in $2$ posizioni): sì. Quindi $\mathbf w=1111$.

Caso $w_4=0$. L'ultimo bit differisce da quello delle parole: contribuisce $1$ alla distanza, e i primi tre bit devono essere a distanza $1$ da $001,010,100$: il vettore $000$ lo è (un solo $1$ da cambiare). Quindi $\mathbf w=0000$.

Le sequenze possibili sono dunque $0000$ e $1111$ (Python: nessun'altra tra le $16$). Si sceglie $\mathbf w=0000$, e $\mathcal C'=\{0011,0101,1001,0000\}$.

2. Errori rivelati e corretti

In $\mathcal C'$ tutte le coppie di parole sono a distanza $2$: $d_H(0000,0011)=d_H(0000,0101)=d_H(0000,1001)=2$ (i pesi sono $2$) e le tre distanze tra le parole originali. Quindi $d_{min}=2$.

• a) Trasmettendo la parola nuova $0000$ la parola più vicina tra le altre è a distanza $2$: un errore singolo si rileva (la sequenza ricevuta, a distanza $1$ da $0000$, non è una parola); non si corregge, perché la sequenza ottenuta è a distanza $1$ da altre parole: per esempio $0001$ è a distanza $1$ da $0000$, $0011$, $0101$ e $1001$, tutte e quattro. Rivelati $1$, corretti $0$.
• b) Per una parola qualsiasi di $\mathcal C'$ la distanza minima dalle altre è $2$: stessi numeri, rivelati $d_{min}-1=1$, corretti $\lfloor\frac{2-1}2\rfloor=0$.

3. $\mathcal C'$ è lineare?

No. Un codice lineare è chiuso rispetto alla somma modulo $2$ (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 →), ma $$0011+0101=0110\notin\mathcal C'.$$ (Contiene sì la parola nulla, ma questo da solo non basta: serve la chiusura per tutte le somme.) Anche $\mathcal C$ non è lineare (non contiene $\mathbf 0$ e ha $3$ parole: non è una potenza di $2$).

4. Un codice lineare con $4$ parole che corregge $2$ errori?

Un codice lineare con $4=2^k$ parole ha $k=2$; la lunghezza è $n=4$. Per correggere $2$ errori serve $d_{min}\ge2t+1=5$. Il bound di Singleton dà $$d_{min}\le n-k+1=4-2+1=3<5.$$ No, non può esistere (servirebbero almeno $n-k\ge2t=4$ bit di parità, cioè $n\ge6$).

5. L'ultimo bit è utile?

Tutte le parole di $\mathcal C$ hanno l'ultimo bit uguale a $1$: quel bit non distingue una parola dall'altra e non porta informazione. Sul BSC senza memoria gli errori sui bit sono indipendenti: la verosimiglianza di una sequenza ricevuta data una parola è il prodotto dei fattori dei singoli bit, e il fattore dell'ultimo bit è lo stesso per tutte le parole (dipende solo dal valore ricevuto, $1-P_{bit}$ o $P_{bit}$). Nel confronto tra le parole quel fattore si semplifica: la decisione e la probabilità di errore non cambiano se si toglie il bit. Il codice $\{001,010,100\}$ che si ottiene ha le stesse distanze ($2$ tra tutte le coppie).

Controllo numerico (Python, parole equiprobabili, ML): $P(\text{decisione corretta})=0{,}84$ per $P_{bit}=0{,}1$ con e senza l'ultimo bit, $0{,}9834$ per $P_{bit}=0{,}01$ in entrambi i casi. L'ultimo bit riconosce solo l'errore su se stesso, e non serve a ridurre la probabilità d'errore sulla decisione: no, non è utile (peggiora solo il rate, $R=\frac{\log_23}{4}$ invece di $\frac{\log_23}3$).

Errori comuni

• Cercare la nuova parola solo guardando una coppia: serve la distanza $2$ da tutte le parole.
• Dire che $\mathcal C'$ è lineare perché ora contiene $\mathbf 0$: la somma $0011+0101$ non è nel codice.
• Applicare Singleton a un codice non lineare: vale per i lineari (nel punto 4 il codice è lineare per ipotesi).
• Dire che l'ultimo bit "aumenta la distanza": la distanza tra due parole non cambia se si toglie un bit uguale in tutte.