POLITECHNIKA POZNAŃSKA

Instytut Elektroniki i Telekomunikacji

LABORATORIUM

TEORIA KODÓW

BADANIE DZIAŁANIA I JAKOŚCI KODERÓW

I DEKODERÓW

LINIOWYCH KODÓW BLOKOWYCH

I

KODÓW CYKLICZNYCH

Poznań, 2003

1.     WPROWADZENIE

1.1  Wiadomości ogólne

W celu zabezpieczenia danych przed przekłamaniami powstającymi w trakcie przesyłania ich w kanale telekomunikacyjnym stosuje się kodowanie kanałowe. Strumień bitów generowany przez dyskretne źródło wprowadza się na wejście kodera kanałowego, który dodaje bity nadmiarowe wedle określonego algorytmu. W odbiorniku dekoder kanałowy wykorzystuje bity nadmiarowe do detekcji lub/i korekcji błędów.

W ogólności system z kodowaniem można przedstawić w postaci poniższego schematu blokowego:

Rys. 1 Schemat blokowy systemu transmisyjnego z kodowaniem kanałowym.

Kody badane na ćwiczeniach są kodami liniowymi. Oznacza to, że dodatnie dwóch słów kodowych za pomocą sumy modulo-2 generuje trzecie słowo kodowe. Podstawowymi dwoma parametrami opisującymi kod jest długości słowa kodowego n oraz ilość bitów informacyjnych k zawartych w tym słowie. Pozostałe n-k bity są nadmiarowymi bitami zwanymi bitami kontroli parzystości. Jeśli bity informacyjne występują w słowie kodowym w sposób jawny, w nie zmienionej formie, to taki kod nazywa się kodem systematycznym. Z tymi parametrami ściśle związana jest stopa kodu będąca bezwymiarowym współczynnikiem określonym wzorem:

Z punktu widzenia szybkości przesyłania bitów informacyjnych wskazane jest, aby stopa kodu była możliwie największa. Z punktu widzenia jakości kodowania lepsza jest sytuacja gdy stopa kodu jest możliwie najmniejsza.

              Z zastosowaniem kodowania kanałowego wiąże się uzyskanie zysku kodowania, które wskazuje różnicę (w dB stosunku sygnału do szumu) między systemem z kodowaniem i systemem bez kodowania. Ponieważ dla różnych wartości SNR lub różnica ta jest inna, definiuje się asymptotyczny zysk kodowania dla :

gdzie t oznacza ilość błędów które dany kod może poprawić.

1.2  Kody blokowe

Kody blokowe są kodami których struktura słowa zorganizowana jest z sposób blokowy tzn. bity parzystości tworzą jeden blok i bity informacyjne tworzą drugi blok, tak jak na rys. 2.

Bity informacyjne

Bity parzystości

                                                  Rys. 2 Struktura słowa kodu blokowego

Pierwszym podstawowym równaniem opisującym działanie kodu blokowego liniowego jest równanie generujące:

gdzie:

m – jest wektorem wiadomości zawierającym k bitów informacyjnych. Oznacza to, że możliwych jest binarnych wektorów wiadmości.

c – jest wektorem zawierającym wszystkie n bitów słowa kodowego.

G – jest macierzą generującą o rozmiarach k x n.

Macierz generującą definiuje się jako:

gdzie:

- jest jednostkową macierzą identyczności o rozmiarach k x k.

P – jest macierzą współczynników o rozmiarach k x (n-k) o postaci:

Współczynnik = 1 jeśli i-ty bit parzystości zależy od j-tego bitu informacyjnego, w przeciwnym przypadku =  0. Współczynniki te dobiera się w taki sposób, aby wiersze macierzy generującej były liniowo niezależne oraz, aby równania parzystości były jednoznaczne.

              Dla liniowego kodu blokowego możliwe jest inne przestawienie zależności bitów parzystości od bitów informacyjnych. Sposobem tym jest przedstawienie macierzy kontroli parzystości zdefiniowanej jako:

Macierz kontroli parzystości ma rozmiary (n-k) x n. Macierz ta związana jest z macierzą generująca w następujący sposób:

Ponieważ wszystkie operacje arytmetyczne wykonywane są modulo-2 ostatecznie otrzymujemy:

