Esercizio - Codici (4,2) lineari o no e probabilità di errore non rivelato

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (scheda "Channel coding"). Si considerino due mappe di codifica $\mu_1$ e $\mu_2$, entrambe $(4,2)$, con i bit di informazione nelle posizioni $1$ e $2$ delle parole di codice. Per $\mu_1$, per $j=3,4$ il $j$-esimo bit è $1$ se il peso globale dei primi $j-1$ bit è minore di $2$, $0$ altrimenti. Per $\mu_2$, per $j=3,4$ il $j$-esimo bit è la parità dei bit in posizione $j-1$ e $j-2$. a. Questi codici sono lineari? Sistematici? Hanno una matrice generatrice? b. Si trasmettono simboli equiprobabili su un BSC con $P_{bit}=3\cdot10^{-4}$, usando le due codifiche per la rivelazione d'errore. Qual è la probabilità di errori non rivelati?

Teoria usata: Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome →, Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione →.

a. Costruire le parole di codice

Entrambi i codici sono sistematici per ipotesi: i primi due bit sono $b_1b_2$.

$\mu_1$. Il bit $c_3$ è $1$ se il peso dei primi $2$ bit è $<2$; il bit $c_4$ è $1$ se il peso dei primi $3$ bit è $<2$.

$\mu_2$. $c_3=c_1+c_2$ (parità dei bit in posizione $2$ e $1$) e $c_4=c_2+c_3=c_2+c_1+c_2=c_1$ (somma modulo $2$). Parole: $00\to0000$, $01\to0110$, $10\to1011$, $11\to1101$.

Linearità.

• $\mu_1$ non è lineare: la parola nulla non appartiene al codice ($b=00$ dà $0011$), e un codice lineare contiene sempre $\mathbf0$. Conferma: $0011+0110=0101$ non è una parola.
• $\mu_2$ è lineare: $c_3=c_1+c_2$ e $c_4=c_1$ sono combinazioni lineari dei bit di informazione. La matrice generatrice (colonna convenzione del corso, $\mathbf c=G\mathbf b$) è $$G=\begin{pmatrix}1&0\\0&1\\1&1\\1&0\end{pmatrix}\quad(c_1=b_1,\ c_2=b_2,\ c_3=b_1+b_2,\ c_4=b_1).$$ Anche $\mu_1$ non ha matrice generatrice (la mappa non è lineare).

b. Probabilità di errore non rivelato

Si ha un errore non rivelato se la parola ricevuta è una parola di codice diversa da quella trasmessa. Su un BSC la probabilità di passare da $\boldsymbol\gamma_i$ a $\boldsymbol\gamma_j$ è $P^{d_{ij}}(1-P)^{4-d_{ij}}$, con $P=P_{bit}$ e $d_{ij}=d_H$. Le parole sono equiprobabili, quindi $$P_{undetected}=\frac14\sum_i\sum_{j\ne i}P^{d_{ij}}(1-P)^{4-d_{ij}}.$$

Stima semplice (da scartare). Prendere "la probabilità di $d_{min}$ errori": $\binom42P^2(1-P)^2=5{,}4\cdot10^{-7}$ per entrambi. È una sovrastima (non tutti i pattern di $2$ errori portano su una parola di codice) e uguale per i due codici, quindi non li distingue.

Calcolo con le distanze.

$\mu_1$: $d(0011,0110)=2$, $d(0011,1010)=2$, $d(0011,1100)=4$, $d(0110,1010)=2$, $d(0110,1100)=2$, $d(1010,1100)=2$. Da ogni parola: $\boldsymbol\gamma_1=0011$ ha $2$ parole a distanza $2$ e $1$ a distanza $4$; $\boldsymbol\gamma_2=0110$: $3$ a distanza $2$; $\boldsymbol\gamma_3=1010$: $3$ a distanza $2$; $\boldsymbol\gamma_4=1100$: $2$ a distanza $2$ e $1$ a distanza $4$. In media $\frac{2+3+3+2}4=2{,}5$ parole a distanza $2$ (e $0{,}5$ a distanza $4$): $$P_{undetected}^{(\mu_1)}=2{,}5\,P^2(1-P)^2+0{,}5\,P^4\simeq2{,}5\cdot9\cdot10^{-8}\cdot0{,}9988=2{,}25\cdot10^{-7}\ (2{,}24\cdot10^{-7}\text{ nel testo del corso}).$$ (Il termine $P^4$ vale $4\cdot10^{-15}$: trascurabile.)

$\mu_2$: parole $0000,0110,1011,1101$. Distanze: $d(0000,0110)=2$, $d(0000,1011)=3$, $d(0000,1101)=3$, $d(0110,1011)=3$, $d(0110,1101)=3$, $d(1011,1101)=2$. Ogni parola ha una parola a distanza $2$ e due a distanza $3$: $$P_{undetected}^{(\mu_2)}=P^2(1-P)^2+2P^3(1-P)\simeq9\cdot10^{-8}\cdot0{,}9988+5{,}4\cdot10^{-11}=8{,}99\cdot10^{-8}+5{,}4\cdot10^{-11}\simeq9\cdot10^{-8}.$$

Conclusione. $\mu_2$ è circa $2{,}5$ volte migliore di $\mu_1$ ($9\cdot10^{-8}$ contro $2{,}25\cdot10^{-7}$) perché ha meno coppie di parole a distanza minima: la sola $d_{min}$ (uguale a $2$ per entrambi) non basta a confrontare i codici, conta anche quante coppie la raggiungono. (La stima $5{,}4\cdot10^{-7}$ del primo paragrafo, che compare anche negli appunti a mano del corso come $\approx6\cdot10^{-7}$, è un limite superiore molto largo.)