Matematica Discreta III
Lezione del giorno 10 marzo 2008
Fra i 3 parametri (lunghezza, cardinalità, distanza) di un codice vi sono, come vedemo, dei vincoli che rendono impossibile ottenere situazioni ideali (quindi spesso si può raggiungere solo un compromesso).
Lemma. Fissati un intero s>0 ed una parola v{0,1}n, la sfera di centro v e raggio s ha cardinalità:
Rs(v) =
s 0
j j
n Dimostrazione:
Fissato un intero j=0,1,….,s, calcoliamo il numero delle parole w{0,1}n tali che (v,w)=j. Ognuna di tali parole si ottiene da v modificando j bits fra gli n bits di v, e tale operazione si può effettuare in
j
n modi diversi, quindi il numero di tali parole coincide con
j n .
Poiché la sfera Rs(v) contiene tutte le parole tali che (v,w)=j con j=0,1,….,s, si ottiene la tesi.
Teorema. Dato un (n, m, )-codice C e posto s=(-1)/2 (in modo che C sia un s-codice a correzione d’errore con il valore di s massimo possibile), si ha:
m
s 0
j j
n ≤ 2n (*) (Hamming bound)
Dimostrazione:
Dai Teoremi precedenti sappiamo che, essendo C un s-codice a correzione d’errore, le sfere di raggio s con centro in distinte parole del codice non si intersecano.
Al variare di v in C, si ottengono m sfere disgiunte Rs(v) contenute in Z2n (ognuna della cardinalità indicata nel Lemma), e si conclude che {0,1}n=2n m
s 0
j j
n .
Il Teorema precedente pone quindi dei limiti per ognuno dei parametri, se il terzo è fissato.
Per esempio si ha in ogni caso:
m 2n/
s 0
j j
n
(**) (per un qualunque (n, m, )-codice C, posto s=(-1)/2) .
Esempio: se C è un (5,m,3)-codice (codice di lunghezza 5, distanza 3, e dunque è un 1-codice a correzione d’errore), allora m 25/
1
0
j j
5 =32/6, da cui m≤5, ossia il codice non può contenere più di 5 parole (quindi può codificare al più 5 messaggi).
Ciò ovviamente non implica che esista necessariamente un (5,5,3)-codice: in effetti si è verificato che un tale codice non esiste (se si vuole dimostrarlo con la “forza bruta” basta esaminare i possibili codici di 5 parole in Z25, in numero di
5
32 =201376, e per ognuno verificare che 3…….).
In effetti è un problema spesso arduo, fissati n e , calcolare il massimo valore m tale che esista un (n,m,)-codice C: tale valore è indicato spesso con A(n,).
Esempio: per le considerazioni precedenti si ha A(5,3)<5, ma d’altronde abbiamo già incontrato un (5,4,3)-codice C={ 00000, 01101, 10110, 11011 }, dunque si conclude che A(5,3)=4.
Esistono delle tabelle che forniscono i valori già calcolati per A(n,) (per alcuni valori di n,).
Fissata la lunghezza n e la distanza (quindi fissato il numero massimo s=(-1)/2 di errori che il codice può correggere), il valore massimo possibile (teorico) del rateo di informazione (log2m)/n si ottiene quando il valore m è massimo, dunque quando la diseguaglianza (**) del Teorema precedente è un’eguaglianza (anche se non è detto che tale situazione ideale sia ottenibile).
Un (n, m, )-codice C a correzione d’errore che corregge s errori è detto perfetto se la diseguaglianza (**) è in effetti una eguaglianza:
m = 2n/
s 0
j j
n
(***)
Nel caso di un tale codice, le sfere di raggio s con centro in distinte parole del codice non solo non si intersecano ma ricoprono l’intero insieme {0,1}n (quindi ogni parola di {0,1}n si trova a distanza
≤s da una e una sola parola del codice C).
Da notare che m, essendo un divisore di 2n, è anch’esso una potenza di 2, quindi i codici perfetti hanno tutti cardinalità uguale ad una potenza di 2.
La costruzione di codici perfetti (che purtroppo non sono molto comuni) è stata una delle più grandi sfide della teoria dei codici.
Esempio: fissata la lunghezza n, consideriamo il codice C di cardinalità 2 contenente le 2 parole di lunghezza n con tutti 0 o tutti 1: C = {0000….0, 1111….1}
Tale codice è detto codice di ripetizione di lunghezza n. Poiché la distanza fra le 2 parole di C è n, si tratta di un (n,2,n)-codice, che è un s-codice a correzione d’errore con s=(n-1)/2.
In particolare, se n è dispari, si ha s=(n-1)/2 e inoltre il codice è perfetto. Per dimostrarlo ricordiamo che i coefficienti binomiali:
j
n j=0,…..,n
hanno come somma 2n (la loro somma coincide con il numero dei sottoinsiemi di un insieme finito di cardinalità n) e inoltre soddisfano le eguaglianze
j
n =
j - n
n , dunque (essendo n dispari):
0
n =
n
n ,
1
n =
1 - n
n ,……,
1)/2 - (n
n =
1)/2 (n
n
da cui:
2n = 2
1)/2 - (n
0
j j
n
e dunque è verificata l’eguaglianza (***) dei codici perfetti.
D’altronde anche il codice C={0,1}n è un (n,2n,1)-codice perfetto perché s=0 e l’eguaglianza (***) è banalmente verificata.
I 2 tipi di codici perfetti considerati (codice di ripetizione di lunghezza n con n dispari e {0,1}n) sono detti codici perfetti banali.
Essi sono ovviamente poco interessanti perché il primo, pur essendo in grado di correggere (n-1)/2 errori (con n grande a piacere) codifica solo 2 messaggi (quindi ha un rateo di informazione 1/n che tende a 0 al crescere della lunghezza n), mentre il secondo non è in grado non solo di correggere errori nella trasmissione, ma neanche di rilevarli.
