Matematica Discreta III Lezione del giorno 07 marzo 2008

(1)

Matematica Discreta III

Lezione del giorno 07 marzo 2008

Un concetto alla base della teoria della rilevazione e correzione di errori, come si intuisce dagli esempi precedenti e dal fatto che un errore di trasmissione in un bit ha come effetto quello di modificare il bit stesso, è quello di distanza di Hamming: date le parole binarie v,w{0,1}

ⁿ

di lunghezza n, si chiama distanza (v,w) di v da w il numero di bits (nella stessa posizione) in cui le due parole differiscono.

Per esempio in {0,1}

⁵

le parole v=00000, w=01101 hanno distanza (v,w)=3 (perché differiscono nel 2°, 3°, 5° bit).

Ricordiamo che, dato un insieme A, una metrica su A è una funzione  dal prodotto cartesiano AxA nell’insieme dei numeri reali non negativi tale che:

1) dati comunque a,bA, si ha (a,b)=0  a=b 2) dati comunque a,bA, si ha (a,b)= (b,a)

3) dati comunque a,b,cA, si ha (a,c)≤(a,b)+(b,c) (diseguaglianza triangolare)

Esempio: se A è l’insieme dei punti del piano e se (a,b) è l’usuale misura della distanza del punto a dal punto b, si ottiene una metrica su A (la diseguaglianza triangolare discende dalla nota proprietà geometrica: la misura di un lato di un triangolo è ≤ della somma delle misure degli altri 2 lati).

Teorema. La distanza di Hamming è una metrica su {0,1}

ⁿ

. Dimostrazione:

Le proprietà 1) e 2) sono evidenti.

Per quanto riguarda la 3): siano v,w,z{0,1}

ⁿ

e sia D(v,z){1,2,…,n} l’insieme delle posizioni dei bits in cui le parole v,w differiscono (quindi (v,z) coincide con la cardinalitàD(v,z)); analoghe costruzioni per D(v,w), D(w,z) (con (v,w) = D(v,w), (w,z) = D(w,z).

Se iD(v,z), le parole v,z differiscono nel bit di posizione i, dunque vi sono 2 casi possibili:

a) v,w differiscono nel bit in posizione i (dunque iD(v,w))

b) v,w hanno lo stesso bit in posizione i (dunque iD(v,w)), ma allora in questo caso iD(w,z), perché w,z differiranno nel bit in posizione i.

Dunque ogni elemento iD(v,z) appartiene ad uno fra gli insiemi D(v,w), D(v,z), ossia D(v,z) è contenuto nell’unione insiemistica di D(v,w) e D(v,z) , e passando alle cardinalità:

D(v,z)≤ D(v,w)D(v,z) ≤D(v,w)+D(w,z), da cui la tesi.

Ovviamente la distanza di Hamming è legata al numero di errori che si verificano nell’invio nella parola v{0,1}

ⁿ

: se s è il numero di errori nella trasmissione, e se viene ricevuta la parola w{0,1}

ⁿ

, il valore di (v,w) coincide esattamente con s.

Possiamo rappresentare la situazione graficamente. Se definiamo, per ogni parola v{0,1}

ⁿ

ed ogni numero naturale s>0, la sfera R

s

(v) di centro v e raggio s uguale all’insieme delle parole w{0,1}

ⁿ

tali che (v,w) ≤ s, fissata una parola vC da inviare, le parole di R

s

(v) distinte da v sono esattamente tutte le possibili parole che possono essere ricevute erroneamente al posto di v nell’ipotesi che il numero di errori sia ≤s :

R

s

(v) La sfera R

s

(v) contiene (oltre v) tutte le parole

s che possono essere ricevute al posto di v (se il

v il numero degli errori non è superiore ad s).

(2)

Esempio: data la parola v=0100{0,1}

⁴

, la sfera R

2

(v) di centro v e raggio 2 contiene (oltre v) le parole 1100, 0000, 0010, 0101, 1000, 1110, 1101, 0010, 0001, 0111 (sono le parole a distanza 1 o 2 da v, e sono le possibili parole che possono essere ricevute erroneamente al posto di v nell’ipotesi che il numero di errori sia ≤2).

Fissato un numero naturale s, diremo che il codice C{0,1}

ⁿ

è un s-codice a rilevazione d’errore se per ogni parola vC la sfera R

s

(v) di centro v e raggio s non contiene parole del codice C diverse da v (quindi se CR

s

(v)={v}).

