Матриця перевірки парності
Кожен лінійний код над GF(2) — полем з усього 0 та 1, арифметика за модулем 2 — має матрицю перевірки парності H. Для коду Хеммінга (7,4) H — матриця 3×7, стовпці якої — бінарні представлення чисел від 1 до 7:
``
H = [ 0 0 0 1 1 1 1 ] ← біт 2 номера позиції
[ 0 1 1 0 0 1 1 ] ← біт 1 номера позиції
[ 1 0 1 0 1 0 1 ] ← біт 0 номера позиції
``
Стовпець j матриці H — це бінарне представлення j. Саме тому синдром s = Hr безпосередньо називає позицію помилки.
Відображення H: GF(2)^7 → GF(2)^3 — це лінійне відображення (матричне множення за модулем 2). Його ядро ker(H) = { r : Hr = 0 } — це саме набір дійсних кодових слів.
Підрахунок розмірності: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Отже, існує 2^4 = 16 кодових слів. Це підтверджує 4 біти повідомлення.
Код як ядро
Слово c ∈ {0,1}^7 — це дійсне кодове слово тоді й тільки тоді, коли Hc = 0 (за модулем 2). Це визначальне рівняння лінійного коду.
Приклад: c = 0011001. Перевіримо Hc за модулем 2:
``
Рядок 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Рядок 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Рядок 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000. Отже, 0011001 — це дійсне кодове слово.
Суміжні класи коду
Кодові слова C = ker(H) утворюють підгрупу GF(2)^7. Кожне інше слово у GF(2)^7 належить рівно одному суміжному класу C.
Визначення суміжного класу: для будь-якого слова e, суміжний клас C + e = { c + e : c ∈ C }.
Два слова належать одному суміжному класу тоді й тільки тоді, коли їхня різниця — це кодове слово — еквівалентно, якщо вони мають один синдром: H(r₁) = H(r₂) тоді й тільки тоді, коли H(r₁ − r₂) = 0 тоді й тільки тоді, коли r₁ − r₂ ∈ C.
Карта синдрому H індукує ізоморфізм GF(2)^7 / C ≅ GF(2)^3. З |C| = 16 та |GF(2)^7| = 128: існує рівно 128/16 = 8 суміжних класів, один для кожного значення синдрому у GF(2)^3.
Стандартний масив: перелічіть одного лідера суміжного класу на суміжний клас — слово мінімальної ваги Хеммінга в цьому суміжному класі. Для виправлення однієї помилки кожен ненульовий синдром унікально відповідає одному шаблону помилки ваги 1 (одна одиниця в одній з 7 позицій). Саме тому 7 шаблонів помилок + 1 без помилок = 8 суміжних класів = 2^3.
Декодування через лідерів суміжних класів
Алгоритм декодування: отримати r → обчислити s = Hr → знайти лідера суміжного класу e_s (канонічний шаблон помилки для синдрому s) → вивести r − e_s = r + e_s (те ж саме у GF(2)).
Для коду (7,4), 8 лідерів суміжних класів такі: 0000000 (синдром 000), 1000000 (синдром 001), 0100000 (синдром 010), 0010000 (синдром 011), 0001000 (синдром 100), 0000100 (синдром 101), 0000010 (синдром 110), 0000001 (синдром 111).
Чому (7,4) ідеальний
Код C ⊆ GF(2)^n з мінімальною відстанню 3 виправляє всі однобітні помилки. Кожне кодове слово c має кулю Хеммінга радіусу 1: центр c та його n сусідніх (шаблони помилок ваги 1). Об'єм кулі = 1 + n.
Для n = 7: об'єм кулі = 8. З 16 кодовими словами: 16 × 8 = 128 = 2^7. Кулі мозаїкують GF(2)^7 ідеально — жодна точка не залишена невкритою, жодна точка не покрита двічі.
Це визначення ідеального коду: M · Vol(n, t) = 2^n. Ідеальні однобітні виправні коди (t=1) існують лише для конкретних параметрів: (7,4), (15,11), (23,12) (двійковий код Голея), та тривіально n = 2^r − 1, k = n − r для будь-якого r ≥ 2.
Геометрія: GF(2)^7 розпадається рівно на 8 орбіт під дією коду як розділення суміжних класів. Кожна орбіта — це суміжний клас; кожний суміжний клас має унікальний синдром. Карта синдрому H — це біекція від суміжних класів до GF(2)^3.
Аргумент підрахунку
Для ідеального однобітного виправного коду на n = 2^r − 1 бітах з r бітами перевірки парності:
- Кількість кодових слів: M = 2^k = 2^(n−r)
- Об'єм кулі: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Всього покрито: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Той факт, що Vol(n,1) = 2^r, коли n = 2^r − 1, це те, що робить ідеальні коди можливими при цих довжинах. При інших довжинах 1 + n не є степенем 2, і ідеальні однобітні виправні двійкові коди не можуть існувати.
Матриця генератора та подвійність
Матриця перевірки парності H визначає код через ядро. Її подвійна: матриця генератора G, рядки якої утворюють базис ker(H).
Для коду (7,4): G — матриця 4×7. Будь-яке кодове слово c = mG для деякого вектора повідомлення m ∈ GF(2)^4. Рядки G охоплюють код; рядки H охоплюють нульовий простір коду.
Ключовий зв'язок: HG^T = 0 (за модулем 2). Кожен рядок G перебуває в ker(H); кожен рядок H анулює кожен рядок G.
Подвійний код: C⊥ = ker(G^T) = образ(H^T). Для коду (7,4), подвійний — це код (7,3) — код [7,3,4] з мінімальною відстанню 4.
Геометрія подвійності: C та C⊥ — це ортогональні підпростори GF(2)^7. Весь простір розпадається на код, його суміжні класи та подвійну структуру, яку кодує карта синдрому.