Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

Zabezpieczanie transmisji przed błędami

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:

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 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)2010 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;
}

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 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:

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.

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:

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

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ść:

b₄b₃b₂b₁ = 1011

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

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:

Aby wyznaczyć kolejne pozycje kontrolne x₄, x₂ i x₁, 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:

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

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.

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:

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:

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.

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. Podobnie postępuje się w przypadku filmów DVD.

Obraz telewizyjny składa się z linii obrazowych wyświetlanych kolejno na ekranie kineskopu. Treść poszczególnych linii jest zapisana cyfrowo na płycie DVD. Jeśli w wyniku błędów nośnika nie daje się odtworzyć jednej lub kilku sąsiednich linii, to odtwarzacz DVD po prostu kopiuje w ich miejsce ostatnią dobrze odebraną linię obrazową. Uzyskany efekt jest zwykle niewidoczny lub mniej irytujący niż w przypadku błędnego wyświetlenia uszkodzonego fragmentu obrazu.

---

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