Kod Hamminga: wykrywanie i korygowanie błędów na przykładach

Co to jest błąd?

Przesyłane dane mogą zostać uszkodzone podczas komunikacji. Prawdopodobnie ma na niego wpływ hałas zewnętrzny lub inne awarie fizyczne. W takiej sytuacji dane wejściowe nie mogą być takie same jak dane wyjściowe. To niedopasowanie jest znane jako „Błąd”.

Błędy w danych mogą skutkować utratą ważnych lub bezpiecznych danych. Większość transferu danych w systemach cyfrowych będzie miała formę „transferu bitowego”. Nawet niewielka zmiana może mieć wpływ na wydajność całego systemu. W sekwencji danych, jeśli 1 zostanie zmienione na 0 lub 0 zostanie zmienione na 1, nazywa się to „błądem bitowym”.

Rodzaje błędów

Podczas transmisji danych od nadawcy do odbiorcy występują trzy główne typy błędów bitowych.

• Błędy jednobitowe
• Wiele błędów bitowych
• Błędy serii

Błędy jednobitowe

Zmiana dokonana w jednym bicie w całej sekwencji danych jest znana jako „błąd pojedynczego bitu”. Jednak występowanie błędu pojedynczego bitu nie jest tak powszechne. Co więcej, błąd ten występuje tylko w równoległym systemie komunikacyjnym, ponieważ dane są przesyłane bitowo w jednym wierszu. Dlatego istnieje większe prawdopodobieństwo, że pojedynczy wiersz może być zaszumiony.

Wiele błędów bitowych

Jeśli w sekwencji danych nastąpi zmiana w dwóch lub więcej bitach sekwencji danych między nadajnikiem a odbiornikiem, nazywa się to „błędami wielobitowymi”.

Ten typ błędu występuje najczęściej w sieciach transmisji danych typu szeregowego i równoległego.

Błędy wybuchowe

Zmiana zestawu bitów w sekwencji danych nazywana jest „błędem serii”. Ten typ błędu danych jest obliczany od pierwszej zmiany bitu do ostatniej zmiany bitu.

Co to jest wykrywanie i korygowanie błędów?

W systemie komunikacji cyfrowej błąd zostanie przeniesiony z jednego systemu komunikacji do drugiego. Jeżeli błędy te nie zostaną wykryte i skorygowane, dane zostaną utracone. Aby komunikacja była skuteczna, dane systemowe powinny być przesyłane z dużą dokładnością. Nastąpi to poprzez w pierwszej kolejności identyfikację błędów i ich skorygowanie.

Wykrywanie błędów to metoda wykrywania błędów występujących w danych przesyłanych z nadajnika do odbiornika w systemie transmisji danych.

Tutaj możesz użyć kodów redundancji, aby znaleźć te błędy, dodając dane podczas ich przesyłania ze źródła. Kody te nazywane są „kodami wykrywającymi błędy”.

Trzy typy kodów wykrywania błędów to:

• Sprawdzanie parzystości
• Cykliczna kontrola nadmiarowa (CRC)
• Wzdłużna kontrola redundancji (LRC)

Sprawdzanie parzystości

• Nazywa się to również kontrolą parzystości.
• Posiada ekonomiczny mechanizm wykrywania błędów.
• W tej technice bit nadmiarowy nazywany jest bitem parzystości. Jest on dołączany do każdej jednostki danych. Całkowita liczba jedynek w jednostce powinna stać się parzysta, co jest znane jako bit parzystości.

Kontrola redundancji wzdłużnej

W tej technice wykrywania błędów blok bitów jest zorganizowany w formacie tabelarycznym. Metoda LRC pomaga obliczyć bit parzystości dla każdej kolumny. Zbiór tej parzystości jest również wysyłany wraz z oryginalnymi danymi. Blok parzystości pomaga sprawdzić redundancję.

Cykliczna kontrola nadmiarowa

Cykliczna kontrola nadmiarowa to sekwencja redundancji, którą należy dołączyć na końcu urządzenia. Dlatego otrzymana jednostka danych powinna stać się podzielna przez drugą, z góry określoną liczbę binarną.

