4

Kody splotowe

Kody splotowe wprowadził P. Elias w roku 1955. Stanowią one całkowicie odmienny rodzaj kodów liniowych niż omawiane w rozdziałach 2 i 3 kody blokowe. Zasadnicza różnica polega na tym, że podczas kodowania blokowego generowane przez koder w kolejnych taktach kodowania ciągi kodowe ..., s^(i-1), s⁽ⁱ⁾, s⁽ⁱ⁺¹⁾, ... możemy traktować jako realizacje ciągu niezależnych zmiennych losowych, podczas kodowania splotowego natomiast musimy je traktować jako realizacje zmiennych losowych zależnych. Zależności te przenoszą się oczywiście na ciągi odbierane ..., y^(i-1), y⁽ⁱ⁾, y⁽ⁱ⁺¹⁾, ... Dekodowanie kodów splotowych stanowi więc trudny problem teoretyczny. Sekwencyjny algorytm dekodowania kodów splotowych przedstawił w roku 1957 J. M. Wozencraft, a jego implementację opisali niezależnie R. M. Fano i J. L. Massey w roku 1963. W roku 1967 A. J. Viterbi przedstawił algorytm dekodowania kodów splotowych, opierający się na zasadzie największego prawdopodobieństwa, który zapewnił lepsze właściwości korekcyjne i mniejsze opóźnienie dekodowania niż algorytm sekwencyjny. Rozwój technologii układów elektronicznych o dużym stopniu scalenia umożliwił praktyczną realizację algorytmu Viterbiego. Już na początku lat 70. kody splotowe zastosowano w systemach telekomunikacyjnych do głębokiej penetracji przestrzeni kosmicznej. Pod koniec lat 80. kodowanie splotowe zastosowano w telefonii komórkowej GSM, mającej dziś znaczenie globalne. Kody splotowe, dzięki bardzo dobrym właściwościom korekcyjnym, są obecnie chętnie stosowane w rozmaitych systemach telekomunikacyjnych.

4.1. Zasada kodowania splotowego

Kody splotowe stanowią szczególny przypadek kodów drzewiastych, których definicja jest następująca.

Niech będzie dany K-stanowy automat sterowany przez k-pozycyjne q-narne ciągi wejściowe h, generujący pod ich wpływem n-pozycyjne q-narne ciągi wyjściowe s. Niech h i s oznaczają odpowiednio zbiory ciągów wejściowych i wyjściowych; zakładamy przy tym, że mają one tę samą liczność L = q^k. Jeśli jest zadana tablica, która na podstawie stanu automatu w (i - 1)-szym takcie pracy oraz podanego na jego wejście w i-tym takcie ciągu h⁽ⁱ⁾ jednoznacznie określa generowany w i-tym takcie ciąg s⁽ⁱ⁾ oraz stan, do którego przechodzi w tym takcie automat, to wówczas zbiory h i s stanowią odpowiednio zbiór ciągów informacyjnych i zbiór ciągów kodowych kodu drzewiastego.

Kod splotowy jest to kod drzewiasty, dla którego ciąg s⁽ⁱ⁾ zależy od ciągu h⁽ⁱ⁾ oraz od skończonej liczby (N - 1) wcześniejszych ciągów informacyjnych za pośrednictwem pewnej funkcji f, będącej przekształceniem liniowym

(4.1)

Kod splotowy jest kodem liniowym (jest to konsekwencja liniowości przekształcenia f), a proces kodowania splotowego - procesem z pamięcią na (N - 1) poprzednich bloków. Parametr N nazywamy długością wymuszoną. Stosuje się również określenie wymuszona długość bloku równa Nk. Z formalnego punktu widzenia kody blokowe można uważać za szczególny przypadek kodów splotowych o długości wymuszonej N = 1.

