Hamminga Code:Wykrywanie i korygowanie błędów z przykładami

Co to jest błąd?

TransmitDane TED mogą ulec uszkodzeniu podczas komunikacji. Prawdopodobnie będą one zakłócane przez zakłócenia zewnętrzne lub inne uszkodzenia fizyczne. W takiej sytuacji dane wejściowe nie mogą być takie same jak dane wyjściowe. Ta niezgodność nazywana jest „błędem”.

Błędy danych mogą spowodować utratę ważnych lub bezpiecznych danych. Większość transferu danych w systemach cyfrowych odbywa się w formie „transferu bitów”, a nawet niewielka zmiana pojedynczego bitu może wpłynąć na wydajność całego systemu. W sekwencji danych, jeśli 1 zostanie zamienione na 0 lub 0 na 1, nazywa się to „błędem bitowym”.

Rodzaje błędów

Istnieją trzy główne typy błędów bitowych, które występują podczas przesyłania danych. transmitod nadawcy do odbiorcy. Poniższy diagram ilustruje, jak każdy typ wpływa na sekwencję danych:

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

Błędy jednobitowe

Zmiana jednego bitu w całej sekwencji danych nazywana jest „błędem pojedynczego bitu”. Występowanie błędu pojedynczego bitu nie jest częste. Najczęściej występuje w równoległym systemie komunikacyjnym, ponieważ dane są przesyłane bitowo na oddzielnych liniach, więc istnieje większe prawdopodobieństwo, że jedna linia będzie zaszumiona, a pozostałe pozostaną czyste.

Wiele błędów bitowych

Gdy dwa lub więcej bitów sekwencji danych zmienia się pomiędzy transmitmiędzy odbiornikiem a odbiornikiem, zjawisko to znane jest jako „błąd wielobitowy”.

Tego typu błąd występuje zarówno w sieciach transmisji danych szeregowych, jak i równoległych.

Błędy wybuchowe

Zmiana zestawu kolejnych bitów w sekwencji danych nazywana jest „błędem serii”. Długość błędu serii mierzona jest od pierwszego zmienionego bitu do ostatniego zmienionego bitu.

Czym jest wykrywanie i korygowanie błędów?

W cyfrowym systemie komunikacji błędy mogą pojawiać się podczas przesyłania danych z jednego urządzenia do drugiego. Jeśli błędy te nie zostaną wykryte i skorygowane, dane zostaną utracone. Aby komunikacja była efektywna, dane muszą być przesyłane z dużą dokładnością, co osiąga się poprzez identyfikację błędów, a następnie ich korektę.

Wykrywanie błędów jest metodą znajdowania błędów obecnych w danych transmitted z transmitdo odbiornika w Komunikacji danych pomimo napiętego harmonogramu

Kody redundancji służą do znajdowania tych błędów poprzez dodawanie dodatkowych bitów do danych, gdy są one transmitTe dodatkowe bity nazywane są „kodami wykrywania błędów”. Trzy najpopularniejsze 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.
• Zapewnia opłacalny mechanizm wykrywania błędów.
• W tej technice nadmiarowy bit dodawany do każdej jednostki danych nazywany jest bitem parzystości. Jest on ustawiany tak, aby łączna liczba jedynek w jednostce była parzysta (parzystość) lub nieparzysta (parzystość).

Kontrola redundancji wzdłużnej

W tej technice wykrywania błędów blok bitów jest organizowany w tabeli. Metoda LRC oblicza bit parzystości dla każdej kolumny, a ten zestaw bitów parzystości jest przesyłany wraz z danymi oryginalnymi. Blok bitów parzystości pomaga odbiornikowi sprawdzić redundancję i wykryć błędy.

Cykliczna kontrola nadmiarowa

Kontrola cyklicznej redundancji polega na dodaniu sekwencji zbędnych bitów na końcu jednostki danych, tak aby powstała jednostka danych stała się podzielna przez drugą, z góry ustaloną liczbę binarną.

W miejscu docelowym dane przychodzące są dzielone przez tę samą liczbę. Jeśli nie ma reszty, jednostka danych jest uznawana za poprawną i akceptowana. W przeciwnym razie oznacza to, że jednostka danych została uszkodzona podczas transmisji i musi zostać odrzucona.

Co to jest Hamming Code?

Kod Hamminga to kod liniowy, który jest przydatny do wykrywania do dwóch natychmiastowych błędów bitowych i korygowania błędów pojedynczych bitów. Tego rodzaju korekcja błędów zazwyczaj działa na poziomie łącza danych, ramkując dane i sprawdzając ich integralność między sąsiednimi węzłami.

W kodzie Hamminga źródło koduje wiadomość, dodając zbędne bity. Te zbędne bity są wstawiane i generowane w określonych miejscach wiadomości, aby przeprowadzić proces wykrywania i korekcji błędów.

Historia Hamminga Code

• Kod Hamminga to technika opracowana przez R.W. Hamminga służąca do wykrywania i korygowania błędów.
• Można ją stosować do jednostek danych o dowolnej długości i wykorzystuje ona relację między bitami danych i bitami redundancji.
• Hamming pracował nad problemem korekcji błędów i opracował coraz bardziej rozbudowany zestaw algorytmów.
• W 1950 roku opublikował kod Hamminga, który do dziś jest szeroko stosowany w takich zastosowaniach, jak pamięć ECC.

Zastosowania Hamminga Code

Oto kilka typowych zastosowań kodu Hamminga:

• Satelity
• Pamięć komputera (ECC RAM)
• Modemy
• PlasmaCAM
• Otwórz złącza
• Przewód ekranowany
• Procesory wbudowane

