Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Przesyłanie bitów

Kody detekcyjne - EDC

SPIS TREŚCI
Podrozdziały

Błędy w transmisji cyfrowej

W trakcie przesyłania sygnału przez ośrodek transmisyjny mogą pojawić się różne zakłócenia, które spowodują deformację sygnału. Zakłócenia wywoływane są na przykład przez wyładowania atmosferyczne, maszyny elektryczne, silniki spalinowe, promieniowanie kosmiczne oraz wiele innych czynników. Nie zawsze da się je wyeliminować. Jeśli zakłócony sygnał dotrze do odbiornika, to może być nieprawidłowo odczytany. W transmisji cyfrowej błąd (przekłamanie) polega na odczycie bitu o stanie przeciwnym w stosunku do nadanego:

nadano 1 ... odebrano 0
nadano 0 ... odebrano 1

Błąd może być pojedynczy lub seryjny - dotyczący grupy kolejnych bitów. Ochrona transmisji przed błędami polega na odpowiednim kodowaniu przesyłanej informacji. Aby zrozumieć problem, przyjrzyjmy się poniższemu schematowi:

Nadajnik wysyła informację cyfrową 1101 (cokolwiek by ona znaczyła). W trakcie przesyłu tej informacji przez kanał transmisyjny pojawia się zakłócenie, które powoduje, iż odbiornik odbiera informację 1001. Porównując informację nadaną i odebraną od razu zauważymy różnicę na drugiej pozycji, gdzie zamiast bitu 1 pojawił się bit 0. Doszło do przekłamania przesyłanej informacji. Ponieważ informacja nie była w żaden sposób zabezpieczona, to odbiornik nie ma pojęcia, iż odebrał dane z przekłamaniem. Przecież nadajnik mógł równie dobrze wysłać dane 1001.

Na początek:  podrozdziału   strony 

Dwukrotne przesyłanie informacji

Pierwszym narzucającym się rozwiązaniem tego problemu jest przesyłanie informacji dwukrotnie. Ponieważ odbiornik "wie", iż informacja odebrana podwójnie, powinna być taka sama, może ją sobie porównać. Na drugiej pozycji jest różnica. Teraz odbiornik wie już, iż odebrał dane z błędem. Kanałem zwrotnym może poprosić nadajnik o powtórzenie ostatniej transmisji danych.

Zwróć uwagę, iż w tym systemie nie wiemy, które z dwóch odebranych słówek jest poprawne, a które zawiera błąd. Sama różnica nie wystarcza do odtworzenia właściwej informacji. Dlatego taki kod nazywamy kodem wykrywającym błędy - kodem detekcyjnym (ang. EDC - Error Detection Code). Prawdopodobieństwo, iż błąd pojawi się w obu przekazach na tej samej pozycji (wtedy słówka będą oba błędne, ale takie same, co spowoduje ich akceptację przez odbiornik), jest naprawdę bardzo małe.

Na początek:  podrozdziału   strony 

Bit parzystości

W praktyce nikt o zdrowych zmysłach nie zgodziłby się na opisany powyżej system zabezpieczania transmisji przed błędami. Powodem jest dwukrotny spadek przepustowości (ilości przesyłanej informacji w jednostce czasu) kanału transmisyjnego - ponieważ każdą informację musimy przesyłać dwa razy. Jeśli błędy pojawiają się w kanale transmisyjnym bardzo rzadko, stosuje się bardziej oszczędny system kodowania przesyłanej informacji, zwany transmisją z bitem parzystości (ang. parity checking).

Polega to na tym, iż do przesyłanego słówka dodajemy jeden bit o takim stanie, aby liczba wszystkich bitów o stanie 1 w tak powiększonym słowie informacyjnym była parzysta (czyli podzielna przez 2). Załóżmy, iż przesyłamy słówka 4-bitowe. Poniżej przedstawiamy kilka przykładów rozszerzania takich słówek do 5-bitowych z bitem parzystości. Umówmy się, iż dodatkowy bit dodajemy na początku nowego słowa:

słówko
informacyjne
słówko
z bitem
parzystości
0000 00000
0001 10001
0011 00011
0110 00110
1011 11011
1110 11110
1111 01111

Co nam to dało? Otóż dużo. Odbiornik wie teraz, iż zawsze w odebranym słowie liczba bitów o stanie 1 powinna być parzysta. Może to sobie sprawdzić. Jeśli otrzyma liczbę nieparzystą, to znaczy, iż któryś z bitów został odebrany z przekłamaniem:

Wynika z tego, iż pojedynczy błąd powoduje utratę parzystości w odebranym słówku danych. Również nieparzysta liczba błędów (1,3,5,...) wywoła taką utratę parzystości. Natomiast błędy parzyste (na 2, 4, 6 ... bitach) przejdą niezauważone, ponieważ nie powodują one utraty parzystości (spróbuj to udowodnić). Ponieważ jednak system ten stosuje się w przypadku, gdy błędy pojawiają się bardzo rzadko, to możemy śmiało założyć, iż wystąpienie błędu podwójnego (parzystego) jest praktycznie niemożliwe.