Zasadę kodowania splotowego ilustruje ogólny schemat kodera pokazany na rysunku 4.1. Koder zawiera Nk-komórkowy rejestr wejściowy, złożony z N sekcji, po k komórek w każdej. Umożliwia on zapamiętanie symbolu aktualnie kodowanego oraz (N - 1) symboli poprzednich. Generatory liniowych funkcji algebraicznych:
,
, ...,
określają układ sprzężeń między Nk-komórkowym rejestrem wejściowym i n-komórkowym rejestrem wyjściowym. W każdym kroku kodowania nowy k-bitowy symbol informacyjny jest wprowadzany do rejestru wejściowego. Symbole znajdujące się w rejestrze ulegają przesunięciu o k pozycji w prawo. Najstarszy symbol zostaje usunięty z rejestru. Poprzez układ sprzężeń tworzy się n-bitowy symbol kodowy. Proces ten jest powtarzany, powodując przekształcenie ciągu k-bitowych symboli informacyjnych w ciąg n-bitowym symboli kodowych. Kod splotowy oznacza się w następujący sposób: (n,k,N). Sprawność kodu

(4.2)

określa ilość informacji przypadającą na jeden bit symbolu kodowego. Jeśli k jest równe jedności, czyli symbole informacyjne są jednobitowe, to mamy do czynienia z binarnym kodem splotowym.

Rys. 4.1. Koder kodu splotowego (n,k,N)

Proces kodowania splotowego można również przedstawić w postaci macierzowej. Zdefiniujmy N podmacierzy G₁, G₂, ..., G_N zawierających po k wierszy i n kolumn. Macierze te opisują układ sprzężeń między rejestrem wejściowym i rejestrem wyjściowym kodera. Podmacierz G_i opisuje połączenie k komórek i-tego segmentu rejestru wejściowego z n komórkami rejestru wyjściowego. Pierwszy wiersz tej podmacierzy opisuje połączenia pierwszej komórki i-tego segmentu rejestru wejściowego z n komórkami rejestru wyjściowego, przy czym 1 oznacza połączenie, 0 - brak połączenia. W ten sam sposób drugi wiersz podmacierzy G_i opisuje połączenia drugiej komórki i-tego segmentu rejestru wejściowego z komórkami rejestru wyjściowego itd. Możemy teraz zdefiniować macierz generującą kod splotowy

(4.3)

Wszystkie pozostałe elementy macierzy generującej są zerami. Macierz G_∞ jest macierzą półnieskończoną, to znaczy rozciąga się do nieskończoności w dół i w prawo. Określmy przez h półnieskończony wektor informacyjny, a przez s - półnieskończony wektor kodowy. Proces kodowania splotowego możemy teraz przedstawić w postaci równania macierzowego

s = h G_∞. (4.4)

Równanie (4.4) jest formalnie identyczne z równaniem (2.16). Macierzowy zapis kodowania splotowego ułatwia zrozumienie podobieństwa i różnic między kodami blokowymi i kodami splotowymi, nie jest jednak dogodny do opisu procesu dekodowania kodów splotowych.

W procesie kodowania za pomocą binarnych kodów splotowych (k = 1) na każdy bit informacyjny przypada n bitów kodowych, opisanych zależnością

(4.5)

Zależność (4.5) przedstawia dyskretny splot wektorów G₁, G₂, ..., G_N i N-bitowej sekwencji wejściowej h_i, h_i-1, ..., h_i-N+1. Stąd pochodzi nazwa kodów splotowych. Na ogół liczba sumatorów modulo dwa w koderze jest mniejsza od długości wymuszonej N. Zwykle stosuje się dwa lub trzy sumatory. Otrzymujemy wówczas kody o sprawności 1/2 lub 1/3 odpowiednio.

Przykład 4.1.

Zasadę kodowania splotowego zilustrujemy na przykładzie prostego kodera binarnego (2,1,3), tzn. n = 2, k = 1, N = 3. Schemat tego kodera pokazano na rysunku 4.2. Koder składa się z trzykomórkowego rejestru wejściowego, dwukomórkowego rejestru wyjściowego oraz dwóch sumatorów modulo dwa.

Generatory funkcji algebraicznych określają wektory:

lub równania kodowania:

									...	1	1	1
								...	1	1	1	0
							...	1	1	1	0	1
						...	1	1	1	0	1	1
					...	1	1	1	0	1	1	0
				...	1	1	1	0	1	1	0	1
			...	1	1	1	0	1	1	0	1	0
		...	1	1	1	0	1	1	0	1	0	1
	...	1	1	1	0	1	1	0	1	0	1	0
...	1	1	1	0	1	1	0	1	0	1	0	0

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

Rys. 4.2. Koder binarnego kodu splotowego (2,1,3)

Przed rozpoczęciem kodowania rejestr wejściowy zostaje wyzerowany. Niech ciąg symboli (bitów) informacyjnych ma postać: 1 0 1 0 1 1 0 1 1 1 ... . W pierwszym kroku do rejestru wejściowego jest wprowadzony symbol 1. W wyniku kodowania otrzymujemy:

symbol kodowy ma więc postać: 1 1. W następnym kroku na wejście kodera jest podawany symbol 0, koder przechodzi do stanu 1 0, i otrzymujemy:

tzn. symbol kodowy ma postać: 0 1. Kodowanie dalszych symboli informacyjnych przedstawiono na rysunku 4.2. Sprawność kodu wynosi 0,5.

Pokażemy jeszcze macierz generującą omawiany kod. Podmacierze mają postać: macierz generująca zatem

Przykład 4.2.

Opiszemy binarny kod splotowy o sprawności 1/3 i długości wymuszonej N = 3. Schemat kodera pokazano na rysunku 4.3.

Rys. 4.3. Koder binarnego kodu splotowego (3,1,3)

Generatory funkcji algebraicznych mają postać:

Równia kodowania:

Pozycja mamy więc do czynienia z systematycznym kodem splotowym. Systematyczne kody splotowe bywają też nazywane kodami rekurencyjnymi.

W formie macierzowej możemy omawiany kod przedstawić następująco:

Łatwo sprawdzić, że sekwencji informacyjnej h = 11011... odpowiada sekwencja kodowa
s = 111100010110100... Kod ma oznaczenie (3,1,3).

Przykład 4.3.

Rozpatrzymy kod splotowy (3,2,2), to znaczy symbole informacyjne są dwubitowe (k = 2), symbole kodowe - trzybitowe (n = 3), długość wymuszona - N = 2. Schemat kodera pokazano na rysunku 4.4.

Rys. 4.4. Koder kodu splotowego (3,2,2)

Kod jest określony przez dwie podmacierze:

, .

i macierz generującą

.

Sekwencji informacyjnej h = 11011011... odpowiada sekwencja kodowa s = 111010100110...

4.2. Diagram stanów, wykres drzewiasty, wykres kratowy

Przyjrzyjmy się bliżej procesowi kodowania za pomocą binarnego kodu splotowego (2,1,3), omawianego w przykładzie 4.1. W miarę jak sekwencja informacyjna jest wprowadzana do rejestru wejściowego (rys. 4.2), bit po bicie, zmienia się stan kodera, który określa się przez obserwację sekwencji informacyjnej w oknie o rozmiarach (N - 1)k. W omawianym przykładzie rozmiar okna jest równy 2. Sekwencji informacyjnej 1010110111... odpowiada następująca sekwencja stanów kodera: 00, 10, 01, 10, 01, 10, 11, 01, 10, 11, ... Każdej zmianie stanu kodera odpowiada wygenerowanie odpowiedniej sekwencji kodowej: 11 01 00 01 00 10 10 00 10 01 ...

Stan kodera opisują (N - 1)k komórki rejestru wejściowego, w omawianym przykładzie są to dwie komórki. Liczba możliwych stanów kodera jest równa
, cztery w rozważanym przypadku. Sa to następujące stany: 00, 10, 01, 11; oznaczmy je przez a, b, c i d, odpowiednio. Na rysunku 4.5 pokazano diagram zmiany stanów automatu generującego omawiany kod splotowy (2,1,3). Gałęzie wychodzące ze stanu obecnego do stanu następnego pokazują zmianę stanu automatu i generowaną przy tym sekwencję kodową. Linia ciągła odpowiada przy tym zmianie stanu spowodowanej wprowadzeniu na wejście kodera bitu o wartości 0, linia przerywana natomiast - bitu o wartości 1. Z każdą gałęzią jest związany dwubitowy symbol kodowy generowany przez koder. Liczba gałęzi wychodzących z każdego stanu jest równa
, tzn. dwa w omawianym przypadku.

