Informatyka dla klas III

Transmisja cyfrowa

Transmisja cyfrowa polega na przesyłaniu informacji w postaci bitów pomiędzy dwoma urządzeniami cyfrowymi, np. komputerami. W rozdziale tym opiszemy podstawowe idee transmisji cyfrowej. Zaczniemy od budowy toru transmisyjnego.

Tor transmisyjny

Zadaniem toru transmisyjnego jest przesłanie informacji binarnej od komputera nadawczego do komputera odbiorczego. Typowy tor transmisji danych cyfrowych składa się z następujących elementów:

 

obrazek

 

Komputer nadawczy przekazuje informację do przesłania modemowi nadawczemu. Modem jest specjalnym urządzeniem, które informację cyfrową w postaci bitów zamienia na odpowiedni dla danego ośrodka sygnał (falę radiową, prąd elektryczny, światło lasera itp). Sygnał przenosi się (propaguje) przez ośrodek transmisyjny (przestrzeń, przewód elektryczny, światłowód itp). Po drugiej stronie toru transmisyjnego sygnał dociera do modemu odbiorczego. Modem odbiorczy odczytuje sygnał i, odpowiednio go interpretując, wydobywa z niego informację cyfrową, którą nadał modem odbiorczy. Wydobyta informacja jest przekazywana do komputera odbiorczego. Kanał transmisyjny posiada zwykle łączność w obu kierunkach. Kanałem zwrotnym komputer odbiorczy może przekazywać potwierdzenie odbioru danych - tzw. transmisja z potwierdzeniem (ang. hand shaking transmission).

 

obrazek

 

Nazwa MODEM pochodzi od nazw MODULATOR i DEMODULATOR. Modulator jest układem wewnątrz modemu, który odpowiednio kształtuje (moduluje) sygnał wysyłany do ośrodka w zależności od przesyłanej informacji cyfrowej. Sygnał ten nazywamy sygnałem nośnym (ang. carrier). Demodulator wykonuje zadanie odwrotne - odebrany z ośrodka sygnał przekształca (demoduluje) z powrotem w informację cyfrową dla komputera odbiorczego.

 

Modulacja sygnału

Słowo modulacja (ang. modulation) oznacza kształtowanie różnych parametrów sygnału propagującego się przez ośrodek za pomocą informacji cyfrowej, którą ten sygnał ma przenieść. Sygnał najczęściej ma formę zbliżoną do kształtu sinusoidy (wykres funkcji f(x) = sin(x)) i jest sygnałem okresowym (czyli takim, który powtarza się po określonym czasie). Fala sinusoidalna jest bardzo rozpowszechnionym rodzajem fali w przyrodzie. Jeśli wrzucisz do spokojnego stawu kamień, to powstałe, rozchodzące się fale będą właśnie falami sinusoidalnymi. Zobaczmy jakie parametry fali sinusoidalnej można modulować (kształtować):

 

obrazek

 

Fala sinusoidalna zmienia się w czasie odchylając się w górę i w dół od położenia naturalnego. Wartość maksymalnego odchylenia od położenia równowagi nazywamy amplitudą sygnału i oznaczamy literką A:

 

f(t) = Asin(wt)

 

Drugim istotnym parametrem sygnału sinusoidalnego jest okres T. Jest to czas, po upływie którego fala zaczyna się powtarzać - przyjmuje te same wartości wychylenia. Okres mierzymy w sekundach. Bezpośrednio z okresem związana jest częstotliwość fali, czyli liczba okresów w ciągu jednej sekundy - oznaczana literką f. Pomiędzy okresem T a częstotliwością f  zachodzi prosty związek:

f =   1 
T

Jednostką częstotliwości jest Hz (Herz - od nazwiska niemieckiego pioniera techniki radiowej, Heinricha Rudolfa Herza). Np. fala, o okresie 0,2 sekundy ma częstotliwość 5 Hz, ponieważ w jednej sekundzie mieści się jej pięć okresów. Wyższe jednostki częstotliwości to:

 

1 kHz = 1000 Hz = 1000 okresów w ciągu jednej sekundy
1 MHz = 1000 kHz = 1.000.000 Hz
1 GHz = 1000 MHz = 1.000.000 kHz = 1.000.000.000 Hz

 

Trzecim parametrem jest przesunięcie fazowe f. Sygnał przesunięty fazowo posiada taką samą amplitudę oraz okres, lecz w stosunku do sygnału nie przesuniętego przyjmuje wartości wychylenia z pewnym opóźnieniem. Miarą przesunięcia fazowego jest kąt w radianach.

