Kody Hamminga: Naprawa Przełączonego Bita Bez Ponownego Pytania

Zamiarowa Redundancja

Kod Hamming dodaje starannie rozmieszczone bity pomocnicze – bity parzystości – do bloku bitów danych, tak aby pojedynczo odwrócony bit nie tylko mógł zostać wykryty, ale także zlokalizowany i skorygowany bez ponownego wysyłania danych. Richard Hamming opracował tę metodę w 1950 roku w Bell Labs po frustracji związanej z tym, że wczesny komputer relajnowy przerywał cały wielodniowy proces z powodu pojedynczego błędu, który mógł wykryć, ale nie skorygować. Klasyczny kod Hamming (7,4) wykorzystuje 4 bity danych i dodaje 3 bity parzystości, aby utworzyć 7-bitową sekwencję bitów, kosztem zapłacenia za redundancję i uzyskania automatycznej korekcji.

Umieszczanie bitów parzystości w potęgach o dwóch

Kluczem jest to, gdzie umieszcza się bity parzystości. W słowie 7-bitowym numerowanym od 1 do 7, pozycje 1, 2 i 4 – czyli potęgi o dwóch – zawierają bity parzystości; pozycje 3, 5, 6 i 7 zawierają dane. Każdy bit parzystości obejmuje określony, nakładający się podzbiór pozycji, zdeterminowany przez jego własne bit w binarnym reprezentacji numeru pozycji: bit parzystości na pozycji 1 sprawdza każdą pozycję, której reprezentacja binarna ma bit 0 ustawiony (1, 3, 5, 7), bit parzystości na pozycji 2 sprawdza pozycje z bitem 1 ustawionym (2, 3, 6, 7), a bit parzystości na pozycji 4 sprawdza pozycje z bitem 2 ustawionym (4, 5, 6, 7).

pozycja: 1 2 3 4 5 6 7 zawartość: p1 p2 d1 p4 d2 d3 d4 p1 sprawdza pozycje 1,3,5,7 (bit 0 pozycji ustawiony) p2 sprawdza pozycje 2,3,6,7 (bit 1 pozycji ustawiony) p4 sprawdza pozycje 4,5,6,7 (bit 2 pozycji ustawiony) każdy pi jest ustawiany tak, aby parzystość (XOR) w pokrytych przez niego pozycjach była równa zero. Ten nakładający się projekt to cała sztuczka: każdy bit danych jest objęty unikalną kombinacją bitów parzystości, więc błąd w tym jednym bicie danych zakłóca unikalny, identyfikowalny podzbiór kontroli parzystości.

position:   1  2  3  4  5  6  7
content:    p1 p2 d1 p4 d2 d3 d4

p1 checks positions 1,3,5,7   (bit 0 of position set)
p2 checks positions 2,3,6,7   (bit 1 of position set)
p4 checks positions 4,5,6,7   (bit 2 of position set)

each pi is set so the parity (XOR) of its covered positions is even

Syndrom: trzy sprawdzanie, które wskazują pozycję

Na końcu odbioru ponownie oblicz trzy kontrolne sumy nad otrzymanym słowem. Jeśli dana suma jest równa zero, jej bitowy wynik wynosi 0; jeśli jest nieparzysta, to 1. Zastosuj te wyniki do p4's bit jako najbardziej znaczący: uzyskane 3-bitowe wyrażenie – syndrom – będzie albo zerem (brak błędu) albo dokładnie określa pozycję odwróconego bitu, ponieważ zestawy pokrycia zostały zbudowane bezpośrednio z binarnych cyfr każdej pozycji.

syndrom = (check_p4 << 2) | (check_p2 << 1) | check_p1 syndrom == 0 → nie wykryto błędu syndrom == k → bit na pozycji k jest błędny – odwróć go i masz gotowe Brak tabeli wyszukiwania, brak ponownego przesyłania – obliczanie syndromu jest samo w sobie adresem usterki. To właśnie oznacza się pojedynczą korekcją błędu: kod automatycznie koryguje dokładnie jeden odwrócony bit na słowo kodowe.

syndrome = (check_p4 << 2) | (check_p2 << 1) | check_p1

syndrome == 0   → no error detected
syndrome == k   → bit at position k is wrong — flip it and you're done

SECDED: dodawanie czwartego bitu do podwójnej detekcji błędów

Prosta (7,4) kod Hamminga ma ślepy punkt: jeśli dwa bity ulegają zmianie jednocześnie, syndrom nadal wskazuje z pewnością na jakąś pozycję – błędną – i dekoder koryguje bit, który nigdy nie był złej, bezgłośnie pogarszając błąd. Naprawa, używana w zasadzie we wszystkich rzeczywistych implementacjach, to SECDED (korekcja pojedynczego błędu, podwójna detekcja błędów): dodaj jeden dodatkowy bit ogólny obejmujący całe słowo wraz z innymi bitami parzystości. Pojedynczy błąd powoduje zmianę ogólnej parzystości i daje niezerowy syndrom – korygowany jak wcześniej. Podwójny błąd daje niezerowy syndrom (fałszując wskazanie gdzieś) ale pozostawia niezmienioną ogólną parzystość, a ta niespójność między 'syndrom mówi o błędzie' i 'ogólna parzystość mówi o braku błędów' jest jednoznaczny sygnałem niekorygowanego podwójnego błędu, więc dekoder go sygnalizuje zamiast mylnie korygować.

Gdzie faktycznie działa

Kody Secded Hamming chronią ECC RAM w serwerach i stacjach roboczych przed błędem bitów spowodowanym przez promieniowanie kosmiczne i cząstki alfa, a także w linkach telemetrycznych satelitarnych i z przestrzeni głębokiej, gdzie koszt ponownego wysłania danych może wynieść kilka minut opóźnionego czasu podróży światła. Ochronę zapewniają również kontrolery pamięci NAND flash.

Schemat ten uogólnia się poza (7,4): kod Hamming z r bitami parzystości chroni 2^r − 1 bitów w sumie (2^r − r − 1 bitów danych), więc kody (15,11), (31,26) i (63,57) handlują mniejszym relatywnym nakładem na to samo gwarantowanie korekty pojedynczego błędu, gdy bloki stają się większe – kosztem większego zasięgu uderzeniowego, jeśli w tym samym powiększonym bloku przypadkowo wystąpi kolejny błąd.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Hamming Codes i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.