Macierz kontroli parzystości
Każdy kod liniowy nad GF(2) — ciałem zawierającym tylko 0 i 1, arytmetyką modulo 2 — posiada macierz kontroli parzystości H. Dla kodu Hamminga (7,4), H jest macierzą 3×7, której kolumny są binarnymi reprezentacjami liczb od 1 do 7:
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 numeru pozycji
[ 0 1 1 0 0 1 1 ] ← bit 1 numeru pozycji
[ 1 0 1 0 1 0 1 ] ← bit 0 numeru pozycji
``
Kolumna j macierzy H jest binarną reprezentacją j. Dlatego syndrom s = Hr bezpośrednio wskazuje pozycję błędu.
Mapa H: GF(2)^7 → GF(2)^3 jest mapą liniową (mnożenie macierzy mod 2). Jej jądro ker(H) = { r : Hr = 0 } jest dokładnie zbiorem ważnych słów kodowych.
Liczenie wymiarów: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Zatem istnieje 2^4 = 16 słów kodowych. To potwierdza 4 bity wiadomości.
Kod jako jądro
Słowo c ∈ {0,1}^7 jest ważnym słowem kodowym wtedy i tylko wtedy, gdy Hc = 0 (mod 2). Jest to równanie definiujące kod liniowy.
Przykład: c = 0011001. Sprawdź Hc mod 2:
``
Wiersz 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Wiersz 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Wiersz 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. Zatem 0011001 jest ważnym słowem kodowym.
Warstwy boczne kodu
Słowa kodowe C = ker(H) tworzą podgrupę GF(2)^7. Każde inne słowo w GF(2)^7 należy do dokładnie jednej warstwy bocznej C.
Definicja warstwy bocznej: dla dowolnego słowa e, warstwa boczna C + e = { c + e : c ∈ C }.
Dwa słowa należą do tej samej warstwy bocznej wtedy i tylko wtedy, gdy ich różnica jest słowem kodowym — równoważnie, jeśli mają ten sam syndrom: H(r₁) = H(r₂) wtedy i tylko wtedy, gdy H(r₁ − r₂) = 0 wtedy i tylko wtedy, gdy r₁ − r₂ ∈ C.
Mapa syndromu H indukuje izomorfizm GF(2)^7 / C ≅ GF(2)^3. Przy |C| = 16 i |GF(2)^7| = 128: istnieje dokładnie 128/16 = 8 warstw bocznych, po jednej dla każdej wartości syndromu w GF(2)^3.
Tablica standardowa: lista jednego przywódcy warstwy bocznej na warstwę — słowa o minimalnej wadze Hamminga w tej warstwie. Dla pojedynczego korygowania błędów, każdy syndrom niezerowy jednoznacznie odpowiada wzorcowi błędu o wadze 1 (pojedynczy 1 w jednej z 7 pozycji). To jest powód, dla którego 7 wzorców błędów + 1 bez błędu = 8 warstw bocznych = 2^3.
Dekodowanie poprzez przywódców warstw bocznych
Algorytm dekodowania: odbierz r → oblicz s = Hr → wyszukaj przywódcę warstwy bocznej e_s (kanoniczny błąd dla syndromu s) → wynik r − e_s = r + e_s (to samo w GF(2)).
Dla kodu (7,4), 8 przywódców warstw bocznych to: 0000000 (syndrom 000), 1000000 (syndrom 001), 0100000 (syndrom 010), 0010000 (syndrom 011), 0001000 (syndrom 100), 0000100 (syndrom 101), 0000010 (syndrom 110), 0000001 (syndrom 111).
Dlaczego (7,4) jest doskonały
Kod C ⊆ GF(2)^n o minimalnej odległości 3 koryguje wszystkie błędy pojedyncze. Każde słowo kodowe c ma kulę Hamminga o promieniu 1: centrum c i jego n bezpośrednich sąsiadów (wzorce błędów o wadze 1). Objętość kuli = 1 + n.
Dla n = 7: objętość kuli = 8. Przy 16 słowach kodowych: 16 × 8 = 128 = 2^7. Kule kafelkują GF(2)^7 doskonale — każdy punkt jest pokryty dokładnie raz.
To jest definicja kodu doskonałego: M · Vol(n, t) = 2^n. Doskonałe kody korygujące błędy pojedyncze (t=1) istnieją tylko dla określonych parametrów: (7,4), (15,11), (23,12) (binarny kod Golaya) i trywialnie n = 2^r − 1, k = n − r dla dowolnego r ≥ 2.
Geometria: GF(2)^7 rozkłada się na dokładnie 8 orbit pod działaniem kodu jako partycji warstw bocznych. Każda orbita jest warstwą boczną; każda warstwa boczna ma unikalny syndrom. Mapa syndromu H jest bijekcją z warstw bocznych na GF(2)^3.
Argument liczeniowy
Dla doskonałego kodu korygującego błędy pojedyncze na n = 2^r − 1 bitach z r bitami kontroli parzystości:
- Liczba słów kodowych: M = 2^k = 2^(n−r)
- Objętość kuli: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Całkowita pokryta: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Fakt, że Vol(n,1) = 2^r, gdy n = 2^r − 1, to powód, dla którego doskonałe kody są możliwe przy tych długościach. Przy innych długościach, 1 + n nie jest potęgą 2, i doskonałe binarne kody korygujące błędy pojedyncze nie mogą istnieć.
Macierz generatora i dualność
Macierz kontroli parzystości H definiuje kod poprzez jądro. Jej dualna: macierz generatora G, której wiersze tworzą bazę dla ker(H).
Dla kodu (7,4): G jest macierzą 4×7. Każde słowo kodowe c = mG dla pewnego wektora wiadomości m ∈ GF(2)^4. Wiersze G rozpinają kod; wiersze H rozpinają przestrzeń zerową kodu.
Kluczowa relacja: HG^T = 0 (mod 2). Każdy wiersz G jest w ker(H); każdy wiersz H anihiluje każdy wiersz G.
Kod dualny: C⊥ = ker(G^T) = image(H^T). Dla kodu (7,4), kod dualny jest kodem (7,3) — kodem [7,3,4] o minimalnej odległości 4.
Geometria dualności: C i C⊥ są ortogonalnymi podprzestrzeniami GF(2)^7. Cała przestrzeń rozkłada się na kod, jego warstwy boczne, i strukturę dualną, którą koduje mapa syndromu.