Temat: Algorytm kodowania informacji z korekcją błędów

I. Błędy transmisji

Błędy transmisji są faktem. Mimo 40-letniej walki z błędami w istniejących instalacjach telefonicznych błędy transmisji nadal występują i będą występować w ciągu najbliższych kilkudziesięciu lat. W kolejnych punktach spojrzymy na pewne problemy nieco dokładniej i zobaczymy, co można zrobić, aby je przezwyciężyć.

1. Natura błędów transmisji

Powodem błędów w transmisji w liniach telefonicznych są różnorakie zjawiska. Jednym ze zjawisk, które zawsze występuje jest szum termiczny. Elektrony w przewodach miedzianych poruszają się szybko powodując szum tła o szerokim paśmie. Stosunek sygnału do szumu jest to tzw. wynik Shannona.

Głównym źródłem szumu przy transmisji danych jest szum impulsowy. Impulsy lub piki w linii maja typowy czas trwania 10 ms. Dla ludzkiego ucha takie impulsy wydają się podobne do słabych trzasków. Powodem większości z nich jest iskrzenie przekaźników i innych elektromechanicznych elementów w starszych centralach komutacyjnych. Błyskawice, nieudolność osób naprawiających telefony, zakłócenia spowodowane zapłonem w samochodach, zakłócenia w liniach zasilania i tony sygnalizacyjne systemu telefonicznego również mają swój udział w tym szumie.

Innym głównym źródłem błędów jest fakt, że amplituda, szybkość propagacji i faza sygnałów są zależne od częstotliwości. System telefoniczny, jak wynika z analizy Fouriera wszystkich sygnałów, wypacza każdy element częstotliwości oddzielnie i następnie łączy je razem na końcu. Zwykle jest możliwe dzierżawienie specjalnie doprowadzanych linii, w którym przedsiębiorstwo telekomunikacyjne stara się zmniejszyć te efekty do minimum, ale takie linie są bardzo kosztowne, a kompensacja błędów nie jest nigdy doskonała. Istnieje również wiele innych źródeł błędów. Miedzy dwoma przewodami fizycznie przyległym mogą wystąpić przesłuchy. W łączach mikrofalowych występują zaniki fal których przyczyną mogą być np. ptaki. Dla transmisji akustycznej pożądana jest kompresja amplitudy sygnału w wąskim zakresie, ponieważ wzmacniacze nie są liniowe w szerokim zakresie. Ta kompresja może wprowadzać błędy. I wreszcie nie jest możliwe wytwarzanie doskonalej fali nośnej. Jej amplituda, częstotliwość i faza będą zawsze nieco odbiegały od ideału. W łączach PCM błędy powstają przy każdej utracie synchronizacji odbiornika z nadajnikiem. Zwykle odzyskanie synchronizacji zajmuje kilkadziesiąt milisekund, ale wszystkie dane nadawane w tym czasie trafiają do złego miejsca przeznaczenia. W wyniku procesów fizycznych powodujących zakłócenia, błędy występują raczej seryjnie niż pojedynczo. Występowanie błędów seryjnych ma zarówno zalety, jak i wady, w stosunku do pojedynczych błędów jednobitowych. Zalety błędów seryjnych widoczne są przy przesyłaniu danych miedzy komputerami. Dane komputerowe zawsze nadaje się blokami bitów. Załóżmy, że wielkość bloku wynosi 1000 bitów, a częstość błędów wynosi 0,001 na bit. Jeżeli błędy byłyby niezależne, większość bloków zawierałaby błąd. Jeżeli błędy pojawią się seryjnie, np. po 100, wtedy wystąpią one przeciętnie w jednym lub dwu blokach na 100. Wadą błędów seryjnych jest to, że dużo trudniej jest je wykryć i poprawić niż błędy wyizolowane. Ponieważ błędy powstają w wyniku różnorodnych procesów fizycznych, można poznać ich rozkład jedynie doświadczalnie. W latach 1969 -1970, przedsiębiorstwo AT&T wykonało badania błędów transmisji w liniach krótkich, średnich i długich przy różnych szybkościach transmisji (Fleming, Hutchison, 1971, Bulkovic i in. 1911). Wykryto na przykład, że przy szybkości 15 znaków/s, z jednym bitem startu, ośmioma bitami danych i jednym bitem stopu, jeden znak na 6850 był niepoprawny. Co gorsza na 1467 znaków jeden był tracony zupełnie. Jednakże 1% wywołań zawierał 90% lub więcej błędów. Inaczej mówiąc, jakość linii jest bardzo nierówna.