Mamy zatem trzy różne parametry sygnału, które można modulować:

  • amplitudę - modulacja amplitudy - AM (ang. Amplitude Modulation)
  • częstotliwość - modulacja częstotliwości - FM (ang. Frequency Modulation)
  • fazę - modulacja fazy - PM (ang. Phase Modulation)

Sygnał zmodulowany jednym z powyższych sposobów przenosił będzie informację cyfrową, czyli bity. Transmisja pojedynczych bitów jest transmisją szeregową. Dla każdego bitu przewidziany jest pewien krótki czas transmisji zwany oknem transmisji bitu (ang. bit transmit window) lub ramką bitu (ang. bit transmit frame). Bity są przesyłane jeden po drugim.

 

Modulacja Amplitudy - AM

W modulacji amplitudy kształtujemy amplitudę sygnału w zależności od przesyłanego bitu 0 lub 1. Umówmy się, iż bit 0 będzie reprezentowany sygnałem o małej amplitudzie, a bit 1 będzie reprezentowany sygnałem o amplitudzie dużej.

 

obrazek

 

Amplitudy dla bitu 0 i 1 muszą być tak dobrane, aby łatwo dały się odróżnić od siebie po stronie odbiorczej toru transmisyjnego.

Modem odbiera od komputera nadawczego informację cyfrową w postaci bitów. Wykorzystując stany bitów modem nadawczy moduluje odpowiednio amplitudę sygnału nośnego i wysyła go do ośrodka transmisyjnego. Poniżej przedstawiamy w dużym uproszczeniu przykładowy kształt sygnału zmodulowanego amplitudowo dla informacji binarnej 11010100.

 

obrazek

 

Transmisja z modulacją amplitudy jest mało odporna na zakłócenia. Przez zakłócenie rozumiemy obcy sygnał, który losowo pojawia się w kanale transmisyjnym i oddziałuje na sygnał nadawany. Zakłócenia powstają z różnych powodów - wyładowania atmosferyczne, praca różnych urządzeń elektrycznych, iskrzenia styków, promieniowanie kosmiczne tp. Sygnał zakłócający dodaje się do sygnału nadawanego zmieniając w ten sposób kształt fali.

 

obrazek

 

Na powyższym przykładzie sygnał zakłócający (niebieski) spowodował taką zmianę sygnału nadawanego, iż nastąpiło przekłamanie jednego bitu, zaznaczonego pod wykresem na czerwono.

 

Modulacja Częstotliwości - FM

W modulacji częstotliwości kształtujemy częstotliwość sygnału (długość okresu). W oknie bitu 0 częstotliwość jest niska, w oknie bitu 1 częstotliwość jest wysoka.

 

obrazek

 

Częstotliwości dla bitu 0 i dla bitu 1 muszą być tak dobrane, aby bez problemu można było odróżnić od siebie te dwa sygnały. Na powyższym rysunku częstotliwość dla 1 jest dwa razy wyższa od częstotliwości dla 0. W praktyce stosunki tych częstotliwości są inne (ze względu na tzw. harmoniczne, czyli fale pochodne o częstotliwościach będących wielokrotnościami częstotliwości fali podstawowej), ale zasada pozostaje taka sama.

 

obrazek

 

Powyżej widzimy kształt sygnału zmodulowanego częstotliwościowo dla danych binarnych 11010100. Ponieważ amplituda sygnału nie niesie informacji, zakłócenia amplitudowe do pewnego stopnia nie wpływają na przekazywaną informację. Dlatego modulacja FM jest dużo bardziej odporna na zakłócenia niż modulacja AM.

 

Modulacja Fazy - PM

W modulacji fazy kształtujemy przesunięcie fazowe. Umówmy się, iż dla bitu 0 przesunięcie wynosi 0 radianów, a dla bitu 1 przesunięcie wynosi  p radianów (o takim sygnale mówimy, iż posiada fazę przeciwną).

 

obrazek

 

Poniżej przedstawiamy przebieg sygnału zmodulowanego fazowo dla danych binarnych 11010100. Zwróć uwagę, iż zmiana fazy występuje wtedy, gdy kolejne bity zmieniają swój stan np. z 1 na 0 lub z 0 na 1. Zamiast wykrywania przesunięć fazowych można jedynie wykrywać zmianę fazy (co jest dużo prostsze) i odpowiednio zmieniać stan odbieranych bitów.

 

obrazek

 

Transmisja PM jest bardzo odporna na zakłócenia.

