Podręcznik

Kodowanie nadmiarowe nazywane też kodowaniem korekcyjnym ma na celu wykrywanie (detekcję) błędów lub wykrywanie i usuwanie (korekcja) błędów w przesyłanym strumieniu bitów. Kodowanie nadmiarowe nie jest operacją wykonywaną na transmitowanym sygnale, lecz na strumieniu bitów, które mają być przesłane. Najogólniej można powiedzieć, że do przesyłanego strumienia bitów dodaje się dodatkowe bity, które służą detekowaniu i korygowaniu błędów binarnych. Dodawanie bitów zmniejsza efektywną szybkość transmisji. Liczba dodawanych bitów oraz ich struktura logiczna zależy od zastosowanego kodu nadmiarowego. W uproszczeniu można powiedzieć, że im więcej bitów możemy dodać, tym większa jest skuteczność kodu. Pojawia się pytanie:  na ile możemy zwiększać skuteczność kodu nadmiarowego kosztem zmniejszania efektywnej szybkości transmisji? Idealny kod to taki, którego zastosowanie pozwala uniknąć jakichkolwiek błędów binarnych, i który nie zmniejsza szybkości transmisji w stosunku do wartości maksymalnej określonej za pomocą twierdzenia Shannon’a. Oczywiście takiego kodu nie ma. Chcąc ocenić skuteczność użytego kodu, albo porównać różne kody między sobą posługujemy się pojęciem zysku kodowego. Najwygodniej pojęcie to zdefiniować graficznie, co zostało zaprezentowane na rysunku 1.20. Zysk kodowy wiąże stosunek SNR w kanale transmisyjnym z jakością transmisji określoną za pomocą bitowej stopy błędów BER (Bit Error Ratio) definiowanej następująco:

Dla zadanej bitowej stopy błędów jest to różnica między wymaganą minimalną wartością stosunku SNR w przypadku braku kodowania nadmiarowego i z kodowaniem nadmiarowym. Najczęściej różnicę tą podaje się w [dB] w odniesieniu do stosunku energii E_b przypadającej na jeden bit do gęstości widmowej mocy gaussowskiego szumu białego N₀.

Rys. 1.20. Ilustracja graficzna zysku kodowego

Zdefiniujmy teraz dwa podstawowe parametry kodu nadmiarowego: minimalną odległość Hamminga i współczynnik kodu. Minimalna odległość Hamminga to najmniejsza różnica między dwoma kodowanymi słowami (sekwencjami), rozumiana jako sumaryczna liczba pozycji o różnej wartości logicznej bitów. Na przykład dla dwóch  sekwencji 1001010 i 1101011 różnica jest na pozycjach 2 i 7, zatem odległość Hamminga wynosi 2.  Minimalna odległość Hamminga dmin dla całego zbioru słów kodowych decyduje o możliwościach detekowania i korygowania błędów. I tak, niezależnie od kodu nadmiarowego minimalna liczba wykrywanych błędów  e_min wynosi:

a minimalna liczba wykrywanych i korygowanych błędów cmin wynosi:

Współczynnik kodu R to stosunek:

gdzie: k – liczba bitów sekwencji kodowanej, n – liczba bitów sekwencji po zakodowaniu. 
Im mniejszy jest współczynnik kodu tym więcej jest bitów nadmiarowych, i tym większa przepustowość kanału transmisyjnego jest wymagana. 

Istnieje wiele kodów nadmiarowych. Najogólniej można je podzielić na kody systematyczne i niesystematyczne. W słowie kodowym kodu systematycznego bity informacyjne (sekwencja kodowana) nie są zmieniane, a słowo kodowe powstaje przez dodanie do nich pewnej liczby bitów, tak zwanych kontrolnych. Inaczej jest w przypadku kodów niesystematycznych, w słowie kodowym nie da się wyróżnić sekwencji kodowanej i bitów kontrolnych. Najogólniej kody nadmiarowe dzieli się na kody blokowe i splotowe. W przypadku blokowych kodów nadmiarowych kodowany strumień bitów jest dzielony na jednakowo liczne bloki i każdy blok jest kodowany niezależnie od pozostałych. W kodach splotowych jest inaczej, słowo kodowe zależy nie tylko od kodowanej informacji, ale również od pewnej liczby poprzedzających słów kodowych.