Jeżeli średnia częstość błędów wynosi e na znak i blok zawiera n znaków, to przy braku grupowania błędów prawdopodobieństwo tego, że blok jest przesłany dokładnie wynosi (1-e)ⁿ. Prawdopodobieństwo tego, że blok jest błędny jest równe l-(l-e)ⁿ. Jeżeli e<<l, to stosując rozwinięcie dwumianowe otrzymuje się przybliżone prawdopodobieństwo bloku wynoszące en. Dane doświadczalne dają jednak prawdopodobieństwo bloku w przybliżeniu równe 10^-4n^0,8 dla bloków zawierających n 8-bitowych bajtów, bez bitów startu i stopu. Wyniki różnią się w zależności od długości linii, szybkości transmisji i innych czynników, tak że jest to właściwie tylko rząd oszacowanej wielkości. Badania wykonane przez europejskie PTT dały podobne wyniki.

2. Kody korekcyjne

Projektanci sieci opracowali dwie podstawowe strategie dotyczące błędów. Jeden sposób polega na włączeniu dostatecznego nadmiaru informacji wraz z każdym nadanym blokiem danych, aby umożliwić odbiornikowi wydedukowanie przesyłanego znaku. Drugi sposób polega na włączeniu dostatecznego nadmiaru pozwalającego odbiornikowi tylko wykryć że błąd wystąpił. W takiej sytuacji może on żądać powtórzenia transmisji. Przy pierwszym sposobie używa się kodów korekcyjnych, a przy drugim kodów detekcyjnych.

Aby zrozumieć jak można wykrywać i poprawiać błędy, należy zrozumieć, czym rzeczywiście jest błąd. Zwykle wiadomość składa się z m bitów wiadomości (tj. dane użyteczne) i r bitów nadmiarowych lub kontrolnych. Niech ogólna długość wiadomość wynosi n (tj. n = m+r) N-bitową jednostkę zawierającą dane i bity kontrolne często nazywa się ciągiem kodowym.

Dane są dowolne dwa ciągi kodowe, powiedzmy 10001001 i 10110001. Możliwe jest określenie na ilu odpowiadających sobie pozycjach one się różnią. W tym przypadku różnią się trzema bitami. Aby określić iloma bitami różnią się dwa ciągi kodowe, obliczamy funkcje XOR (różnica symetryczna) dla tych ciągów i zliczamy liczbę jedynek w wyniku. Liczba pozycji bitowych, na których dwa ciągi kodowe różnią się od siebie, nazywa się odległością Hamminga (Hamming distance). Oznacza to, że jeśli dwa ciągi kodowe są w odległości Hamminga równej d, to do zamienienia jednego ciągu w drugi będzie wymagane wystąpienie d błędów jednobitowych (Hamming 1950 r).

W większości zastosowań transmisji danych wszystkie 2^m możliwych wiadomości jest legalnych, ale ze względu na sposób obliczania bitów kontrolnych nie stosuje się wszystkich 2ⁿ możliwych ciągów kodowych. Dla danego algorytmu obliczania bitów kontrolnych można skonstruować kompletną listę legalnych ciągów kodowych i w tej liście znaleźć dwa ciągi kodowe, których odległość Hamminga jest minimalna. Ta odległość jest nazywana odległością Hamminga całego kodu.

Właściwości detekcyjne i korekcyjne kodu zależą od jego odległości Hamminga. Do wykrycia d błędów, potrzebujemy kodu o odległości d+1 ponieważ przy takim kodzie d jednobitowych błędów nie można zamienić poprawnego ciągu kodowego w inny poprawny ciąg kodowy. Odbiornik widząc jakiś niepoprawny ciąg kodowy może stwierdzić, że wystąpił błąd transmisji. Podobnie do poprawiania d błędów, potrzebujemy kodu o odległości 2d+1 dlatego, że legalne ciągi kodowe są tak bardzo oddalone od siebie, że nawet przy d zmianach pierwotny ciąg kodowy znajduje się w mniejszej odległości od błędnego ciągu niż jakikolwiek inny ciąg kodowy. Z tego względu możemy jednoznacznie określić ciąg pierwotny.

