Ciała skończone i kod Hamminga — modulo p, GF(2^n), korekcja błędów
Ciało Z_p i odwrotność z Euklidesa, wielomiany nierozkładalne, GF(4) i GF(8), element pierwotny, odległość Hamminga, kod (7,4), syndrom i kody doskonałe.
Ciała skończone i kod Hamminga to dwa końce jednej historii: zaczyna się od zwykłego liczenia reszt z dzielenia, a kończy na tym, że kod QR da się odczytać mimo zabrudzenia, a porysowana płyta CD wciąż gra. W tej lekcji zbudujesz całą drogę krok po kroku. Dowiesz się, czym jest pierścień i ciało, dlaczego arytmetyka modulo 7 pozwala dzielić, a modulo 6 nie, jak algorytmem Euklidesa znaleźć odwrotność, czym są wielomiany nierozkładalne i jak z nich zrobić ciało \(\mathrm{GF}(8)\) o ośmiu elementach. Potem przejdziesz do kodów korekcyjnych: odległości Hamminga, macierzy kontrolnej, dekodowania syndromowego kodu Hamminga (7,4) i kodów doskonałych. To materiał z pierwszego roku studiów (algebra, matematyka dyskretna, teoria informacji), ale wystarczy ci dobra znajomość liceum — reszt z dzielenia, wielomianów i mnożenia macierzy.
Pierścień i ciało — co to znaczy po ludzku
W szkole liczysz w zbiorach liczb całkowitych \(\mathbb{Z}\), wymiernych \(\mathbb{Q}\), rzeczywistych \(\mathbb{R}\) i zespolonych \(\mathbb{C}\). Algebra abstrakcyjna pyta: które reguły rachunku naprawdę są potrzebne i w jakich innych zbiorach też działają? Odpowiedź to dwa pojęcia.
Przykłady: \(\mathbb{Q}\), \(\mathbb{R}\) i \(\mathbb{C}\) są ciałami. \(\mathbb{Z}\) jest pierścieniem, ale nie ciałem, bo \(2\) nie ma odwrotności w liczbach całkowitych (\(\frac{1}{2} \notin \mathbb{Z}\)). Pierścieniem są też wielomiany o współczynnikach rzeczywistych i macierze kwadratowe (te ostatnie — z nieprzemiennym mnożeniem).
W ciele obowiązuje prawo, z którego korzystasz przy każdym równaniu: jeśli \(ab = 0\), to \(a = 0\) lub \(b = 0\). Dowód: gdy \(a \ne 0\), mnożymy przez \(a^{-1}\) i dostajemy \(b = a^{-1} \cdot 0 = 0\). Elementy \(a, b \ne 0\) z \(ab = 0\) nazywamy dzielnikami zera — w ciele ich nie ma.
Arytmetyka modulo n — pierścień Z_n
Zbiór \(\mathbb{Z}_n = \{0, 1, \ldots, n-1\}\) z dodawaniem i mnożeniem „modulo \(n\)” (liczymy normalnie, potem bierzemy resztę z dzielenia przez \(n\)) jest pierścieniem. Tak działa zegar: w \(\mathbb{Z}_{12}\) mamy \(9 + 5 = 2\). Zapis \(a \equiv b \pmod{n}\) oznacza, że \(a\) i \(b\) dają tę samą resztę z dzielenia przez \(n\). Przypomnienie dzielenia z resztą i NWD znajdziesz w lekcji o cechach podzielności, liczbach pierwszych i NWD.
Najważniejszy dla informatyki jest \(\mathbb{Z}_2 = \{0, 1\}\): dodawanie to XOR (\(1 + 1 = 0\)), a mnożenie to AND. W \(\mathbb{Z}_2\) odejmowanie jest tym samym co dodawanie, bo \(-1 = 1\).
Przykład 1. Dzielniki zera w Z_6
Pokaż, że \(\mathbb{Z}_6\) nie jest ciałem, i wskaż elementy odwracalne.
W \(\mathbb{Z}_6\) mamy \(2 \cdot 3 = 6 = 0\) oraz \(3 \cdot 4 = 12 = 0\) — to dzielniki zera. Mnożąc \(4\) kolejno przez \(0, 1, \ldots, 5\), dostajemy \(0, 4, 2, 0, 4, 2\): nigdy \(1\), więc \(4\) nie ma odwrotności. Sprawdzając wszystkie elementy, odwracalne są tylko \(1\) i \(5\) (\(5 \cdot 5 = 25 = 1\)), a \(2, 3, 4\) to dzielniki zera. Skutek praktyczny: równanie \(2x = 3\) nie ma w \(\mathbb{Z}_6\) rozwiązań, a \(2x = 4\) ma dwa: \(x = 2\) i \(x = 5\). W ciele równanie liniowe \(ax = b\) z \(a \ne 0\) ma zawsze dokładnie jedno rozwiązanie.
Kiedy Z_n jest ciałem — ciało Z_p i odwrotność z algorytmu Euklidesa
Uzasadnienie w dwie strony. Jeśli \(n = ab\) z \(1 < a, b < n\), to w \(\mathbb{Z}_n\) jest \(a \cdot b = 0\) — dzielniki zera, więc to nie ciało. Jeśli \(n = p\) jest pierwsza, a \(a \in \{1, \ldots, p-1\}\), to \(\mathrm{NWD}(a, p) = 1\). Rozszerzony algorytm Euklidesa daje liczby całkowite \(u, v\) z
Po wzięciu reszt modulo \(p\) składnik \(pv\) znika, więc \(au \equiv 1 \pmod{p}\), czyli \(u\) to odwrotność \(a\). Ciało \(\mathbb{Z}_p\) oznacza się też \(\mathbb{F}_p\) albo \(\mathrm{GF}(p)\) — od Galois field, na cześć Évariste’a Galois.
Jest też drugi sposób: małe twierdzenie Fermata mówi, że \(a^{p-1} \equiv 1 \pmod{p}\) dla \(a \not\equiv 0\), więc \(a^{-1} = a^{p-2}\). Euklides jest szybszy ręcznie, potęgowanie — wygodne w programie.
Przykład 2. Odwrotność 17 modulo 43
Dzielimy z resztą, aż dojdziemy do reszty 1:
- \(43 = 2 \cdot 17 + 9\)
- \(17 = 1 \cdot 9 + 8\)
- \(9 = 1 \cdot 8 + 1\)
Teraz cofamy się, wyrażając 1 przez 43 i 17:
Zatem \(17 \cdot (-5) \equiv 1 \pmod{43}\), a \(-5 \equiv 38\). Sprawdzenie: \(17 \cdot 38 = 646 = 15 \cdot 43 + 1\). W \(\mathbb{Z}_{43}\) jest więc \(17^{-1} = 38\) (to samo daje \(17^{41} \bmod 43\)).
Przykład 3. Równanie liniowe w Z_11
Rozwiąż \(5x + 3 = 1\) w \(\mathbb{Z}_{11}\).
Odejmujemy 3: \(5x = -2 = 9\). Odwrotność 5 to 9, bo \(5 \cdot 9 = 45 = 4 \cdot 11 + 1\). Mnożymy obie strony przez 9: \(x = 81 = 7 \cdot 11 + 4 = 4\). Sprawdzenie: \(5 \cdot 4 + 3 = 23 = 2 \cdot 11 + 1\). Rozwiązanie jest jedno, bo \(\mathbb{Z}_{11}\) jest ciałem — porównaj z \(\mathbb{Z}_6\) z przykładu 1.
Wielomiany nad Z_p i wielomiany nierozkładalne
Wielomian nad \(\mathbb{Z}_p\) to zwykły wielomian, którego współczynniki liczymy modulo \(p\). Dodawanie, mnożenie i dzielenie wielomianów z resztą działają tak jak w liceum — dzielenie zawsze się udaje, bo przez współczynnik wiodący dzielimy w ciele. Zmieniają się tylko wyniki: nad \(\mathbb{Z}_2\)
bo \(2 = 0\). Nad \(\mathbb{Z}_3\) ten sam kwadrat to \(x^2 + 2x + 1\). Twierdzenie Bézouta też obowiązuje: \(a \in \mathbb{Z}_p\) jest pierwiastkiem \(f\) wtedy i tylko wtedy, gdy \((x - a) \mid f\).
Test dla małych stopni: wielomian stopnia 2 lub 3 jest nierozkładalny dokładnie wtedy, gdy nie ma pierwiastka w \(\mathbb{Z}_p\) — bo każdy rozkład zawierałby czynnik stopnia 1. Od stopnia 4 to nie wystarcza: nad \(\mathbb{Z}_2\) wielomian \(x^4 + x^2 + 1\) nie ma pierwiastka (dla 0 i dla 1 daje 1), a mimo to \(x^4 + x^2 + 1 = (x^2 + x + 1)^2\).
Przykład 4. Nierozkładalne wielomiany stopnia 2, 3 i 4 nad Z_2
Rozważamy wielomiany unormowane (współczynnik wiodący 1 — nad \(\mathbb{Z}_2\) innych i tak nie ma). Pierwiastek 0 odpada, gdy wyraz wolny to 1. Pierwiastek 1 odpada, gdy \(f(1) = 1\), czyli liczba niezerowych współczynników jest nieparzysta.
- Stopień 2: z czterech wielomianów \(x^2 + ax + b\) warunki spełnia tylko \(x^2 + x + 1\).
- Stopień 3: wielomian \(x^3 + ax^2 + bx + 1\) potrzebuje \(a + b = 1\), więc są dwa: \(x^3 + x + 1\) i \(x^3 + x^2 + 1\).
- Stopień 4: \(x^4 + ax^3 + bx^2 + cx + 1\) z \(a + b + c\) nieparzystym — cztery kandydaty. Jeden z nich, \(x^4 + x^2 + 1\), to kwadrat jedynego nierozkładalnego trójmianu. Zostają trzy: \(x^4 + x + 1\), \(x^4 + x^3 + 1\), \(x^4 + x^3 + x^2 + x + 1\).
Ogólnie liczba unormowanych wielomianów nierozkładalnych stopnia \(n\) nad \(\mathbb{Z}_2\) dla \(n = 1, 2, \ldots, 6\) wynosi \(2, 1, 2, 3, 6, 9\) (sprawdzone pełnym przeglądem), a dla stopnia 8 — już 30. Daje ją wzór Gaussa \(N_p(n) = \frac{1}{n}\sum_{d \mid n} \mu(d)\, p^{n/d}\), gdzie \(\mu\) to funkcja Möbiusa; w przybliżeniu \(N_p(n) \approx \frac{p^n}{n}\), więc wielomianów nierozkładalnych nigdy nie brakuje.
Przykład 5. Ile jest nierozkładalnych trójmianów kwadratowych nad Z_p
Unormowanych trójmianów \(x^2 + bx + c\) jest \(p^2\). Rozkładalne to \((x - a)(x - b)\): z \(a = b\) jest ich \(p\), z \(a \ne b\) — tyle, ile par nieuporządkowanych, czyli \(\binom{p}{2}\) (to kombinacje z lekcji o kombinatoryce). Zatem
Dla \(p = 2\) wychodzi 1 (zgodnie z przykładem 4), a dla \(p = 3\) wychodzi 3. Nad \(\mathbb{Z}_3\) są to \(x^2 + 1\), \(x^2 + x + 2\) i \(x^2 + 2x + 2\) — żaden nie ma pierwiastka, np. \(x^2 + 1\) daje dla \(0, 1, 2\) wartości \(1, 2, 2\).
Ciała GF(4) i GF(8) — jak zbudować ciało o 2^n elementach
Liczba pierwsza \(p\) daje ciało \(\mathbb{Z}_p\). Analogicznie wielomian nierozkładalny \(f\) stopnia \(n\) nad \(\mathbb{Z}_p\) daje ciało \(\mathbb{Z}_p[x]/(f)\):
- elementy to wielomiany stopnia mniejszego niż \(n\) — jest ich \(p^n\);
- dodajemy współczynnik po współczynniku (modulo \(p\));
- mnożymy jak wielomiany, a wynik zastępujemy resztą z dzielenia przez \(f\).
Pierwiastek \(x\) w tym ciele oznaczamy \(\alpha\); spełnia on \(f(\alpha) = 0\), co daje regułę redukcji. Odwrotności istnieją z tego samego powodu co w \(\mathbb{Z}_p\): \(f\) jest nierozkładalny, więc \(\mathrm{NWD}(g, f) = 1\) dla każdego niezerowego \(g\), a algorytm Euklidesa dla wielomianów daje \(gu + fv = 1\).
Uwaga: \(\mathrm{GF}(4)\) to nie \(\mathbb{Z}_4\) — w \(\mathbb{Z}_4\) jest \(2 \cdot 2 = 0\).
Przykład 6. Ciało GF(4)
Zbuduj \(\mathrm{GF}(4) = \mathbb{Z}_2[x]/(x^2 + x + 1)\) i wypisz mnożenie.
Elementy: \(0, 1, \alpha, \alpha + 1\). Reguła redukcji z \(\alpha^2 + \alpha + 1 = 0\) to \(\alpha^2 = \alpha + 1\) (nad \(\mathbb{Z}_2\) przenosimy bez zmiany znaku). Dodawanie: każdy element dodany do siebie daje 0, np. \(\alpha + \alpha = 2\alpha = 0\), oraz \(\alpha + (\alpha+1) = 1\). Mnożenie niezerowych elementów:
- \(\alpha \cdot \alpha = \alpha + 1\)
- \(\alpha(\alpha + 1) = \alpha^2 + \alpha = (\alpha + 1) + \alpha = 1\)
- \((\alpha + 1)^2 = \alpha^2 + 1 = \alpha\)
Zatem \(\alpha^{-1} = \alpha + 1\), a \(\alpha^3 = \alpha \cdot \alpha^2 = \alpha(\alpha+1) = 1\). Żaden iloczyn niezerowych elementów nie daje 0, więc dzielników zera nie ma. Ten sam mechanizm \(x^3 = 1\) „modulo \(x^2 + x + 1\)” wykorzystuje zadanie o reszcie z dzielenia \(x^{2027} + 3x^{1000} - 2x^5 + 1\) przez \(x^2 + x + 1\) (link w „Sprawdź się”).
Przykład 7. Mnożenie i dzielenie w GF(8)
Weź \(f = x^3 + x + 1\) (nierozkładalny z przykładu 4). Ciało \(\mathrm{GF}(8)\) ma elementy \(c_2\alpha^2 + c_1\alpha + c_0\), czyli trójki bitów \(c_2c_1c_0\), a reguła redukcji to
Kolejne potęgi \(\alpha\) (każda to poprzednia razy \(\alpha\), po czym \(\alpha^3\) zamieniamy na \(\alpha + 1\)):
- \(\alpha^0 = 1\) — bity 001
- \(\alpha^1 = \alpha\) — 010
- \(\alpha^2\) — 100
- \(\alpha^3 = \alpha + 1\) — 011
- \(\alpha^4 = \alpha^2 + \alpha\) — 110
- \(\alpha^5 = \alpha^3 + \alpha^2 = \alpha^2 + \alpha + 1\) — 111
- \(\alpha^6 = \alpha^3 + \alpha^2 + \alpha = \alpha^2 + 1\) — 101
- \(\alpha^7 = \alpha^3 + \alpha = 1\)
Siedem potęg to wszystkie siedem niezerowych elementów ciała.
a) Oblicz \((\alpha^2 + 1)(\alpha^2 + \alpha)\). Wprost: \((x^2+1)(x^2+x) = x^4 + x^3 + x^2 + x\). Redukujemy \(x^3 = x + 1\) oraz \(x^4 = x \cdot x^3 = x^2 + x\):
bo \(x^2 + x^2 = 0\) i \(x + x + x = x\). Przez potęgi szybciej: \(\alpha^6 \cdot \alpha^4 = \alpha^{10} = \alpha^{3} = \alpha + 1\). Ta sama odpowiedź.
b) Znajdź odwrotność \(\alpha^2 + \alpha + 1\). To \(\alpha^5\), więc odwrotność to \(\alpha^{7-5} = \alpha^2\). Sprawdzenie: \(\alpha^4 + \alpha^3 + \alpha^2 = (\alpha^2 + \alpha) + (\alpha + 1) + \alpha^2 = 1\).
c) Rozwiąż \((\alpha + 1)\,y = \alpha^2\). Ponieważ \(\alpha + 1 = \alpha^3\), mamy \(y = \alpha^{2-3} = \alpha^{-1} = \alpha^6 = \alpha^2 + 1\). Sprawdzenie: \((\alpha+1)(\alpha^2+1) = \alpha^3 + \alpha^2 + \alpha + 1 = (\alpha + 1) + \alpha^2 + \alpha + 1 = \alpha^2\).
Wniosek praktyczny: dodawanie w \(\mathrm{GF}(2^n)\) to XOR bitów, a mnożenie najłatwiej robić przez tablicę logarytmów (wykładników \(\alpha\)). Dokładnie tak liczą dekodery kodów Reeda–Solomona.
Grupa multiplikatywna jest cykliczna — element pierwotny
W \(\mathrm{GF}(8)\) jedna liczba \(\alpha\) „generuje” wszystkie niezerowe elementy. To nie przypadek.
Szkic uzasadnienia: rząd elementu \(a\) (najmniejsze \(k\) z \(a^k = 1\)) dzieli \(q - 1\). Elementy rzędu dzielącego \(d\) są pierwiastkami \(x^d - 1\), a wielomian stopnia \(d\) ma w ciele najwyżej \(d\) pierwiastków. Z tego wynika, że elementów rzędu \(d\) jest 0 albo \(\varphi(d)\), a ponieważ \(\sum_{d \mid q-1} \varphi(d) = q - 1\), zawsze jest ich dokładnie \(\varphi(d)\) — w szczególności \(\varphi(q-1) > 0\) elementów rzędu \(q - 1\). Przy okazji wychodzi małe twierdzenie Fermata: \(a^{q-1} = 1\) dla każdego \(a \ne 0\).
W \(\mathbb{Z}_7\) potęgi 3 to kolejno \(3, 2, 6, 4, 5, 1\) — wszystkie niezerowe reszty, więc 3 jest pierwotne. Potęgi 2 to \(2, 4, 1\) i od nowa: rząd 2 wynosi 3. Pierwotne są dwa elementy (\(\varphi(6) = 2\)): 3 i 5. W \(\mathrm{GF}(8)\) mamy \(\varphi(7) = 6\), więc pierwotny jest każdy element poza 0 i 1.
Przykład 8. Elementy pierwotne w Z_11
Sprawdź, że 2 jest elementem pierwotnym \(\mathbb{Z}_{11}\), i znajdź wszystkie elementy pierwotne.
Rząd dzieli \(10\), więc wystarczy sprawdzić, że \(2^{10/5} = 2^2\) i \(2^{10/2} = 2^5\) są różne od 1 (dzielniki pierwsze 10 to 2 i 5). Mamy \(2^2 = 4\) oraz \(2^5 = 32 = 2 \cdot 11 + 10 = 10\). Oba różne od 1, więc rząd 2 to 10. Kolejne potęgi: \(2, 4, 8, 5, 10, 9, 7, 3, 6, 1\). Element \(2^k\) jest pierwotny wtedy, gdy \(\mathrm{NWD}(k, 10) = 1\), czyli dla \(k = 1, 3, 7, 9\): to \(2, 8, 7, 6\). Dla porównania \(3^5 = 243 = 22 \cdot 11 + 1\), więc 3 ma rząd 5 i pierwotne nie jest. Bonus: \(2^{-1} = 2^{9} = 6\), bo \(2 \cdot 6 = 12 = 1\).
Odległość Hamminga — ile błędów kod wykryje, a ile poprawi
Teraz zastosowanie. Wysyłamy ciąg bitów przez kanał, który czasem zamienia 0 na 1 lub odwrotnie (szum radiowy, rysa na płycie, promieniowanie kosmiczne w pamięci). Kod korekcyjny dokłada do danych bity nadmiarowe tak, by odbiorca mógł błędy wykryć lub poprawić. Słowa długości \(n\) traktujemy jak wektory z \(\mathbb{Z}_2^n\), więc dodawanie słów to XOR po współrzędnych.
Na przykład \(d(10110, 11011) = 3\), bo \(10110 + 11011 = 01101\) ma trzy jedynki. Odległość Hamminga spełnia nierówność trójkąta: \(d(u, w) \le d(u, v) + d(v, w)\).
Kod to wybrany zbiór \(C\) słów kodowych, a odległość minimalna \(d\) to najmniejsza odległość między dwoma różnymi słowami kodu.
Dlaczego? Mniej niż \(d\) błędów nie zamieni słowa kodowego w inne słowo kodowe, więc odbiorca widzi, że coś jest nie tak. Do poprawiania potrzebne są kule Hamminga: kula promienia \(t\) wokół \(c\) to wszystkie słowa w odległości co najwyżej \(t\) od \(c\). Jeśli \(2t < d\), kule wokół różnych słów kodowych są rozłączne: słowo \(r\) w obu kulach dawałoby \(d(c, c') \le d(c, r) + d(r, c') \le 2t < d\). Słowo z co najwyżej \(t\) błędami leży więc w kuli dokładnie jednego słowa kodowego i to ono jest najbliższe.
Najprostszy przykład to kod powtórzeniowy \(\{000, 111\}\): \(d = 3\), więc \(t = 1\). Odbiorca dekoduje głosowaniem większościowym: \(010 \mapsto 000\), \(110 \mapsto 111\). Kosztem jest szybkość — na jeden bit danych wysyłamy trzy.
Kod liniowy to kod, który jest podprzestrzenią \(\mathbb{Z}_2^n\): suma dwóch słów kodowych jest słowem kodowym. Wtedy \(d(u, v) = w(u + v)\) i \(u + v \in C\), więc odległość minimalna to po prostu najmniejsza waga niezerowego słowa kodowego — zamiast \(\binom{|C|}{2}\) par sprawdzamy \(|C| - 1\) słów.
Przykład 9. Mały kod liniowy i dekodowanie do najbliższego słowa
Kod \(C = \{00000, 11100, 00111, 11011\}\) ma dwa bity danych i trzy nadmiarowe. Wyznacz \(d\) i zdekoduj słowa \(10111\) oraz \(11111\).
Kod jest liniowy: \(11100 + 00111 = 11011\), a dodanie zera lub słowa do siebie nie wyprowadza poza \(C\). Wagi niezerowych słów to \(3, 3, 4\), więc \(d = 3\): kod wykrywa 2 błędy i poprawia 1.
Odległości słowa \(10111\) od kolejnych słów kodowych: \(4, 3, 1, 2\). Najbliższe jest \(00111\) (jeden błąd, na pierwszej pozycji). Dla \(11111\) odległości to \(5, 2, 2, 1\), więc dekodujemy do \(11011\). Gdyby jednak nadawca wysłał \(11100\) i wystąpiły dwa błędy, dekoder pomyliłby się — dwa błędy kod tylko wykrywa, a nie poprawia.
Kod Hamminga (7,4) — macierz kontrolna i dekodowanie syndromowe
Kod Hamminga (7,4) koduje 4 bity danych w 7 bitach i poprawia jeden błąd. Szybkość \(\frac{4}{7} \approx 0{,}571\) jest dużo lepsza niż \(\frac{1}{3}\) kodu powtórzeniowego. Pomysł Richarda Hamminga z 1950 roku: ponumeruj pozycje od 1 do 7, na pozycjach 1, 2, 4 (potęgi dwójki) umieść bity kontrolne \(p_1, p_2, p_4\), a na pozycjach 3, 5, 6, 7 — dane \(d_3, d_5, d_6, d_7\). Bit \(p_b\) pilnuje parzystości tych pozycji \(j\), w których zapisie dwójkowym występuje składnik \(b\):
- \(p_1\) pilnuje pozycji 1, 3, 5, 7: \(p_1 = d_3 + d_5 + d_7\)
- \(p_2\) pilnuje pozycji 2, 3, 6, 7: \(p_2 = d_3 + d_6 + d_7\)
- \(p_4\) pilnuje pozycji 4, 5, 6, 7: \(p_4 = d_5 + d_6 + d_7\)
(Dodawanie w \(\mathbb{Z}_2\).) Wygodnie to zobaczyć jako trzy koła: każdy bit danych leży w co najmniej dwóch kołach, a w każdym kole liczba jedynek ma być parzysta.
Te same warunki zapisuje macierz kontrolna \(H\). Jej \(j\)-ta kolumna to liczba \(j\) w zapisie dwójkowym (od góry: bit czwórek, dwójek, jedynek):
Słowo \(c\) jest kodowe dokładnie wtedy, gdy \(H c^{T} = 0\) — to zwykłe mnożenie macierzy przez wektor, tylko modulo 2. Rozwiązań jest \(2^4 = 16\): to wszystkie słowa kodu.
Przykład 10. Kodowanie danych 1010
Dane: \(d_3 = 1\), \(d_5 = 0\), \(d_6 = 1\), \(d_7 = 0\). Bity kontrolne:
- \(p_1 = d_3 + d_5 + d_7 = 1 + 0 + 0 = 1\)
- \(p_2 = d_3 + d_6 + d_7 = 1 + 1 + 0 = 0\)
- \(p_4 = d_5 + d_6 + d_7 = 0 + 1 + 0 = 1\)
Słowo kodowe na pozycjach 1–7 (\(p_1 p_2 d_3 p_4 d_5 d_6 d_7\)) to 1011010. Kontrola na rysunku: w kole \(p_1\) są bity \(1, 1, 0, 0\), w kole \(p_2\) bity \(0, 1, 1, 0\), w kole \(p_4\) bity \(1, 0, 1, 0\) — wszędzie dwie jedynki.
Przykład 11. Dekodowanie syndromowe krok po kroku
Odebrano \(r = 1011110\). Znajdź i popraw błąd, odczytaj dane.
Krok 1 — syndrom. Każdy wiersz \(H\) sumuje bity na swoich pozycjach:
- \(s_4 = r_4 + r_5 + r_6 + r_7 = 1 + 1 + 1 + 0 = 1\)
- \(s_2 = r_2 + r_3 + r_6 + r_7 = 0 + 1 + 1 + 0 = 0\)
- \(s_1 = r_1 + r_3 + r_5 + r_7 = 1 + 1 + 1 + 0 = 1\)
Krok 2 — odczyt pozycji. Syndrom \((s_4, s_2, s_1) = (1, 0, 1)\) to dwójkowo \(101_2 = 5\). Na rysunku z kołami: nie zgadzają się koła \(p_1\) i \(p_4\), zgadza się \(p_2\) — jedyna pozycja w \(p_1\) i \(p_4\), a poza \(p_2\), to 5.
Krok 3 — poprawka. Odwracamy bit 5: \(1011\mathbf{1}10 \to 1011\mathbf{0}10\). Kontrolnie \(H c^{T} = 0\).
Krok 4 — dane z pozycji 3, 5, 6, 7: 1010. Zgadza się z przykładem 10.
Co, jeśli błędy są dwa? Niech w 1011010 przekłamią się bity 2 i 6: \(r = 1111000\). Syndrom to suma kolumn 2 i 6, czyli \(010 + 110 = 100\) — numer 4 (\(2 \oplus 6 = 4\) w zapisie XOR). Dekoder odwraca bit 4 i zwraca 1110000: poprawne słowo kodowe, ale inne niż wysłane (odległe od niego o 3). Kod Hamminga poprawia jeden błąd, przy dwóch się myli.
Dlaczego odległość minimalna wynosi 3
Kod jest liniowy, więc liczy się najmniejsza waga. Słowo o wadze 1 z jedynką na pozycji \(j\) miałoby syndrom równy kolumnie \(j\), a żadna kolumna \(H\) nie jest zerowa. Słowo o wadze 2 miałoby syndrom równy sumie dwóch różnych kolumn, a ta nie jest zerem, bo kolumny są parami różne. Waga 3 jest osiągana: kolumny 1, 2, 3 sumują się do zera, więc 1110000 jest słowem kodowym. Pełny przegląd 16 słów daje wagi: jedno słowo 0, siedem słów wagi 3, siedem wagi 4 i jedno wagi 7.
Kody doskonałe i granica Hamminga
Kula promienia \(t\) w \(\mathbb{Z}_2^n\) zawiera \(\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{t}\) słów (wybieramy, które bity się różnią). Rozłączne kule wokół \(|C|\) słów kodowych mieszczą się w zbiorze \(2^n\) słów, więc
To granica Hamminga (granica upakowania kul). Kod, dla którego zachodzi równość, nazywamy doskonałym: kule pokrywają wszystkie słowa bez luk i nakładania.
Kod Hamminga (7,4) jest doskonały: \(16 \cdot (1 + 7) = 128 = 2^7\). Każde z 128 słów leży w odległości co najwyżej 1 od dokładnie jednego słowa kodowego, więc dekoder nigdy nie jest „bezradny”. Ogólniej kody Hamminga mają \(n = 2^r - 1\) i \(k = n - r\) bitów danych, a \(2^{n-r}(1 + n) = 2^n\). Inne kody doskonałe to kody powtórzeniowe nieparzystej długości oraz binarny kod Golaya długości 23: \(2^{12}\left(1 + 23 + 253 + 1771\right) = 2^{12} \cdot 2^{11} = 2^{23}\), poprawiający 3 błędy.
Przykład 12. Granica Hamminga w praktyce
a) Ile najwyżej słów może mieć kod długości 8 poprawiający 1 błąd? Kula ma \(1 + 8 = 9\) słów, więc \(|C| \le \frac{256}{9}\), czyli \(|C| \le 28\). Ponieważ 9 nie dzieli 256, kod doskonały tej długości nie istnieje.
b) Kod długości 7 poprawiający 2 błędy: kula ma \(1 + 7 + 21 = 29\) słów, więc \(|C| \le \frac{128}{29}\), czyli \(|C| \le 4\). Granica nie musi być osiągalna — tu najwięcej są dwa słowa. Dowód: dla trzech słów \(a, b, c\) każda pozycja wnosi do sumy \(d(a,b) + d(b,c) + d(a,c)\) zero albo dwa (wśród trzech bitów co najwyżej dwie pary się różnią), więc suma jest co najwyżej \(2 \cdot 7 = 14\). Odległość 5 dla każdej pary wymagałaby sumy co najmniej 15 — sprzeczność.
Kody BCH i Reeda–Solomona — ciała skończone w kodach QR i na płytach CD
Kod Hamminga ma piękny opis w \(\mathrm{GF}(8)\). Zapisz słowo \(c_0c_1\ldots c_6\) jako wielomian \(c(x) = c_0 + c_1x + \ldots + c_6x^6\). Wtedy \(c\) jest słowem kodowym dokładnie wtedy, gdy \(c(\alpha) = 0\), gdzie \(\alpha^3 = \alpha + 1\) jak w przykładzie 7. Słowa kodowe to wielokrotności \(g(x) = x^3 + x + 1\) stopnia mniejszego niż 7 — taki kod nazywamy cyklicznym, bo przesunięcie cykliczne słowa kodowego jest słowem kodowym. To ten sam kod Hamminga, tylko z inną kolejnością pozycji: rolę kolumn \(H\) grają tu potęgi \(\alpha^0, \ldots, \alpha^6\), czyli wszystkie niezerowe trójki bitów.
Przykład 13. Syndrom jako element GF(8)
Wysłano \(g(x) = 1 + x + x^3\) (bity 1101000), odebrano \(r(x) = 1 + x + x^3 + x^5\). Znajdź błąd.
Syndrom to \(r(\alpha)\). Korzystamy z listy potęg: \(\alpha^3 = \alpha + 1\), więc
Pojedynczy błąd na pozycji \(x^j\) daje syndrom \(\alpha^j\) — tu \(j = 5\). Usuwamy składnik \(x^5\) i wracamy do \(g(x)\).
Kody BCH (Bose, Chaudhuri, Hocquenghem) idą dalej: żądamy, by \(c(x)\) zerował się w kilku kolejnych potęgach \(\alpha\). Na przykład w \(\mathrm{GF}(16)\) z \(\alpha^4 = \alpha + 1\) warunki w \(\alpha, \alpha^2, \alpha^3, \alpha^4\) dają generator \((x^4 + x + 1)(x^4 + x^3 + x^2 + x + 1) = x^8 + x^7 + x^6 + x^4 + 1\) i kod BCH(15,7) o odległości 5, poprawiający 2 błędy.
Kody Reeda–Solomona robią to samo z symbolami zamiast bitów: symbolem jest cały bajt, czyli element \(\mathrm{GF}(256) = \mathrm{GF}(2^8)\). Kod RS o długości \(n\) i \(k\) symbolach danych ma odległość \(n - k + 1\) i poprawia \(\left\lfloor \frac{n-k}{2} \right\rfloor\) błędnych bajtów — niezależnie od tego, ile bitów w bajcie się zepsuło. Dlatego RS świetnie znosi błędy seryjne.
- Kody QR używają RS nad \(\mathrm{GF}(256)\) zbudowanym z wielomianu \(x^8 + x^4 + x^3 + x^2 + 1\), w którym \(\alpha\) jest elementem pierwotnym (rzędu 255). Poziomy korekcji L, M, Q, H pozwalają odtworzyć ok. 7%, 15%, 25% i 30% słów kodowych — dlatego kod z logo na środku nadal działa.
- Płyty CD stosują dwa kody RS nad \(\mathrm{GF}(256)\), o długościach 32 i 28 bajtów, z przeplotem rozpraszającym długą rysę na wiele bloków. Dzięki temu w pełni korygowane są serie do ok. 3500 bitów.
- Sondy kosmiczne (np. Voyager) i dyski RAID-6 też korzystają z RS; klasyczny RS(255,223) poprawia 16 błędnych bajtów w bloku.
Kod Hamminga (7,4) żyje też w świecie kwantowym: kod Steane’a, chroniący jeden kubit siedmioma kubitami, używa jego macierzy kontrolnej dwa razy — raz do wykrywania błędów bitowych, raz fazowych.
Typowe błędy
- Dzielenie w \(\mathbb{Z}_n\) dla złożonego \(n\). W \(\mathbb{Z}_6\) nie wolno „skrócić” \(2x = 4\) do \(x = 2\) — rozwiązaniem jest też 5. Dzielić można przez element odwracalny, czyli względnie pierwszy z \(n\).
- Ułamek zamiast odwrotności. W \(\mathbb{Z}_{11}\) zapis \(\frac{1}{5}\) to 9, nie 0,2. Odwrotność liczysz Euklidesem albo jako \(a^{p-2}\).
- Ujemne reszty. Wynik \(-5\) z algorytmu Euklidesa trzeba zamienić na \(-5 + 43 = 38\).
- „Brak pierwiastków, więc nierozkładalny” dla stopnia 4 i wyżej. \(x^4 + x^2 + 1 = (x^2 + x + 1)^2\) nad \(\mathbb{Z}_2\) nie ma pierwiastków, a jest rozkładalny.
- Utożsamianie \(\mathrm{GF}(4)\) z \(\mathbb{Z}_4\). \(\mathbb{Z}_4\) nie jest ciałem; \(\mathrm{GF}(4)\) buduje się z wielomianu \(x^2 + x + 1\).
- Zapomniana redukcja. Wynik mnożenia w \(\mathrm{GF}(8)\) musi mieć stopień co najwyżej 2 — każde \(\alpha^3\) zamieniaj na \(\alpha + 1\), aż zniknie.
- Znaki nad \(\mathbb{Z}_2\). \(-1 = 1\), więc \(\alpha^2 + \alpha + 1 = 0\) daje \(\alpha^2 = \alpha + 1\), a \(x + x = 0\).
- \(t = \frac{d}{2}\) zamiast \(\left\lfloor \frac{d-1}{2} \right\rfloor\). Kod o \(d = 4\) poprawia 1 błąd, a nie 2 (wykrywa 3).
- Kolejność bitów syndromu. Syndrom czytaj w tej samej kolejności, w jakiej zapisane są kolumny \(H\). Czytany od końca syndrom \(110\) daje \(011_2 = 3\) zamiast 6 i poprawka psuje dobry bit.
- Wiara, że kod Hamminga „zawsze naprawia”. Przy dwóch błędach dekoder z pewnością zwróci złe słowo (przykład 11).
Ściąga — ciała skończone i kod Hamminga w pigułce
Sprawdź się
Rozwiąż samodzielnie, potem porównaj z odpowiedziami.
- Znajdź \(7^{-1}\) w \(\mathbb{Z}_{19}\).
- Czy \(x^2 + x + 2\) jest nierozkładalny nad \(\mathbb{Z}_3\)?
- W \(\mathrm{GF}(8)\) z \(\alpha^3 = \alpha + 1\) oblicz \((\alpha^2 + \alpha)(\alpha^2 + 1)\) i odwrotność \(\alpha + 1\).
- Odebrano słowo kodu Hamminga (7,4): 0011011. Popraw je i odczytaj dane.
- Ile najwyżej słów może mieć kod długości 10 poprawiający jeden błąd?
- Sprawdź, że 2 jest elementem pierwotnym \(\mathbb{Z}_{13}\). Ile elementów pierwotnych ma \(\mathbb{Z}_{13}\)?
Zadania z pełnymi rozwiązaniami, które ćwiczą narzędzia z tej lekcji:
- NWD liczb 84 i 126 — algorytm Euklidesa, od którego zaczyna się szukanie odwrotności.
- Reszta z dzielenia potęgi dwójki przez 7 — rząd elementu 2 w \(\mathbb{Z}_7\) z rysunku o potęgach.
- Najmniejsza wielokrotność 11 z resztami 3, 4, 5 przy dzieleniu przez 4, 5, 6 — układ kongruencji.
- Dwie ostatnie cyfry wieży potęg trójki — rząd elementu modulo 100.
- Reszta z dzielenia x²⁰²⁷ + 3x¹⁰⁰⁰ − 2x⁵ + 1 przez x² + x + 1 — redukcja \(x^3 = 1\) jak w \(\mathrm{GF}(4)\).
- Kontrola parzystości bloku 8 bitów przy szumie 1/4 — których błędów nie wykryje kod o \(d = 2\).
- Kod Steane’a: ile trzykubitowych błędów X nie zostawia syndromu — słowa wagi 3 kodu Hamminga w wersji kwantowej.
Więcej zadań: algebra abstrakcyjna — grupy, pierścienie, ciała skończone i kody — oraz teoria liczb — podzielność, kongruencje i reszty.
Nowe zadania z pełnymi rozwiązaniami, które ćwiczą rachunki z tej lekcji:
- [Elementy odwracalne pierścienia Z₁₅[i] — „liczby Gaussa” modulo 15](/zadania/algebra-abstrakcyjna/elementy-odwracalne-pierscienia-z-i-liczby-gaussa-modulo-15/)
- Wielomiany stopnia 3 nad ciałem Z₅ mające pierwiastek w Z₅
- [Elementy pierwotne ciała Z₂[x]/(x⁵ + x² + 1)](/zadania/algebra-abstrakcyjna/elementy-pierwotne-ciala-z-x-x-x-1/)
- Kodowanie informacji 1001 kodem Hamminga (7, 4) z bitami kontrolnymi na pozycjach 1, 2, 4
- Korekcja pojedynczego błędu w słowie kodu Hamminga długości 15
- Liczba słów kodowych wagi 3 w kodzie Hamminga długości 15
Arytmetykę reszt od podstaw — kongruencje, odwrotność modulo i małe twierdzenie Fermata — omawia lekcja kongruencje i reszty z dzielenia.
Dzisiejszy zestaw zadań → Trening liczenia w pamięci · 2 min