Zabezpieczenie transmisji bitem parzystości jest już bardziej ekonomiczne od dwukrotnego przesyłania każdego słowa informacyjnego. Spadek szybkości transmisji jest tym mniejszy, im więcej bitów informacyjnym mają przesyłane słowa danych. Jednakże wtedy rośnie również prawdopodobieństwo błędów parzystych.

Na początek:  podrozdziału   strony 

Suma kontrolna

Kolejnym sposobem zabezpieczania transmisji przed błędami jest tzw. suma kontrolna (ang. checksum). Polega ona na tym, iż kolejno przesyłane porcje danych traktujemy jak liczby binarne. Sumujemy je ograniczając wynik do określonej liczby bitów (np. 8, 16, 32 lub 64). Otrzymaną w ten sposób sumę dołączamy na koniec przesłanego bloku informacji. Odbiornik również tworzy sumę kontrolną odbieranych danych. Następnie sprawdza swoją sumę z sumą odczytaną na końcu transmisji bloku danych. Jeśli sumy się różnią, to znaczy, iż w odebranym bloku wystąpił błąd.

Innym, bardzo podobnym sposobem, jest potraktowanie przesyłanych danych jako liczb ze znakiem. Otrzymaną sumę kontrolną neguje się arytmetycznie (wyznacza się wartość o przeciwnym znaku) i dołącza na końcu przesyłanego bloku danych. Odbiornik po prostu sumuje wszystkie odebrane dane, łącznie z sumą kontrolną. Jeśli w wyniku otrzyma wartość różną od zera, to znaczy, iż w odebranym bloku są błędy.

Poniższy program oblicza 8-bitową sumę kontrolną wg sposobu 2.

C++
// Prosta suma kontrolna
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>

using namespace std;

int main( )
{ 
    char s [ 129 ];

    cin.getline ( s,128 );

    signed char suma = 0;

    for( int i = 0; s [ i ]; i++ )
        suma += s [ i ];

    suma = -suma;

    cout << ( int ) suma << endl;

    return 0;
}
Wynik:
abc ABC
-12
 
ABC abc
-12
 
cba ACB
-12

Przyjrzyj się dokładnie wynikom działania programu dla różnych danych wejściowych. Otóż okazuje się, iż prosta suma kontrolna nie wykrywa zmiany kolejności danych. Nie wykryje również błędów polegających na zwiększeniu o pewną wartość jednego słówka kodowego a innego zmniejszeniu o tą samą wartość. Jeśli z transmisji znikną dane o wartości 0, to nie zostanie to wykryte! Także dodanie dowolnej ilości danych 0 nie zmieni sumy kontrolnej. Zatem suma kontrolna jest pewnym zabezpieczeniem transmisji przed błędami, lecz posiada wiele wad.

Na początek:  podrozdziału   strony 

Suma kontrolna Adler-32

Aby usunąć niedogodności zwykłej sumy kontrolnej, wymyślono wiele efektywnych algorytmów wyznaczania złożonych sum kontrolnych, które są czułe na wszelkie zmiany danych w zabezpieczanym bloku. Adler-32 jest jednym z algorytmów wyznaczania takiej złożonej sumy kontrolnej. Został on wymyślony przez Marka Adlera.

Algorytm Adler-32 polega na wyliczaniu dwóch sum kontrolnych, które nazwiemy A i B. Obie sumy są 16-bitowe. Suma A powstaje przez zsumowanie modulo 65521 danych w bloku - suma ma początkowo wartość 1. Suma B jest sumą modulo 65521 kolejnych wartości sumy A. Na końcu sumy A i B łączy się w jedną sumę kontrolną 32 bitową - B zajmuje starsze 16 bitów, A zajmuje młodsze.

Użyta do operacji modulo liczba 65521 jest największą liczbą pierwszą mniejszą od 216 = 65536.

Matematycznie rachunki wyglądają następująco:

D = {d1 d2 d3 ... dn-1 dn} - blok danych.
A1 = (1 + d1) mod 65521
B1 = (0 + A1) mod 65521 = (1 + d1) mod 65521

A2 = (A1  + d2) mod 65521 = (1 + d1 + d2) mod 65521
B2 = (B1 + A2) mod 65521 = ((1 + d1) + (1 + d1 + d2)) mod 65521

A3 = (A2 + d3) mod 65521 = (1 +  d1 + d2 + d3) mod 65521
B3 = (B2 + A3) mod 65521 = ((1 + d1) + (1 + d1 + d2) + (1 + d1 + d2 + d3)) mod 65521