Zalety metody Hamminga Code

• Kod Hamminga sprawdza się w sieciach, w których strumienie danych narażone są na błędy pojedynczych bitów.
• Nie tylko wykrywa błąd bitowy, ale także pomaga zidentyfikować bit zawierający błąd, dzięki czemu można go naprawić.
• Łatwość stosowania kodów Hamminga sprawia, że ​​doskonale nadają się one do pamięci komputerowej i korekcji pojedynczych błędów.

Wady metody Hamminga Code

• Jest to kod do wykrywania i korekcji błędów na poziomie jednego bitu. Jeśli okaże się, że wiele bitów jest błędnych, wynik może zmienić inny bit, który był poprawny, co jeszcze bardziej zniekształci dane.
• Algorytm kodu Hamminga może rozwiązać tylko problemy jednobitowe.

Jak zakodować wiadomość w systemie Hamminga Code

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

• Oblicz całkowitą liczbę bitów nadmiarowych.
• Określ położenie zbędnych bitów.
• Oblicz wartość każdego zbędnego bitu.

Po umieszczeniu nadmiarowych bitów w wiadomości, do odbiorcy wysyłane jest pełne słowo kodowe.

Krok 1) Oblicz całkowitą liczbę bitów nadmiarowych.

Załóżmy, że wiadomość zawiera n bity danych i p nadmiarowe bity, dodane tak, że 2^p może wskazywać co najmniej (n + p + 1) różnych stanów.

Tutaj (n + p) odpowiada za lokalizację błędu w każdej z pozycji bitów (n + p), a jeden dodatkowy stan oznacza brak błędu. Ponieważ p bitów parzystości może wskazywać 2^p stany, 2^p musi być co najmniej równe (n + p + 1).

Krok 2) Umieść zbędne bity w odpowiednich miejscach.

Nadmiarowe bity umieszczane są na pozycjach bitowych, które są potęgami liczby 2 — na przykład 1, 2, 4, 8 i 16. Są one nazywane p₁ (na pozycji 1), s. XNUMX₂ (na pozycji 2), s. XNUMX₃ (na pozycji 4) i tak dalej.

Krok 3) Oblicz wartość każdego zbędnego bitu.

Każdy nadmiarowy bit to bit parzystości, który określa liczbę jedynek w swojej grupie jako parzystą lub nieparzystą. Istnieją dwa rodzaje parzystości:

• Parzystość parzysta: łączna liczba jedynek na pokrytych pozycjach jest parzysta.
• Nieparzystość: całkowita liczba jedynek na pokrytych pozycjach jest nieparzysta.

Każdy bit parzystości pokrywa konkretny zestaw pozycji, określony przez binarną reprezentację numerów pozycji:

• p₁ sprawdza każdą pozycję, której wartość binarna ma 1 w najmniej znaczącym bicie — pozycje 1, 3, 5, 7, 9, 11 itd.
• p₂ sprawdza każdą pozycję, której wartość binarna ma 1 na drugim bicie od prawej — pozycje 2, 3, 6, 7, 10, 11 itd.
• p₃ sprawdza każdą pozycję, której wartość binarna ma 1 na trzecim bicie od prawej — pozycje od 4 do 7, od 12 do 15 itd.

Przykład rozwiązania (7,4): Rozważ cztery bity danych 1011. Wymagane są trzy bity parzystości (2³ = 8 ≥ 4 + 3 + 1), co daje siedmiobitowe słowo kodowe przedstawione jako p₁ p₂ d₁ p₃ d₂ d₃ d₄Umieszczenie danych ustawia pozycje 3, 5, 6, 7 = 1, 0, 1, 1. Używając parzystości: p₁ obejmuje pozycje 1, 3, 5, 7 (bity 1, 0, 1 → p₁ = 0); p₂ obejmuje 2, 3, 6, 7 (bity 1, 1, 1 → p₂ = 1); p₃ obejmuje 4, 5, 6, 7 (bity 0, 1, 1 → p₃ = 0). Ten transmithasło ted jest zatem 0110011.

Jak zdekodować wiadomość w systemie Hamminga Code

Odbiorca odbiera przychodzącą wiadomość i wykonuje przeliczenia w celu znalezienia i poprawienia błędów. Proces przeliczania obejmuje następujące kroki:

• Policz liczbę zbędnych bitów.
• Prawidłowo rozmieść wszystkie zbędne bity.
• Wykonaj kontrolę parzystości.

Krok 1) Policz liczbę zbędnych bitów. Użyj tego samego wzoru, co przy kodowaniu: 2^p ≥ n + p + 1, gdzie n jest liczbą bitów danych, a p jest liczbą bitów redundantnych.

Krok 2) Prawidłowe rozmieszczenie wszystkich zbędnych bitów. Każdy zbędny bit znajduje się na pozycji będącej potęgą liczby 2 — na przykład 1, 2, 4 i 8.

Krok 3) Wykonaj kontrolę parzystości. Bity parzystości są przeliczane na podstawie bitów danych i odebranych bitów nadmiarowych:

• p₁ = parzystość(1, 3, 5, 7, 9, 11, …)
• p₂ = parzystość(2, 3, 6, 7, 10, 11, …)
• p₃ = parzystość(4–7, 12–15, 20–23, …)

Przeliczone bity parzystości tworzą liczbę binarną. Jeśli ta liczba wynosi zero, błąd nie występuje; w przeciwnym razie jej wartość wskazuje dokładną pozycję pojedynczego uszkodzonego bitu, który jest następnie odwracany w celu poprawienia komunikatu.

FAQ