Spazio di Hamming

Distanza sullo spazio di Hamming

Definizione (399 Spazio di Hamming)

Sia $Q$$Q$ un insieme finito con $q$$q$ elementi, e sia $n$$n$ un numero naturale. Lo spazio di Hamming, $H(n,q)$$H(n,q)$ è l'insieme delle n-uple $(x_{1},x_{2},\dots ,x_{n})$$(x_{1},x_{2},\dots ,x_{n})$ con $x_{i}\in Q$$x_{i}\in Q$.

 

Definisco una distanza $d\in H(n,q)$$d\in H(n,q)$:

Definizione (400 Distanza di Hamming)

Dati $v=(v_{1},\dots ,v_{n})$$v=(v_{1},\dots ,v_{n})$ e $w=(w_{1},\dots ,w_{n})$$w=(w_{1},\dots ,w_{n})$, definisco la distanza

$$d(v,w)=|\{i\,t.c.\,v_{i}\neq w_{i}\}|.$$

$$d(v,w)=|\{i\,t.c.\,v_{i}\neq w_{i}\}|.$$

$d$$d$ si chiama distanza di Hamming.

 

Proposizione (401)

$d$$d$ è una distanza.

 

Dimostrazione

1. $d(v,w)=0$$d(v,w)=0$ se e solo se $v=w$$v=w$;
2. $d(v,w)=d(w,v)$$d(v,w)=d(w,v)$
3. $d(v,w)\leq d(v,z)+d(z,w)$$d(v,w)\leq d(v,z)+d(z,w)$

Infatti sia $a=d(v,z)$$a=d(v,z)$ e $b=d(z,w)$$b=d(z,w)$: questo significa che se cambio $a$$a$ coordinate di $v$$v$ trovo $z$$z$, e se cambio $b$$b$ coordinate di $z$$z$ trovo $w$$w$, quindi se cambio al più $a+b$$a+b$ coordinate trovo $w$$w$ a partire da $v$$v$.

 

Codici

Definizione (402 Codice e parole di un codice)

Un codice $C$$C$ di lunghezza $n$$n$ e sull'alfabeto $Q$$Q$ è un sottoinsieme di $H(n,q)$$H(n,q)$ con almeno due elementi. Gli elementi di $C$$C$ si chiamano parole del codice.

 

Supponiamo che $C$$C$ abbia $k$$k$ elementi, cioè che $C=\{c_{1},c_{2},c_{3},\dots ,c_{k}\}$$C=\{c_{1},c_{2},c_{3},\dots ,c_{k}\}$. Sia $M$$M$ l'insieme dei messaggi che vogliamo spedire. Sia $f:M\to C$$f:M\to C$ biettiva (nell'esempio precedente, i messaggi sono i numeri tra 0 e 15, e $f$$f$ la funzione che a ogni numero associa le risposte alle sette domande che rappresentano i codici).