W miejscu docelowym przychodzące dane muszą zostać podzielone przez tę samą liczbę. W przypadku braku reszty jednostka danych jest uznawana za poprawną i jest akceptowana. W przeciwnym razie wskazuje to, że jednostka danych jest uszkodzona w transmisji i dlatego musi zostać odrzucona.

W kodzie Hamminga źródło koduje wiadomość, dodając do niej zbędne bity. Te nadmiarowe bity są najczęściej wstawiane i generowane w określonych miejscach komunikatu w celu przeprowadzenia procesu wykrywania i korygowania błędów.

Historia kodu Hamminga

• Kod Hamminga to technika opracowana przez RWHamming w celu wykrywania błędów.
• Kod Hamminga powinien być stosowany do jednostek danych o dowolnej długości i wykorzystuje relację pomiędzy danymi a bitami redundancji.
• Pracował nad problemem metody korekcji błędów i opracował coraz bardziej zaawansowaną gamę algorytmów zwanych kodem Hamminga.
• W 1950 roku opublikował Kod Hamminga, który jest dziś szeroko stosowany w zastosowaniach takich jak pamięć ECC.

Zastosowanie kodu Hamminga

Oto kilka typowych zastosowań kodu Hamminga:

• Satelity
• Pamięć komputera
• Modemy
• PlasmaCAM
• Otwórz złącza
• Drut ekranujący
• Wbudowany procesor

Zalety kodu Hamminga

• Metoda kodu Hamminga jest skuteczna w sieciach, w których strumienie danych podawane są dla błędów jednobitowych.
• Kod Hamminga nie tylko umożliwia wykrycie błędu bitowego, ale także pomaga wciąć bit zawierający błąd, aby można go było poprawić.
• Łatwość użycia kodów Hamminga sprawia, że ​​najlepiej nadają się one do stosowania w pamięci komputera i korekcji pojedynczych błędów.

Wady kodu Hamminga

• Jednobitowy kod wykrywania i korekcji błędów. Jeśli jednak wiele bitów zostanie uznanych za błędne, wówczas wynikiem może być inny bit, który powinien być poprawny i można go zmienić. Może to spowodować dalsze błędy w danych.
• Algorytm kodu Hamminga może rozwiązać tylko problemy z pojedynczymi bitami.

Jak zakodować wiadomość w kodzie Hamminga

Proces kodowania wiadomości przez nadawcę obejmuje trzy następujące kroki:

• Obliczanie całkowitej liczby nadmiarowych bitów.
• Sprawdzanie położenia zbędnych bitów.
• Na koniec obliczenie wartości tych zbędnych bitów.

Gdy powyższe nadmiarowe bity zostaną osadzone w wiadomości, zostanie ona wysłana do użytkownika.

Krok 1) Obliczanie całkowitej liczby nadmiarowych bitów.

Załóżmy, że wiadomość zawiera:

• n– liczba bitów danych
• p – liczba nadmiarowych bitów, które są do niego dodawane, aby np mógł wskazywać co najmniej (n + p + 1) różne stany.

Tutaj (n + p) przedstawia lokalizację błędu w każdej z (n + p) pozycji bitowych, a jeden dodatkowy stan oznacza brak błędu. Ponieważ bity p mogą wskazywać 2^p stany, 2^p musi być co najmniej równe (n + p + 1).

Krok 2) Umieszczenie zbędnych bitów we właściwym miejscu.

Bity nadmiarowe powinny być umieszczone na pozycjach bitów potęgi 2. Na przykład 1, 2, 4, 8, 16 itd. Są one określane jako p₁ (na pozycji 1), s. XNUMX₂ (na pozycji 2), s. XNUMX₃ (na pozycji 4) itd.

Krok 3) Obliczanie wartości bitu nadmiarowego.

Nadmiarowe bity powinny być bitami parzystości, dzięki czemu liczba jedynek jest parzysta lub nieparzysta.

Te dwa rodzaje parytetu to?

