Co to jest kod Hamminga?
Kod Hamminga to metoda wykrywania i korygowania błędów w transmisji binarnej. Odbywa się to poprzez włączenie dodatkowych cyfr binarnych do sekwencji używanych do sprawdzania, a także algorytmu zapewniającego logikę wykrywania. Taki kod jest w stanie znaleźć dwa błędy w dowolnej sekwencji bitów i naprawić jeden bit, który może być niepoprawny. Najczęściej przywoływany kod Hamminga jest znany jako Hamming (7,4), gdzie cztery wskazują pierwotną liczbę bitów początkowych, a siedem reprezentuje całkowitą liczbę bitów w sekwencji po uwzględnieniu dodatkowych bitów kontrolnych.
Technika ta ma swoją nazwę od twórcy, Richarda Hamminga, który opublikował metodę w 1950 r. Sposób działania kodu Hamminga polega na pobraniu ciągu bitów i wstawieniu dodatkowych bitów kontrolnych, zwanych bitami parzystości, do sekwencji. Bity kontrolne są zawsze wstrzykiwane w miejscu, które jest potęgą dwóch, więc dowolną liczbę bitów można zweryfikować, włączając dodatkowe bity parzystości. Może to trwać, dopóki ostatni bit parzystości dodany do sekwencji nie znajdzie się w pozycji, która jest potęgą dwóch, która jest mniejsza lub równa końcowej pozycji w sekwencji.
Po wprowadzeniu wszystkich bitów parzystości pozostałe pozycje są faktycznymi bitami danych. Biorąc pod uwagę czterobitowy przykład, pozycje bitów 1, 2 i 4 byłyby bitami parzystości, podczas gdy pozycje 3, 5, 6 i 7 są danymi. Po ustaleniu tej sekwencji logika kodu Hamminga zaczyna działać.
W kodzie Hamminga każdy z bitów parzystości, który został dodany do sekwencji, służy do sprawdzania niektórych pozycji bitów, w których są blisko, w tym siebie. Bit parzystości w pierwszej pozycji sprawdza co drugą pozycję bitu, która jest zasadniczo każdą nieparzystą pozycją w sekwencji. Drugi bit parzystości, w pozycji drugiej, sprawdza pozycje drugą i trzecią, następnie pomija dwie pozycje, sprawdza dwie kolejne pozycje, pomija dwie kolejne i tak dalej. Jeśli w pozycji czwartej znajduje się bit parzystości, działa on podobnie, ponieważ sprawdza pozycje od czterech do siedmiu, następnie pomija cztery pozycje, sprawdza cztery kolejne i dalej. Każdy bit parzystości w sekwencji jest kontynuowany w ten sposób przez całą sekwencję.
Proces, w którym kod Hamminga wykrywa i koryguje błąd, polega na dodaniu bitów w sekwencji sprawdzania dla każdego sprawdzania parzystości, z których każdy musi wynikać z liczby parzystej. Biorąc pod uwagę siedmiobitowy przykład, dla pierwszego sprawdzenia parzystości sumuje się bity 1, 3, 5 i 7. Jeśli suma jest liczbą parzystą, sprawdzana jest parzystość, ale jeśli suma jest nieparzysta, oznacza to błąd. Ponieważ kontrole parzystości nakładają się, pojawią się dwa takie błędy. Kiedy sumy bitów z dwiema parzystościami, które nie dają parzystych sum, są sumowane, ujawni to bit, który należy poprawić.
W siedmiobitowym przykładzie kodu Hamminga należy wziąć pod uwagę, że bit w pozycji numer pięć jest niepoprawny. Suma bitów na pozycjach 1, 3, 5 i 7 wyjdzie jako liczba nieparzysta, podobnie jak suma bitów na pozycjach od 4 do 7. Wskazuje to, że kontrole parzystości dla bitów kontrolnych w pozycjach 1 i 4 nie powiodły się. Po dodaniu jednego i czterech suma wynosi pięć, co oznacza pozycję niepoprawnego bitu w transmisji, który należy poprawić.