Matematica Discreta II
Lezione del giorno 28 novembre 2007
Teoria dei codici a rilevazione e correzione d’errore.
Supponiamo che un soggetto A debba spedire un’informazione ad un soggetto B attraverso un canale di comunicazione.
Poiché i canali attuali sono per lo più digitali, è necessario effettuare prima una codifica dell’informazione: se supponiamo, per semplicità, che il canale di comunicazione sia un canale binario, saranno spediti numeri binari, quindi blocchi di n cifre binarie a1a2…….an con ai=0,1 (supporremo anche che la lunghezza n del blocco sia costante).
Ognuno di tali blocchi in termini combinatori è una parola di lunghezza n sull’alfabeto {0,1}.
Se identifichiamo {0,1} con l’insieme Z2 delle classi di congruenza modulo 2, ogni parola di lunghezza n sull’alfabeto {0,1} può essere identificata con una n-upla di elementi di Z2 , quindi con un elemento del prodotto cartesiano di n insiemi tutti coincidenti con Z2 , che indicheremo con Z2n: Z2n = { v / v= a1a2…….an con ai=0,1Z2 }
Dal calcolo combinatorio sappiamo che le parole in Z2n sono in totale in numero di 2n .
Se l’informazione da spedire attraverso il canale è composta da elementi minimi di informazione contenuti in un insieme S (che possono per esempio essere singoli caratteri alfanumerici, oppure blocchi di alcuni di essi, o in generale qualunque elemento che contenga un’informazione di qualche natura), la codifica consiste nell’associare ad ogni elemento di S una parola di lunghezza n in Z2n : tale parola viene spedita lungo il canale, ricevuta da B, il quale effettua la decodifica, risalendo all’elemento di S che rappresenta l’informazione originaria (ovviamente per garantire l’univocità della decodifica, due elementi distinti di S devono avere codifiche diverse in Z2n ).
In termini formali la codifica è una funzione iniettiva f: S Z2n , mentre la decodifica è una funzione g: Z2n S tale che g(f(s))=s per ogni sS (quindi la composizione gf è la funzione identica di S). Si può notare che deve essere necessariamente S≤ 2n, dunque n≥log2S.
Tutte le possibili immagini di elementi di S mediante f (quindi tutte le possibili codifiche degli elementi di S) formano un sottoinsieme C di Z2n (che ha la stessa cardinalità di S), detto codice (binario) di lunghezza n: quindi un codice (binario) di lunghezza n non è altro che un sottoinsieme (non vuoto) di parole di lunghezza n in Z2n, dette appunto parole del codice.
Il canale di trasmissione attraverso il quale vengono trasmesse le informazioni può però essere disturbato da interferenze, rumori etc., e dunque una parola vZ2n trasmessa dal soggetto A può essere modificata da alcuni errori ed essere ricevuta come parola diversa wZ2n dal soggetto B.
Chiameremo errore (di trasmissione) la modifica di 1 singolo bit della parola inviata: quindi un bit 0 che si trasforma in 1 o viceversa.
Esempio.
Supponiamo che l’informazione trasmessa sia un’indicazione di direzione in una delle direzioni cardinali N,S,E,O, e che la codifica utilizzi un codice C1 di lunghezza 2 nel modo seguente:
N 00, S 01, E 10, O 11 Dunque in questo caso C1= Z22.
Questo codice è “economico” (le parole del codice hanno lunghezza “breve”), ma se si verifica 1 errore nella trasmissione esso non può essere rilevato: se una parola vC1 viene modificata in 1 bit, essa si trasforma in ogni caso in un’altra parola del codice, quindi in una parola “accettabile” e il soggetto B non può accorgersi dell’errore di trasmissione.
Supponiamo invece che la codifica utilizzi un codice C2 di lunghezza 3 nel modo seguente:
N 000, S 110, E 011, O 101 quindi C2={000,110,011,101}Z23 .
Questo codice, di lunghezza maggiore del precedente, è capace di rilevare il verificarsi di 1 singolo errore nella trasmissione: se una parola vC2 viene modificata in 1 bit, essa si trasforma in ogni caso in un’altra parola che non appartiene al codice, e il soggetto B si accorge che la parola ricevuta non è corretta. D’altronde questo codice non è capace di rilevare il verificarsi di 2 errori nella trasmissione: se per esempio la parola inviata é v=000C2 e viene modificata nel 2° e 3° bit, essa si trasforma nella parola w=011C2, e il soggetto B non può accorgersi dell’errore di trasmissione.
Pur rilevando 1 singolo errore di trasmissione, il codice C2 non è però sempre in grado di correggerlo, cioè di individuare con certezza la parola esatta che era stata inviata: per esempio se la parola inviata è v=000C2 e viene modificata nel 1° bit, essa si trasforma nella parola w=100C2, e il soggetto B (se è a conoscenza del fatto che al più 1 errore è possibile) dopo avere rilevato che si è verificato l’errore, non può essere certo della parola corretta inviata, perché questa potrebbe ugualmente essere la parola z=110 (con errore nel 2° bit) o la parola r=101 (con errore nel 3° bit).
Infine supponiamo invece che la codifica utilizzi un codice C3 di lunghezza 6 nel modo seguente:
N 000000, S 111000, E 001110, O 110011 quindi C2={000000,111000,001110,110011}Z26 .
Questo codice, di lunghezza ancora maggiore, è capace di rilevare il verificarsi di 1 singolo errore nella trasmissione (come si verifica con ragionamento analogo al precedente) ed anche di 2 errori (perché se una parola vC3 viene modificata in 2 bits, essa si trasforma in ogni caso in un’altra parola che non appartiene al codice, e il soggetto B si accorge che la parola ricevuta non è corretta).
D’altronde questo codice è anche capace di correggere 1 singolo errore nella trasmissione: in ogni caso, partendo da una parola vC3 e modificando 1 solo bit, si ottiene una parola che non può provenire, con la modifica di 1 solo bit, da altre parole del codice diverse da v, quindi il soggetto B è in grado di stabilire con certezza che v è la parola corretta inviata.
Gli esempi precedenti sono relativi a problematiche che riguardano i codici a rilevazione d’errore e i codici a correzione d’errore.
L’origine storica della teoria di fa risalire ad Hamming, in un periodo (dopo la seconda guerra mondiale) in cui egli si occupava della memorizzazione di informazioni su schede perforate, ognuna contenente una parola binaria di 32 bits: avendo osservato che talvolta una scheda conteneva un singolo bit errato, cercò una teoria formale che permettesse di scoprire automaticamente l’errore ed eventualmente correggerlo.
Un concetto alla base della teoria, come si capisce dagli esempi precedenti, è quello di distanza di Hamming: date le parole binarie v,wZ2n di lunghezza n, si chiama distanza (v,w) di v da w il numero di bits (nella stessa posizione) in cui le due parole differiscono.
Per esempio nel codice C3 introdotto sopra, le parole v=000000, w=111000 hanno distanza 3 (differiscono nel 1°, 2°, 3° bit).
Ricordiamo che, dato un insieme A, una metrica su A è una funzione dal prodotto cartesiano AxA nell’insieme dei numeri reali non negativi tale che:
1) dati comunque a,bA, si ha (a,b)=0 a=b 2) dati comunque a,bA, si ha (a,b)= (b,a)
3) dati comunque a,b,cA, si ha (a,c)≤(a,b)+(b,c) (diseguaglianza triangolare)
Esempio: se A è l’insieme dei punti del piano e se (a,b) è l’usuale misura della distanza del punto a dal punto b, si ottiene una metrica su A (la diseguaglianza triangolare discende dalla nota proprietà geometrica: la misura di un lato di un triangolo è ≤ della somma delle misure degli altri 2 lati).
Teorema. La distanza di Hamming è una metrica su Z2n. Dimostrazione:
Le proprietà 1) e 2) sono evidenti.
Per quanto riguarda la 3): siano v,w,zZ2n sia D(v,z) l’insieme delle posizioni dei bits in cui le parole v,w differiscono (quindi (v,z) = D(v,z)); analoghe costruzioni per D(v,w), D(w,z) (con
(v,w) = D(v,w), (w,z) = D(w,z).
Se iD(v,z), le parole v,z differiscono nel bit di posizione i, dunque vi sono 2 casi possibili:
a) v,w differiscono nel bit in posizione i (dunque iD(v,w))
b) v,w hanno lo stesso bit in posizione i (dunque iD(v,w)), ma allora in questo caso iD(w,z), perché w,z differiranno nel bit in posizione i.
Dunque ogni elemento iD(v,z) appartiene ad uno fra gli insiemi D(v,w), D(v,z), ossia D(v,z) è contenuto nell’unione insiemistica di D(v,w) e D(v,z) , e passando alle cardinalità:
D(v,z)≤ D(v,w)D(v,z) ≤D(v,w)+D(w,z), da cui la tesi.
Ovviamente la distanza di Hamming è legata al numero di errori nella parola inviata vZ2n : se s è il numero di errori nella trasmissione, e se viene ricevuta la parola wZ2n, il valore di (v,w) coincide esattamente con s.
Possiamo rappresentare la situazione graficamente. Se definiamo, per ogni parola vZ2n la sfera Rs(v) di centro v e raggio s uguale all’insieme delle parole di wZ2n tali che (v,w) ≤ s, fissata una parola vC da inviare, le parole di Rs(v) distinte da v sono esattamente tutte le possibili parole che possono essere ricevute erroneamente al posto di v nell’ipotesi che il numero di errori sia ≤s :
Rs(v) La sfera Rs(v) contiene (oltre v) tutte le parole s che possono essere ricevute al posto di v (se il v il numero degli errori non è superiore ad s).
Diremo che il codice CZ2n è un codice a rilevazione d’errore che rileva s errori se, per ogni parola vC inviata, e in caso di ricezione di una diversa parola wZ2n al posto di v, è possibile rilevare che la parola ricevuta è errata nell’ipotesi che nella trasmissione il numero di errori sia
≤s .
Per potere rilevare che la parola ricevuta w è errata, si deve verificare che wC, dunque (per quanto detto sopra) la definizione precedente equivale ad affermare che per ogni vC la sfera Rs(v) non contiene parole del codice C diverse da v.
Dato un codice CZ2n chiameremo distanza del codice C la minima distanza di 2 parole distinte v,wC: = min{(v,w) / v,wC, vw}
Dato un generico codice CZ2n di cardinalità m, per calcolare la distanza di C si devono calcolare tutte le possibili distanze di coppie di parole distinte (che sono in tutto m(m-1)/2, per la proprietà 2) della metrica).
Esempio. Dato il codice C={0111, 0001, 1010, 1000}Z24, si ha, calcolando le distanze di tutte le coppie di parole distinte del codice:
(0111,0001)=2, (0111, 1010)=3, (0111, 1000)=4, (0001, 1010)=3, (0001, 1000)=2,
(1010, 1000)=1
dunque in questo caso =1.
Teorema. Sia dato un codice CZ2n di distanza .
C è un codice a rilevazione d’errore che rileva s errori ≥s+1.
Dimostrazione:
(): Se C è un codice a rilevazione d’errore che rileva s errori, e se per assurdo ≤s , esisterebbero due parole distinte v,wC tali che (v,w)=≤s, dunque wRs(v), contraddizione.
(): Se ≥s+1, fissata una parola vC, per ogni parola wC diversa da v è (v,w)≥≥s+1>s, dunque wRs(v), e C è un codice a rilevazione d’errore che rileva s errori.
Diremo che il codice CZ2n è un codice a correzione d’errore che corregge s errori se, per ogni parola vC inviata, e in caso di ricezione di una diversa parola wZ2n al posto di v, è possibile rilevare che la parola ricevuta è errata ed anche correggerla, ossia calcolare in modo univoco la parola corretta v, nell’ipotesi che nella trasmissione il numero di errori sia ≤s .
Teorema. Il codice CZ2n è un codice a correzione d’errore che corregge s errori comunque date 2 parole distinte v,wC si ha Rs(v)Rs(w)=.
Dimostrazione:
(): Se per assurdo esistesse una parola zRs(v)Rs(w), essa, se ricevuta, potrebbe provenire (con un numero di errori ≤s) sia da v che da w, quindi l’errore non potrebbe essere corretto in modo univoco, contraddizione.
(): Sia w una parola errata ricevuta al posto della parola vC (quindi wRs(v)): allora si può rilevare l’errore in quanto wC (se per assurdo fosse wC, sarebbe wRs(v)Rs(w), contraddizione).
Ma si può anche correggere l’errore in modo univoco con il metodo della parola più vicina (o della massima verosimiglianza): si calcola la parola tC che abbia distanza minima dalla parola errata w (quindi (t,w)≤(v,w)≤s, ossia wRs(t)); tale parola t coincide con la parola v inviata (in caso contrario sarebbero v,t parole distinte di C tali che wRs(v)Rs(t), contraddizione).
In termini di sfere, il Teorema precedente afferma che il codice CZ2n è un codice a correzione d’errore che corregge s errori le sfere di raggio s con centro in distinte parole del codice non si intersecano.
Teorema. Sia dato un codice CZ2n di distanza .
C è un codice a correzione d’errore che corregge s errori ≥2s+1.
Dimostrazione:
(): Se per assurdo fosse <2s+1, esisterebbero 2 parole distinte v,wC tali che (v,w)=≤2s, quindi v,w differiscono in bits.
Poiché in particolare C è anche un codice a rilevazione d’errore che rileva s errori, per un Teorema precedente si ha ≥s+1.
Possiamo allora costruire una parola tZ2n ottenuta da v modificando s dei bits in cui v differisce da w: si ha ovviamente (v,t)=s, (t,w)=-s≤s, dunque tRs(v)Rs(w), in contraddizione con il Teorema precedente.
(): Per il Teorema precedente basta dimostrare che comunque date 2 parole distinte v,wC si ha Rs(v)Rs(w)=. Se per assurdo fosse tRs(v)Rs(w), sarebbe (v,t)≤s, (w,t)≤s, e per la diseguaglianza triangolare si avrebbe:
≤(v,w)≤(v,t)+(w,t)≤2s in contraddizione con l’ipotesi.