Rys. 4.5. Diagram zmiany stanów automatu generującego kod splotowy (2,1,3)

Rysunek 4.5 umożliwia skonstruowanie diagramu stanów automatu generującego rozważany kod splotowy. Diagram ten pokazano na rysunku 4.6. Zawiera on wszystkie możliwe stany i wszystkie możliwe przejścia pokazane na rysunku 4.5. Diagram stanów umożliwia prześledzenie procesu kodowania za pomocą określonego kodu splotowego. W omawianym przykładzie koder na początku znajduje się w stanie a (00). Podanie na wejście kodera bitu o wartości 1 powoduje przejście kodera do stanu b (10) i wygenerowanie symbolu kodowego 11. Jeśli na wejście kodera w stanie b zostanie podany bit o wartości 0, to koder przejdzie do stanu c (01) i wygeneruje symbol kodowy 10. Łatwo prześledzić, że proces kodowania pokazany na rysunku 4.2 jest zgodny z diagramem stanów kodera z rysunku 4.6.

Rys. 4.6. Diagram stanów automatu generującego kod splotowy (2,1,3)

Diagram stanów automatu generującego kod (3,1,3), omawiany w przykładzie 4.2, pokazano na rysunku 4.7. Podanie na wejście kodera znajdującego się w stanie a (00) bitu o wartości 1 powoduje przejście kodera do stanu b (10) i wygenerowanie symbolu kodowego 111. Podanie na wejście kodera w stanie b bitu o wartości 1 powoduje jego przejście do stanu d (11) i wygenerowanie symbolu kodowego 100. Łatwo prześledzić dalszy ciąg procesu kodowania opisanego w przykładzie 4.2.

Rys. 4.7. Diagram stanów automatu generującego kod splotowy (3,1,3)

Proces kodowania za pomocą kodów splotowych można również zilustrować za pomocą drzewa kodowego. Drzewo takie dla kodu rozpatrywanego w przykładzie 4.2 pokazano na rysunku 4.8. Na początku koder znajduje się w stanie a (00). Podanie na wejście kodera bitu o wartości 1 powoduje przejście do stanu określonego ścieżką "w górę" i wygenerowanie symbolu kodowego przypisanego tej ścieżce. Podanie na wejście kodera bitu o wartości 1 powoduje przejście do stanu określonego ścieżką "w dół" i wygenerowanie symbolu kodowego przypisanego tej ścieżce. Na rysunku 4.8 linią pogrubioną pokazano proces kodowania rozważany w przykładzie 4.2. Podanie na wejście kodera znajdującego się w stanie a (00) bitu o wartości 1 powoduje przesunięcie się "w dół" do stanu b (10) i wygenerowanie symbolu kodowego 111. Podanie na wejście kodera kolejnej jedynki powoduje przejście do stanu d (11) oraz wygenerowanie symbolu kodowego 100 itd.

Rys. 4.8. Drzewo kodowe kodu splotowego (3,1,3) omawianego w przykładzie 4.2; linią pogrubioną zaznaczono przebieg kodowania dla wybranej sekwencji informacyjnej: 11011...

Posługiwanie się w praktyce drzewem kodowym jest kłopotliwe, szybko bowiem osiąga ono monstrualne rozmiary. Wygodniejszym sposobem ilustracji procesu kodowania splotowego jest wykres kratowy. Na osi rzędnych takiego wykresu zaznacza się stany kodera, a na osi odciętych - kolejne takty kodowania. Wykres kratowy dla kodu omawianego w przykładzie 4.1 pokazano na rysunku 4.9.

4.4. Pojęcie odległości w kodach splotowych

Daniel Józef Bem, Kody splotowe 12

---