Jako prosty przykład kodu detekcyjnego rozważamy kod, w którym do danych jest dodany jeden bit parzystości. Bit parzystości jest tak wybrany, aby liczba jedynek w ciągu kodowym była parzystą

( lub nieparzystą ). Taki kod ma odległość 2, ponieważ dowolny jednobitowy błąd wytwarza ciąg kodowy z błędną parzystością. Można go używać do wykrywania pojedynczych błędów.

Jako prosty przykład kodu korekcyjnego, rozważmy kod tylko z czterema następującymi poprawnymi ciągami kodowymi:

0000000000, 0000011111, 1111100000, 1111111111.

Kod ten ma odległość 5, co oznacza, że może on poprawiać błędy podwójnie. Jeżeli pojawi się ciąg kodowy 0000000111, odbiornik wie, że oryginalny ciąg musiał być 0000011111. Jeżeli jednak potrójny błąd zamieni 0000000000 w 0000000111, błąd nie będzie poprawiony właściwie.

Wyobraźmy sobie, że chcemy skonstruować kod z m bitami wiadomości i r bitami kontrolnymi, który pozwoli na poprawianie wszystkich błędów pojedynczych. Każda z 2^m legalnych wiadomości ma n nielegalnych ciągów kodowych w odległości 1 od siebie. Są one tworzone przez systematyczne zamienianie każdego z n bitów w n-bitowym ciągu kodowym utworzonym z kodu. W ten sposób 2ⁿ legalnych wiadomości wymaga n+1 ciągów kodowych. Ponieważ ogólna liczba ciągów kodowych wynosi 2ⁿ, musi być spełniony warunek (n+1)2^m<=2ⁿ. Podstawiając n = m+r, otrzymujemy (m+r+1)<=2^r. Dla danego m daje to dolne ograniczenie liczby bitów kontrolnych potrzebnych do poprawiania pojedynczych błędów. To teoretyczne dolne ograniczenie można faktycznie osiągnąć przy zastosowaniu metody Hamminga (1950). Bity ciągu kodowego są ponumerowane kolejno od bitu 1 z lewej strony. Bity których numery są potęgą 2 (1, 2, 4, 8, 16 itd.) są bitami kontrolnymi. Pozostałe bity (3, 5, 6, 7, 9 itd.) są wartościami m bitów danych. Każdy bit kontrolny wymusza parzystość pewnego zbioru bitów obejmującego również ten bit kontrolny, tak aby liczba bitów 1 była parzysta (lub nieparzysta). Bit wiadomości maże występować w kilku zbiorach, dla których oblicza się bity parzystości. Aby zobaczyć, które bity kontrolne kontrolują bit danych na pozycji k, zapiszmy k jako sumę potęg 2. Na przykład, 11=1+2+8, a 29 = 1+4+8+16. Bit danych jest więc kontrolowany przez bity kontrolne występujące w takim rozwinięciu (np. bity 1, 2 i 8 kontrolują bit jedenasty).

Kiedy pojawi się ciąg kodowy, wówczas odbiornik ustawia licznik na zero. Następnie sprawdza czy każdy bit kontrolny k (k = 1. 2, 4, 8...) uzyskują poprawną parzystość określonego zbioru bitów. Jeżeli nie, dodaje k do licznika. Jeżeli licznik jest równy zero po sprawdzeniu wszystkich bitów kontrolnych (tj. jeżeli wszystkie były poprawne), przyjmuje się, że ciąg kodowy jest poprawny. Jeżeli licznik jest niezerowy, zawiera on numer niepoprawnego bitu. Jeżeli np. bity kontrolne 1, 2 i 8 dają błąd, to zamienionym bitem był bit 11, ponieważ jest jedynym bitem kontrolowanym przez bity 1, 2 i 8. Pamiętajmy, że dane znajdują się na miejscach bitów 3, 5, 6, 7, 9, 10, 11.