Aby zwiększyć przepustowość kanału transmisyjnego często łączy się ze sobą kilka modulacji (np. AM i FM). W ten sposób można zwielokrotnić postać sygnału, a co za tym idzie w oknie bitowym przesyłać nie pojedynczy bit lecz kilka bitów. Dla przykładu zademonstrujemy taką modulację AM/FM. Naraz będą przesyłane dwa bity wg schematu:

 

obrazek

 

Sygnał modulujemy amplitudowo i częstotliwościowo wg dwóch bitów danych. Poniżej przedstawiamy przykładowy kształt sygnału dla danych binarnych 11010100. Zwróć uwagę, iż informację tą przesyłamy w dwa razy krótszym czasie niż w przypadku modulacji prostej. Zwielokrotniliśmy przepustowość kanału transmisyjnego.

 

obrazek

 


Pokazane sposoby modulacji nie wyczerpują wszystkich stosowanych w praktyce metod kształtowania sygnału. Naszym celem było jedynie naszkicowanie problemów transmisji cyfrowej i sposobów ich rozwiązania.

Szybkość transmisji cyfrowej wyraża się w jednostkach zwanych bodami (ang.baud rate):

 

1 bod = 1 bit w ciągu jednej sekundy

 

Większe jednostki to

 

1 kilo bod = 1000 bitów / sekundę
1 mega bod = 1000 kilo bodów = 1.000.000 bodów

 

Kody detekcyjne

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ą 1011 (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 przedostatniej 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ł wysłać dane 1001.

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 przedostatniej 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.

 

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:

  • Jeśli błąd transmisji wywołał zmianę stanu bitu z 0 na 1, to w odebranym słowie otrzymamy o jeden więcej bitów 1. Skoro nadano parzystą liczbę bitów 1, to w wyniku otrzymamy liczbę nieparzystą. Np. nadano 11110, odebrano 11111. Ilość jedynek jest nieparzysta.

  • Jeśli z kolei błąd spowodował zmianę stanu bitu z 1 na 0, to w odebranym słowie będzie o 1 mniej bitów 1, czyli także otrzymamy liczbę nieparzystą. Np. nadano 01111, odebrano 01011. Ilość jedynek jest nieparzysta.

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 prawie 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.

 

Poniższy program wyznacza bit parzystości dla danej 8-mio bitowej.

 

// Bit parzystości
// (C)2015 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned v,m,lj;

    cin >> v;

    lj = 0;

    for(m = 0x80; m; m >>= 1)
        if(v & m)
        {
          cout << 1;
          lj++;  
        }
        else cout << 0;

    cout << " " << (lj & 1) << endl;

    return 0;
}

 

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.

 

// Prosta suma kontrolna
// (C)2015 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;
}
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.

 

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:

 

// Suma kontrolna Adler-32
// (C)2015 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;
}
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.

 

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.

 

// Suma kontrolna Fletchera
// (C)2015 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;
}
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ć.

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.

 

Kody korekcyjne

Kod korekcyjny (ang. ECC - Error Correction Code) ma za zadanie odtworzenie, naprawę informacji w przypadku wystąpienia błędu (lub błędów) spowodowanych zakłóceniami sygnału w kanale transmisyjnym. Kody ECC stosujemy zwykle tam, gdzie:

  • powtórzenie transmisji jest niemożliwe, np. odbiornik nie ma łączności z nadajnikiem. Jako przykład można podać nadajniki strumieniowe (telewizja cyfrowa, radio cyfrowe). Jeśli wystąpią zakłócenia dla pewnej grupy odbiorników, to będą one musiały same poradzić sobie z tym problemem.
  • powtórzenie transmisji jest utrudnione, np. komunikacja z próbnikiem kosmicznym znajdującym się w dużej odległości od Ziemi. Teoretycznie transmisję można powtórzyć, lecz może to trwać kilka godzin i nie ma pewności, iż powtórzony przekaz będzie bezbłędny z uwagi na częste zakłócenia - promieniowanie słoneczne i kosmiczne..
  • powtórzenie transmisji nie usuwa błędu, np. zarysowany nośnik CD lub DVD. Powtórne odtworzenie ścieżki nic nie daje, ponieważ zawsze wystąpi ubytek odczytanych danych.

Potrójne przesyłanie danych

Najprymitywniejszym kodem ECC jest po prostu trzykrotne przesyłanie każdego bitu danych. Jeśli w trakcie transmisji nastąpi przekłamanie jednego bitu, to dwa pozostałe pozwolą odtworzyć właściwy bit danych.

 