...

An = (An-1 + dn) mod 65521 = (1 + d1 + d2 + d3 + ... + dn - 1 + dn) mod 65521
Bn = (Bn-1 + An) mod 65521 = ((1 + d1) + (1 + d1 + d2) + (1 + d1 + d2 + d3) + ... + (1 + d1 + d2 + d3 + ... + dn - 1)  + (1 + d1 + d2 + d3 + ... + dn - 1 + dn)) mod 65521
Bn = (nd1 + (n - 1)d2 + (n - 2)d3 + ... + 2dn - 1 + dn + n) mod 65521

Po wyznaczeniu końcowych sum kontrolnych An i Bn sumę Adler-32 tworzymy następująco:

SAdler-32 = 216 x Bn + An = 65536 x Bn + An.

Zamiast mnożenia możemy wykorzystać operację przesunięcia bitów Bn o 16 pozycji w lewo. Dodawanie można zrealizować za pomocą alternatywy bitowej. W efekcie otrzymujemy 32 bitową sumę kontrolną, która jest już czuła na:

  • zmiany danych
  • zmiany kolejności danych
  • dodanie zer lub usunięcie zer z bloku
  • dodanie tej samej wartości do jednej danej i odjęcie tej wartości od innej danej

Poniżej przedstawiamy prosty program wyliczający sumę kontrolną Adler-32:

C++
// Suma kontrolna Adler-32
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>

using namespace std;

int main( ) 
{ 
    char s [ 129 ];

    cin.getline ( s,128 );

  int A = 1;
  int B = 0;

  for( int i = 0; s [ i ]; i++ ) 
  { 
    A = ( A + ( unsigned ) s [ i ] ) % 65521;
    B = ( B + A ) % 65521;
  }

  unsigned int SAdler32 = ( B << 16 ) | A;

  cout << SAdler32 << endl;

  return 0;
}
Wynik:
abc ABC
150143501
 
ABC abc
124977677
 
cba ACB
150471181

W przypadku sumy kontrolnej Adler-32 dostajemy różne wartości przy przestawieniu danych. Zatem jest ona dużo lepsza od prostej sumy kontrolnej.

Na początek:  podrozdziału   strony 

Suma kontrolna Fletchera

Jest to bardzo podobny algorytm do sumy kontrolnej Adler-32. Różnica polega na zastąpieniu operacji modulo 65521 operacją modulo 65535 (jest to wartość 16-bitowa, w której wszystkie 16 bitów znajduje się w stanie 1). Sumy początkowe startują od wartości 65535.

Poniżej przedstawiamy przykładowy program wyliczający sumę kontrolną Fletchera.

C++
// Suma kontrolna Fletchera
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>

using namespace std;

int main( ) 
{ 
    char s [ 129 ];
    unsigned A = 65535, B = 65535;

    cin.getline ( s,128 );

    for( int i = 0; s [ i ]; i++ ) 
    { 
        A += ( unsigned ) s [ i ];
        B += A;
    }

    A %= 65535;
    B %= 65535;

    unsigned SFletcher = ( B << 16 ) | A;

    cout << SFletcher << endl;

    return 0;
}
Wynik:
abc ABC
149684748
 
ABC abc
124518924
 
cba ACB
150012428

Sumy kontrolne pozwalają zabezpieczyć transmisję przed ewentualnymi błędami. Odbiornik ma możliwość sprawdzenia, czy odebrał poprawne dane. Jeśli tak, przekazuje je komputerowi odbiorczemu. Jeśli nie, kanałem zwrotnym prosi nadajnik o powtórzenie ostatniego bloku danych. Wynika stąd, iż kody detekcyjne można stosować tylko w przypadku tzw. transmisji z potwierdzeniem.

Jeśli nie można powtórzyć transmisji informacji (np. olbrzymia odległość przekazu - próbniki kosmiczne) lub nic to nie daje (np. uszkodzony nośnik CD), stosowanie kodów detekcyjnych nie ma większego sensu - w takich przypadkach stosuje się bardziej zaawansowaną ochronę transmisji, czyli kody korekcyjne (ang. ECC - Error Correction Code), które nie tylko wykrywają błędy w odebranym przekazie, ale często potrafią je naprawić. Kody takie opisujemy w kolejnym rozdziale.

Nie wyczerpaliśmy tematyki kodów detekcyjnych. Zainteresowanym czytelnikom proponujemy poszukanie w Internecie informacji o cyklicznej kontroli nadmiarowości (ang. CRC - Cyclic Redundancy Check). Dział ten pominęliśmy z uwagi na zaawansowaną matematykę binarną (wyznaczanie reszty z dzielenia przez wielomiany), która jest wykorzystywana. Kody CRC wymagają w sumie nowego artykułu i wykraczają znacznie poza program szkoły średniej.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.