Coduri Reed-Muller

Coduri Reed-Muller

Prezentare generală

Codurile Reed-Muller (RM) reprezintă o categorie importantă de coduri liniare, distincte de codurile Hamming prin algoritmul de codificare și decodificare. La codurile Reed-Muller, detecția, corecția și decodificarea propriu-zisă se produc simultan, rezultând în mod direct simbolurile informaționale din cuvântul de cod recepționat.

Definiția și parametrii codului RM(r, m)

Un cod Reed-Muller de ordinul r și lungimea determinată de parametrul m se notează RM(r, m) și are următorii parametri:

unde C(m, i) este combinarea de m luate câte i, iar 0 ≤ r ≤ m.

Matricea generatoare (construcție recursivă)

Matricea generatoare a codului RM(r, m) se construiește recursiv pornind de la vectorii de bază. Se definesc vectorii:

V₀ = (1 1 1 1 ... 1 1 1 1)    [2ᵐ componente, toate 1]
Vₘ = (0 0 0 0 ... 1 1 1 1)    [prima jumătate 0, a doua 1]
Vₘ₋₁ = (0 0 ... 1 1 0 0 ... 1 1)  [alternare pe sferturi]
...
V₁ = (0 1 0 1 ... 0 1 0 1)    [alternare bit cu bit]

Matricea generatoare cuprinde:

• Ordinul 0: doar vectorul V₀
• Ordinul 1: vectorii V₀, Vₘ, Vₘ₋₁, ..., V₁
• Ordinul 2: se adaugă toate produsele vectoriale Vᵢ × Vⱼ cu i > j
• Ordinul r: se adaugă toate produsele de câte r vectori simpli

Codarea se realizează prin: X = m × G, unde m este mesajul informațional.

Decodarea prin logică majoritară

Algoritmul de decodare Reed-Muller se bazează pe logica majoritară (majority logic decoding):

1. Se scriu relațiile de control pentru fiecare componentă a mesajului informațional, pornind de la vectorii compuși spre cei simpli
2. Pentru fiecare componentă, se evaluează un sistem de ecuații
3. Valoarea fiecărei componente este valoarea majoritară din sistemul corespunzător
4. Se elimină progresiv influența vectorilor deja evaluați
5. Procesul se repetă până la determinarea tuturor componentelor mesajului

Exemplu: RM(1, 3)

Pentru codul RM(1, 3) calculăm parametrii:

m = 3, r = 1
n = 2³ = 8
k = C(3,0) + C(3,1) = 1 + 3 = 4
n - k = 4 biți de control
d_min = 2³⁻¹ = 4
t = (4-1)/2 = 1 eroare corectabilă

Matricea generatoare (4×8):

V₀ = (1 1 1 1 1 1 1 1)
V₃ = (0 0 0 0 1 1 1 1)
V₂ = (0 0 1 1 0 0 1 1)
V₁ = (0 1 0 1 0 1 0 1)

Codarea mesajului m = (a₀, a₃, a₂, a₁) = (1, 0, 1, 1):

X = m · G = 1·V₀ + 0·V₃ + 1·V₂ + 1·V₁
  = (1 1 1 1 1 1 1 1) + (0 0 1 1 0 0 1 1) + (0 1 0 1 0 1 0 1)
  = (1 0 0 1 1 0 0 1)

Decodarea: Presupunem că se recepționează y = (1 0 0 1 1 0 1 1) (eroare pe poziția 7).

Determinarea lui a₁ prin logică majoritară, utilizând sistemul:

a₁ = y₀ ⊕ y₁ = 1 ⊕ 0 = 1
a₁ = y₂ ⊕ y₃ = 0 ⊕ 1 = 1
a₁ = y₄ ⊕ y₅ = 1 ⊕ 0 = 1
a₁ = y₆ ⊕ y₇ = 1 ⊕ 1 = 0

Valoarea majoritară: a₁ = 1 (apare de 3 ori din 4).

Se procedează similar pentru a₂ și a₃, apoi se elimină influența vectorilor simpli și se determină a₀.

Puncte cheie pentru examen

• Parametri RM(r,m): n = 2ᵐ, k = Σ C(m,i) pentru i = 0..r, d_min = 2ᵐ⁻ʳ
• Matricea generatoare se construiește recursiv din vectorii V₀, V₁, ..., Vₘ și produsele lor
• Codarea: X = m · G, operații în GF(2)
• Decodarea se face prin logică majoritară: valoarea fiecărei componente este cea care apare cel mai frecvent în sistemul de ecuații de control
• RM(1,3): n = 8, k = 4, d_min = 4, corectează 1 eroare
• Diferența față de Hamming: la RM, detecția, corecția și decodificarea sunt simultane