Nadajnik   Kanał
transmisyjny
  Odbiornik
1 ... 111 ... 011 ... 011 1
0 ... 000 ... 001 ... 001 → 0
1 ... 111 ... 101 ... 1011
1 ... 111 ... 110 ... 110 → 1


 

W powyższym przykładzie występuje błąd w trakcie każdej transmisji trójek bitów. Dlatego po stronie odbiornika odebrane trójki zawierają różne bity. Za bit nadany odbiornik przyjmuje bit powtarzający się najczęściej. Oczywiście system ten zawiedzie, gdy przekłamane zostaną dwa bity w trójce.
 

Kod Hamminga

Potrójne przesyłanie danych nie jest stosowane w praktyce - przepustowość kanału transmisyjnego spada trzykrotnie, na co nikt nie mógłby sobie pozwolić ze względów ekonomicznych. Jeśli błędy pojawiają się rzadko w kanale transmisyjnym, to przesyłaną informację można zabezpieczyć kodem Hamminga. Kod ten, wynaleziony przez Richarda Hamminga w 1950 roku, pozwala naprawić pojedyncze przekłamania bitów w odebranym słowie binarnym. Poniżej przedstawiamy konstrukcję słówek kodu Hamminga dla wiadomości 4-bitowych.

Na początek będzie nam potrzebna tablica liczb binarnych o wartościach od 0 do 7:

 

dziesiętnie binarnie
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

 

Słówko danych składa się z 4 bitów b4b3b2b1. Bity te umieszczamy w słówku kodu Hamminga w sposób następujący:

 

Numer pozycji : 7 6 5 4 3 2 1
Słowo kodu Hamminga: b4 b3 b2 x4 b1 x2 x1


 

Pozycje o numerach będących kolejnymi potęgami liczby 2 (1, 2, 4, 8, 16, ...) są tzw. pozycjami kontrolnymi. Oznaczyliśmy je literką x. Pozycje kontrolne musimy obliczyć na podstawie słowa danych. Zróbmy to na konkretnym przykładzie. Niech nasze słowo informacyjne ma wartość:

 

b4b3b2b1 = 1011

 

Bity informacyjne wpisujemy na odpowiednie pozycje w słowie kodu Hamminga:

 

Numer pozycji : 7 6 5 4 3 2 1
Słowo kodu Hamminga: 1 0 1 x4 1 x2 x1

 

Zapiszmy wszystkie numery pozycji, na których występują bity o stanie 1. Są to pozycje 7, 5 i 3. Wykorzystując tabelkę konwersji dziesiętno-dwójkowej zapiszmy wyznaczone numery pozycji binarnie: 7 = 111, 5 = 101 i 3 = 011. Teraz otrzymane liczby binarne wpisujemy do poniższej tabelki:

 

x4 x2 x1
1 1 1
1 0 1
0 1 1

 

Aby wyznaczyć kolejne pozycje kontrolne x4, x2 i x1, pionowo w kolumnach uzupełniamy bity bitem parzystości (w danej kolumnie liczba bitów 1 musi być parzysta). Otrzymane w ten sposób bity parzystości są wartościami dla pozycji kontrolnych:

 

x4 x2 x1
1 1 1
1 0 1
0 1 1
0 0 1

 

 Bity parzystości kolumn przepisujemy do odpowiednich pozycji kontrolnych w słowie kodowym Hamminga:

 

Numer pozycji : 7 6 5 4 3 2 1
Słowo kodu Hamminga: 1 0 1 0 1 0 1

 

Gotowe, utworzyliśmy słowo kodu Hamminga dla danej informacji: 1011 → 1010101.


Przesyłamy wyznaczone powyżej słowo kodu Hamminga 1010101 przez kanał transmisyjny. Występuje przekłamanie na pozycji nr 6 i w efekcie odbiornik odbiera słowo 1110101.

 

Numer pozycji : 7 6 5 4 3 2 1
Odebrane słowo kodu Hamminga: 1 1 1 0 1 0 1

 

Odbiornik wyznacza pozycje wszystkich bitów 1 w odebranym słowie: 7, 6, 5, 3 i 1. Numery pozycji przekształca na kod binarny zgodnie z podaną wcześniej tabelą konwersji: 7 = 111, 6 = 110, 5 = 101, 3 = 011 i 1 = 001. Binarne numery pozycji odbiornik umieszcza w tabeli i każdą kolumnę uzupełnia bitem parzystości:

 

7 1 1 1
6 1 1 0
5 1 0 1
3 0 1 1
1 0 0 1
bit parzystości 1 1 0

 

