Spazio di Hamming

Distanza sullo spazio di Hamming

Definizione

Sia un insieme finito con elementi, e sia un numero naturale. Lo spazio di Hamming, è l'insieme delle n-uple con .

 



Definisco una distanza :

Definizione

Dati e , definisco la distanza

si chiama distanza di Hamming.

 


Proposizione

è una distanza.

 


Dimostrazione
  1. se e solo se ;

Infatti sia e : questo significa che se cambio coordinate di trovo , e se cambio coordinate di trovo , quindi se cambio al più coordinate trovo a partire da .

 

Codici

Definizione

Un codice di lunghezza e sull'alfabeto è un sottoinsieme di con almeno due elementi. Gli elementi di si chiamano parole del codice.

 



Supponiamo che abbia elementi, cioè che . Sia l'insieme dei messaggi che vogliamo spedire. Sia biettiva (nell'esempio precedente, i messaggi sono i numeri tra 0 e 15, e la funzione che a ogni numero associa le risposte alle sette domande che rappresentano i codici).


Decifratura: se si riceve un vettore , lo si decodifica prendendo un elemento tale che sia minima. Dato , risalgo al messaggio calcolando . Se , si prende . (nell'esempio precedente, si correggeva la bugia per trovare )

Correttore di errori

Definizione

Dato un intero , diremo che è correttore di errori se per ogni esiste al più un tale che .

 


Definizione

La distanza del codice è denotata con ed è per definizione (è la distanza tra due parole arbitrarie, nell'esempio precedente era 3).

 


Proposizione

di distanza minima è correttore di errori se e solo se . (il codice nell'esempio precedente è correttore di 1 errore, perché implica )

 
Dimostrazione

Supponiamo che ; sia e supponiamo per assurdo che esistano due vettori tali che . Allora per definizione di distanza sul codice e per l'ipotesi:

e questo è assurdo, quindi e è correttore di errori.


Viceversa, supponiamo per assurdo che , e supponiamo che , siano parole del codice a distanza . Posso portare in alterando coordinate: chiamo la parola che ottengo alterando coordinate di per portarlo in , allora e . sono (), ma dista al più sia da che da , ma allora il codice non può correggere errori.


: se è pari, la disuguaglianza è ovvia perché . Invece se è dispari, implica perché è intero, quindi )

 


In genere si cercano codici con , ma questi due valori sono in conflitto; infatti se prendo grande il codice potrà avere meno parole.


Denoto con

allora vale il seguente corollario:

Corollario

è correttore di errori se e solo se le palle centrate negli elementi del codice di raggio sono a due a due disgiunte.

 

Considerazioni probabilistiche

Per semplicità assumeremo che l'alfabeto sia . Facciamo le seguenti tre ipotesi sul canale di trasmissione:

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

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 , 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

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

 
Proposizione

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 " sia trasmessa dato che sia ricevuta". Sia , allora la probabilità che sia ricevuta dato che sia trasmessa è data dalla formula (infatti esattamente cordinate di sono state cambiate per trovare , e siccome la probabilità che una coordinata venga cambiata è , la probabilità che ne vengano cambiate è , mentre il fattore rappresenta il fatto che coordinate non vengono cambiate). Inoltre la probabilità che sia trasmessa è data da , quindi per la formula di Bayes:

La funzione che a associa è decrescente in , quindi è massima quando è minima.

 

Rate di un codice

Definizione

Il rate di un codice è .

 


Esempio

Supponiamo che , allora il rate è dato da . Se , allora il numero di parole che posso spedire è vicino al numero massimo di n-uple a disposizione, invece se , il codice è rarefatto all'interno delle possibili n-uple.

 


Teorema

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

a)
sia tale che e , allora esiste un codice con rate e per cui la probabilità

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

b)
se allora la probabilità di errore di una parola generica in

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

 


Definizione

La quantità è detta capacità del canale.

 



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

 PrecedenteSuccessivo