Da quanto osservato prima, é ovvio che, se le parole dell’s-codice a rilevazione d’errore C sono utilizzate come codifica dei messaggi di un insieme M spediti da A a B attraverso un canale di trasmissione in cui il numero degli errori è ≤s, il destinatario B è in grado di rilevare la presenza di errori nella trasmissione, perché la parola w erroneamente ricevuta (al posto della parola vC inviata) certamente C, in quanto si trova nella sfera R

s

(v).

Esempio: nel codice di lunghezza 5 (considerato nella lezione precedente):

C={ 00000, 01101, 10110, 11011 }

le 4 sfere di centro vC e raggio s=2 non contengono parole di C diverse dal centro v.

Per esempio la sfera:

R

2

(00000)={00000, 01000, 00100, 00010, 00001, 11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011}

non contiene parole di C diverse da 00000 (e così avviene per le sfere R

2

(01101), R

2

(10110), R

2

(11011)).

Tale 2-codice a rilevazione d’errore, se usato per codificare 4 messaggi (come le direzioni cardinali dell’esempio della lezione precedente) consente di rilevare la presenza di errori nella trasmissione, se il numero di errori è ≤2.

Dato un codice C{0,1}

ⁿ

chiameremo distanza (C) del codice C la minima distanza di 2 parole distinte v,wC:

(C) = min{(v,w) / v,wC, vw}

Dato un generico codice C{0,1}

ⁿ

di cardinalità m, per calcolare la distanza (C) si devono calcolare tutte le possibili distanze di coppie di parole distinte (che sono in tutto m(m-1)/2, per la proprietà 2) della metrica che evita di calcolare (w,v) conoscendo (w,v) ).

Esempio. Dato il codice di cardinalità m=4 del precedente esempio:

C={ 00000, 01101, 10110, 11011 }

per calcolare (C) si devono calcolare le distanze di 4(4-1)/2=6 coppie di parole distinte:

(00000,01101)=3, (00000, 10110)=3, (00000, 11011)=4, (01101, 10110)=4,

(01101, 11011)=3, (10110, 11011)=3 dunque in questo caso (C)=3.

Caratterizziamo gli s-codici a rilevazione d’errore in termini di distanza (C):

Teorema. Sia dato un codice C{0,1}

ⁿ

di distanza =(C). Allora, fissato un numero naturale s:

C è un s-codice a rilevazione d’errore  ≥s+1.

(3)

Dimostrazione:

(): Se C è un s-codice a rilevazione d’errore che rileva s errori, e se per assurdo <s+1, cioé ≤s, essendo =(C) la minima distanza fra parole distinte di C, esisterebbero due parole distinte v,wC tali che (v,w)=≤s, dunque wR

s

(v), contraddizione.

(): Se ≥s+1, fissata una parola vC, per ogni parola wC diversa da v è (v,w)≥≥s+1>s, dunque wR

s

(v), e C è un s-codice a rilevazione d’errore.

Esempio. Nell’esempio precedente essendo =(C)=3, C è un 2-codice a rilevazione d’errore, come già notato esaminando le diverse sfere centrate in parole di C.

Dunque, dal teorema precedente, segue che il massimo valore s tale che il codice C sia un s-codice a rilevazione d’errore è s=(C)-1 (ed è anche il massimo numero di errori che il codice può rilevare).

Considerazioni probabilistiche.

Per semplificare la situazione, faremo da ora in poi delle ipotesi sul canale di trasmissione:

1) tutte le parole del codice C hanno la stessa probabilità (uguale a 1/C) di essere trasmesse 2) la probabilità di errore di trasmissione in un singolo bit è una costante p indipendente dalla posizione del bit (p è detta probabilità d’errore del canale)

3) p é indipendente dal tipo di bit modificato (quindi p è la probabilità che un bit 0 sia modificato in 1 e viceversa).

Un canale che soddisfa tali proprietà è detto simmetrico.

Se vC, w{0,1}

ⁿ

, indicheremo con p(v/w) la probabilità che, supponendo trasmessa la parola v , sia w la parola ricevuta.

Sotto le ipotesi precedenti è facile calcolare p(v/w) in funzione della distanza: se (v,w)=k (numero dei bits in cui v,w differiscono), p(v/w) coincide con la probabilità che nella trasmissione della parola v di lunghezza n si verifichino k errori, dunque è il prodotto delle probabilità che k bits siano modificati e i rimanenti (n-k) restino inalterati, ossia