• Jeśli całkowita liczba bitów w wiadomości jest równa, nazywa się to parzystością.
• Całkowita liczba bitów w wiadomości, która jest nieparzysta, nazywana jest parzystością nieparzystą.

Tutaj cały nadmiarowy bit p1 musi zostać obliczony jako parzystość. Powinien obejmować wszystkie pozycje bitów, których reprezentacja binarna powinna zawierać 1 na 1. pozycji, z wyłączeniem pozycji p1.

P1 to bit parzystości dla wszystkich bitów danych na pozycjach, których reprezentacja binarna zawiera 1 na mniej ważnej pozycji, nie licząc 1 Like (3, 5, 7, 9,….)

P2 to bit parzystości dla wszystkich bitów danych na pozycjach, których reprezentacja binarna obejmuje 1 na pozycji 2 od prawej, nie licząc 2 Like (3, 6, 7, 10, 11,…)

P3 jest bitem parzystości dla każdego bitu na pozycjach, którego reprezentacja binarna zawiera 1 na pozycji 3 od prawej, nie obejmuje 4 Podobnie (5-7, 12-15,…)

Odszyfrowanie wiadomości w kodzie Hamminga

Odbiorca otrzymuje przychodzące wiadomości, które wymagają przeprowadzenia ponownych obliczeń w celu znalezienia i skorygowania błędów.

Proces przeliczania przebiega w następujących krokach:

• Zliczanie liczby zbędnych bitów.
• Prawidłowe ustawienie wszystkich zbędnych bitów.
• Test zgodności

Krok 1) Zliczanie liczby zbędnych bitów

Możesz użyć tego samego wzoru do kodowania, liczby zbędnych bitów

2^p ? n + p + 1

Tutaj liczba bitów danych, a p to liczba nadmiarowych bitów.

Krok 2) Prawidłowe ustawienie wszystkich zbędnych bitów

Tutaj p jest bitem nadmiarowym, który znajduje się na pozycjach bitów potęgi 2, na przykład 1, 2, 4, 8 itd.

Krok 3) Test zgodności

Bity parzystości należy obliczać na podstawie bitów danych i bitów nadmiarowych.

p1 = parzystość (1, 3, 5, 7, 9, 11…)

p2 = parzystość (2, 3, 6, 7, 10, 11… )

p3 = parzystość (4-7, 12-15, 20-23… )

Podsumowanie

• Przesyłane dane mogą zostać uszkodzone podczas komunikacji
• Trzy rodzaje błędów bitowych to: 1) błędy jednobitowe, 2) błędy wielobitowe, 3) błędy bitowe typu Burst
• Zmiana dokonana w jednym bicie w całej sekwencji danych nazywana jest „błądem jednobitowym”.
• Jeśli w sekwencji danych nastąpi zmiana w dwóch lub więcej bitach sekwencji danych między nadajnikiem a odbiornikiem, nazywa się to „błędami wielobitowymi”.
• Zmiana zestawu bitów w sekwencji danych nazywana jest „błędem serii”.
• Wykrywanie błędów to metoda wykrywania błędów występujących w danych przesyłanych z nadajnika do odbiornika w systemie transmisji danych
• Trzy typy kodów wykrywania błędów to 1) kontrola parzystości 2) cykliczna kontrola redundancji (CRC) 3) podłużna kontrola redundancji (LRC)
• Kod Hamminga to kod liniowy, który jest przydatny do wykrywania błędów maksymalnie dwóch natychmiastowych błędów bitowych. Jest zdolny do błędów jednobitowych.
• Kod Hamminga to technika opracowana przez RWHamming w celu wykrywania błędów.
• Typowe zastosowania kodu Hamminga to pamięć komputera satelitarnego, modemy, wbudowany procesor itp.
• Największą zaletą metody kodu Hamminga jest skuteczność w sieciach, w których strumienie danych podawane są dla błędów jednobitowych.
• Największą wadą metody kodu Hamminga jest to, że może ona rozwiązać tylko problemy z pojedynczymi bitami.
• Proces szyfrowania i dekodowania wiadomości możemy przeprowadzić za pomocą kodu Hamminga.