Matematica Discreta III
Lezione del giorno 9 maggio 2008
Un caso particolare dell’algoritmo di decodifica (mediante la matrice di decodifica) si ha se C è un H(r)-codice di Hamming (quindi un [2r-1, 2r-r-1, 3]-codice lineare): esso è un codice perfetto in cui s=(-1)/2=1, dunque le sfere di raggio 1 e centro nelle distinte parole di C sono una partizione di Z2n (dove n=2r-1). Ogni parola w di Z2n che non appartiene a C si trova a distanza 1 da una e una sola parola vC (che è dunque quella a distanza minima): se j è la posizione del bit in cui v, w differiscono, si ha w=v+ej (dove ej è il vettore di Z2n che ha 1 nella posizione j e tutti gli altri bits 0) dunque, se H è la matrice di controllo di C:
Syn(w) = wH = vH+ejH = ejH Se H1,…..,Hn sono le righe di H, ciò equivale a:
Syn(w) = ejH = 0H1+0H2+…+1Hj+…+0Hn = Hj
Dunque, per individuare la parola vC a distanza minima da w, l’algoritmo è il seguente: si calcola la sindrome di w, si trova la riga di indice j con cui tale sindrome coincide, e si modifica in w il bit di posizione j (in questo caso perciò non è necessario costruire l’intera matrice di decodifica e le sindromi delle parole leader).
Esempio: Per esempio per r=3, data la matrice di controllo 7x3 del 3-codice di Hamming H(3):
H =
1 0 0
0 1 0
0 0 1
1 1 0
1 0 1
0 1 1
1 1 1
se w =1001101Z2n, la sindrome Syn(w)=wH =001 coincide con la riga di indice 7, dunque, modificando in w il bit di posizione 7, si trova la parola del codice a distanza minima: v =1001100.
Se poi il codice di Hamming H(r) è definito mediante una matrice di controllo (non in forma standard) con le righe che ordinatamente (dall’alto in basso) sono le rappresentazioni in base 2 dei numeri 1,2,….,2r-1, allora l’algoritmo di decodifica diventa ancora più semplice: per individuare la parola vC a distanza minima da w si calcola la sindrome di w, si calcola poi il numero j di cui tale sindrome è la rappresentazione in base 2, e si modifica in w il bit di posizione j.
Esempio: Per esempio per r=3, data la matrice di controllo 7x3 del 3-codice di Hamming H(3):
H =
1 1 1
0 1 1
1 0 1
0 0 1
1 1 0
0 1 0
1 0 0
e considerata la parola w =1001101Z2n, calcolando la sindrome wH =110 si osserva che essa è la rappresentazione in base 2 del numero j=6, dunque, modificando in w il bit di posizione 6, si trova la parola del codice a distanza minima: v =1001111.
Pattern di errore
Se v,w{0,1}n=Z2n, sappiamo che la distanza di Hamming fra v e w è uguale al peso della somma:
(v,w) = (v+w)
in quanto i bits =1 nella somma corrispondono esattamente ai bits in cui le 2 parole differiscono.
Per questo la parola somma v+w è detta anche pattern di errore relativo alla coppia (v,w) : se v è la parola trasmessa nel canale di trasmissione e se w è quella ricevuta, i bits =1 del pattern di errore v+w indicano in quali posizioni sono avvenuti gli errori di trasmissione.
Per esempio se v=01001, w=11100, allora v+w=10101 (errori nel 1°, 3° e 5° bit).
Se il canale di trasmissione è simmetrico e la probabilità di errore (nel singolo bit) è p, fissata la parola zZ2n , la probabilità che (nell’invio di una parola nel canale) il pattern di errore coincida con z è esattamente ps(1-p)n-s, se s=(z) è il peso della parola z.
Probabilità di corretta decodifica in un codice lineare
Sia C Z2n un codice lineare di dimensione k, e supponiamo costruita una sua matrice standard di decodifica:
(wij) i=1,…,2n-k ; j=1,…..,2k (con leaders: w11,w21,….. ) Allora:
Teorema. La decodifica (mediante il principio della minima distanza) è corretta il pattern di errore è una delle parole leaders.
Dimostrazione:
Siano v,w rispettivamente la parola trasmessa e quella inviata, e supponiamo che w=wij (dunque w si trova in riga i e colonna j nella matrice di decodifica). Sappiamo che (mediante il principio della minima distanza) w viene decodificata come w1j (la parola di C nella 1a riga e nella stessa colonna j). Dunque la codifica è corretta quando v=w1j .
(): Se per ipotesi v=w1j (decodifica corretta) allora, per il modo in cui si costruisce la matrice di decodifica:
wij = w = w1j+wi1 = v+wi1 ; v+w = wi1
dunque il pattern di errore coincide con una delle parole leaders (quella della riga i) . (): Se per ipotesi il pattern di errore coincide con il leader della riga k:
v+w = wk1
allora wk1-w=vC, dunque wk1w (mod C), ossia wk1 si trova nella stessa classe di congruenza (e quindi nella stessa riga) di w=wij , da cui i=k, wk1= wi1, wij = w = w1j+wi1 = v+w+wi1, v=w1j, e la decodifica è corretta.