Kody Hamminga mogą poprawiać tylko pojedyncze błędy. Jednak istnieje pewna sztuczka, którą można zastosować umożliwiając kodom Hamminga poprawianie błędów seryjnych. Sekwencje k kolejnych ciągów kodowych można przedstawić w postaci macierzy umieszczając po jednym ciągu kodowym w rzędzie. Zwykle dane nadaje się ciągami kodowymi od strony lewej do prawej. W celu poprawiania błędów seryjnych dane należy nadawać kolumnami, rozpoczynając od kolumny leżącej najbardziej po lewej stronie. Po nadaniu wszystkich k bitów kolumny, nadaje się drugą kolumnę itd. Kiedy wiadomość pojawia się w odbiorniku, wówczas macierz jest rekonstruowana kolumnami. Jeżeli wystąpił błąd seryjny o długości k błędów, to jeden bit w każdym z k ciągów kodowych będzie zmieniony. Kod Hamminga może jednak poprawiać jeden błąd w ciągu kodowym, tak więc cały blok można odtworzyć. W metodzie tej używa się kr bitów kontrolnych do tworzenia bloków o km bitów danych. Bloki te są odporne na pojedyncze błędy seryjne o długości k lub mniejszej.

3. Kody detekcyjne.

Kody korekcyjne są czasami stosowane w transmisji danych, na przykład wówczas, kiedy kanał jest simpleksowy i nic można żądać retransmisji. Wykrywanie błędów poprzedzając retransmisje ma jednak więcej zwolenników, ponieważ jest bardziej efektywne. Jako prosty przykład rozważmy kanał, w którym błędy są izolowane i częstość błędu wynosi 10^-6 na bit. Niech wielkość bloku wynosi 1000 bitów. Dla zapewnienia korekcji błędów 1000 bitowych bloków jest potrzebnych 10 bitów kontrolnych, megabit danych wymagałby 10 000 bitów kontrolnych. Do wykrycia błędnego bloku wystarczy tylko jeden bit parzystości na blok. Na każde 1000 bloków trzeba nadać dodatkowy blok (1001 bitów). Ogólny koszt metody wykrywania błędów i retransmisji wynosi jedynie 1001 bitów na megabit danych, natomiast 10 000 bitów przy kodzie Hamminga.

Przy dodaniu pojedynczego bitu parzystości do bloku, jeżeli blok jest zniekształcony przez długi blok seryjny, prawdopodobieństwo wykrycia błędu wyniesie tylko 0,5, co jest właściwie nie do przyjęcia. Wartość tę można jednak znacznie poprawić traktując każdy nadawany blok jako macierz prostokątną o n bitach szerokości i k bitach wysokości. Bit parzystości jest obliczany oddzielnie dla każdej kolumny i dołączany do macierzy jako ostatni rząd. Macierz jest wtedy nadawana rzędami. Kiedy pojawia się blok, wówczas odbiornik sprawdza wszystkie bity parzystości. Jeżeli któryś z nich jest zły, żąda retransmisji bloku.

Metodą tą można wykrywać pojedynczy blok seryjny o długości n błędów, ponieważ tylko 1 bit na kolumnę będzie zmieniony. Jednakże błąd seryjny o długości n+l przejdzie nie wykryty, jeżeli pierwszy i ostatni bit będą zmienione, a wszystkie pozostałe zostaną poprawne.

(Błąd seryjny nie implikuje, że wszystkie bity są złe, a tylko to, że conajmniej pierwszy i ostatni są złe). Jeżeli blok jest zniekształcony przez jeden długi lub wiele krótkich błędów seryjnych, to prawdopodobieństwo tego, że dowolna z n kolumn będzie przez przypadek miała poprawną parzystość wynosi 0,5, tak więc prawdopodobieństwo tego, że niepoprawny blok będzie przyjęty, kiedy nie powinien być, wynosi 2^-n.

Pomimo że powyższa metoda może być czasami wystarczająca w praktyce powszechnie stosuje się inną metodę - kod wielomianowy - nazywany również nadmiarowym kodem cyklicznym lub kodem CRC. Kody wielomianowe traktują łańcuchy bitów jak wielomiany ze współczynnikami 0 lub 1. Wiadomość k-bitowa jest traktowana jak lista współczynników wielomianu z k członami o zakresie od x^k-1 do x⁰. Mówimy, że taki wielomian jest stopnia k-l. Najwyższy (najbardziej z lewej strony) bit jest współczynnikiem przy x^k-1, następny bit jest współczynnikiem przy x^k-2 itd. Na przykład 110001 ma 6 bitów i w ten sposób reprezentuje sześć członów wielomianu ze współczynnikami 1, 1, 0, 0, 0 i l: x⁵+x⁴+x⁰. Zgodnie z prawami teorii pola w arytmetyce wielomianów stosuje się operacje modulo 1. Nie istnieją przeniesienia przy dodawaniu i pożyczki przy odejmowaniu. Zarówno dodawanie, jak i odejmowanie, są identyczne z funkcją XOR. Na przykład:

1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1

[phone] + 1 1 0 0 1 1 0 1 -1 0 1 0 0 1 1 0 - 1 0 1 0 1 1 1 1

0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0

Długie dzielenie jest wykonywane tak samo jak binarne, z wyjątkiem tego, że odejmowanie jest wykonywane modulo 2, jak powyżej. Mówimy że dzielnik ,,przechodzi w dzielną", jeżeli dzielna ma tyle samo bitów co dzielnik. Przy stosowaniu metody kodu wielomianowego nadajnik i odbiornik muszą wcześniej uzgodnić wielomian generujący, G(x). Zarówno najstarszy, jak i najmłodszy bit wielomianu generującego musi być 1. Do obliczania sumy kontrolnej pewnej wiadomości z m bitami, wiadomość odpowiadająca wielomianowi M(s) musi być dłuższa niż wielomian. Podstawową zasadą jest dodawanie sumy kontrolnej na końcu wiadomości w taki sposób, żeby wielomian reprezentujący wiadomość: z sumą kontrolną był podzielony przez G(s). Kiedy odbiornik uzyska wiadomość z sumą kontrolną, próbuje ją dzielić przez G(s). Jeżeli w wyniku tego dzielenia pojawia się reszta, to znaczy że wystąpił błąd transmisji.

Algorytm obliczania sumy kontrolnej jest następujący:

(1) Niech r będzie stopniem wielomianu G(x). Dodaj r bitów zerowych do mniej znaczącego końca wiadomości, tak żeby zawierała obecnie m+r bitów i odpowiadała wielomianowi x' M(x).

(2) Podziel łańcuch bitów odpowiadający wielomianowi G(x) przez łańcuch bitów odpowiadający x'M(x) stosując dzielenie modulo 2.

(3) Odejmij resztę ( która ma zawsze r lub mniej bitów) od łańcucha bitów odpowiadających x’M(x) stosując odejmowanie modulo 2. Wynik jest wiadomością z sumą kontrolną, która ma być nadana. Nazwijmy ten łańcuch wielomianem T(x).

Na rysunku pokazano obliczanie sumy kontrolnej dla wiadomości 1101011011 i wielomianu G(z) = x⁴+x+1.

Oczywiście T(s) jest podzielne (modulo 2) przez G(x). W dowolnym dzieleniu, jeżeli zmniejszysz dzielnik o resztę, to co pozostanie jest podzielne przez dzielnik. Przy podstawie 10, jeżeli np. dzielimy 210278 przez 10941, to resztą jest 2399. Odejmując 2399 od 210278 otrzymamy 207879, która to wartość jest podzielna bez reszty przez 10941.

Obecnie przeanalizujemy moc tej metody. Jakie rodzaje błędów będą wykrywane? Wyobraźmy sobie, że pojawił się błąd transmisji, tak że zamiast wielomianu T(x) otrzymamy wielomian T(x)+E(x). Każdy bit 1 w wielomianie E(x) odpowiada jakiemuś bitowi wiadomości, który został zamieniony. Jeżeli istnieje k bitów 1 w E(x) to wystąpiło k jednobitowych błędów. Pojedynczy błąd seryjny charakteryzuje się początkową jedynką, mieszaniną zer i jedynek i końcową 1, wszystkie pozostałe bity są 0.

Po odebraniu wiadomości z sumą kontrolną, odbiornik dzieli ją przez G (x), to znaczy oblicza T(x)+E(x)/G(x). Wartość T(x)/G(x) jest zawsze 0, tak że wynik obliczenia jest po prostu E(x)/G(x). Te błędy,

