Spazio di Hamming

==Distanza sullo spazio di Hamming==
{{InizioDefinizione|title=399 Spazio di Hamming}}
Sia <math>Q</math> un insieme finito con <math>q</math> elementi, e sia <math>n</math> un numero naturale. 
Lo ''spazio di Hamming'', <math>H(n,q)</math> è l'insieme delle n-uple <math>(x_1,x_2,\dots,x_n)</math> con <math>x_i \in Q</math>.
{{FineDefinizione}}




Definisco una distanza <math>d \in H(n,q)</math>:

{{InizioDefinizione|title=400 Distanza di Hamming}}
Dati <math>v=(v_1,\dots,v_n)</math> e <math>w=(w_1,\dots,w_n)</math>, definisco la distanza
<math display="block">d(v,w) = |\{ i \, t.c. \, v_i \neq w_i \}|.</math><math>d</math> si chiama ''distanza di Hamming''.
{{FineDefinizione}}



{{InizioProposizione|title=401}}
<math>d</math> è una distanza.
{{FineProposizione}}



{{InizioDimostrazione}}
#<math>d(v,w)=0</math> se e solo se <math>v=w</math>;
#<math>d(v,w) = d(w,v)</math>
#<math>d(v,w) \le d(v,z)+d(z,w)</math>

Infatti sia <math>a=d(v,z)</math> e <math>b=d(z,w)</math>: questo significa che se cambio <math>a</math> coordinate di <math>v</math> trovo <math>z</math>, e se cambio <math>b</math> 
coordinate di <math>z</math> trovo <math>w</math>, quindi se cambio al più <math>a+b</math> coordinate trovo <math>w</math> a partire da <math>v</math>.
{{FineDimostrazione}}

==Codici==
{{InizioDefinizione|title=402 Codice e parole di un codice}}
Un codice <math>C</math> di lunghezza <math>n</math> e sull'alfabeto <math>Q</math> è un sottoinsieme di <math>H(n,q)</math> con almeno due elementi. 
Gli elementi di <math>C</math> si chiamano ''parole'' del codice.
{{FineDefinizione}}




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



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

==Correttore di errori==
{{InizioDefinizione|title=403 Correttore di errori}}
Dato un intero <math>e</math>, diremo che <math>C</math> è ''correttore di <math>e</math> errori'' se per ogni <math>w \in H(n,q)</math> esiste al più un <math>c \in C</math> tale che <math>d(w,c) \le e</math>.
{{FineDefinizione}}



