Algorytmy korekcji i detekcji błędów

Kontrola parzystości (ang. check parity), jest prostą odmianą metody sum kontrolnych. Parzystość obejmuje wysłanie dodatkowych bitów które zawierają nadmiarową informację wygenerowaną za pomocą prostego algorytmu. Ten algorytm jest powtarzany przy odbieraniu: - jeśli nie daje tego samego rezultatu, wnioskujemy, że wystąpił błąd. Sprawdzanie parzystości może być zaimplementowane na dwa sposoby. Pierwszy polega na zliczaniu 0, a drugi 1 w bajcie. Odpowiednio dla nieparzystej lub parzystej ich ilości bit kontrolny ustawiany jest na 'zero' lub 'jeden'. Dlatego właśnie, jeśli dwa bity zmienią swoją wartość, parzystość nie ulegnie zmianie. Rozróżniamy 2 metody, normalną i negatywną kontrolę parzystości.

Rozważmy dla przykładu transmisję znaku ASCII 'K' przy zastosowaniu negatywnej kontroli parzystości. Znak 'K' jest kodowany sekwencją bitów '1 0 0 1 0 1 1', a więc bit parzystości musi być ustawiony na 1, aby łączna liczba jedynek była nieparzysta. Bit parzystości jest dołączany jako najbardziej znaczący bit słowa n-bitowego.

bit parzystości 6 5 4 3 2 1 0
1 1 0 0 1 0 1 1

Tab. Zakodowany znak K za pomocą kontroli parzystości.

bit parzystości 6 5 4 3 2 1 0
1 1 0 0 1 1 1 1

Tab. Zakodowany znak K za pomocą kontroli parzystości z błędem na pozycji bitu nr 2.

W otrzymanej sekwencji łączna liczba jedynek jest parzysta, a to oznacza przekłamanie otrzymanej sekwencji. W tym przypadku odbiornik nie jest w stanie określić, który bit błędnie odebrano, a więc transmisja całego znaku musi zostać powtórzona.

Kod Hamminga jest jednym z najprostszych metod detekcji błędów, która umożliwia również ustalenie pozycji błędnych bitów. Metoda kodowania polega na wysyłaniu nadmiarowych informacji zakodowanych tak, że może być ona wykorzystana do zidentyfikowania błędnego bitu. Ma on małe zastosowanie, ponieważ jest dość prymitywny i jego działanie jest dość wąskie. Kod Hamminga (korygujący błąd pojedynczy) wykrywa dowolny błąd pojedynczy oraz wskazuje jego pozycję, co umożliwia stosowną korekcję przez zmianę bitu na przeciwny. Jest to kod korygujący błąd pojedynczy i jest przykładem kodowania FEC (ang. Forward Error Correction). Główna zasada kodowania polega na umieszczaniu bitów nadmiarowych w tych pozycjach wiadomości, których numery wyrażają się przez potęgę liczby 2.

Bity nadmiarowe = 2n

Zakodowana informacja jest kombinacją 'I' bitów z bitami informacyjnymi i 'K' bitami nadmiarowymi. Całkowita długość ciągu zakodowanego w kodzie Hamminga wynosi :

Długość ciągu zakodowanego = K + I

Przy założeniu że : (2 do potęgi K) - 1 >= K + 1

Bity w kodzie Hamminga numerowane są kolejno zaczynając od prawej strony np.:

I7 I6 I5 K4 I3 K2 K1

Kod korekcyjny Hamminga jest stosowany w tablicach, macierzach dyskowych typu RAID 2 (ang. Redundant Array of Inexpensive Disks). Idea tego urządzenia opiera się na połączeniu maksymalnie pięciu dysków w jeden system, w którym dane zapisywane są na wszystkich dyskach. W swej podstawowej postaci służy do wykrywania i korygowania pojedynczych błędów w ciągach kodowych. Działa w ten sposób, że informacja jest dzielona między kolejne dyski matrycy dyskowej bit po bicie. Towarzyszące bitom danych bity kodu Hamminga pozwalają na poprawianie nie tylko pojedynczych błędów, ale i ich grup, jednak kod Hamminga został uznany jako algorytm zbyt kosztowny w zastosowaniach sieciowych (tańsze okazały się algorytmy zapisu bajt po bajcie na kolejnych dyskach), technika ta jest jeszcze używana jedynie w dużych komputerach.

