Wykrywanie błędów

Ostatnia aktualizacja: środa 10 październik 2018 à 12:40 przez Anna Dobrzyńska.

Kodowanie binarne jest praktyczne w użyciu na urządzeniach elektronicznych, np. komputerach, na których informacje mogą być kodowane na podstawie sygnału elektrycznego lub jego braku.

Mogą jednak występować zakłócenia (zniekształcenia lub szum), zwłaszcza, gdy dane są przesyłane na duże odległości. Z tego powodu możliwość sprawdzenia poprawności danych jest koniecznością w niektórych przypadkach (np. zastosowania profesjonalne, bankowe, przemysłowe, informacje poufne lub związane z bezpieczeństwem).

Dlatego też istnieją mechanizmy zapewniające pewien poziom integralności danych, tzn. potwierdzanie odbiorcy, iż otrzymane dane są identyczne z przesyłanymi. Istnieją dwa sposoby ochrony danych przed błędami:

zainstalowanie bardziej rzetelnego nośnika transmisyjnego, tj. fizycznej warstwy ochronnej. Konwencjonalne połączenie zwykle posiada poziom błędu od 10^-5 do 10^-7.
wprowadzenie logicznych mechanizmów do wykrywania i korygowania błędów.

Systemy kontroli błędów oparte na logice w większości opierają się na dodawaniu informacji (in. "redundancji") w celu sprawdzenia poprawności danych. Ta dodatkowa informacja jest nazywana sumą kontrolną.

Korygowanie błędów

Lepsze systemy wykrywania błędów zostały udoskonalone – korzystają z kodów zwanych:

Kodami samokorygującymi.
Kodami samosprawdzającymi.

Kontrola parzystości

Kontrola parzystości (zwana również VRC, tzn. Vertical Redundancy Check lub Vertical Redundancy Checking, pionowa kontrola nadmiarowa/pionowa kontrola redundancji) jest jednym z najprostszych mechanizmów kontrolnych. Polega na dodawaniu dodatkowego bitu (zwanego bitem parzystości) do pewnej liczby bitów danych zw. słowem kodowym (przeważnie 7 bitów, aby uformować bit po połączeniu z bitem parzystości), którego wartość (0 lub 1) jest taka, że całkowita suma bitów 1 jest parzysta. Mówiąc wprost, 1 , jeśli liczba bitów w słowie kodowym jest nieparzysta, w pozostałych przypadkach - 0.

Rozważmy przykład:

W tym przykładzie liczba bitów danych 1 jest parzysta, a więc bit parzystości jest ustawiony na 0. Dla kontrastu w przykładzie poniżej bity danych są nieparzyste, więc bit parzystości to 1:

Przyjmijmy, że po transmisji najmłodszy bit z poprzedniego bajtu (najbardziej na prawo) uległ interferencji:

W tym przypadku bit parzystości nie odpowiada już parzystości bajtu: wykryto błąd.

Jeśli jednak dwa bity (lub parzysta liczba bitów) zmieniłyby się jednocześnie, gdy wysyłano sygnał, nie wykryto by żadnego błędu.

Jako że system kontroli parzystości może wykrywać wyłącznie nieparzystą liczbę błędów, może wykryć jedynie 50% błędów. Ten mechanizm wykrywania błędów ma jeszcze jedną wadę: nie jest w stanie skorygować znalezionych błędów (a zatem można je naprawić tylko poprzez żądanie ponownego przesłania błędnego bajtu).

Wzdłużna kontrola nadmiarowa

Wzdłużna kontrola nadmiarowa (w skrócie LRC; zwana także poprzeczną kontrolą nadmiarową lub krzyżową kontrolą parzystości) polega nie na sprawdzaniu integralności danych reprezentujących pojedynczy znak, ale integralności parzystości bitów grupy znaków.

Przyjmijmy, że przesyłamy wiadomość o treści "HELLO" przy użyciu standardowego ASCII.

Poniżej przedstawiamy dane tak, jak będą przesłane przy pomocy kodów wzdłużnej kontroli nadmiarowej:

Litera	Kod ASCII (7-bitowy)	Bit parzystości (LRC)
H	1001000	0
E	1000101	1
L	1001100	1
L	1001100	1
0	1001111	1
VRC	1000010	0

Cykliczna kontrola nadmiarowa

Cykliczna kontrola nadmiarowa (lub w skrócie CRC) to skuteczna i łatwa w użyciu metoda kontroli integralności danych. Jest to pierwotna metoda wykrywania błędów używana w telekomunikacji.

Koncepcja

Cykliczna kontrola nadmiarowa polega na ochronie danych w blokach zwanych ramkami. Każdej ramce przypisuje się segment danych zwany kodem kontrolnym (zdarza się, że FCS dla Frame Check Sequence (sekwencji kontroli ramki) w przypadku sekwencji 32-bitowej, czasem błędnie nazywanej CRC). Kod CRC zawiera dane redundantne w ramce, zatem błędy mogą być nie tylko wykrywane, ale też naprawiane.

Koncepcja CRC polega na traktowaniu sekwencji binarnych jako wielomianów binarnych, tzn. wielomianów, których współczynniki odpowiadają sekwencji binarnej. Na przykład sekwencja binarna 0110101001 może być przedstawiana jako wielomian, jak pokazano poniżej:

0*X⁹ + 1*X⁸ + 1*X⁷ + 0*X⁶ + 1*X⁵ + 0*X⁴ + 1*X³ + 0*X² + 0*X¹ + 1*X⁰
czyli
X⁸ + X⁷ + X⁵ + X³ + X⁰
lub
X⁸ + X⁷ + X⁵ + X³ + 1

W ten sposób najmłodszy bit w sekwencji (najbardziej na prawo) oznacza stopień 0 wielomianu (X⁰ = 1), 4^th bit od prawej oznacza stopień 3 wielomianu (X³), itd. Sekwencja n-bitowa tworzy zatem wielomian o maks. stopniu n-1. Operacje na wszelkich wyrażeniach wielomianowych należy wobec tego przeprowadzać przy użyciu modułu 2.

W tym procesie wykrywania błędów z góry określony wielomian (zwany wielomianem generującym , w skrócie G(X)) jest znany zarówno nadawcy, jak i odbiorcy. Nadawca, aby uruchomić mechanizm wykrywania błędów, stosuje algorytm na bitach ramek, aby wygenerować CRC, po czym przesyła te 2 elementy odbiorcy. Odbiorca wówczas dokonuje tych samych obliczeń celem sprawdzenia, czy CRC jest prawidłowe.

Zastosowanie w praktyce

Przyjmijmy, że M będzie informacją, która odpowiada bitom ramki, które chcemy przesłać, a M(X) będzie powiązanym wielomianem. M’ będzie przesyłaną wiadomością, tj. wstępną wiadomością, z którą n-bitowa CRC ma być powiązana. CRC jest takie, że M'(X)/G(X)=0. Zatem kod CRC jest równy reszcie z dzielenia wielomianu M(X) (do którego wcześniej dołączone zostały bity nnul (bity o wartości zerowej), odpowiadające długości CRC) na G(X).

Przykład: weźmy informację M z następującymi 16 bitami: 1011 0001 0010 1010 (zw. B1 w postaci szesnastkowej). Przyjmijmy G(X) = X³ + 1 (w wersji binarnej przedstawiane jako 1001). Jako że G(X) ma stopień 3, wynikiem jest dodanie 4 bitów nul do M: 10110001001010100000. CRC jest równe reszcie z dzielenia M przez G:

10110001001010100000
1001...,..,.,.,.....
----...,..,.,.,.....
0100..,..,.,.,.....
0000..,..,.,.,.....
----..,..,.,.,.....
1000.,..,.,.,.....
0000.,..,.,.,.....
----.,..,.,.,.....
1000.,..,.,.,.....
1001,..,.,.,.....
----,..,.,.,.....
1111..,.,.,.....
1001..,.,.,.....
----..,.,.,.....
1100.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
1101,.,.,.....
1001,.,.,.....
----,.,.,.....
1000.,.,.....
0000.,.,.....
----.,.,.....
10001......
1001,.,.....
----,.,.....
10000.,.....
1001.,.....
----
1111,.....
1001,.....
----,.....
1100.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----..
1100.
1001.
----.
1010
1001
----
0011

Aby stworzyć M', należy powiązać uzyskane CRC z bitami ramki, które mają zostać wysłane:

M' = 1011000100101010 + 0011 
M' = 10110001001010100011

Zatem, jeśli odbiorca podzieli M' przez G, otrzyma resztę zero, jeśli transmisja odbyła się bez błędów:

10110001001010100011
1001...,..,.,.,...,,
----...,..,.,.,...,,
0100..,..,.,.,...,,
0000..,..,.,.,...,,
----..,..,.,.,...,,
1000.,..,.,.,.....
1001.,..,.,.,.....
----.,..,.,.,.....
0010,..,.,.,.....
0000,..,.,.,.....
----,..,.,.,.....
0101..,.,.,.....
0000..,.,.,.....
----..,.,.,.....
1010.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
0110,.,.,.....
0000,.,.,.....
----,.,.,.....
1101.,.,.....
1001.,.,.....
----.,.,.....
1010,.,.....
1001,.,.....
----,.,.....
0111.,.....
0000.,.....
----
1110,.....
1001,.....
----,.....
1111.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----,,
1101,
1001,
----,
1001
1001
----
0

Wielomiany generujące

Najczęściej używane wielomiany generujące to:

CRC-12: X¹² + X¹¹ + X³ + X² + X + 1
CRC-16: X¹⁶ + X¹⁵ + X² + 1
CRC CCITT V41: X¹⁶ + X¹² + X⁵ + 1 (ten kod jest używany w procedurze HDLC.)
CRC-32 (Ethernet): = X³² + X²⁶ + X²³ + X ²² + X¹⁶ +X¹² + X¹¹ + X¹⁰ + X⁸ + X⁷ + X⁵ + X⁴ + X² + X + 1
CRC ARPA: X²⁴ + {exp|23}}+X¹⁷ + X¹⁶ + X¹⁵ + X¹³ + X¹¹ + X¹⁰ + X⁹ + X⁸ + X⁵ + X³ + 1

Zobacz również

Ten dokument zatytułowany "Wykrywanie błędów" opublikowany przez CCM (pl.ccm.net) jest udostępniany na licencji Creative Commons. Możesz kopiować i modyfikować kopie tej strony, na warunkach określonych przez licencję i wymienionych w niniejszym tekście.

Base64

Reprezentacje