Matematica Discreta III
Lezione del giorno 28 aprile 2008
Abbiamo dimostrato che, dato un codice (sistematico) CZ2n di lunghezza n e dimensione k, e data la sua matrice generatrice kx(n-k) in forma standard:
M = [ IkM’] M’ = (βij) i=1,….,k; j=1,…..,n-k da essa si può ricavare la matrice di controllo nx(n-k):
H =
k
In
M'
in modo che le parole vC del codice si possano caratterizzare in 2 modi equivalenti:
1) Esiste una parola wZ2k tale che wH=v 2) vH=0
Se si vuole definire qualcosa di analogo alla matrice di controllo anche per un generico codice (non necessariamente sistematico) CZ2n di lunghezza n e dimensione k, basta ragionare in questo modo:
- si costruisce, con una opportuna permutazione degli indici {1,2,…,n} delle posizioni dei bits, un codice sistematico C0 equivalente a C:
C0 = {x(1)x(2)…… x(n) / x1x2…… xnC}
e la sua matrice generatrice (ottenuta da opportune modifiche della matrice generatrice di C) - si costruisce la matrice di controllo H0 di C0 (in modo che vC0 vH0=0)
- si permutano le righe di H0 applicando agli indici di riga {1,2,…,n} la permutazione inversa
-1, ottenendo una matrice H
- le parole v del codice originario C sono tutte e sole quelle tali che vH=0 (come si verifica facilmente) e tale matrice H può essere definita come la matrice di controllo di C
Codici con bit di parità
Fissata la lunghezza n>1 del codice, costruiamo un codice lineare CZ2n che abbia distanza 2 (e che quindi sia in grado di rilevare 1 errore). La massima dimensione che C può avere (e che rende massimo il rateo di informazione k/n) è k=n-1 (se k=n, il codice C coincide con Z2n e =1). Per quanto dimostrato in precedenza, per costruire un codice di lunghezza n e dimensione k=n-1, basta costruire la sua matrice di controllo:
H =
k In
M'
Tale matrice è una matrice nx(n-k), dunque nx1 (in pratica 1 colonna di n bits) ed il blocco superiore M’ è una matrice kx(n-k)=(n-1)x1 (in pratica 1 colonna di n-1 bits), mentre la matrice identica In-k=I1 è un singolo bit=1.
Se vogliamo che 2, dobbiamo imporre che tutte le righe siano non nulle, dunque la matrice H è una colonna di n bits tutti =1.
La matrice generatrice del codice C è una matrice M = [ In-1M’] con k=n-1 righe, n colonne: le prime n-1 colonne formano la matrice identica In-1 , mentre l’ultima colonna è la colonna M’ con tutti bits=1.
Per generare le parole di C, al variare di una parola di lunghezza n-1:
w = (x1,x2,….,xn-1)Z2n-1
calcoliamo v = wM = (x1,x2,….,xn-1,x1+x2+……+xn-1)
Dunque, oltre agli n-1 bits di informazione, vi è un bit di controllo xn ottenuto sommando (in Z2) i bits di informazione x1,x2,….,xn-1. Il bit di controllo xn=x1+x2+……+xn-1 è allora =0 se è pari il
numero dei bits x1,x2,….,xn-1 che sono=1; invece è xn=x1+x2+……+xn-1=1 in caso contrario: tale bit di controllo è detto per questo bit di parità.
Per verificare se una parola di lunghezza n:
v = (x1,x2,….,xn-1,xn)Z2n
appartiene al codice C, si deve verificare se 0 = vH = (x1+x2+……+xn-1+xn) (quindi se la somma di tutti i bits è nulla).
Notiamo anche che la distanza è =2, perché 2 righe hanno sempre somma nulla.
Tali codici con bit di parità sono in grado di rilevare 1 errore (ma non sono in grado di correggerlo).
In effetti sono in grado in generale di rilevare un numero dispari (3,5,7…) di errori, perché, data la parola v = (x1,x2,….,xn-1,xn)C, quindi supponendo che 0 = vH = (x1+x2+……+xn-1+xn), la modifica di un numero dispari di bits xi rende la somma (x1+x2+……+xn-1+xn) non nulla, dando la possibilità di rilevare che la parola ricevuta non appartiene al codice C.
Codici di Hamming
Cerchiamo ora di costruire un codice lineare CZ2n che abbia distanza 3 (quindi che rilevi un massimo di 2 errori e corregga 1 errore): la matrice nx(n-k) di controllo dovrà avere righe tutte diverse e non nulle.
Poniamo r=n-k, ed esprimiamo tutto in funzione di tale parametro.
Se vogliamo rendere massimo il rateo di informazione k/n dobbiamo rendere minimo 1-k/n=r/n, dunque (fissato r=n-k) rendere massimo il numero n di righe della matrice di controllo.
Il numero massimo possibile di righe distinte non nulle (come vettori di Z2n-k) è 2n-k-1=2r-1: esse sono in pratica le rappresentazioni in base 2 dei numeri 1,2,…..,2r-1 (considerandole tutte di lunghezza omogenea r con l’aggiunta di opportuni bits=0 non significativi a sinistra).
Possiamo allora costruire la matrice H di controllo nx(n-k) dove il numero di righe è n=2r-1 (coincidente con la lunghezza del codice) e dove la dimensione è k=n-r=2r-1-r: tale matrice H avrà tutte le possibili n righe distinte non nulle di lunghezza 2n-k=2r (per avere la forma “standard” le ultime n-k righe dovranno formare la matrice identica In-k=Ir quindi dovranno corrispondere alle rappresentazioni in base 2 delle potenze 2r-1,2r-2,….,21,20, rappresentazioni che hanno un solo bit =1 e tutti gli altri =0).
Otterremo in questo modo (fissato il parametro r) un [2r-1,2r-1-r,]-codice lineare C con 3: tale codice è detto r-codice di Hamming e indicato con H(r) .
Per quanto osservato all’inizio della lezione, modificando tale matrice di controllo con una permutazione delle righe si ottiene un codice equivalente (che rispetta sempre la condizione di avere le righe che rappresentano tutti i numeri 1,2,…..,2r-1 in base 2): in effetti, quindi, l’r-codice di Hamming H(r) è un insieme di codici equivalenti, e non un singolo codice, ma ciò, dal punto di vista operativo, non è essenziale. Una forma notevole della matrice di controllo è quella
“crescente”, in cui le righe sono ordinatamente (dall’alto in basso) le rappresentazioni dei numeri 1,2,…..,2r-1 in base 2.
Notiamo anche che r2 (da r=1 segue n=1, k=0, ma noi studiamo solo valori della dimensione con k1), dunque n=2r-13.
In effetti la distanza dell’r-codice di Hamming (con r2) è esattamente =3: infatti vi sono 3 righe di somma nulla (per esempio le righe (1,0,0,….,0), (0,1,0,….,0), (1,1,0,….,0)).
Studiamo il caso r=2: il 2-codice di Hamming H(2) è un [3,1,3]-codice lineare (di cardinalità 21=2) con matrice di controllo 3x2 che ha 3 righe coincidenti con la rappresentazione in base 2 dei numeri 1,2,3:
H =
1 0
0 1
1 1
La matrice generatrice è la matrice 1x3:
M = 1 1 1
Al variare del vettore w=0,1Z21 si ottengono le 2 parole v=wM del codice:
H(2) = {000, 111}
Dunque H(2) coincide con il già noto codice di ripetizione di lunghezza 3.
Studiamo il caso r=3: il 3-codice di Hamming H(3) è un [7,4,3]-codice lineare (di cardinalità 24=16) con matrice di controllo 7x3 che ha 7 righe coincidenti con la rappresentazione in base 2 dei numeri 1,….,7:
H =
1 0 0
0 1 0
0 0 1
1 1 0
1 0 1
0 1 1
1 1 1
La matrice generatrice è la matrice 4x7:
M =
1 1 0 1 0 0 0
1 0 1 0 1 0 0
0 1 1 0 0 1 0
1 1 1 0 0 0 1
Al variare del vettore w=(x1,x2,x3,x4)Z24 si ottengono le 16 parole v=wM del codice:
H(3) = {0000000, 1000111, 0100110, 0010101, 0001011, 1100001, 1010010, 1001100, 0110011, 0101101, 0011110, 1110100, 1101010, 1011001, 0111000, 1111111}.
Ragionando in modo analogo si otterrà per r=4 un [15,11,3]-codice lineare H(4) di cardinalità 211, per r= 5 un [31,26,3]-codice lineare H(5) di cardinalità 226 e così via.
Possiamo notare che un difetto degli r-codici di Hamming è quello di avere lunghezza e dimensione di tipo particolare (n=2r-1, k=2r-1-r), e inoltre di avere in ogni caso distanza =3 (quindi l’incapacità di correggere più di 1 errore).
Un notevole pregio è quello di avere un rateo di informazione che cresce al crescere di r, ed anzi converge ad 1:
limrk/n= limr(2r-1-r)/(2r-1) = 1
Per esempio per r=3 il rateo é 4/70,57, per r= 4 è 11/150,73, per r=5 è 26/310,84 . Codici lineari perfetti
L’ Hamming bound per un generico (n,m,)-codice C:
m
s 0
j j
n ≤ 2n (dove s = (-1)/2 )
nel caso di un [n,k,]-codice lineare C diventa (essendo la cardinalità m=2k):
s 0
j j
n ≤ 2n-k (dove s = (-1)/2 )
Inoltre tale codice lineare sarà perfetto se la disuguaglianza è un’eguaglianza:
s 0
j j
n = 2n-k (dove s = (-1)/2 ) (*)
Notiamo allora che ogni r-codice di Hamming H(r) è perfetto: si tratta di un [2r-1,2r-1-r,3]-codice lineare con s=1, da cui (essendo n-k=r)
1 0
j j
n = n+1 = 2r = 2n-k