Decifratura: se si riceve un vettore $v\in H(n,q)$$v\in H(n,q)$, lo si decodifica prendendo un elemento $c'\in C$$c'\in C$ tale che $d(v,c')$$d(v,c')$ sia minima. Dato $c'$$c'$, risalgo al messaggio calcolando $f^{-1}(c')$$f^{-1}(c')$. Se $v\in C$$v\in C$, si prende $c'=v$$c'=v$. (nell'esempio precedente, si correggeva la bugia per trovare $c'$$c'$)

Correttore di errori

Definizione (403 Correttore di errori)

Dato un intero $e$$e$, diremo che $C$$C$ è correttore di $e$$e$ errori se per ogni $w\in H(n,q)$$w\in H(n,q)$ esiste al più un $c\in C$$c\in C$ tale che $d(w,c)\leq e$$d(w,c)\leq e$.

 

Definizione (404 Distanza del codice)

La distanza del codice$C$$C$ è denotata con $d$$d$ ed è per definizione $\min _{c,c'\in C,\,c\neq c'}\{d(c,c')\}$$\min _{c,c'\in C,\,c\neq c'}\{d(c,c')\}$ (è la distanza tra due parole arbitrarie, nell'esempio precedente era 3).

 

Proposizione (405)

$C$$C$ di distanza minima $d$$d$ è correttore di $e$$e$ errori se e solo se $d\geq 2e+1$$d\geq 2e+1$. (il codice nell'esempio precedente è correttore di 1 errore, perché $d=3$$d=3$ implica $e=1$$e=1$)

 

Dimostrazione

Supponiamo che $d\geq 2e+1$$d\geq 2e+1$; sia $w\in H(n,q)$$w\in H(n,q)$ e supponiamo per assurdo che esistano due vettori $c_{1},c_{2}\in C$$c_{1},c_{2}\in C$ tali che $d(w,c_{1})=d(w,c_{2})\leq e$$d(w,c_{1})=d(w,c_{2})\leq e$. Allora per definizione di distanza sul codice $C$$C$ e per l'ipotesi:

$$d=\min _{c,c'\in C}\{d(c,c')\}\leq d(c_{1},c_{2})\leq d(c_{1},w)+d(w,c_{2})\leq 2e$$

$$d=\min _{c,c'\in C}\{d(c,c')\}\leq d(c_{1},c_{2})\leq d(c_{1},w)+d(w,c_{2})\leq 2e$$

e questo è assurdo, quindi $c_{1}=c_{2}$$c_1=c_2$ e $C$$C$ è correttore di $e$$e$ errori.

Viceversa, supponiamo per assurdo che $d\leq 2e$$d\leq 2e$, e supponiamo che $f=\lfloor d/2\rfloor$$f=\lfloor d/2\rfloor$, siano $c_{1},c_{2}$$c_{1},c_{2}$ parole del codice a distanza $d$$d$. Posso portare $c_{1}$$c_1$ in $c_{2}$$c_{2}$ alterando $d$$d$ coordinate: chiamo $w$$w$ la parola che ottengo alterando $f$$f$ coordinate di $c_{1}$$c_1$ per portarlo in $c_{2}$$c_{2}$, allora $d(w,c_{1})=f$$d(w,c_{1})=f$ e $d(w,c_{2})=d-f$$d(w,c_{2})=d-f$. $f,d-f$$f,d-f$ sono $\leq e$$\leq e$ ($\ast$$\ast$), ma $w$$w$ dista al più $e$$e$ sia da $c_{1}$$c_1$ che da $c_{2}$$c_{2}$, ma allora il codice non può correggere $e$$e$ errori.

$\ast$$\ast$: se $d$$d$ è pari, la disuguaglianza $d-f\leq e$$d-f\leq e$ è ovvia perché $f=d-f=d/2$$f=d-f=d/2$. Invece se $d$$d$ è dispari, $d/2\leq e$$d/2\leq e$ implica $\lfloor d/2\rfloor +1\leq e$$\lfloor d/2\rfloor +1\leq e$ perché $e$$e$ è intero, quindi $d-f=d-\lfloor d/2\rfloor <\lfloor d/2\rfloor +1<e$$d-f=d-\lfloor d/2\rfloor <\lfloor d/2\rfloor +1<e$)

 

In genere si cercano codici con $d\geq 2e+1$$d\geq 2e+1$, ma questi due valori sono in conflitto; infatti se prendo $d$$d$ grande il codice potrà avere meno parole.

Denoto con

$$B_{e}(c)=\{w\in Q^{n}\,t.c.\,d(w,c)\leq e\}.$$

$$B_{e}(c)=\{w\in Q^{n}\,t.c.\,d(w,c)\leq e\}.$$

allora vale il seguente corollario:

Corollario (406)

$C$$C$ è correttore di $e$$e$ errori se e solo se le palle $B_{e,c}$$B_{e,c}$ centrate negli elementi del codice di raggio $e$$e$ sono a due a due disgiunte.

 

Considerazioni probabilistiche

Per semplicità assumeremo che l'alfabeto sia $Q=\{0,1\}=\mathbb {Z} _{2}$$Q=\{0,1\}=\mathbb {Z} _{2}$. Facciamo le seguenti tre ipotesi sul canale di trasmissione:

1. la probabilità $p$$p$ che 0 venga cambiato in 1 è la stessa che 1 sia cambiato in 0.
2. $p$$p$ non dipende dalla coordinata, e inoltre $p<1/2$$p<1/2$

In realtà l'ipotesi che tutte le coordinate possono essere cambiate con la stessa probabilità non è realistica, perché nella pratica, quando si trasmette un segnale, è più probabile che ci siano rumori che portano a errori nella trasmissione all'inizio piuttosto che alla fine del processo. Per quanto riguarda l'altra ipotesi, se $p=1/2$$p=1/2$, non si spedisce nessuna informazione perché quello che sta succedendo è aleatorio.

1. la probabilità di errore è indipendente dalle coppie di coordinate.

Anche quest'ipotesi non è realistica perché nella realtà, se una coordinata è sbagliata, è più probabile che anche le seguenti siano sbagliate.

Definizione (407 Decodificazione con il metodo maximum likelyhood)

Data $w$$w$, la decodificazione con il metodo maximum likelyhood è quella con $c$$c$ per cui la probabilità che "$c$$c$ trasmessa e $w$$w$ ricevuta" siano massime.

 

Proposizione (408)

