Coduri Hamming

Coduri Hamming

Prezentare generală

Codurile Hamming sunt cele mai cunoscute coduri liniare bloc, capabile să corecteze o singură eroare. Un cod Hamming este definit de parametrul m ≥ 3 și are următoarele caracteristici:

Coduri bloc liniare - cadrul general

Un cod bloc liniar (n, k) codează blocuri de k biți mesaj în cuvinte de cod de n biți prin adăugarea a n - k biți de control. Codarea se realizează matriceal:

c = m · G

unde m este vectorul mesaj (1×k), iar G este matricea generatoare (k×n).

Pentru un cod sistematic, matricea generatoare are forma:

G = [Iₖ | P]

unde Iₖ este matricea unitate k×k, iar P este matricea de paritate k×(n-k).

Matricea de paritate H

Matricea de paritate (sau de control) H are dimensiunea (n-k) × n și satisface:

G · Hᵀ = 0

Pentru un cod sistematic: H = [Pᵀ | Iₙ₋ₖ].

Un cuvânt c este valid dacă și numai dacă c · Hᵀ = 0.

Decodarea prin sindrom

La recepție se primește vectorul r = c + e, unde e este vectorul de eroare. Se calculează sindromul:

s = r · Hᵀ = (c + e) · Hᵀ = e · Hᵀ

• Dacă s = 0: nu există erori detectabile
• Dacă s ≠ 0: sindromul indică poziția erorii (pentru erori singulare)

La codurile Hamming, coloanele matricei H sunt toate combinațiile nenule de m biți. Sindromul s nenul coincide cu coloana din H corespunzătoare poziției eronate.

Exemplu complet: Hamming(7, 4)

Alegem m = 3, deci n = 7, k = 4, n - k = 3.

Matricea de paritate H (3×7) conține toate combinațiile nenule de 3 biți ca și coloane:

        c₁ c₂ c₃ c₄ c₅ c₆ c₇
H = [ 1  1  1  0  1  0  0 ]
    [ 0  1  1  1  0  1  0 ]
    [ 1  1  0  1  0  0  1 ]

Matricea generatoare G (4×7) în formă sistematică:

        c₁ c₂ c₃ c₄ c₅ c₆ c₇
G = [ 1  0  0  0  1  0  1 ]
    [ 0  1  0  0  1  1  1 ]
    [ 0  0  1  0  1  1  0 ]
    [ 0  0  0  1  0  1  1 ]

Se verifică G · Hᵀ = 0 (toate produsele sunt vectorul nul, modulo 2).

Pas 1 - Codarea mesajului m = (1, 0, 1, 1):

c = m · G = (1,0,1,1) · G
c₁ = 1, c₂ = 0, c₃ = 1, c₄ = 1 (biți mesaj)
c₅ = 1·1 + 0·1 + 1·1 + 1·0 = 0 (mod 2)
c₆ = 1·0 + 0·1 + 1·1 + 1·1 = 0 (mod 2)
c₇ = 1·1 + 0·1 + 1·0 + 1·1 = 0 (mod 2)

Cuvânt de cod: c = (1, 0, 1, 1, 0, 0, 0)

Pas 2 - Simularea unei erori pe poziția 3:

Vectorul de eroare: e = (0, 0, 1, 0, 0, 0, 0)
Cuvânt recepționat: r = c + e = (1, 0, 0, 1, 0, 0, 0)

Pas 3 - Calculul sindromului:

s = r · Hᵀ = (1, 0, 0, 1, 0, 0, 0) · Hᵀ

s₁ = 1·1 + 0·1 + 0·1 + 1·0 + 0·1 + 0·0 + 0·0 = 1
s₂ = 1·0 + 0·1 + 0·1 + 1·1 + 0·0 + 0·1 + 0·0 = 1
s₃ = 1·1 + 0·1 + 0·0 + 1·1 + 0·0 + 0·0 + 0·1 = 0

Sindrom: s = (1, 1, 0)

Sindromul (1, 1, 0) coincide cu coloana 3 din H, deci eroarea este pe poziția 3.

Pas 4 - Corectarea:

Se inversează bitul de pe poziția 3: r₃: 0 → 1.

Cuvântul corectat: (1, 0, 1, 1, 0, 0, 0) = cuvântul original c.

Observații importante

• Codurile Hamming pot corecta o singură eroare (d_min = 3)
• Adăugând un bit global de paritate se obține codul Hamming extins cu d_min = 4, capabil să corecteze 1 eroare și să detecteze 2 erori
• Eficiența codului este k/n; pentru Hamming(7,4): 4/7 ≈ 57%

Puncte cheie pentru examen

• Parametrii: n = 2ᵐ - 1, k = n - m, d_min = 3
• Matricea generatoare G = [Iₖ | P], codarea: c = m · G
• Matricea de paritate H = [Pᵀ | Iₙ₋ₖ], relația G · Hᵀ = 0
• Decodarea: sindromul s = r · Hᵀ; dacă s ≠ 0, identifică poziția erorii
• La Hamming(7,4): n = 7, k = 4, m = 3, corectează 1 eroare
• Codul Hamming extins (cu bit de paritate suplimentar): d_min = 4, detectează 2 erori