Otrzymaliśmy wartość 110. Wg tabeli konwersji jest to liczba 6, która oznacza pozycję w słowie kodowym Hamminga, na której wystąpiło przekłamanie. Ponieważ przekłamanie w transmisji cyfrowej polega na odebraniu bitu o stanie przeciwnym do nadanego, zatem wystarczy zanegować (zmienić stan na przeciwny) bit na pozycji 6, aby otrzymać nadane słowo Hamminga:

 

Numer pozycji : 7 6 5 4 3 2 1
Naprawione słowo kodu Hamminga: 1 0 1 0 1 0 1

 

Teraz usuwamy bity kontrolne i otrzymujemy informację nadaną: 1011. Jeśli w trakcie transmisji błąd nie wystąpi, to odbiornik otrzyma w wyniku dekodowania pozycję 000 = 0. W takim przypadku usuwa jedynie bity kontrolne.


Poniższy program tworzy kody Hamminga dla 8-bitowych słówek b8b7b6b5b4b3b2b1. W przypadku słówek 8-bitowych słówko kodowe Hamminga posiada 4 pozycje kontrolne x8, x4, x2 i x1:

 

Numer pozycji : 12 11 10 9 8 7 6 5 4 3 2 1
Słowo kodu Hamminga: b8 b7 b6 b5 x8 b4 b3 b2 x4 b1 x2 x1

 

Słówka informacyjne wprowadzamy do programu w postaci ciągu zer i jedynek.
 
// Kodowanie Hamminga
// (C)2015 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    char s[10];
    int  h,w,x,mw,mh,i;

    cout << "        dane = ";
    cin.getline(s,9);

// odczytane słówko przekształcamy na wartość

    for(w = i = 0; (s[i]) && ((s[i] == '0') || (s[i] == '1')); i++)
        w = w + w + (s[i] == '1');

// bity w umieszczamy na odpowiednich pozycjach h
// i wyznaczamy bity kontrolne x

    x = h = 0;

    for(i = 12, mh = 0x800, mw = 0x80; mw; mh >>= 1, mw >>= 1, i--)
    {
        if((mh == 0x80) || (mh == 0x08))
        {
            mh >>= 1;
            i--;
        }

        if(w & mw)
        {
            h |= mh;
            x ^= i;
        }
    }

// bity kontrolne x wstawiamy na odpowiednie pozycje w h

    for(mh = 0x80, mw = 0x8; mw; mw >>= 1)
    {
         if(x & mw) h |= mh;
         switch(mh)
         {
             case 0x80 : mh = 0x08; break;
             case 0x08 : mh = 0x02; break;
             case 0x02 : mh = 0x01; break;
         }
    }

// wyświetlamy gotowe słówko kodu Hamminga

    cout << "kod Hamminga = ";

    for(mh = 0x800; mh; mh >>= 1) cout << ((h & mh) ? "1" : "0");

    cout << endl;

    return 0;
}
        dane = 11001110
kod Hamminga = 110001110011

 


Podane w tym artykule informacje nie wyczerpują zagadnienia kodów korekcyjnych. Zainteresowanych tym tematem czytelników odsyłamy do źródeł w Internecie dotyczących kodów Golay'a, Reeda-Mullera i Reeda-Salomona. Wymagają one zaawansowanej arytmetyki binarnej, wykraczającej poza zakres materiału dla szkoły średniej i dlatego zostały tutaj pominięte. Z drugiej strony kody te są stosowane w popularnym sprzęcie Audio-CD oraz DVD do korekcji błędów odczytu z nośników cyfrowych. Kody ECC Reeda-Salomona pozwalają odtworzyć informację przy wystąpieniu tzw. błędów seryjnych, czyli ciągu kolejnych przekłamanych bitów (powstających np. przy zarysowaniu nośnika CD/DVD). Dzięki nim odtwarzarki CD i DVD mogą poprawnie odczytywać zarysowane i poplamione płyty cyfrowe (oczywiście tylko do pewnego stopnia). Inteligentne urządzenia odtwarzające nawet radzą sobie w sytuacji, gdy fragment danych jest niemożliwy do odtworzenia. W takim przypadku, aby zapobiec nieuniknionym trzaskom w odtwarzanym nagraniu, w miejsce uszkodzonego fragmentu utworu wstawiany jest fragment bezpośrednio poprzedzający uszkodzenie. Niewprawne ucho nawet nie zauważy tego oszustwa w odtwarzanym utworze muzycznym.

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe