Teoria dei codici correttori d'errore
Fondatore: Richard W. Hamming
Articolo: Error Detecting and Error Correcting Codes (1950)
In ogni trasmissione digitale possono avvenire errori.
Es. ricezione da sonde spaziali o satelliti: canale molto disturbato, segnale
molto debole  errori frequenti.
Es. riproduzione musica o immagini digitali: supporto fisico danneggiato.
Senza metodi efficaci e veloci di correzione degli errori non darebbe
possibile ricevere informazioni dallo spazio, usare un lettore di CD o un
telefonino!
Es. graffio di alcuni millimetri sulla superficie di un CD non pregiudica
l'ascolto grazie a codice di Reed - Solomon, in grado di correggere
'raffiche' di errori consecutivi di notevole lunghezza.
Es. Telefoni cellulari GSM e satelliti: interferenze gestite utilizzando
codici convoluzionali.
Applicazioni nei campi più diversi: dalle telecomunicazioni alla biologia
molecolare
Gestione errore su 1 bit in sequenze di bit.
Codice di ripetizione: Ripeti ciascun bit 3 volte
Se uno dei bit è erroneamente invertito, viene riconosciuto e corretto
durante la decodifica del suo blocco di 3 bit.
0000 000 000 000 000
Inefficiente: rapporto tra i bit attuali e i bit totali è solo 1/3
(per memorizzare/comunicare 1MB si memorizzano/inviano 3Mb)
Codifica Hamming (7,4) Sequenza di bitsuddividisa in porzioni da 4 bit.
Sia b il vettore che rappresenta una di tali porzioni, e codifichiamo b
come bG a 7 bit, (operazioni modulo 2)
1111 00000001111111
b  b0b1b2b3  bG  b0b1b2b3(b1  b2  b3)(b0  b2  b3)(b0  b1  b3)
Il tasso è 4/7, molto migliore. Vedremo che corregge 1 errore.
A=alfabeto
An=insieme di sequenze di n simboli su A
Definizione. La distanza di Hamming tra x e y in An è
d(x, y)=numero di coordinate i t.c. xi diverso da yi
es. d(0110,0011)=2
La distanza di Hamming è una metrica:
d(x, y) = d(y, x)
d(x, z) < d(x, y) + d(y, z)
d(x, y) = 0 sse x=y
Definizione: Un codice a correzione di errore è un sottoinsieme C di An.
La distanza minima di C è (minimo su tutte le coppie di parole diverse in C)
d(C)=min d(x,y)
Definizione: C è e error detecting se può rilevare <e errori;
C è t error correcting se può correggere <t errori
DECODIFICA: a minima distanza
Nota(esercizio): su BSC (con prob. errore <1/2)
(min distanza)=(max probabilità)
Definizione: Un codice a correzione di errore è un sottoinsieme C di An.
La distanza minima di C è (minimo su tutte le coppie di parole diverse in C)
d(C)=min d(x,y)
Definizione: C è e error detecting se può rilevare <e errori;
C è t error correcting se può correggere <t errori
Proposizione: Se d(C)>2t+1, C e’ 2t error detecting e t error correcting
Dim. d(C)=2t+1  sequenza a distanza <2t da parola codice non è in C
 2t error detecting
d(C)= 2t+1  sequenza r a distanza <t da p.c. ha distanza almeno
2t+1-t>t da ogni altra p.c. (vale disug. triangolare)
 prendendo la p.c. più vicina a r correggiamo t errori
 t error correcting