które odpowiadają wielomianom zawierającym czynnik G(x) przejdą niezauważone, ale pozostałe błędy będą wykryte. Jeżeli istnieje jednobitowy błąd, to E(x)=xⁱ gdzie i określa, który bit jest błędny. Jeżeli G(x) zawiera dwa człony lub więcej, nie nastąpi dzielenie E(x), tak więc wszystkie jednobitowe błędy będą wykryte.

Jeżeli istnieją dwa oddzielne jednobitowe błędy, E(x)=xⁱ+x^j, gdzie i>j. Alternatywnie można to zapisać jako E(x)=x^j(x^i-j+1). Jeżeli założymy, że G(x) nie jest podzielne przez x, warunkiem dostatecznym do wykrycia wszystkich podwójnych błędów jest, żeby wielomian G(x) nie dzielił x^k+1 dla każdego k, aż do maksymalnej wartości i-j (tj. aż do maksymalnej długości wiadomości). Znane są proste wielomiany niskiego stopnia dające zabezpieczenie długim wiadomościom. Na przykład x¹⁵+x¹⁴+1 nie podzieli x^k+1 dla żadnego k poniżej 32768.

Jeżeli istnieje nieparzysta liczba błędnych bitów, to E(x) zawiera nieparzystą liczbę członów (np. x⁵+x²+1,ale nie x²+1). Ciekawe, że nie istnieje wielomian z nieparzystą liczbą członów, który ma czynnik x+l w systemie modulo 2. Przez uwzględnienie x+1 jako czynnika G(x) możemy wyłapać wszystkie błędy składające się z nieparzystej liczby zamienionych bitów.

Wiadomość: 1 1 0 1 0 1 1 0 1 1

Generator: 1 0 0 1 1

Wiadomość po dodaniu: 1 1 0 1 0 1 1 0 1 1 0 0 0 0

4 bitów zerowych

1 1 0 0 0 0 1 0 1 0

10011 1 1 0 1 0 1 1 0 1 1 0 0 0 0

1 0 0 1 1

1 0 0 1 1

1 0 0 1 1

0 0 0 0 1

0 0 0 0 0

0 0 0 1 0

0 0 0 0 0

0 0 1 0 1

0 0 0 0 0

0 1 0 1 1

0 0 0 0 0

1 0 1 1 0

1 0 0 1 1

0 1 0 1 0

0 0 0 0 0

1 0 1 0 0

1 0 0 1 1

0 1 1 1 0

0 0 0 0 0

1 1 1 0

Wiadomość nadana :1 1 0 1 0 1 1 0 1 1 1 1 1 0

Rys. Obliczanie sumy kontrolnej kodu wielomianowego.

Aby stwierdzić, że żaden wielomian z nieparzystą liczba członów nie jest podzielny przez x+1, załóżmy, że E(x) ma nieparzystą liczbę członów i jest podzielny przez x+1. Przedstawmy czynnik E(x) jako (x+1)Q(x). Obecnie oszacujmy E (1)=(1+1)Q(x). Ponieważ 1+1=0 (modulo 2), E(1) musi być zero. Jeżeli E(x) ma nieparzystą liczbę członów, to zawsze podstawiając wszędzie 1 za x otrzymamy w wyniku 1. W ten sposób żaden wielomian z nieparzystą liczbą członów nie jest podzielny przez x+1.

W końcu najważniejsze, kod wielomianowy z r bitami kontrolnymi będzie wykrywał wszystkie błędy seryjne o długości mniejszej lub równej r. Błąd seryjny o długości k można przedstawić jako xⁱ(x^k-1+..+1), gdzie i określa jak blisko prawej strony odebranej wiadomości znajduje się błąd seryjny. Jeżeli G(x) zawiera człon x⁰, nie będzie miał xⁱ jako czynnika, tak że jeżeli stopień wyrażenia w nawiasach będzie mniejszy niż stopień G(x), reszta nigdy nie wyniesie zero.

Jeżeli długość błędu seryjnego wynosi r+1, to reszta z dzielenia przez G(x) będzie zerem wtedy i tylko wtedy, gdy błąd seryjny jest identyczny z G(x). Zgodnie z definicją błędu seryjnego pierwszy i ostatni bit muszą być 1, tak więc równość błędu seryjnego i wielomianu G(x) zależy od r-1 bitów pośrednich. Jeżeli traktujemy wszystkie kombinacje jako tak samo prawdopodobne, to prawdopodobieństwo odebrania niepoprawnej wiadomości jako poprawnej wynosi 1/2^r-1.