In un canale che soddisfa le precedenti richieste, il metodo di decodifica maximum likelihood coincide con il metodo di decodifica dato dalla minima distanza.

 

Dimostrazione

Calcolo la probabilità condizionale dell'evento "$c$$c$ sia trasmessa dato che $w$$w$ sia ricevuta". Sia $d=d(w,c)$$d=d(w,c)$, allora la probabilità che $w$$w$ sia ricevuta dato che $c$$c$ sia trasmessa è data dalla formula $p^{d}*(1-p)^{n-d}$$p^{d}*(1-p)^{n-d}$ (infatti esattamente $d$$d$ cordinate di $c$$c$ sono state cambiate per trovare $w$$w$, e siccome la probabilità che una coordinata venga cambiata è $p$$p$, la probabilità che ne vengano cambiate $d$$d$ è $p^{d}$$p^{d}$, mentre il fattore $(1-p)^{n-d}$$(1-p)^{n-d}$ rappresenta il fatto che $n-d$$n-d$ coordinate non vengono cambiate). Inoltre la probabilità che $c$$c$ sia trasmessa è data da $1/|C|$$1/|C|$, quindi per la formula di Bayes:

$$P(c{\rm {{trasmessa}|w{\rm {{ricevuta})={\frac {P(w{\rm {{ricevuta}|c{\rm {{trasmessa})}}}}}{P(w{\rm {{ricevuta})}}}}*P(c{\rm {{trasmessa})}}}}}}$$

$$P(c{\rm {{trasmessa}|w{\rm {{ricevuta})={\frac {P(w{\rm {{ricevuta}|c{\rm {{trasmessa})}}}}}{P(w{\rm {{ricevuta})}}}}*P(c{\rm {{trasmessa})}}}}}}$$

$$={\frac {p^{d}*(1-p)^{n-d}*1/|C|}{P(w{\rm {{ricevuta})}}}}$$

$$={\frac {p^{d}*(1-p)^{n-d}*1/|C|}{P(w{\rm {{ricevuta})}}}}$$

La funzione che a $d$$d$ associa $p^{d}*(1-p)^{n-d}$$p^{d}*(1-p)^{n-d}$ è decrescente in $d$$d$, quindi $P(c{\rm {{trasmessa}|w{\rm {{ricevuta})}}}}$$P(c{\rm {{trasmessa}|w{\rm {{ricevuta})}}}}$ è massima quando $d$$d$ è minima.

 

Rate di un codice

Definizione (409 Rate)

Il rate di un codice $C$$C$ è ${\frac {\log _{q}|C|}{n}}$${\frac {\log _{q}|C|}{n}}$.

 

Esempio (410)

Supponiamo che $|C|=|Q|^{k}$$|C|=|Q|^{k}$, allora il rate è dato da ${\frac {\log _{|Q|}(|Q|^{k})}{n}}=k/n$${\frac {\log _{|Q|}(|Q|^{k})}{n}}=k/n$. Se $k/n\to 1$$k/n\to 1$, allora il numero di parole che posso spedire è vicino al numero massimo di n-uple a disposizione, invece se $k/n\to 0$$k/n\to 0$, il codice è rarefatto all'interno delle possibili n-uple.

 

Teorema (411 teorema di Shannon)

Dato un canale con le tre proprietà di prima, e tale che la probabilità che "0 trasmesso e 1 ricevuto" sia $p$$p$, allora

a)

sia $r$$r$ tale che $r<1+p*\log _{2}p+(1-p)*\log _{2}(1-p)$$r<1+p*\log _{2}p+(1-p)*\log _{2}(1-p)$ e $\varepsilon >0$$\varepsilon >0$, allora esiste un codice $C$$C$ con rate $r$$r$ e per cui la probabilità

che venga commesso un errore usando il metodo di decodifica è minore di $\varepsilon$$\varepsilon$.

b)

se $r>1+p\log _{2}p+(1-p)\log _{2}(1-p)$$r>1+p\log _{2}p+(1-p)\log _{2}(1-p)$ allora la probabilità di errore di una parola generica in

codice con rate $r$$r$ è limitata inferiormente da una costante maggiore di 0.

 

Definizione (412 Capacità del canale)

La quantità $1+p*\log _{2}p+(1-p)*\log _{2}(1-p)$$1+p*\log _{2}p+(1-p)*\log _{2}(1-p)$ è detta capacità del canale.

 

Intuitivamente, se $r$$r$ è minore della capacità del canale, si può sempre trovare un codice che minimizza l'errore di trasmissione, altrimenti questo non è possibile.

La dimostrazione è di esistenza ma non costruttiva: non si ha idea di come realizzare il codice.