y
t
1
r
t
x
Parametri:
q = |A|
n = lunghezza delle parole codice
k = lunghezza del messaggio (lunghezza pre-codifica) = logq |C|
d = d(C)
Si vuole: valori grandi di k e d, e valori piccoli di n.
Possiamo anche cercare di massimizzare il tasso del codice k/n
codice a correzione di errore con questi parametri  codice (n, k, d)q .
Trasmissione su canali rumorosi:
confronto tra Teoria di Hamming e Teoria di Shannon
(Visione ad Alto Livello)
•Scopo:
Shannon: massimizzare il tasso e minimizzare la
probabilità di decodifica errata.
Fornisce: funzioni di codifica e decodifica
Hamming: massimizzare il tasso
e numero errori corretti.
Fornisce: codice
(funzioni di codifica e decodifica efficienti)
• Modello d’errore:
Shannon: random.
Hamming: avversariale (caso peggiore).
• In Pratica:
Risultati di Shannon ottimali ma non costruttivi
Teoria dei codici: non ottimali ma efficienti e veloci
Codici a correzione di errore
Applicazioni in vari campi: matematica e informatica. Es.:
• Trasmissione affidabile
• Memorizzazione su supporti soggetti a guasti (es. CD graffiato)
• Complessità: per pseudo-randomness, hardness amplification,
probabilistically checkable proofs.
• Crittografia: schemi di condivisione segreti, sistemi crittografici.
• Matematica combinatoria e ricreativa.
Esempio: Derandomizzazione di algoritmi
Definizione:
S  0,1 è paiwise - independen t se per ogni
n
i, j  1,..., n e b, c  0,1 si ha
PryS yi  b, y j  c  1 / 4
A= algoritmo randomizzato (usa n random bits indip.)
A volte basta indipendenza limitata.
Pairwise independence sufficiente  derandomizzazione possibile:
Invece di y di n bits random
(A corretto  prob scegliere y con successo =p>0)
run A per ogni y in S
( A corretto  esiste y con successo)
Algoritmo Deterministico A’
running time T(A’)= O(|S|T(A))
vogliamo S piccolo
Teroria dei codici  Esiste S dimensione O(n)
Codici lineari
Alfabeto= A = campo finito (es. {0,…,q-1}, q primo, operazioni mod q)
codice è lineare  esiste una matrice di controllo parità H (n-k x n) su
A tale che C è lo spazio nullo di H, cioè
C = {y | HyT = 0}
C lineare è un sottospazio lineare di An  x, y є C  x + y є C
x є C, a є Σ  ax є C.
C lineare generato da una matrice G (k x n):
righe = insieme massimale di parole codice linearmente indipendenti
= base spazio lineare.
Codice = {x | x=aG}
Codice di Hamming n=2l-1
H  tutti vettori di l bits, tranne 0...0
Codice = spazio nullo di H = {x | HxT=0}
k  2l  l  1
Numero parole codice =
2 2
k
2l 1l
ESEMPIO n=7=23-1
1 1 1 0 1 0 0
H  1 1 0 1 0 1 0
1 0 1 1 0 0 1
l=3, k=4,
numero parole codice =16
Definizione w(x) = peso di Hamming di x
= numero componenti di x non nulle
w(C)= minx in Cw(x)
Lemma Dato codice lineare C
w (C)= min numero colonne linearmente dipendenti di H
Dim. H ha r colonne l.d. in posizioni i1,…,ir
 esistono a1,...,ar tali che
a1ci1  ...  ar cir  0
 Esiste parola codice di peso r:
x  ( x1 ,..., xn )
ai
xi  
0
HxT  a1ci1  ...  ar cir  0
per i  i1 ,..., ir
altrimenti
Lemma Dato codice lineare C
w (C)= min numero colonne linearmente dipendenti di H
Per codici di Hamming il peso minimo di una parola è 3:
•
Tutte colonne non nulle  min num colonne l.d. >1
•
Tutte colonne diverse  c+c’ non nullo  min num colonne l.d. >2
•
In H tutti vettori  date c,c’ esiste in H colonna c’’=c+c’
 c + c’+ c’ ’=0  min num colonne l.d. è 3
Lemma Dato codice lineare C,
w (C) = d(C)
Dim.
d (C )  min d ( x , y)  d ( x' , y' )  w( x'  y' )  w(C )
x , yC
d (C )  min d ( x , y)  min d ( x ,0)  min w( x )  w(C )
x , yC
xC
xC
Corollario Un codice lineare C corregge t errori se
w (C)= d(C) > 2t+1
CODIFICA/DECODIFICA?
CODIFICA/DECODIFICA dei Codici di Hamming
H   tutti vettori l bits,  0...0   0 ,... n 1 ,
n  2l  1
x  C  Hx T  0
D(C)=3  corregge 1 errore
Siano c=(c0,…,cn-1)=parola codice,
c
r
r=(r0,…,rn-1)=sequenza da decodificare
r=c+e,
ei=1 sse errore in posizione i
HrT=H(c+e)T=HcT +HeT=HeT
0 errori
 r=c
e=0
 HrT=H0T=0
1 errore posizione i  r=c+(0...010…0)=c+ei  HrT=HeiT=i
DECODIFICA: Calcola sindrome s=HrT
se s=0 output r
se s=i output r+ei
Se si sono avuti >2 errori?
CODIFICA dei Codici di Hamming
| C | 2
n l
2
2l 1l
INPUT: bit di informazione= blocco di k=2l-l-1 bits
Vogliamo codifica sistematica: bit di informazione in primi k bit della p.c.
Proprietà Se scegliamo H=[A | In-k] allora G=[Ik | AT]
Dim. Dobbiamo mostrare che
Hx T  0 sse x  aG per qualche a  0,1 .
k
Sia x  (x' , x' ' )
Hx T  0  Ax 'T  x ' 'T  0  x ' 'T  Ax 'T
 x  ( x' , x ' A)  x  x ' G
CODIFICA SISTEMATICA:
input a=(a0,…,ak-1)
output parola codice c=aG c=(a0,…,ak-1,ck,…,cn-1)