Coduri BCH

Coduri BCH (Bose-Chaudhuri-Hocquenghem)

Prezentare generală

Codurile BCH constituie o clasă importantă de coduri ciclice cu o capacitate deosebită de corecție a erorilor. Ele generalizează codurile Hamming pentru corecția erorilor multiple și sunt fundamentale în aplicații practice de telecomunicații și stocare a datelor.

Câmpuri Galois GF(2ᵐ)

Codurile BCH se construiesc pe baza câmpurilor Galois (câmpuri finite). Un câmp Galois GF(2ᵐ) conține 2ᵐ elemente și se construiește pornind de la un polinom ireductibil p(x) de grad m peste GF(2).

Proprietăți esențiale ale lui GF(2ᵐ):

• Conține 2ᵐ elemente, inclusiv 0 și 1
• Operațiile de adunare și înmulțire se fac modulo p(x)
• Există un element primitiv α astfel încât fiecare element nenul poate fi scris ca o putere a lui α: GF(2ᵐ) \ {0} = {α⁰, α¹, α², ..., α^(2ᵐ-2)}
• Elementul primitiv satisface α^(2ᵐ-1) = 1

Polinomul minimal

Polinomul minimal al unui element αⁱ din GF(2ᵐ) este polinomul de cel mai mic grad peste GF(2) care are pe αⁱ ca rădăcină.

Proprietăți ale polinoamelor minimale:

• Polinomul minimal mᵢ(x) al lui αⁱ divide pe x^(2ᵐ-1) - 1
• Elementele conjugate αⁱ, α²ⁱ, α⁴ⁱ, ... (puterile lui 2 ale exponentului, modulo 2ᵐ - 1) au același polinom minimal
• Gradul lui mᵢ(x) este cel mult m

Construcția codului BCH

Un cod BCH binar, corector de t erori, are parametrii:

Polinomul generator g(x) al codului BCH corector de t erori este cel mai mic multiplu comun (cmmmc) al polinoamelor minimale ale elementelor α, α², ..., α²ᵗ:

g(x) = cmmmc{ m₁(x), m₂(x), ..., m₂ₜ(x) }

Deoarece elementele conjugate au același polinom minimal, în practică se simplifică:

g(x) = cmmmc{ m₁(x), m₃(x), m₅(x), ..., m₂ₜ₋₁(x) }

(polinoamele minimale ale elementelor cu indice par coincid cu cele ale conjugatelor lor cu indice impar.)

Matricea de control

Matricea de control H a codului BCH se construiește astfel încât un cuvânt de cod v(x) să admită rădăcinile α, α², ..., α²ᵗ:

        [ 1    α      α²      ...  α^(n-1)    ]
H   =   [ 1    α²     α⁴      ...  α^(2(n-1)) ]
        [ ...                                   ]
        [ 1    α²ᵗ    α⁴ᵗ     ...  α^(2t(n-1))]

Un vector v este cuvânt de cod dacă și numai dacă v · Hᵀ = 0.

Exemplu: construcția unui cod BCH cu t = 2

Alegem m = 4, deci n = 2⁴ - 1 = 15. Fie α un element primitiv al lui GF(2⁴), rădăcină a polinomului ireductibil p(x) = x⁴ + x + 1.

Pas 1: Determinăm polinoamele minimale.

Polinomul minimal al lui α:

m₁(x) = x⁴ + x + 1

(chiar polinomul primitiv, deoarece α este element primitiv)

Polinomul minimal al lui α³:

m₃(x) = x⁴ + x³ + x² + x + 1

(rădăcinile conjugate sunt α³, α⁶, α¹², α⁹)

Pas 2: Calculăm polinomul generator.

Deoarece 2t = 4, avem nevoie de polinoamele minimale ale lui α, α², α³, α⁴:

• m₁(x) = m₂(x) = m₄(x) = x⁴ + x + 1 (conjugatele lui α)
• m₃(x) = x⁴ + x³ + x² + x + 1

g(x) = cmmmc{m₁(x), m₃(x)}
     = m₁(x) · m₃(x)
     = (x⁴ + x + 1)(x⁴ + x³ + x² + x + 1)
     = x⁸ + x⁷ + x⁶ + x⁴ + 1

Pas 3: Parametrii codului rezultat.

