Matematica Discreta II
Lezione del giorno 6 dicembre 2007
Se vogliamo costruire una matrice di controllo di un codice lineare a rilevazione d’errore che rilevi 1 errore, per i risultati precedenti dobbiamo scegliere colonne tutte non nulle.
Un caso semplice di matrice di controllo H (in forma standard) con tale proprietà è il seguente:
fissiamo r=1, dunque la matrice Arx(n-r)= A1x(n-1) è una riga di n-1 bits (tutti non nulli), mentre la matrice identica Ir=I1 è un singolo bit=1
H =
1 1 1 . . . 1
In questo caso la matrice generatrice è la matrice nx(n-1):
K =
A
I
1) - 1x(n
1 -
n =
1 . . 1 1
1 . . 0 0
. . . . .
. . . . .
0 . . 1 0
0 . . 0 1
e facendo variare la parola w=x1x2…..xn-1 di lunghezza n-1, i prodotti:
v = Kw =
2 n
1 1 n
2 1
...x x x
x . x x
danno tutte le parole v del codice C.
Notiamo che vi è un solo bit di ridondanza xn=x1+x2+…..+xn-1: ricordando che la somma di (n-1) bits 0,1 in Z2 è 0 se il numero di bits=1 è pari, ed è 1 se il numero di bits=1 è dispari, tale bit di controllo è detto bit di parità; in pratica se il numero di bits=1 nei primi n-1 bits non è coerente con il bit di parità, si rileva che la parola non è parte del codice (quindi si rileva 1 errore, ma senza essere in grado di correggerlo, perché il bit modificato può essere uno qualunque).
In effetti tale codice è in grado di rilevare anche un numero di errori >1: esattamente rileva un numero dispari di errori (1,3,5,7…) (anche in questo caso il bit di parità non è coerente con i primi n-1 bits).
Esempio: nel codice ASCII vengono codificati 128 simboli (caratteri alfanumerici e comandi come
“vai a capo” etc…): essi vengono prima codificati (secondo un tabella internazionale) con le 128 parole di lunghezza 7 in Z27, e poi viene aggiunto un ottavo bit di parità (ottenendo un codice di lunghezza 8 in Z27) in grado di rilevare un errore (o un numero dispari di errori).
Nel procedimento con il quale da una matrice rxn si costruisce un codice di lunghezza n e dimensione n-k di cui essa è la matrice di controllo, supponiamo di fissare il numero di righe r>1 e di cercare un valore n massimo tra quelli che diano luogo ad un codice a correzione d’errore che corregge 1 errore.
Per un risultato precedente, la matrice deve avere tutte le colonne non nulle e diverse: le colonne distinte possibili sono 2r (in ogni colonna vi sono r bits 0,1), quindi quelle non nulle sono 2r-1, ossia il valore massimo di n è n=2r-1. In pratica per costruire una tale matrice basta considerare la rappresentazione binaria di tutti i numeri interi positivi <2r (aggiungendo opportuni 0 non significativi a sinistra per renderli della stessa lunghezza r) e disporre in colonne tali rappresentazioni binarie (per esempio con i bits dal basso verso l’alto, in alto i meno significativi), ottenendo una matrice rxn con n=2r-1.
Per esempio per r=3 si ottiene la matrice 3x7:
H =
1 1 1 1 0 0 0
1 1 0 0 1 1 0
1 0 1 0 1 0 1
(valore numerico di ogni colonna: 1 2 3 4 5 6 7 )
Per un valore generico di r, con tale procedimento otteniamo una matrice rxn (dove n=2r-1) della forma H = [Arx(n-r) Ir ], matrice di controllo di un codice lineare CZ2n di lunghezza n e dimensione k=n-r=2r-r-1.
Naturalmente, permutando le colonne in modo che le ultime r colonne corrispondano ordinatamente alle rappresentazioni binarie delle potenze 20, 21,…, 2r-1 si ottiene una matrice di controllo in forma standard di un codice equivalente (quindi con eguali parametri).
Per esempio per r=3 si ottiene la matrice 3x7 in forma standard:
H’ =
1 0 0 1 1 1 0
0 1 0 1 1 0 1
0 0 1 1 0 1 1
(valore numerico di ogni colonna: 3 5 6 7 1 2 4 )
Se è la distanza di tale codice C, poiché per costruzione la matrice H ha colonne tutte diverse e non nulle, si ha 3, e C è un [n=2r-1, k=2r-r-1, ]-codice lineare a correzione d’errore che corregge 1 errore.
Calcoliamo l’esatto valore della distanza : consideriamo la parola v=x1x2…..xn Z2n in cui x1=x2=x3=1 ed xj=0 per ogni j>3 (in pratica tutti i bits di v sono nulli tranne quelli di indice corrispondente alle colonne di valore numerico 3,1,2 che sono =1: ricordare che n=2r-13 perché r>1); si ha allora
Hv = H1x1+H2x2+ ….+ Hnxn = H1x1+ H2x2+H3x3 = H1+ H2+H3 = 0
(sommando le 3 colonne corrispondenti ai valori numerici 1,2,3 si ottiene 0, come è facile verificare). Dunque la somma di 3 delle colonne è nulla, e per i risultati precedenti si ha =3 (perché
3)
Abbiamo dunque (fissato r>1) costruito un [n=2r-1, k=2r-r-1 ,3]-codice lineare a correzione d’errore che corregge 1 errore: tale codice è detto codice di Hamming H(r) e fu costruito da Hamming (1950) (in effetti per ogni fissato r si tratta di una classe di codici equivalenti, al variare dell’ordine delle colonne della matrice di controllo).
Teorema. Il codice di Hamming H(r) è perfetto.
Dimostrazione:
Si deve dimostrare vera l’eguaglianza:
2n-k =
s
0
j j
n
dove s=1 in quanto 3==2s+1. Dunque la tesi diventa nel nostro caso:
2n-k =
0
n +
1
n = n+1
E tale eguaglianza è vera perché n-k=r, n=2r-1.
Esempio: nel caso r=3, abbiamo visto che la matrice di controllo del codice H(3) (in forma standard) è:
H =
1 0 0 1 1 1 0
0 1 0 1 1 0 1
0 0 1 1 0 1 1
Il codice H(3) é un (n=2r-1=7, k=2r-r-1=4 ,3)-codice lineare contenente 2k=24=16 parole di lunghezza 7. Per trovare le parole del codice basta costruire la matrice generatrice:
K =
1 1 1 0
1 1 0 1
1 0 1 1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
e calcolare tutti i prodotti w=Kv al variare di v=x1x2x3x4Z24, ottenendo le 16 parole seguenti:
C = { 0000000, 1000110, 0100101, 0010011, 0001111, 1100011, 1010101, 1001001, 0110110, 0101010, 0011100, 1110000, 1101100, 1011010, 0111001, 1111111 }.
Il codice di Hamming H(r) permette di codificare 2k simboli distinti (dove k=2r-r-1).
Nella tabella seguente, in corrispondenza di alcuni valori della ridondanza r , vi sono la lunghezza n, la dimensione k e la cardinalità 2k del codice H(r):
ridondanza r lunghezza n=2r-1 dimensione k=2r-r-1 cardinalità 2k
2 3 1 2
3 7 4 16
4 15 11 2048
5 31 26 2147483648
Se vogliamo codificare i simboli di un insieme S con un codice di Hamming, troviamo la minima cardinalità 2k che non sia inferiore alla cardinalità di S, associamo ad ogni simbolo s di S una e una sola parola v di lunghezza k in Z2k , e poi (calcolando Kv dove K è la matrice generatrice) aggiungiamo r bits di controllo, ottenendo alla fine una parola di lunghezza n=2r-1 in Z2k che viene spedita nel canale di comunicazione: un tale codice ci permette di correggere 1 errore di trasmissione (e di rilevare un massimo di 2 errori di trasmissione, essendo =3).
Per cercare in generale [n, k, ]-codici lineari perfetti, diversi da quelli di Hamming, sappiamo che essi devono soddisfare l’eguaglianza:
(*) 2n-k =
s
0
j j
n
(dove 2s+1, in modo che il codice corregga s errori).
Golay negli anni ’50 cercò sperimentalmente prima di tutto delle terne di numeri n,k,s (diverse dai parametri dei codici di Hamming) per cui l’eguaglianza (*) risultasse vera, e trovò solo 2 terne:
(23,12,3), (90,78,2), corrispondenti a dei “possibili” codici lineari.
La seconda terna avrebbe dovuto corrispondere ad un [90,78,5]-codice lineare, ma lo stesso Golay dimostrò che un tale codice non esiste.
Per la prima terna, invece, Golay riuscì a costruire (probabilmente per tentativi, ma questo non è storicamente noto) un [23,12,7]-codice lineare G23, mediante una matrice di controllo 11x23, e dunque una matrice generatrice 23x12.
Per qualche tempo si credette che i codici H(r) di Hamming e il codice G23 di Golay fossero gli unici codici perfetti (a meno di equivalenza), ma in seguito furono costruiti codici (non lineari) perfetti non equivalenti a questi (anche se con gli stessi parametri di questi).
Nel 1973, infine, Van Lint e Tievatainen dimostrarono che ogni codice (anche non lineare) perfetto ha gli stessi parametri di un codice di Hamming H(r) o del codice G23 di Golay.
Decodifica di un codice lineare.
La decodifica di un codice è un algoritmo che permette, data in input la parola v ricevuta attraverso il canale di comunicazione, di rilevare se c’è stato errore (se il codice è a rilevazione di errore) ed eventualmente di correggerlo (se il codice è a correzione d’errore), trovando la parola corretta originariamente inviata.
Nel caso di un codice generico a rilevazione d’errore C Z2n l’algoritmo di rilevazione dell’errore consiste nel verificare se la parola ricevuta v appartiene al codice o no, confrontandola con tutte le parole del codice.
Nel caso di un codice lineare, con matrice di controllo H, esiste un algoritmo di rilevazione dell’errore più efficiente: Hv0 vC si è verificato errore nella trasmissione.
Nel caso di un codice generico a correzione d’errore CZ2n, l’algoritmo di correzione dell’errore, se wC è la parola erroneamente ricevuta, consiste, come visto già in precedenza, nel calcolare la parola vC tale che la distanza (v,w) sia minima (metodo della parola più vicina): v sarà la parola originariamente inviata. Si tratta di calcolare le distanze di 2k coppie di parole (le coppie formate da w e da una parola di C): è un algoritmo di alta complessità di calcolo.
Vediamo, nel caso di un codice lineare con matrice di controllo K, se esiste un algoritmo di correzione dell’errore più efficiente.
Facciamo alcune operazioni preliminari.
Sia dato un codice lineare C Z2n, di dimensione k.
Essendo C un sottogruppo additivo del gruppo Z2n, possiamo considerare la relazione di congruenza modulo C nel gruppo Z2n e per ogni vZ2n possiamo costruire la classe di equivalenza [v] rappresentata da v, contenente le somme della forma v+w al variare di w nel sottogruppo C: sappiamo che le diverse classi formano una partizione di Z2n e che ognuna ha cardinalità =C= 2k ; inoltre il numero delle classi (sempre per il Teorema di Lagrange) è uguale a 2n/2k=2n-k.
E’ ovvio che la classe [0] coincide con lo stesso codice C.
Poniamo m=2k ed elenchiamo in una riga le m parole di C (in un ordine arbitrario), cominciando dalla parola nulla:
v1=0 v2 v3 …….. vm
Ora scegliamo una parola wZ2n di peso minimo fra quelle che non compaiono nella riga degli elementi di C (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 nella prima riga:
v1=0 v2 v3 …….. vm w=w+v1 w+v2 w+v3 …… w+vm
Poiché w non é congruo 0 modulo C, si ha [w][0]=C.
Scegliamo poi una parola zZ2n di peso minimo fra quelle che non compaiono nelle 2 righe già costruite, ed elenchiamo in una terza riga le parole della classe [z] ottenute sommando ordinatamente z con le parole di C della prima riga:
v1=0 v2 v3 …….. vm w=w+v1 w+v2 w+v3 …… w+vm
z=z+v1 z+v2 z+v3 …… z+vm
Poiché z non é congruo 0 modulo C e non è congruo w modulo C, si ha [z][0]=C, e [z][w].
Così procedendo otteniamo 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: la parola iniziale di ogni riga è detta leader della classe. Inoltre per costruzione ogni parola (dalla seconda riga in poi) si ottiene sommando al leader la parola di C (nella prima riga) che sta nella stessa colonna.
La matrice ottenuta è detta matrice standard 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.
Inoltre la matrice ha come numero di colonne la cardinalità 2k del codice, e come numero di righe il numero 2 n-k delle distinte classi di congruenza modulo C.