Można również wykazać, że jeżeli pojawi się błąd seryjny o długości większej niż r+l bitów lub wystąpi kilka krótszych błędów seryjnych, prawdopodobieństwo nie zauważenia przyjścia błędnej wiadomości wynosi 1/2^r, przy założeniu, że wszystkie ciągi kodowe są tak samo prawdopodobne.

Poniższe trzy wielomiany przyjęto jako standardy międzynarodowe:

CRC -12 =x¹²+x¹¹+x³+x²+x¹+1

CRC-16> = x¹⁶+x¹⁵+x²+1

CRC-CCITT = x¹⁶+x¹²+x⁵+1

Wszystkie one zawierają x+l jako podstawowy czynnik. CRC-12 stosu je się wówczas, kiedy długość znaku wynosi 6 bitów. Pozostałe są stosowane dla znaków 8-bitowych. 16-bitowa suma kontrolna, taka jak CRC-16 lub CRC-CCITT, wyłapuje wszystkie pojedyncze i podwójne błędy, wszystkie błędy z nieparzystą liczbą bitów, wszystkie błędy seryjne o długości 16 lub mniej, 99,997% błędów seryjnych l7-bitowych i 99,990% błędów seryjnych 18-bitowych i dłuższych.

Pomimo że obliczanie sumy kontrolnej może wydawać się skomplikowane, Peterson i Brown (1961) wykazali, że można skonstruować prosty układ rejestru przesuwnego do obliczania i sprawdzania sum kontrolnych w sposób układowy. W praktyce prawie zawsze stosuje się ten układ.

II. Podsumowanie

Prawa natury nakładają dwa podstawowe ograniczenia na szybkość przesyłania danych w kanale. Ograniczenia Nyquista limituje liczbę niezależnych próbek na sekundę do dwukrotnej szerokości pasma, nie ogranicza jednak dokładności tych próbek, ani ogólnej szybkości przesyłania danych. Ograniczenie Shannona przeciwnie, limituje ogólną szybkość przesyłania danych do wielkości zależnej od szerokości pasma i stosunku sygnału

do szumu.

System telefoniczny zawiera trzy główne elementy: łącza abonenckie, centrale i międzycentralowe łącza transmisyjne. Łącza abonenckie są dwuprzewodowymi, dedykowanymi kanałami o częstotliwości 3000 Hz, podczas gdy międzycentralowe łącza są to szerokopasmowe kable koncentryczne, kanały mikrofalowe, falowodowe, światłowody lub kanały satelitarne, w których można zwielokrotnić wiele kanałów akustycznych.

Dotychczas w łączach sygnały analogowe były przenoszone z zastosowaniem zwielokrotniania przez podział częstotliwości, istnieje jednak ogólna tendencja do stosowania komunikacji cyfrowej i zwielokrotniania sygnału przez podział czasu.

W sieciach komputerowych stosuje się komutację łączy, komutację pakietów lub połączenie obu technik. Przy komutacji łączy dla użytkownika na czas trwania połączenia wydziela się kanał od źródła do miejsca przeznaczenia. X.21 jest miedzynarodowym standardowym sprzęgiem dla sieci z komutacją łączy. Przy komutacji pakietów nie ma wydzielonego łącza, natomiast wszystkie bloki danych są zapamiętywane w każdej pośredniej centrali komutacyjnej i następnie wysyłane do kolejnej centrali wzdłuż drogi przesyłania ich do miejsca przeznaczenia.

Terminale można przyłączać do sieci przez multiplekser lub koncentrator, aby zmniejszyć liczbę potrzebnych linii komunikacyjnych. Multiplekser ma przepustowość wyjścia równą sumie przepustowości jego

wejść. Koncentrator ma mniejszą przepustowość wyjścia niż przepustowość wejść i wykorzystuje się w nim fakt, że nie wszystkie linie wejściowe są zajęte przez cały czas.

W liniach transmisyjnych często występują ostre impulsy nietermiczne powodujące błędy seryjne. Błędy te można korygować stosując kody korekcyjne, jakkolwiek w praktyce najczęściej po prostu wykrywa się błędy i ponownie przesyła złe bloki.