Grad(g(x)) = 8, deci n - k = 8
Codul BCH(15, 7): n = 15, k = 7, d ≥ 5, corectează t = 2 erori

Cazuri particulare

• BCH cu t = 1: echivalent cu codul Hamming, g(x) = m₁(x), n - k = m
• Coduri BCH primitive: lungimea n = 2ᵐ - 1, generate de elemente primitive
• Coduri BCH extinse: se adaugă un bit de paritate pentru a crește distanța minimă

Puncte cheie pentru examen

• Codurile BCH sunt coduri ciclice care generalizează Hamming pentru corecția a t erori multiple
• Se construiesc pe câmpuri Galois GF(2ᵐ) cu element primitiv α
• Polinomul minimal mᵢ(x) = polinomul de grad minim peste GF(2) cu rădăcina αⁱ
• Polinomul generator: g(x) = cmmmc{m₁(x), m₃(x), ..., m₂ₜ₋₁(x)}
• Parametri: n = 2ᵐ - 1, d ≥ 2t + 1, n - k ≤ mt
• Exemplu BCH(15,7): m = 4, t = 2, g(x) = x⁸ + x⁷ + x⁶ + x⁴ + 1
• Elementele conjugate αⁱ și α²ⁱ au același polinom minimal

Exemple practice suplimentare

Exemplu 1: Tabelul complet GF(2⁴)

Fie p(x) = x⁴ + x + 1 polinomul primitiv. Elementele lui GF(2⁴) sunt:

Verificare: α¹⁵ = α⁰ = 1 (ciclul se repetă).

Cum se obține α⁴: Din p(α) = 0 → α⁴ + α + 1 = 0 → α⁴ = α + 1 (în GF(2), adunarea = scăderea).

Cum se obține α⁷: α⁷ = α⁶ · α = (x³ + x²) · x = x⁴ + x³ = (x + 1) + x³ = x³ + x + 1.

Exemplu 2: Determinarea polinoamelor minimale în GF(2⁴)

Clasele de conjugate (prin ridicare la puterea 2, modulo 15):

{α¹, α², α⁴, α⁸}    → m₁(x) = x⁴ + x + 1
{α³, α⁶, α¹², α⁹}   → m₃(x) = x⁴ + x³ + x² + x + 1
{α⁵, α¹⁰}           → m₅(x) = x² + x + 1
{α⁷, α¹⁴, α¹³, α¹¹} → m₇(x) = x⁴ + x³ + 1

Verificare clasa lui α³: α³ → α⁶ → α¹² → α²⁴ = α⁹ → α¹⁸ = α³ (ciclu de lungime 4).

Verificare clasa lui α⁵: α⁵ → α¹⁰ → α²⁰ = α⁵ (ciclu de lungime 2, deci grad 2).

Exemplu 3: Codarea unui mesaj cu BCH(15, 7)

Codul BCH(15, 7) are g(x) = x⁸ + x⁷ + x⁶ + x⁴ + 1.

Fie mesajul: m(x) = x⁶ + x⁴ + x² + 1 (biți: 1010101).

Codare sistematică (mesajul apare în primii k = 7 biți):

Pas 1: Calculăm x⁸ · m(x) = x¹⁴ + x¹² + x¹⁰ + x⁸

Pas 2: Calculăm restul r(x) = x⁸ · m(x) mod g(x)

  x¹⁴ + x¹² + x¹⁰ + x⁸ : x⁸ + x⁷ + x⁶ + x⁴ + 1
  ─────────────────────────
  x¹⁴ + x¹³ + x¹² + x¹⁰ + x⁶
  ─────────────────────────
  rest parțial: x¹³ + x⁸ + x⁶
  x¹³ + x¹² + x¹¹ + x⁹ + x⁵
  ─────────────────────────
  rest parțial: x¹² + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵
  ...continuând diviziunea...

  r(x) = x⁷ + x⁶ + x⁴ + x    (restul final)

Pas 3: Cuvântul de cod:
  v(x) = x⁸ · m(x) + r(x)
       = x¹⁴ + x¹² + x¹⁰ + x⁸ + x⁷ + x⁶ + x⁴ + x

  Binar: (1 0 1 0 1 1 1 1 0 1 0 0 1 0 0)
          ─────────────────  ───────────────
          mesaj (7 biți)     control (8 biți)