Coduri detectoare si corectoare de erori. Coduri Hamming

În domeniul compresiei de date (considerata în teoria codarii ca si ”codarea sursei”) codarea s-a
facut în scopul reducerii dimensiunii reprezentarii, presupunând un canal de comunicatie ideal, fara
pierderi. În cele ce urmeaza vom aborda pe scurt o problema diferita, si anume codarea în scopul
detectiei si eventual corectiei erorilor ce pot apare pe un canal de comunicatie real, cu erori
(considerata în teoria codarii ca si ”codarea canalului”).

În acest al doilea caz este evident ca, pentru a obtine detectie si corectie de erori, trebuie sa
încarcam suplimentar fluxul cu biti dedicati acestui lucru, având de a face cu o crestere a
dimensiunii reprezentarii (trebuie platit un pret...). În timp ce la compresia datelor se elimina cât
mai mult posibil redundanta, codurile corectoare adauga acel nivel de redundanta necesar pentru a
transmite datele în mod eficient si cu fidelitate pe un canal cu zgomot (cu erori).

•  Distanta Hamming 

 Pe lânga distantele prezentate într-un material anterior, o distanta de un interes deosebit în problema
noastra este distanta Hamming, numita astfel dupa Richard Hamming, cel care a introdus-o în 1950.
Distanta Hamming între doi vectori de dimensiuni egale este data de numarul de pozitii în care
acestia difera. Ea masoara astfel numarul de schimbari care trebuie facute într-un vector pentru a îl
obtine pe celalalt, sau reformulat numarul de erori care transforma un vector în celalalt.

• Exemple: 

vector 1 codare 126359 01101011
vector 2 notate 226389 01001110
distanta Hamming 3 2 3

Desi definirea este generala, în cele ce urmeaza von considera doar cazul vectorilor cu elemente
binare, fiind vorba de fluxuri de biti transmise pe canalul de comunicatie. În acest caz distanta este
data de numarul de 1 din rezultatul obtinut prin XOR.

Pentru început vom considera doar cazul simplu al erorilor singulare - adica avem un singur bit
eronat.

Sa consideram urmatoarea solutie simpla de codare – fiecare bit este codat prin repetarea sa de doua
ori. Introducem astfel în mod evident o redundanta care însa ne va permite sa detectam erori
singulare.

Daca la receptie obtinem coduri 00 respectiv 11 am receptionat corect 0 respectiv 1 iar daca
obtinem 01 sau 10 am detectat o eroare singulara (fara a putea decide însa nimic în sensul corectiei
ei).

• Exemplu: 

mesaj initial: 0.1.0.0.1.0.1.1.0.1
mesaj codat: 00.11.00.00.11.00.11.11.00.11
mesaj receptionat cu eroare: 00.11.00.00.10.00.11.11.00.11 => detectie de eroare

Remarcam faptul ca între oricare doua ”cuvinte de cod” valide avem o distanta Hamming 2.

• Exemplu: 

mesaj initial: 0.1.0.0.1.0.1.1.0.1 

mesaj codat: 000.111.000.000.111.000.111.111.000.111 

mesaj receptionat cu eroare: 000.101.000.000.111.000.111.111.001.111 

mesaj corectat: 000.111.000.000.111.000.111.111.000.111 

 => detectie si corectie de erori singulare 

Remarcam faptul ca între oricare doua ”cuvinte de cod” valide avem o distanta Hamming 3.

Din exemplele anterioare constatam ca, daca distanta Hamming între oricare cuvinte de cod valide 

este 2, putem detecta erori singulare dar nu le putem corecta - nu stim care cod valid aflat la distanta 

1 este cel corect. Daca distanta Hamming între oricare cuvinte de cod valide este 3 putem detecta 

erori singulare si putem corecta înspre codul valid aflat la distanta 1 (remarcam faptul ca, în acest 

caz, putem detecta chiar erori duble ! – fara însa a le putea corecta). 

Daca scopul este doar de a detecta erori se pot folosi si alte solutii cum ar fi simpli biti de paritate, 

sume de control, coduri ciclice de tip CRC, functii hash criptografice, etc. 

•  Codul Hamming (7,4) 

Unul din cele mai cunoscute coduri detectoare si corectare de erori singulare este codul numit 

Hamming (7,4). Acesta notatie indica faptul ca avem un cod de 7 biti din care 4 sunt biti de date 

independenti (restul fiind biti redundanti, reprezentând paritatea a diferite combinatii a bitilor de 

date). Codul contine deci 4 biti de date d1, d2, d3, d4 si 3 biti de paritate p1, p2, p3. Bitii de paritate 

sunt calculati astfel: 

p1 sumeaza d1, d2, d4 

p2 sumeaza d1, d3, d4 

p3 sumeaza d2, d3, d4 

iar organizarea bitilor în cuvântul de cod este urmatoarea: 

p1 p2 d1 p3 d2 d3 d4