Kody parzystości
Najprostszym kodem blokowym i zarazem systematycznym jest kod oparty na sumowaniu modulo 2 liczby jedynek w kodowanej porcji informacji (w bloku). Wynikiem takiej operacji jest 1 (liczba jedynek nieparzysta) lub 0 (liczba jedynek parzysta). Wynik ten jest dodawany do bloku. Kody tak działające są nazywane kodami parzystości. Nie umożliwiają one korygowania błędów, a nawet wykrywania błędów, jeżeli ich liczba w bloku jest parzysta.  Powszechnie stosowanym kodem tego typu jest kod ASCII, a także kody BIP-N (Binary Interleaved Parity) – bitowej kontroli parzystości, w którym N oznacza liczbę bloków, na które dzielona jest przesyłana informacja. Dla każdego bloku oblicza się bit kontroli parzystości, ale nie jest on, tak jak w kodzie ASCII dopisywany do każdego bloku, lecz tworzy jedną N-bitową sekwencję parzystości.  

Cykliczne kody nadmiarowe 
Cykliczne kody nadmiarowe CRC (Cyclic Redundancy Check) są kodami blokowymi. Podobnie jak kody z kontrolą parzystości są one powszechnie stosowane we współczesnej telekomunikacji i teleinformatyce.  
Pozwalają one skutecznej niż kody z kontrolą parzystości wykrywać błędy w przesyłanym bloku bitów. Blok n bitów, które mają być przesłane może być kodowany na kilka sposobów. W każdym z nich blok bitów, oznaczmy je następująco: $a_{n-1},a_{n-2},...,a_1,a_0$ , jest zastępowany wielomianem o współczynnikach   przyjmujących takie wartości jak kolejne bity bloku (0 albo 1). Wielomian  ten ma następującą postać:

i jest nazywany wielomianem wiadomości. Z kodem cyklicznym jest związany, tak zwany wielomian generatora G(x). Wielomian ten ma ogólnie następującą postać:

Stopień wielomianu generatora i wartości współczynników   zależą od konkretnego zastosowania.
Kody cykliczne dzielą się na kody systematyczne i niesystematyczne. W przypadku kodu niesystematycznego wielomian kodowy   powstaje w wyniku pomnożenia wielomianu wiadomości przez wielomian generatora. Współczynniki tak otrzymanego wielomianu są odpowiednimi bitami ciągu kodowego.

W przypadku kodowania systematycznego zamiast mnożenia wykonuje się dzielenie wielomianu $A(x)\cdot x^r$ przez wielomian generatora stopnia r. W wyniku dzielenia otrzymujemy wielomian stopnia  n-i  oraz wielomian R(x) będący resztą z dzielenia:

Przykład 1.13
Przykład dzielenia modulo 2 wielomianów:
(x5⊕x³⊕x²)x³⊕x2)=x²⊕x
x⁵⊕x⁴
x⁴⊕x³⊕x²
x⁴⊕x³
  x²          -   reszta z dzielenia

Do kodowanego bloku bitów dopisuje się resztę z dzielenia wielomianów. Chcą sprawdzić poprawność wiadomości wykonuje się identyczną operację dzielenia i sprawdza się, czy otrzymana bity reszty są takie same jak dopisane przy tworzeniu słowa kodowego.
Przedstawione kody cykliczne pozwalają jedynie wykrywać błędy, ale nie dają możliwości ich usuwania.  Są jednak kody cykliczne, których użycie pozwala nie tylko wykrywać, ale i usuwać błędy. Warto tu wspomnieć o kodzie Reed’a-Solomon’a. Jest to kod bajtowy, a nie bitowy, a zatem wykrywa się błędne bajty i ewentualnie je koryguje.

Kody splotowe
Dotychczas zajmowaliśmy się kodami blokowymi. Kodowanie informacji zawartej w bloku jest niezależne od postaci wiadomości w blokach poprzedzających i następujących po kodowanym bloku. Inaczej jest w kodach splotowych. W tych kodach historia kodowania ma znaczenie. W najprostszym przypadku może ona dotyczyć dwóch ostatnich bitów wiadomości. Kodowanie następującego po nich bitu zależy od tego  jakie były te dwa wcześniejsze bity, a dokładniej jak je kodowano. 

Rys.1.21. Schemat przykładowego kodera splotowego

