Distanța Hamming și detectarea erorilor

Distanța Hamming și detectarea erorilor

Introducere

Transmiterea datelor pe canale perturbate poate introduce erori: un bit 0 transmis poate fi recepționat ca 1 și invers. Pentru a detecta și corecta aceste erori, se utilizează coduri detectoare și corectoare de erori, al căror fundament matematic se bazează pe noțiunea de distanță Hamming.

Definiția distanței Hamming

Distanța Hamming d(x, y) între două cuvinte binare x și y de aceeași lungime n este numărul pozițiilor pe care cele două cuvinte diferă.

Formal, dacă x = (x₁, x₂, ..., xₙ) și y = (y₁, y₂, ..., yₙ), cu xᵢ, yᵢ ∈ {0, 1}, atunci:

d(x, y) = Σᵢ (xᵢ ⊕ yᵢ),  i = 1, ..., n

unde ⊕ reprezintă operația XOR (adunare modulo 2).

Proprietățile distanței Hamming

Distanța Hamming verifică axiomele unei metrici:

1. Non-negativitate și simetrie: d(x, y) = d(y, x) ≥ 0
2. Identitatea: d(x, y) = 0 dacă și numai dacă x = y
3. Inegalitatea triunghiului: d(x, y) ≤ d(x, w) + d(w, y)

Geometric, cele 2ⁿ cuvinte binare de lungime n pot fi reprezentate ca vârfurile unui hipercub n-dimensional cu latura 1, iar distanța Hamming corespunde numărului de muchii parcurse pe cel mai scurt drum între două vârfuri.

Greutatea Hamming

Greutatea Hamming w(x) a unui cuvânt binar x este numărul de poziții nenule, adică w(x) = d(x, 0), unde 0 este cuvântul nul.

Relația fundamentală este: d(x, y) = w(x ⊕ y).

Distanța minimă a codului

Fie un cod bloc C format dintr-o submulțime de cuvinte de cod din spațiul {0, 1}ⁿ. Se definește:

Distanța minimă a codului d_min = min { d(x, y) | x, y ∈ C, x ≠ y }.

Distanța minimă determină integral capacitatea de detecție și corecție a codului.

Capacitatea de detecție și corecție

Detecția erorilor: un cod cu distanță minimă d_min poate detecta cel mult e erori dacă:

d_min ≥ e + 1

Corecția erorilor: un cod cu distanță minimă d_min poate corecta cel mult t erori dacă:

d_min ≥ 2t + 1

Detecție și corecție simultană: un cod poate corecta t erori și detecta simultan e erori (e ≥ t) dacă:

d_min ≥ t + e + 1

Modelul canalului binar simetric (CBS)

Canalul binar simetric este modelul fundamental pentru analiza transmisiei cu erori. Acesta are:

• Intrare și ieșire: simboluri din {0, 1}
• Probabilitatea de eroare p: probabilitatea ca un bit transmis să fie inversat
• Simetria: P(ieșire = 1 | intrare = 0) = P(ieșire = 0 | intrare = 1) = p

Eroarea pe canal are caracter aditiv: dacă se transmite bitul b și se recepționează b', perturbația este e = b ⊕ b'. Un cuvânt de eroare e cu greutatea Hamming w(e) = t corespunde apariției a t erori.

Exemplu numeric

Fie cuvintele de cod x = 1011001 și y = 1100101 de lungime n = 7.

Calculăm distanța Hamming comparând poziție cu poziție:

Pozitia:  1  2  3  4  5  6  7
x:        1  0  1  1  0  0  1
y:        1  1  0  0  1  0  1
XOR:      0  1  1  1  1  0  0

Se obține d(x, y) = 4 (diferă pe pozițiile 2, 3, 4, 5).

Dacă aceste cuvinte fac parte dintr-un cod cu d_min = 4, atunci:

• Detecție: poate detecta cel mult e = 3 erori (4 ≥ 3 + 1)
• Corecție: poate corecta cel mult t = 1 eroare (4 ≥ 2·1 + 1 = 3)
• Simultan: poate corecta 1 eroare și detecta 2 erori (4 ≥ 1 + 2 + 1)

Puncte cheie pentru examen

• Distanța Hamming d(x, y) = numărul pozițiilor diferite între două cuvinte binare
• Greutatea Hamming w(x) = numărul de biți nenuli; relația d(x, y) = w(x ⊕ y)
• Distanța minimă d_min = cea mai mică distanță între oricare două cuvinte distincte ale codului
• Capacitate de detecție: d_min ≥ e + 1
• Capacitate de corecție: d_min ≥ 2t + 1
• Canalul binar simetric: model cu probabilitate de eroare p, eroare aditivă e = b ⊕ b'
• Reprezentarea geometrică: cuvintele de cod sunt vârfuri ale unui hipercub n-dimensional

Exemple practice suplimentare

Exemplu 1: Determinarea distanței minime a unui cod

Fie codul C = {0000, 0110, 1011, 1101} (cod bloc cu n = 4, k = 2).

Calculăm distanțele între toate perechile de cuvinte de cod:

d(0000, 0110) = 2    (diferă pe pozițiile 2, 3)
d(0000, 1011) = 3    (diferă pe pozițiile 1, 3, 4)
d(0000, 1101) = 3    (diferă pe pozițiile 1, 2, 4)
d(0110, 1011) = 3    (diferă pe pozițiile 1, 2, 4)
d(0110, 1101) = 3    (diferă pe pozițiile 1, 3, 4)
d(1011, 1101) = 2    (diferă pe pozițiile 2, 3)

Distanța minimă: d_min = 2

Capacitate:

• Detecție: d_min ≥ e + 1 → 2 ≥ e + 1 → e ≤ 1 — detectează cel mult 1 eroare
• Corecție: d_min ≥ 2t + 1 → 2 ≥ 2t + 1 → t ≤ 0.5 — nu poate corecta nicio eroare

Exemplu 2: Greutatea Hamming și relația cu distanța

Pentru un cod liniar, distanța minimă este egală cu greutatea minimă a cuvintelor de cod nenule.

Fie codul liniar generat de matricea:

G = [1 0 1 1]
    [0 1 1 0]

Cuvintele de cod (toate combinațiile de mesaje):

m = (0,0) → c = (0,0,0,0)    w = 0
m = (1,0) → c = (1,0,1,1)    w = 3
m = (0,1) → c = (0,1,1,0)    w = 2
m = (1,1) → c = (1,1,0,1)    w = 3

Greutatea minimă nenulă: w_min = 2, deci d_min = 2.

Exemplu 3: Sfere Hamming și limita de împachetare

Pentru un cod (n, k) corector de t erori, fiecare cuvânt de cod este centrul unei sfere de rază t în spațiul {0,1}ⁿ. Volumul sferei este:

V(n, t) = Σ C(n, i)  pentru i = 0, 1, ..., t

Limita Hamming (limita de împachetare):

2ᵏ · V(n, t) ≤ 2ⁿ

Exemplu: Hamming(7, 4), t = 1:

V(7, 1) = C(7,0) + C(7,1) = 1 + 7 = 8

2⁴ · 8 = 16 · 8 = 128 = 2⁷  ✓  (egalitate!)

Când se atinge egalitatea, codul se numește cod perfect. Codurile Hamming sunt coduri perfecte!