Matematica Discreta III
Lezione del giorno 5 maggio 2008
Notiamo che un codice perfetto (anche non lineare) ha distanza di Hamming dispari. Infatti ricordiamo che se C è un (n,m,) codice perfetto (dove m=C), posto s=(-1)/2 le sfere di raggio s e centro nelle parole di C formano una partizione di {0,1}n: se per assurdo fosse pari, si avrebbe
=2s+2, e, fissate una parola aC, ed una parola v{0,1}n ottenuta modificando s+1 bits di v, si avrebbe, per ogni parola w{0,1}n, w≠a
2s+2=≤(a,w)≤ (a,v)+(v,w)≤s+1+(v,w) ; (v,w)s+1
dunque la parola v non apparterrebbe a nessuna sfera di di raggio s e centro nelle parole di C (contraddizione). Dunque per un (n,m,)-codice perfetto C si ha:
m
s 0
j j
n = 2n dove s = (-1)/2 e in particolare per un [n,k,]-codice lineare perfetto C si ha:
s 0
j j
n = 2n-k dove s = (-1)/2 (*)
I matematici hanno cercato l’esistenza di codici perfetti diversi dai codici di Hamming (più esattamente non equivalenti ad essi): studiando il problema nel caso di un codice lineare, Golay negli anni ’50 cercò sperimentalmente prima di tutto delle terne di numeri n,k,s (diverse dai quelle dei codici di Hamming) per cui l’eguaglianza (*) risultasse vera, e trovò 2 terne: (23,12,3), (90,78,2), corrispondenti a dei “possibili” codici lineari. Sono infatti vere le seguenti eguaglianze:
3 0
j j
23 = 211 ;
2 0
j j
90 = 212
La prima terna (essendo dispari per quanto premesso all’inizio) dovrebbe corrispondere ad un [23,12,7]-codice lineare, la seconda ad un [90,78,5]-codice lineare.
Lo stesso Golay dimostrò con un ragionamento formale che un [90,78,5]-codice lineare non esiste.
Golay riuscì invece a costruire (probabilmente per tentativi, ma questo non è storicamente noto) un [23,12,7]-codice lineare (detto G23), mediante una matrice di controllo 23x11:
H =
I11 M'
dove il blocco M’ è la seguente matrice 12x11:
M’ =
1 1 1 0 0 1 0 0 0 1 1
1 0 1 1 1 0 0 0 1 0 1
1 1 0 1 0 0 1 1 0 0 1
1 1 0 0 1 0 1 0 1 1 0
1 0 0 1 1 1 0 1 0 1 0
1 0 1 0 0 1 1 1 1 0 0
1 0 0 1 0 1 1 0 1 1 1
1 0 1 0 1 0 1 1 0 1 1
1 1 0 0 1 1 0 1 1 0 1
1 1 1 1 0 0 0 1 1 1 0
1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1
I matematici riuscirono poi a dimostrare che ogni codice lineare perfetto non banale (quindi diverso da Z2n e dal codice di ripetizione di lunghezza n) è equivalente ad uno dei codici H(r) di Hamming o
al codice G23 di Golay. Per qualche tempo si credette che i codici H(r) di Hamming e il codice G23
di Golay fossero gli unici codici perfetti non banali (a meno di equivalenza), ma in seguito furono costruiti codici (non lineari) perfetti diversi da questi (anche se con gli stessi parametri di questi).
Nel 1973, infine, Van Lint e Tievatainen chiusero definitivamente la questione dimostrando che ogni codice (anche non lineare) perfetto non banale ha gli stessi parametri di un codice di Hamming H(r) o del codice G23 di Golay.
Algoritmo di decodifica per un codice lineare
Nel caso di un codice generico a correzione d’errore (anche non lineare) CZ2n, sappiamo che l’algoritmo di correzione dell’errore che dal punto di vista probabilistico è più conveniente (se il canale è simmetrico) è l’algoritmo di decodifica della parola più vicina: se w è la parola ricevuta, e se wC, si “decodifica” w come la parola vC tale che la distanza (v,w) sia minima. Dal punto di vista computazionale si tratta di calcolare le distanze di m=C coppie di parole (le coppie formate da w e da una parola di C) e scegliere il valore minimo.
Vedremo che, nel caso di un codice lineare con matrice di controllo H, esiste un algoritmo di correzione dell’errore più efficiente.
Facciamo alcune considerazioni preliminari.
Supponiamo dato un codice lineare CZ2n di lunghezza n e dimensione k. Essendo C un sottogruppo additivo del gruppo Z2n, possiamo considerare la cosiddetta relazione di congruenza modulo C nel gruppo Z2n:
v, wZ2n v w (mod C) se v - wC
(é facile dimostrare che si tratta di una relazione di equivalenza). Per ogni vZ2n possiamo costruire la classe di equivalenza [v] rappresentata da v (detta anche classe di congruenza modulo C rappresentata da v), contenente tutte le parole zZ2n che sono in relazione con v, cioè tali che si abbia z-v=wC. Gli elementi della classe [v] sono dunque tutte le somme della forma z=v+w al variare di wC. Dalla teoria generale delle relazioni di equivalenza sappiamo che le diverse classi di equivalenza formano una partizione di Z2n. Ognuna di tali classi ha inoltre la stessa cardinalità 2k del codice C (è facile infatti verificare che la funzione f: C [v] definita da f(w)=v+w è biunivoca). Dunque, se t è il numero di tali classi, si ha 2n =Ct= 2kt (è il cosiddetto Teorema di Lagrange) e in particolare il numero delle classi è t = 2n-k.
E’ ovvio anche che la classe [0] rappresentata dalla parola nulla coincide con lo stesso codice C.
Costruiremo ora una matrice (wij) che contiene tutte le 2n parole distinte di Z2n, con t = 2n-k righe, e 2k colonne, in modo che le parole di ogni riga formino una classe di congruenza modulo C.
Poniamo m=2k ed elenchiamo in una prima riga le m parole di C (in un ordine arbitrario), cominciando però dalla parola nulla:
w11=0 w12 w13 …….. w1m (dove C= { w11=0 , w12 , w13 , …….. , w1m } ).
Ora scegliamo una parola wZ2n di peso minimo fra quelle che non compaiono nella prima riga già costruita (se vi è più di una parola di peso minimo, se ne sceglie una a piacere), ed elenchiamo in una seconda riga le parole della classe [w] ottenute sommando ordinatamente w con le parole di C della prima riga:
w11=0 w12 w13 …… vm (prima riga)
w21=w+v11=w w22=w+v12 w23=w+v13 …… w2m=w+v1m (seconda riga) Poiché w[0]=C, le classi [w], [0] sono disgiunte.
Procediamo così per costruire le righe successive della matrice, ogni volta scegliendo una parola di peso minimo fra quelle che non compaiono nelle righe già costruite, e sommando ordinatamente tale parola con le parole di C (nella prima riga) per ottenere le parole di una nuova riga (parole che formano una classe di congruenza modulo C).
Otteniamo alla fine una matrice in cui ogni riga contiene gli elementi di una singola classe di congruenza modulo C, e la prima parola di ogni riga è di peso minimo rispetto a tutte le parole che compaiono nella riga stessa (e nelle righe che seguono): tale parola iniziale wi1 di ogni riga è detta leader della sua riga. Inoltre per costruzione ogni parola wijdella matrice si ottiene sommando al leader (della sua riga) la parola di C (nella prima riga) che sta nella stessa colonna: wij = wi1+w1j . La matrice così ottenuta è detta matrice di decodifica del codice lineare C: essendo le classi di congruenza modulo C una partizione di Z2n , la matrice contiene tutte le parole di lunghezza n, ognuna contata una sola volta. Si può notare che tale matrice di decodifica non è unica (per esempio la scelta della parola di peso minimo fra quelle non presenti nelle righe già costruite può non essere univoca).
Inoltre la matrice ha come numero di colonne la cardinalità m=2k del codice C, e come numero di righe il numero t=2n-k delle distinte classi di congruenza modulo C.
Esempio: Sia CZ26 il codice (sistematico) di lunghezza 6 e dimensione 3 con matrice generatrice:
M =
1 1 0 1 0 0
1 1 1 0 1 0
1 0 1 0 0 1
Al variare della parola w=x1x2x3Z23 i prodotti wM generano le 8 parole del codice:
C = {000000, 100110, 010011, 011100, 001111, 101001, 110101, 111010 }
La prima riga della matrice standard di C è formata dagli elementi di C (in ordine generico ma cominciando dalla parola nulla):
000000 100110 010011 011100 001111 101001 110101 111010 (prima riga)
Per costruire la seconda riga, scegliamo una parola di peso minimo non presente nella prima riga (per esempio 100000 che ha peso 1) e la sommiamo ordinatamente con le parole di C, ottenendo come elementi della seconda riga quelli di una seconda classe di congruenza modulo C:
000000 100110 010011 011100 001111 101001 110101 111010 (prima riga) 100000 000110 110011 111100 101111 001001 010101 111010 (seconda riga)
Per costruire la terza riga, scegliamo una parola di peso minimo non presente nella prima e nella seconda riga (per esempio 010000 che ha peso 1) e la sommiamo ordinatamente con le parole di C, ottenendo come elementi della terza riga quelli di una terza classe di congruenza modulo C.
Otteniamo alla fine la seguente matrice di decodifica di C:
con 23=8 righe (corrispondenti alle diverse classi) e con il primo elemento di ogni riga che è il leader della classe.
Vediamo come, costruita la matrice standard di decodifica (wij), si può, fissata comunque una parola w, trovare una parola vC a distanza minima da w .
Sappiamo già che, se (v) indica il peso di una generica parola v, comunque prese le parole v,w si ha (v,w)= (v+w) (quindi la distanza fra v,w coincide con il peso della loro somma).
Fissata una parola w, essa si troverà in una e una sola riga i della matrice, in colonna j:
w = wij (per opportuni i,j)
Si tratta di trovare una parola vC tale che il peso (v+w) sia minimo: ma v+w è una generica parola della classe di congruenza rappresentata da w modulo C cioè della riga i in cui si trova w, dunque per costruzione basta scegliere v+w=wi1 (leader della classe di w), da cui w=wij=wi1+v e di nuovo per costruzione v=w1j (la parola di C che si trova nella prima riga, nella stessa colonna j di w).
Dunque, costruita la matrice standard di decodifica (wij), un algoritmo di decodifica per un codice lineare C che, data in input una generica parola w, calcoli la parola v di C più vicina a w, consiste semplicemente nell’individuare la posizione di w nella matrice di decodifica (w=wij) e scegliere la parola v di C (nella prima riga) che si trova nella stessa colonna di w (v=w1j= wij+wi1).
In questo algoritmo, per trovare la posizione di w nella matrice di decodifica, si devono effettuare (al più) 2n confronti di w con tutte le parole della matrice.
Ma l’algoritmo di decodifica precedente può ancora essere reso più efficiente, conoscendo la matrice di controllo del codice, con il concetto di sindrome.
Dato un codice lineare C Z2n con matrice di controllo H, la sindrome di una parola wZ2n è la parola Syn(w)=wHZ2n-k (se k è la dimensione di C).
Già sappiamo che wH =0 wC.
Ma si ha anche, date 2 parole v,wZ2n :
v w (mod C) Syn(v)=Syn(w) (dunque 2 parole stanno nella stessa classe di congruenza modulo C se e solo se hanno la stessa sindrome).
Infatti se v w (mod C), si ha v-w=v+wC, dunque 0=(v+w)H=vH+wH, da cui vH=wH (l’implicazione inversa si dimostra invertendo i passaggi).
L’algoritmo di decodifica basato sulla matrice standard di decodifica (wij) si rende allora più efficiente nel modo seguente: si costruisce una tabella con le parole leader w11,w21,…,wt1 (dove t=2n-
k) e le loro corrispondenti sindromi Syn(w11),Syn(w21),…,Syn(wtm); data una parola w, si calcola la sindrome Syn(w)=wH e la si confronta con le sindromi delle parole leader, cercando la parola leader wi1 con la stessa sindrome di w: per quanto osservato in precedenza una parola vC a distanza minima da w sarà v=w+wi1 .
In questo algoritmo si confronta la sindrome di w con quella dei leader delle classi (in totale un numero massimo di 2n-k confronti invece dei 2n della versione precedente dell’algoritmo).
Esempio. Nell’esempio precedente si costruisce la tabella delle parole leader e delle loro sindromi:
Leader: Syn:
000000 000
100000 110
010000 011
001000 111
000100 100
000010 010
000001 001
000101 101
Se per esempio si considera la parola w=001011, calcolando wH=Syn(w)=1000 si rileva che wC e, individuato il leader che ha la stessa sindrome w51=000100, si trova una parola v di C a distanza minima da w ponendo v=w+w51=001111. Abbiamo dunque effettuato (al più) 23=8 confronti (invece di 26=64 confronti).