Układ równań zdefiniowany powyższym równaniem nosi nazwę równań kontroli parzystości i jest drugim podstawowym równaniem opisującym działanie liniowego kodu blokowego.

              Macierz generującą stosuje się w nadajniku do operacji kodowania, natomiast macierz kontroli parzystości stosuje się w odbiorniku do operacji dekodowania. W celu zdekodowania odebranego bloku r należy pomnożyć go przez transponowaną macierz H. Odebrany blok r jest sumą nadanego słowa kodowego c oraz wektora błędów e. W wyniku operacji mnożenia r i H otrzymuje się wektor syndromu błędu s o długości n-k. Jak łatwo wykazać syndrom zależy jedynie od rozkładu błędów, a nie od wysłanego słowa kodowego. Syndrom zawiera informację o rozkładzie błędów i może być zastosowany do ich detekcji.

              Dla każdego liniowego kodu blokowego można określić minimalną odległość będącą najmniejszą odległością z sensie Hamminga między jakimikolwiek wektorami kodu. Odległość Hamminga między wektorami jest liczbą pozycji na których wektory te się różnią. Znając minimalną odległość kodu możliwe jest wyznaczenie ile błędów będzie mógł ten kod skorygować. Zależność dana jest wzorem:

Odległość minimalna powiązana jest również z macierzą kontroli parzystości i na jej podstawie może być wyznaczona. Odległość minimalna jest bowiem zdefiniowana przez minimalną liczbę wierszy macierzy , których suma jest równa wektorowi zerowemu.

              Dla każdego liniowego kodu blokowego można wyznaczyć kod dualny. Kod dualny uzyskuje się przez wykorzystanie macierzy H jako macierzy generującej i macierzy G jako macierzy kontroli parzystości. Nowy kod ma wówczas parametry (n,n-k).

1.3 Kody cykliczne

              Ważną podklasą liniowych kodów blokowych są kody cykliczne. Aby kod był cykliczny musi spełniać dwie właściwości:

·         Właściwość liniowości, która była omówiona przy opisie kodów blokowych

·         Właściwość cykliczności oznaczająca, że każde cykliczne przesunięcie słowa kodowego tworzy nowe słowo kodowe.

Właściwość cykliczności oznacza, że jeśli wektor jest słowem kodowym, to wektory:

są również słowami kodowymi.

              Wygodną metodą przedstawienia kodów cyklicznych jest metoda wielomianowa. Słowo kodowe c, jak również wektor wiadomości m można przedstawić w postaci wielomianu:

Każda potęga wielkości X w wielomianie c(X) reprezentuje przesunięcie w czasie o jeden  bit. Oznacza to, że pomnożenie wielomianu c(X) przez X odpowiada przesunięciu w prawo.

Cykliczność kodu w notacji wielomianowej przedstawia się następująco:

Jeśli c(X) jest wielomianem kodowym, to wielomian:

jest również wielomianem kodowym dla każdego i-tego przesuwu cyklicznego. W równaniu tym zastosowane jest mnożenie modulo- z warunkiem .

              Dla kodów cyklicznych w notacji wielomianowej definiuje się wielomian generujący postaci:

Wielomian ten jest wielomianem rzędu n-k , jest czynnikiem wielomianu i jest dla kodu wielomianem najmniejszego rzędu. Kod cykliczny jest jednoznacznie określony przez wielomian generujący g(X).

              Procedura kodowania w kodzie cyklicznym (n,k) przy użyciu wielomianu generującego przedstawia się następująco:

·         Pomnóż wielomian wiadomości m(X) przez .

·         Podziel otrzymany wielomian przez wielomian generujący otrzymując resztę b(X).

·         Dodaj otrzymaną resztę do otrzymując wielomian kodu c(X).

Kod cykliczny można również jednoznacznie określić przez wielomian rzędu k zwany wielomianem kontroli parzystości h(X):

W wielomianowym opisie kodów wielomian kontroli parzystości jest odpowiednikiem macierzy kontroli parzystości w opisie macierzowym. Podobnie wielomian generujący jest odpowiednikiem macierzy generującej.  W opisie wielomianowym można określić również odpowiednik macierzowego układu równań kontroli parzystości . Odpowiednik ten ma postać:

Wynika z tego, że wielomiany g(X) i h(X) są składnikami wielomianu zgodnie z wzorem:

Własność ta jest podstawą wyboru wielomianu generującego lub kontroli parzystości kody cyklicznego. Każdy czynnik wielomianu rzędu (n-k) może być użyty jako wielomian generujący. Dla odpowiednio dużego n wielomian może mieć wiele czynników rzędu (n-k), co oznacza że może istnieć wiele wielomianów generujących. Nie każdy z tych wielomianów generujących generuje dobry kod cykliczny.

2. Zadania

2.1  Symulacja systemu transmisji cyfrowej z koderem blokowym.

Otworzyć model systemu kody_blokowe.mdl. W schemacie standardowo użyty jest koder o następującej macierzy generującej:

a)      podać parametry (n,k,t), oraz sprawność tego kodu,

b)     zmierzyć bitową stopę błędów BER w zależności od wartości SNR dla modulacji QPSK,

c)      znaleźć kod dualny i powtórzyć zadania z punktów a i b

d)     powtórzyć punkty a i b dla kodu określonego poniższą macierzą kontroli parzystości:

e)      zaprojektować kod o sprawności 5/8, powtórzyć punkty a i b

...