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.
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.
Inefficiente: rapporto tra i bit attuali e i bit totali è solo 1/3
(per memorizzare/comunicare 1MB si memorizzano/inviano 3Mb)
Codifica Hamming
Data una sequenza di bit, la suddividiamo 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)
Il tasso è 4/7, molto migliore del precedente.
Resta da dimostrare che correggere 1 errore.
Affermazione: Per ogni b e b’, le codifiche bG e b’G differiscono in ≥ 3
coordinate
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
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
Affermazione: Per ogni b e b’, le codifiche bG e b’G differiscono in ≥ 3
coordinate
d(x, y)= numero coordinate i con xi diverso da yi.
Spazio di tutte le possibili parole codice = {0, 1}7.
Se possiamo dimostrare Affermazione 1
ogni parola-codice bG non ha altre parole-codice in un raggio 2 intorno
ad essa.
 ogni punto a distanza Hamming 1 da una parola codice è sicuramente
più vicina a quella parola di qualunque altra, e dunque possiamo in tal modo
correggere gli errori a 1 bit.
c’ y
x
c
d(c,c’)=3, d(c,x)=1
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 >t da ogni
altra p.c.
 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 .
Nostra affermazione (Per ogni b e b’, le codifiche bG e b’G differiscono in
≥ 3 coordinate)
 {bG|b in {0, 1}4} è un codice (7, 4, 3).
Codici a correzione di errore
Applicazioni in vari campi: matematica e informatica.
Esempio 1: 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)
Esempio 2: Problema dei cappelli.
Tre giocatori: Anna, Beppe e Carlo.
Possono, prima della partita, concordare strategia.
Inizia il gioco.
Sulla testa di ognuno viene messo un cappello, rosso o blu.
Il colore è scelto in modo casuale, lanciando una moneta.
Ciascuno può vedere il cappello degli altri ma non il proprio.
Non possono comunicare in alcun modo.
Osservando il colore dei cappelli degli amici, Anna, Beppe e
Carlo devono scrivere indipendentemente su di un foglietto:
quello che ritengono il colore del loro cappello oppure 'passo'.
-A, B e C vincono solo se non tutti sono passati e se tutti
quelli che hanno indicato un colore lo hanno indicato giusto.
SOLUZIONI
E’ possibile garantirsi la vincita con probabilità ½:
A e B passano e C scrive a caso rosso o blu.
E' possibile vincere con probabilità 3/4:
Se vedo due colori diversi passo; se vedo lo stesso colore nei
due cappelli scrivo l'altro colore.
Otto casi possibili
In due casi (1/4 dei casi) i tre cappelli hanno lo stesso colore:
tutti e tre i giocatori sbaglieranno.
Nei rimanenti 6 casi (3/4 del totale), ci saranno due cappelli
dello stesso colore e uno diverso. I giocatori con il cappello
dello stesso colore passeranno, vedendo due colori diversi,
mentre il terzo risponderà correttamente!
Numero n qualsiasi di giocatori.
•
•
•
•
•
•
•
•
•
•
Ci sono n giocatori, numerati da 1 ad n.
I giocatori concordano una strategia, prima dell'inizio del gioco.
Sul capo di ciascuno di essi viene messo un cappello rosso o blu.
Il colore del cappello è scelto a caso.
I giocatori non conoscono il colore del proprio cappello.
I giocatori non possono comunicare durante il gioco.
I giocatori vedono il colore dei cappelli degli altri.
I giocatori consegnano un foglio con 'passo‘ oppure un colore.
Se tutti passano, perdono.
Se il colore scritto su uno dei fogli non corrisponde al colore del
cappello di chi lo ha consegnato, i giocatori perdono.
• Se tutti i giocatori che non hanno scritto passo, hanno riportato il
colore corretto allora i giocatori vincono.
Se n=2k-1, esiste strategia con cui si perde in 1 caso su 2k.
Strategia: Basata sulla Teoria dei codici per il controllo degli
errori
Trasmissione su canali rumorosi:
confronto tra Teoria di Hamming e Teoria di Shannon
(Visione ad Alto Livello)
•Obiettivi:
Shannon: funzioni di codifica e decodifica.
Hamming: codici, distanza minima.
•Scopo:
Shannon: massimizzare il tasso e minimizzare la
probabilità di decodifica errata.
Hamming: massimizzare il tasso e la distanza minima.
• Modello d’errore:
Shannon: casuale.
Hamming: avversariale (caso peggiore).
• In Pratica:
Risultati di Shannon ottimali ma non costruttivi
Teoria dei codici: non ottimali ma efficienti e veloci
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
Σ tale che C è lo spazio nullo di H, cioè
C = {y | HyT = 0}
C lineare è un sottospazio lineare di Σn  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=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
Codice = spazio nullo di H = {x | HxT=0}
Numero parole codice = 27-3=24
Codice di Hamming n=2l-1
H  tutti vettori di l bits, tranne 0...0
Codice = spazio nullo di H = {x | HxT=0}
l 1l
Numero parole codice = 2 2
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 wmin=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)
Codici a correzione di errore
Applicazioni in vari campi: matematica e informatica. Es.:
• Complessità: per pseudo-randomness, hardness amplification,
probabilistically checkable proofs.
• Crittografia: schemi di condivisione segreti, sistemi crittografici.
•
Matematica combinatoria e ricreativa.