Na rysunku 1.21 pokazano schemat blokowy przykładowego kodera splotowego. W jego skład wchodzą dwa sumatory modulo 2 i dwa jednobitowe rejestry przesuwne (Rp1 i Rp2). Każdemu bitowi podawanemu na wejście kodera odpowiadają dwa bity otrzymywane w różny sposób, stąd na schemacie widnieje przełącznik. Współczynnik  kodu, którego schemat pokazano na rysunku 1.21 wynosi ½. W czasie trwania jednego taktu pracy kodera najpierw są wyznaczane dwa bity wyjściowe, a następnie bit wejściowy jest wpisywany do rejestru pierwszego Rp1, a bit z tego rejestru jest wpisywany do rejestru drugiego Rp2. Pracę kodera splotowego często ilustruje się za pomocą struktury kratowej. Dla najprostszego kodera struktura taka jest pokazana na rysunku 1.22. Stan rejestrów przesuwnych w każdej poziomej linii jest taki sam. Pojawienie się w danym stanie rejestru przesuwnego zera oznacza konieczność wyboru drogi górnej, albo prawej, a bitu o wartości logicznej 1 wyboru drogi dolnej, albo lewej. Należy zauważyć, że działanie kodera w pełni opisuje uproszczona struktura, ze względu na jej  powtarzalność, poczynając od trzeciego taktu – ogólnie od M-tego taktu, gdzie M oznacza liczbę rejestrów przesuwnych (patrz rysunek 1.22).

Rys.1.22. Struktura kratowa kodera splotowego pokazanego na rys.1.21

Modulacje kodowe  
Okazuje się, że zysk kodowy może być jeszcze większy, gdy połączy się kodowanie splotowe z modulacją cyfrową, w porównaniu z zastosowaniem tylko modulacji cyfrowej. Takie techniki kodowania są nazywane modulacjami kodowymi TCM (Trellis Coded Modulation). Idea modulacji kodowej sprowadza się do równoczesnego użycia kodu splotowego i modulacji cyfrowej. Na rysunku 1.23 pokazany jest ogólny schemat kodera TCM.  J bitów kodowanych jest podawanych na wejście kodera splotowego, a pozostałe K nie. Liczba bitów wyjściowych z kodera splotowego jest o jeden większa niż liczba bitów wejściowych. Bity te służą do wyboru stanu rejestrów przesuwnych, a pozostałe bity do wyboru jednej z dwóch równoległych dróg przejścia.   
Rozważmy działanie kodera TCM, gdy koder splotowy składa się z dwóch rejestrów przesuwnych (rysunek 1.22), a modulacją jest modulacja QAM-8. Na rysunku 1.24 pokazano strukturę kratową kodera z modulacją QAM-8. W tym przypadku na wyjściu kodera mamy trzy bity y_i , y_i+1 oraz y_i+2  zależne od pary bitów wejściowych  x_i oraz x_i +1.  Na przykład, jeżeli koder splotowy jest w stanie 01 (w rejestrze Rp1 jest 0, a w rejestrze Rp2 bit 1)  i  na  wejściu  kodera  splotowego pojawia się bit x_i = 0 to na jego wyjściu mielibyśmy bity y_i =1 oraz y_i +1 = 1. Ponieważ bit x_i +1 = 0 to do sekwencji 11 dopisana jest 0 (y_i +3 =0), co z kolei odpowiada punktowi 110 z konstelacji QAM-8. Ze stanu 01 następuje przejście do stanu 00. Zwróćmy uwagę, że przypisanie do punktów konstelacji sekwencji trzybitowych musi być takie by odległości między punktami dla dwóch linii równoległych były jak największe.    

Rys.1.23. Ogólny schemat blokowy kodera TCM

Rys.1.24. Krata kodera TCM, dla kodera splotowego pokazanego na rys.1.21 i modulacji QAM-8Rys.1.24.

Punkty konstelacji QAM-8 zaznaczono kolorami. Takie same kolory mają prostokąty, w których zamieszczone są wyjściowe sekwencje bitów. Przypisanie sekwencji bitów punktowi z konstelacji nie jest przypadkowe. Wybrano je tak by odległości między punktami tego samego koloru były możliwie duże. W takim przypadku ryzyko popełnienia błędu po stronie dekodera jest zminimalizowane.