CRC, czyli Cykliczna Kontrola Nadmiarowa (ang. Cyclic Redundancy Chec). Polega na wyliczeniu wartości pewnego wielomianu na podstawie wartości oryginalnego komunikatu. Obecnie stosowany jest CRC 16 i 32, możemy je spotkać w Ethernecie, archiwizatory (ZIP, RAR), programy do dzielenia plików itp.

Inne rodzaje znane, ale mniej wykorzystywane to.:

  • CRC-8, zastosowano wielomian typu x8+x2+x+1, bitowo 100000111, wykorzystywany przy ATM (ang. Asynchronous Transwer Mode), czyli szerokopasmowej technologii komunikacyjnej, wykorzystywanej do asynchronicznej transmisji danych.
  • CRC-10, zastosowano wielomian typu x10+x9+x5+x4+x+1, bitowo 11000110011, wykorzystywany przy ATM.
  • CRC-12, zastosowano wielomian typu x12+x11+x3+x2+x+1, bitowo 1100000001111.
  • CRC CCITT 16, zastosowano wielomian typu x16+x12+x5+1, bitowo 10001000000100001, używany w protokole HDLC ( ang. High level Data Link Control).

W przypadku CRC 32 mamy wielomian typu x32+ x26+ x23+ x22+ x16+ x12+ x11+ x10+ x8+ x7+ x5+ x4+ x2+ x+1, a przy CRC 16 wielomian x16+ x15+ x2+ 1. Na podstawie danego wielomianu obliczany jest specjalny ciąg bitów, który przesyłany jest razem z informacją w celu dalszej weryfikacji. Stosowanie tej metody daje dobre rezultaty w detekcji błędów.

CRC może wykryć :

  • 1. Wszystkie pojedyncze błędne bity,
  • 2. Wszystkie podwójne błędne bity gdy wielomian jest dobrze dobrany,
  • 3. Grupy bitów błędnych do długości n ( n jest wielokrotnością 8 ), oraz większość dłuższych,
  • 4. Wszystkie z wyjątkiem 1 n błędów n+1 bitowego dzielnika.

CRC umożliwia wykrywanie szerszej klasy błędów niż sumy kontrolne. Szczególnie ważne jest wykrywanie dwóch konkretnych kategorii typowych błędów. Po pierwsze, awaria sprzętu często powoduje uszkadzanie określonej grupy bitów. Na przykład w urządzeniu znakowego wejścia/wyjścia może to oznaczać ustawianie pierwszych dwóch bitów każdego znaku na zero. Takie błędy są czasami nazywane błędami pionowymi (ang. bit errors), gdyż występują w pionowych kolumnach (gdy dane zapiszemy wierszami). Mechanizm CRC wykrywa błędy pionowe skuteczniej niż mechanizm sum kontrolnych. Po drugie, CRC pozwala na szczególnie skuteczne wykrywanie błędów związanych ze zmianą wartości niewielkiej liczby bliskich bitów. Takie błędy są nazywane błędami grupowymi (ang. burst errors). Wykrywanie błędów grupowych jest bardzo ważne, gdyż odpowiadają one za znaczną część wszystkich błędów transmisji w sieciach komputerowych. Zakłócenia elektryczne, spowodowane na przykład przez burzę, powodują często błędy tego właśnie typu. Podobne skutki mają zakłócenia powodowane przez silniki elektryczne i inne urządzenia tego typu.

W pliku poniżej, do pobrania, są dokładnie wytłumaczone powyższe metody na przykładach i programach pomocniczych.

detekcja_i_korekcja.rar