PL 
EnglishDomyślny
Українська⚙️ Kody Hamminga
Odwróć bit w słowie zakodowanym Hammingiem i obserwuj, jak kontrole parzystości dają syndrom wskazujący dokładnie pozycję błędu.
O kodach Hamminga SECDED
Kody Hamminga to rodzina liniowych kodów korekcyjnych, wynaleziona przez Richarda Hamminga w Bell Labs w 1950 roku. Kod Hamming(7,4) koduje 4 bity danych w 7-bitowe słowo kodowe, dodając 3 bity parzystości umieszczone na pozycjach będących potęgami dwójki (1, 2, 4); każdy bit parzystości obejmuje konkretny podzbiór pozycji bitów danych, zdefiniowany przez kolumny macierzy kontroli parzystości H. Taki układ nadaje kodowi minimalną odległość Hamminga równą 3, co gwarantuje, że może skorygować dowolny pojedynczy błąd bitu i wykryć dowolny błąd dwubitowy. Dodanie jednego ogólnego bitu parzystości daje kod SECDED (Single-Error Correcting, Double-Error Detecting) Hamming(8,4), stosowany w pamięci ECC RAM, gdzie odwrócony bit pamięci jest automatycznie korygowany przy każdym odczycie pamięci.
Symulator pozwala wprowadzać 4-bitowe słowa danych, obserwować, jak macierz kontroli parzystości koduje je w 7- lub 8-bitowe słowa kodowe, wprowadzać pojedyncze lub podwójne odwrócenia bitów oraz obserwować dekodowanie syndromowe: wektor syndromu s = H·r (mod 2) wskazuje bezpośrednio pozycję błędnego bitu, umożliwiając automatyczną korekcję w jednym kroku.
Najczęściej zadawane pytania
Jak dekodowanie syndromowe lokalizuje pojedynczy błąd bitu?
Po odebraniu słowa kodowego r dekoder oblicza syndrom s = H·r (mod 2), gdzie H to macierz kontroli parzystości. Jeśli s = 0, nie wykryto błędu. Jeśli s ≠ 0, jest on równy jednej z kolumn H; pozycja tej kolumny wskazuje bit do odwrócenia. Dla Hamming(7,4) syndrom to 3-bitowa liczba binarna równa bezpośrednio indeksowi (liczonemu od 1) błędnego bitu, co czyni korekcję niezwykle szybką w sprzęcie.
Czym jest odległość Hamminga i dlaczego jest ważna?
Odległość Hamminga między dwoma słowami kodowymi to liczba pozycji bitów, na których się różnią. Kod o minimalnej odległości Hamminga d_min może wykryć do d_min − 1 błędów i skorygować do ⌊(d_min − 1)/2⌋ błędów. Hamming(7,4) ma d_min = 3, więc koryguje 1 błąd i wykrywa 2. Aby skorygować t błędów, potrzeba d_min ≥ 2t + 1; minimalna długość słowa kodowego rośnie wtedy jak O(t log n) zgodnie z granicą Hamminga (granicą upakowania sfer).
Czym jest pamięć ECC RAM i jak wykorzystuje kody Hamminga?
Pamięć ECC (Error-Correcting Code) wykorzystuje schemat SECDED Hamminga dla każdego 64-bitowego słowa pamięci, dodając 8 bitów kontrolnych (72 bity przechowywane na słowo). Przy każdym odczycie słowa syndrom jest obliczany sprzętowo; pojedynczy błąd bitu jest korygowany w sposób przezroczysty w jednym cyklu pamięci (~60 ns na DDR5) bez udziału oprogramowania. Pamięć ECC jest standardem w serwerach i stacjach roboczych, gdzie ciche uszkodzenie danych mogłoby zagrozić obliczeniom finansowym, medycznym lub naukowym.
Dlaczego bity parzystości umieszczane są na pozycjach będących potęgami dwójki?
W konstrukcji Hamminga bit parzystości na pozycji 2ᵏ obejmuje wszystkie pozycje bitowe, których reprezentacja binarna ma 1 na k-tym bicie. Na przykład bit parzystości 1 (pozycja 001₂) obejmuje pozycje 1, 3, 5, 7 (wszystkie pozycje z ustawionym bitem 0). Zapewnia to, że każda pozycja danych jest objęta unikalnym, niepustym podzbiorem bitów parzystości, dzięki czemu syndrom jednoznacznie identyfikuje pozycję dowolnego pojedynczego błędu. Umieszczenie na potęgach dwójki czyni tę strukturę podzbiorów elegancką i wydajną.
Jaka jest różnica między Hamming(7,4) a Hamming(8,4) SECDED?
Hamming(7,4) używa 3 bitów parzystości na 4 bity danych i koryguje 1 błąd (d_min = 3). Dodanie czwartego, ogólnego bitu parzystości (XOR wszystkich 7 bitów) tworzy Hamming(8,4), który wykrywa podwójne błędy, zauważając, kiedy syndrom jest niezerowy, ale ogólna parzystość się zgadza — co sygnalizuje wzorzec błędu 2-bitowego. Ta właściwość SECDED jest kluczowa dla systemów pamięci, gdzie dwa błędy są rzadkie, ale możliwe podczas zdarzeń promieniowania kosmicznego lub wielokomórkowych zaburzeń.
Czym są kody Reeda-Solomona i jak wypadają w porównaniu?
Kody Reeda-Solomona operują na większych alfabetach (symbolach po k bitów, a nie pojedynczych bitach) i mogą korygować wiele błędów symboli. Kod Reed-Solomon(255,223) (używany w płytach CD, DVD, kodach QR i komunikacji dalekiego kosmosu) koryguje do 16 błędów symboli na blok 255-symbolowy. O ile kody Hamminga są optymalne do korekcji pojedynczych błędów bitowych przy minimalnej redundancji, o tyle Reed-Solomon jest znacznie potężniejszy dla błędów seryjnych (burst) i jest preferowany w przechowywaniu danych oraz komunikacji satelitarnej.
Czym jest granica Hamminga (granica upakowania sfer)?
Granica Hamminga mówi, że dla kodu binarnego o długości n korygującego t błędów, liczba słów kodowych M spełnia M · Σᵢ₌₀ᵗ C(n,i) ≤ 2ⁿ. Kody osiągające równość nazywane są kodami doskonałymi; kody Hamminga są doskonałe (ich sfery błędów o promieniu 1 dzielą całą przestrzeń n-bitową bez luk). Jedynymi innymi doskonałymi kodami binarnymi są trywialny kod powtórzeniowy oraz kod Golaya (23,12).
Jak kody Hamminga są wykorzystywane poza pamięcią RAM?
Kody Hamminga pojawiają się w telemetrii satelitarnej (ochrona łączy dowodzenia), ECC pamięci NAND flash (choć do korekcji wielobitowej częściej stosuje się kody BCH), wczesnych modemach transmisji danych, taśmach magnetycznych oraz nagłówkach protokołów sieciowych. Hamming(7,4) jest też klasycznym przykładem dydaktycznym w kursach teorii informacji i algebraicznej teorii kodowania, ilustrującym potęgę algebry liniowej nad GF(2).
Co się dzieje przy dwóch jednoczesnych błędach bitów w Hamming(7,4)?
Przy samej tylko korekcji pojedynczego błędu (bez ogólnego bitu parzystości) błąd 2-bitowy generuje niezerowy syndrom, który pasuje do jakiejś kolumny H — ale do niewłaściwej. Dekoder „koryguje” niewłaściwy bit, wprowadzając trzeci błąd i po cichu uszkadzając dane. SECDED (8,4) temu zapobiega: ogólny bit parzystości odróżnia błędy 1-bitowe (niezgodność parzystości nieparzystej + niezerowy syndrom) od błędów 2-bitowych (niezgodność parzystości parzystej + niezerowy syndrom), oznaczając te drugie zamiast błędnie je korygować.