Codul Hamming

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. De obicei se definesc doua matrici în legatura cu acest cod: matricea generatoare de cod G si matricea de detectie a paritatii H.

Se constata în G ca liniile 1,2 si 4 calculeaza sumele aferente paritatilor respective iar liniile 3,5,6,7 simplu copiaza bitii de date. În H cele 3 linii calculeaza paritatile corespunzatoare. La codare: se determina cuvântul de cod calculând paritatile corespunzatoare (se poate utiliza atât paritatea para cât si paritatea impara – în exemplele urmatoare vom folosi paritatea impara). La decodare: se calculeaza paritatile corespunzatoare si se verifica cu cele corecte (în fapt se sumeaza si cu paritatile corecte si se verifica sa rezulte 0).

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. Exemplu: vector 1: codare 126359 01101011 vector 2: notate 226389 01001110 Distanta Hamming 3 2 3 Desi definirea este generala, în cele ce urmeaza vom 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. XOR este o operație logică care emite adevărat atunci când ambele intrări sunt diferite (una este adevarata, cealalta este falsa). Altfel spus, XOReste adevărat ori de câte ori un număr impar de intrări este adevărat.