{{InizioDefinizione|title=404 Distanza del codice}}
La ''distanza del codice''<math>C</math> è denotata con <math>d</math> ed è per definizione <math>\min_{c,c' \in C, \, c \neq c'} \{ d(c,c') \}</math> 
(è la distanza tra due parole arbitrarie, nell'esempio precedente era 3).
{{FineDefinizione}}



{{InizioProposizione|title=405}}
<math>C</math> di distanza minima <math>d</math> è correttore di <math>e</math> errori se e solo se <math>d \ge 2e+1</math>.
(il codice nell'esempio precedente è correttore di 1 errore, perché <math>d=3</math> implica <math>e=1</math>)
{{FineProposizione}}

{{InizioDimostrazione}}
Supponiamo che <math>d \ge 2e+1</math>; sia <math>w \in H(n,q)</math> e supponiamo per assurdo che esistano due vettori <math>c_1,c_2 \in C</math> tali che <math>d(w,c_1)=d(w,c_2) \le e</math>.
Allora per definizione di distanza sul codice <math>C</math> e per l'ipotesi:
<math display="block">d =\min_{c,c' \in C} \{ d(c,c') \} \le d(c_1,c_2) \le d(c_1,w)+d(w,c_2) \le 2e</math>
e questo è assurdo, quindi <math>c_1=c_2</math> e <math>C</math> è correttore di <math>e</math> errori.


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


<math>\ast</math>: se <math>d</math> è pari, la disuguaglianza <math>d-f \le e</math> è ovvia perché <math>f=d-f=d/2</math>. Invece se <math>d</math> è dispari, <math>d/2 \le e</math> implica <math>\lfloor d/2 \rfloor+1 \le e</math> perché <math>e</math> è intero, quindi <math>d-f = d-\lfloor d/2 \rfloor < \lfloor d/2 \rfloor+1 < e</math>)
{{FineDimostrazione}}


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


Denoto con
<math display="block">B_e(c) = \{ w \in Q^n \, t.c. \, d(w,c) \le e \}.</math>
allora vale il seguente corollario:

{{InizioCorollario|title=406}}
<math>C</math> è correttore di <math>e</math> errori se e solo se le palle <math>B_{e,c}</math> centrate negli elementi del codice di raggio <math>e</math> sono a due a due disgiunte.
{{FineCorollario}}

==Considerazioni probabilistiche==
Per semplicità assumeremo che l'alfabeto sia <math>Q= \{0,1\} = \mathbb Z_2</math>. Facciamo le seguenti tre ipotesi sul canale di trasmissione:

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

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 <math>p=1/2</math>, non si spedisce nessuna informazione perché quello che sta succedendo è aleatorio.
#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.

{{InizioDefinizione|title=407 Decodificazione con il metodo maximum likelyhood}}
Data <math>w</math>, la decodificazione con il metodo maximum likelyhood è quella con <math>c</math> per cui la probabilità che "<math>c</math> trasmessa e <math>w</math> ricevuta" siano massime.
{{FineDefinizione}}

{{InizioProposizione|title=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.
{{FineProposizione}}

{{InizioDimostrazione}}
Calcolo la probabilità condizionale dell'evento "<math>c</math> sia trasmessa dato che <math>w</math> sia ricevuta". Sia <math>d = d(w,c)</math>, allora la probabilità che <math>w</math> sia ricevuta dato che <math>c</math> sia trasmessa è data dalla formula <math>p^d*(1-p)^{n-d}</math> (infatti esattamente <math>d</math> cordinate di <math>c</math> sono state cambiate per trovare <math>w</math>, e siccome la probabilità che una coordinata venga cambiata è <math>p</math>, la probabilità che ne vengano cambiate <math>d</math> è <math>p^d</math>, mentre il fattore <math>(1-p)^{n-d}</math> rappresenta il fatto che <math>n-d</math> coordinate non vengono cambiate).  Inoltre la probabilità che <math>c</math> sia trasmessa è data da <math>1/|C|</math>, quindi per la formula di Bayes:
<math display="block">P(c \rm{trasmessa}|w \rm{ricevuta} ) = \frac{P(w \rm{ricevuta} | c \rm{trasmessa})}{P(w \rm{ricevuta})}*P(c \rm{trasmessa})</math><math display="block">= \frac{p^d*(1-p)^{n-d}*1/|C|}{P(w \rm{ricevuta})}</math>
La funzione che a <math>d</math> associa <math>p^d*(1-p)^{n-d}</math> è decrescente in <math>d</math>, quindi <math>P(c \rm{trasmessa}|w \rm{ricevuta})</math> è massima quando <math>d</math> è minima.
{{FineDimostrazione}}

==Rate di un codice==
{{InizioDefinizione|title=409 Rate}}
Il ''rate'' di un codice <math>C</math> è <math>\frac{\log_q |C|}{n}</math>.
{{FineDefinizione}}



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



{{InizioTeorema|title=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 <math>p</math>, allora

;a):sia <math>r</math> tale che <math>r<1+p*\log_2 p+(1-p)*\log_2 (1-p)</math> e <math>\varepsilon >0</math>, allora esiste un codice <math>C</math> con rate <math>r</math> e per cui la probabilità 
che venga commesso un errore usando il metodo di decodifica è minore di <math>\varepsilon</math>.

;b):se <math>r>1+p \log_2 p+(1-p) \log_2 (1-p)</math> allora la probabilità di errore di una parola generica in
codice con rate <math>r</math> è limitata inferiormente da una costante maggiore di 0.
{{FineTeorema}}



{{InizioDefinizione|title=412 Capacità del canale}}
La quantità <math>1+p*\log_2 p+(1-p)*\log_2 (1-p)</math> è detta ''capacità del canale''.
{{FineDefinizione}}




Intuitivamente, se <math>r</math> è 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.