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

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.

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

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:

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

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

3. znaleźć kod dualny i powtórzyć zadania z punktów a i b

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

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

6. zaprojektować kod o zdolności korekcyjnej 2 i powtórzyć punkty a i b,

7. porównać badane kody.

1. Symulacja systemu transmisji cyfrowej z koderem cyklicznym.

1. sprawdzić istnienie wielomianu generacyjnego (komenda cyclpoly(n,k)) dla kodu o niskiej sprawności. Przyjąć k równe 3 lub 4. Zbadać zależność bitowej stopy błędów BER od stosunku sygnału do szumu SNR dla modulacji QPSK,

2. dla kodu cyklicznego, o długości słowa kodowego 15, określonego wielomianem generującym
   znaleźć wielomian kontroli parzystości h(X), oraz macierz generującą. Zależność BER(SNR) zbadać dla modulacji QPSK,

3. mając następujące słowa kodowe (1111), (0011), (0101) liniowego kodu cyklicznego, znaleźć pozostałe słowa kodowe (POMOC - kod liniowy zawiera słowo kodowe składające się z samych zer), określić parametry kodu oraz zbudować macierz generującą. Zbadać zależność BER(SNR) dla modulacji QPSK. UWAGA w celu zbadania zależności BER(SNR) należy użyć koder Binary Linear Encoder, oraz dekoder Binary Linear Decoder z biblioteki Communications Blockset.

Bity parzystości

Bity informacyjne

Źródło

danych

Koder

kanałowy

Modulator

kanał

Demodulator

Dekoder

Układ

decyzyjny

---