Zawartość
Kody Hamminga służą do wstawiania informacji korekcji błędów do strumieni danych. Kody są zaprojektowane tak, aby błąd był nie tylko wykrywany, ale także korygowany. Dodanie informacji korekcji błędów zwiększa ilość danych, ale także zwiększa niezawodność komunikacji za pośrednictwem mediów o wysokich współczynnikach błędów.
Kodowanie Hamminga może być skomplikowane w implementacji, ale można to zrobić bardzo szybko, używając sztuczek arytmetycznych na poziomie bitów. Pozwala to na stworzenie użytecznego i szybkiego systemu korekcji błędów do wykorzystania w aplikacjach wbudowanych.
Krok 1
Utwórz słowo danych. Każdy bit z pozycją będącą potęgą dwójki (pierwszy, drugi, czwarty itd.) Musi być zarezerwowany dla informacji o parzystości. Użyj tak długo, jak to konieczne, aby słowo miało oryginalne dane i bity parzystości.
Przykład:
1 1 0 1 0 0 1 0 staje się _ _ 1 _ 1 0 1 _ 0 0 1 0
Oryginalne bity pozostają w tej samej kolejności, ale zostały rozłożone, aby wstawić bity parzystości.
Krok 2
Oblicz pierwszy bit parzystości. Zaczynając od pierwszego bitu, odczytywany jest bit, a następnie bit jest pomijany i procedura jest powtarzana do końca. W międzyczasie zliczana jest liczba znalezionych. Bity parzystości nie są uwzględniane w tym procesie.
Jeśli liczba jedynek jest parzysta, ustaw pierwszy bit na zero. W przeciwnym razie ustaw go na jeden.
Przykład:
Bity 1, 3, 5, 7, 9 i 11 z _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101 zawierają cztery jedynki. Jest to parzyste, więc pierwszy bit jest zerowany: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Krok 3
Oblicz pozostałe bity parzystości. Zaczynając od drugiego bitu, odczytywane są dwa bity, a następnie dwa bity są pomijane i procedura jest powtarzana do końca. Czwarty bit odczytuje cztery bity, pomija kolejne cztery, zaczynając od bitu czwartego. Po tym samym wzorcu następują wszystkie bity parzystości, dopóki nie zostaną obliczone.
Przykład:
Bit 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 sprawdza _1, 01, 01, które zawierają trzy jedynki, więc bit 2 jest ustawiony na jeden. Bit 4: _ 0 1 1 1 0 1 _ 0 0 1 0 sprawdza _101, 0, który zawiera dwa jedynki, więc bit 4 jest ustawiony na zero. Bit 8: 0 1 1 0 1 0 1 _ 0 0 1 0 sprawdza _0010, który zawiera tylko jeden, więc bit 8 jest ustawiony na jeden.
Dlatego słowo jest kodowane jako 011010110010.
Krok 4
Potwierdź słowo. Jeśli słowo jest uszkodzone, bity parzystości nie będą zgodne z oczekiwaniami. Aby potwierdzić, że słowo nie jest uszkodzone, wystarczy obliczyć bity parzystości, wykonując kroki drugi i trzeci. Jeśli bity nie są takie same, zapisz ich pozycje.
Krok 5
Popraw zły bit. Jeśli znajdziesz nieprawidłowe bity parzystości, po prostu dodaj pozycje bitów. Wartość sumaryczna to pozycja nieprawidłowego bitu. Zmień wartość bitu w tej pozycji.
Na przykład, jeśli niepoprawne bity parzystości to jeden i cztery, zmiana wartości piątego bitu skoryguje błąd.