Kod splotowy

Kod splotowy (ang. convolutional codes) – typ kodu korekcyjnego. Kody splotowe zwykle są określane przez trzy parametry: ${\displaystyle (n,k,m).}$ Ideą kodowania splotowego jest przekształcenie wejściowego ${\displaystyle k}$-bitowego ciągu informacyjnego na ${\displaystyle n}$-bitowy ciąg wyjściowy. Sprawność kodu splotowego wynosi ${\displaystyle k/n(n\geqslant k).}$ Dodatkowym parametrem jest ${\displaystyle m,}$ który oznacza liczbę przerzutników „D” w rejestrze układu kodującego albo ilość boksów, z których ten rejestr się składa. Można również wyróżnić wielkość ${\displaystyle L,}$ która oznacza ograniczoną długość kodu i jest definiowana jako: ${\displaystyle L=k(m-1).}$ Ograniczona długość ${\displaystyle L}$ reprezentuje liczbę bitów w pamięci kodera wpływających na generowanie ${\displaystyle n}$ bitów wyjściowych.

Kody splotowe używane są często w celu zwiększenia niezawodności transmisji w radiofonii cyfrowej, telefonii komórkowej oraz w łączach satelitarnych.

Wykluczanie

Kody o szczególnych parametrach takich jak ${\displaystyle k=1}$ i sprawnościach 1/2, 1/3, 1/4, 1/5, 1/7 są czasem nazywane „kodami matkami”. Nie zawsze pożądana jest tak duża nadmiarowość kodowania i można ją zmniejszyć, wykorzystując do transmisji tylko niektóre z wyjściowych bitów, „wykluczając” pozostałe. Przykładowo z kodera o sprawności 1/2 (na jeden bit wejściowy przypada 2 bity zakodowane) można pobierać dwa kolejne bity wyjściowe, opuszczając trzeci. Uzyskuje się przez to sprawność równą 2/3. Kody splotowe z wykluczaniem używane są w systemach satelitarnych, np. w Intelsat lub DVB.

Struktura koderów kodu splotowego

Koder zapamiętuje stany w pamięci. Wyrafinowane kodery mają długie ${\displaystyle L,}$ natomiast niektóre prostsze kodery mają krótkie ${\displaystyle L.}$ Liczba stanów kodera to liczba kombinacji bitów w ${\displaystyle L}$ rejestrach i wyraża się wzorem: Liczba stanów ${\displaystyle =2^{L}.}$

• ${\displaystyle k=1}$

Koder składa się z: ${\displaystyle m}$ boksów reprezentujących ${\displaystyle m}$ rejestrów pamiętających, ${\displaystyle n}$ sumatorów modulo-2, które reprezentują ${\displaystyle n}$ bitów wejściowych. Rejestry pamięci są odpowiednio połączone z sumatorami generującymi wielomian. Wybór, które bity są dodawane i wytwarzają bit wyjściowy jest dokonywany na podstawie wielomianu generującego ${\displaystyle g}$ dla tego bitu. Dla kodera na rys. 2: pierwszy bit wyjściowy ma wielomian generujący w postaci (1,1,1), drugi bit (0,1,1), a trzeci (1,0,1).

${\displaystyle v_{1}={\bmod {2}}(u_{1}+u_{0}+u_{-1});}$

${\displaystyle v_{2}={\bmod {2}}(u_{0}+u_{-1});}$

${\displaystyle v_{3}={\bmod {2}}(u_{1}+u_{-1});}$

Koder przedstawiony na rys. 1 ma ograniczoną długość kodu ${\displaystyle L=2.}$ Z tego wynika, że liczba stanów kodera wynosi 4. Zaciemnione rejestry są układem pamiętającym historię.

• ${\displaystyle k>1.}$

Kolejne etapy rysowania kodera dla kodu ${\displaystyle (n,k,m),}$ gdzie ${\displaystyle k}$ jest większe niż jeden, są następujące. Najpierw rysujemy ${\displaystyle m}$ boksów, gdzie w każdym z nich znajduje się po ${\displaystyle k}$ rejestrów. Potem rysujemy ${\displaystyle n}$ sumatorów i łączymy je z rejestrami pamięci, wykorzystując do tego celu współczynniki przy ${\displaystyle n}$-tym stopniu wielomianu. Dla kodera na rys. 3 kod ma 3 bity wejściowe, daje 4 bity na wyjściu. Liczba rejestrów w tym koderze jest równa 3. Łatwo wyznaczyć skróconą długość, która wynosi 3 × 2 = 6, a ilość stanów w kodzie wynosi 64. Kod ten wymaga wielomianów generujących dziewiątego stopnia. Zaciemnione rejestry na rysunku reprezentują skróconą długość kodu.

Kod splotowy systematyczny

Specjalna odmiana kodu splotowego, w której bity wyjściowe zawierają łatwo rozpoznawalna sekwencje bitów wejściowych, jest nazywana odmianą systematyczną. Wersja systematyczna wcześniejszego kodu (4,3,3) z rys. 3 jest pokazana poniżej. Z czterech bitów wyjściowych, trzy są dokładnie taki same jak bity wejściowe. Czwarty bit jest odmianą bitu parzystości wytwarzany jako kombinacja trzech bitów używanego pojedynczego wielomianu.

Kody systematyczne są często chętniej stosowane od kodów niesystematycznych, ponieważ można je łatwo rozpoznać. Dodatkowo kody te potrzebują mniej zasobów sprzętowych do ich zdekodowania. Inną ważną własnością kodów systematycznych jest to, że nie są one „katastrofalne”, co znaczy, że błędy nie mogą się katastrofalnie propagować. Wszystkie te własności czynią ten kod bardzo pożądanym. Kody systematyczne są również używane w modulacji kratowo-kodowej (ang. Trellis-Code Modulation, TCM). Jednakże własności zabezpieczające przed błędami kody systematyczne są takie same jak w kodach niesystematycznych.

Jak dobrać wielomian generujący?

Dla każdego ${\displaystyle m}$ szukanego kodu istnieje wiele różnych wielomianów generujących. Wielomiany te nie generują wszystkich możliwych sekwencji wyjściowych, a mimo to mają dobre własności wykrywania błędów. Poniżej w tabeli znajduje się lista „dobrych” wielomianów.

Tab.1 Wielomiany generujące dla kodów o klasie 1/2 znalezione przez Busganga.

Ograniczona długość ${\displaystyle L}$	${\displaystyle g_{1}}$	${\displaystyle g_{2}}$
3	110	111
4	1101	1110
5	11010	11101
6	110101	111011
7	110101	110101
8	110111	1110011
9	110111	111001101
10	110111001	1110011001

Kodowanie kodów splotowych

Wyjściowa sekwencja ${\displaystyle v}$ może być wyliczona przez splot wejściowej sekwencji bitów ${\displaystyle u}$ z odpowiedzią impulsową ${\displaystyle g.}$ Można to przedstawić jako: ${\displaystyle v=u\cdot g}$ lub w bardziej ogólnej formie:

${\displaystyle v_{l}^{j}=\sum \limits _{i=0}^{m}u_{l-i}\cdot g_{i}^{j},}$

gdzie ${\displaystyle v_{l}^{j}}$ jest bitem wyjściowym ${\displaystyle l}$ z kodera ${\displaystyle j,}$ ${\displaystyle u_{l-i}}$ bitem wejściowym, a ${\displaystyle g_{i}^{j}}$ jest ${\displaystyle i}$-tym wyrazem w wielomianie ${\displaystyle j.}$

Tablica look-up

Kodery kodów splotowych używają gotowych tablic do kodowania – tzw. look-up table. Taka tablica składa się z czterech kolumn:

1. Bit wejściowy.

2. Stan kodera.

3. Bity wyjściowe.

4. Stan wyjścia, który będzie stanem wejściowym dla następnego bitu.

Diagram stanu

W diagramie stanu każdy okrąg reprezentuje jeden stan kodera. W każdej chwili czasowej koder przebywa w jednym z tych stanów. Strzałki, które łączą poszczególne okręgi pokazują rodzaj transmisji, jaka może wystąpić w zależności od tego jaki bit podamy na wejście. W dowolnym momencie może nadejść „1” lub „0”. W zależności od tego bitu, który nadszedł, koder przechodzi do różnych stanów. Wadą diagramu stanu jest to, że nie obejmuje on działania w czasie, ale tylko połączenia logiczne.

Diagram o strukturze drzewa

W tym diagramie zamiast skoków z jednego stanu do innego, poruszamy się po gałęziach drzewa w górę bądź w dół, w zależności czy na wejściu zostało odebrane „0” czy „1”. Pierwsza gałąź wykrywa przybycie „1” lub „0”. Zaczynamy od stanu „0..0” (${\displaystyle L}$ zer). Jeżeli zostanie odebrane „0” idziemy w drzewie do góry, a jeżeli „1” to idziemy w dół. Na rys. 6 linie koloru czerwonego oznaczają przybycie na wejście „0”, natomiast linie kolor niebieskiego mówią, że na wejście nadeszła „1”. Pierwsze bity oznaczają stan wyjścia, bity w nawiasach informują o stanie kodera. W przypadku, gdy sekwencja wejściowa jest dłuższa od gałęzi drzewa należy „rozciągnąć” gałęzie drzewa – przeskakujemy w drzewie do miejsca gdzie bity wyjściowe i stan odpowiada naszemu następnemu stanowi.

Diagram kratowy

• Tworzenie diagramu kratowego

stany, jakie mogą wystąpić. W diagramie takim poruszamy się poziomo zgodnie z upływem czasu. Każda transmisja oznacza, że na wejście został podany jeden nowy bit. Rysując diagram kratowy, musimy najpierw nanieść wszystkie możliwe stany ${\displaystyle (2^{L})}$ na oś pionową. Później łączymy każdy stan z dopuszczalnym stanem następnym. W każdym stanie są tylko dwie możliwości do wybrania. Są one zdeterminowane przez nadchodzące bity w zależności czy to jest „0” czy „1”. Na poszczególnych strzałkach zaznaczone są bity wejściowe oraz bity wyjściowe, które umieszczamy w nawiasie. Strzałki są skierowane w górę bądź w dół, w zależności od tego jaki bit został podany na wejście. Jeżeli podamy „1” wówczas strzałka jest skierowana w dół, jeżeli natomiast podamy „0” to strzałka skierowana jest do góry. Taki diagram kratowy jest unikatowy dla każdego kodu, podobnie jak diagram stanu i diagram o strukturze drzewa. Możemy także rysować kraty dla tylu okresów ile chcemy. Każdy okres będzie powtarzał możliwą transmisje. Zawsze startujemy ze stanu „0..0” (${\displaystyle L}$ zer). Rozpoczynamy z tego punktu i rozszerzamy kraty, aż wszystkie możliwe transmisje zostaną wykorzystane i uwzględnione na diagramie.

• Kodowanie z użyciem diagramy kratowego

W górnej części rys. 8 pokazano nadchodzące bity w danych chwilach czasowych. Zaczynamy z punktu „0..0” (${\displaystyle L}$ zer). Następnie przesuwamy się w prawą stronę – w zależności od stanów na wejściu w górę, gdy jest „0” lub w dół, gdy przychodzi „1”. Na rys. 8 przedstawiono tak zbudowaną „ścieżkę” dla przykładowej sekwencji bitów wejściowych 1011000.

Dekodowanie kodów splotowych

Istnieje kilka metod dekodowania kodów splotowych. Są one podzielone na dwie zasadnicze kategorie.

1. Metoda „twarda” (ang. hard). Porównujemy odebraną sekwencję z wszystkimi dostępnymi kombinacjami i wybieramy jedną, która ma najmniejszą odległość Hamminga. Metoda ta ma bardzo silny próg decyzyjny. Jest to przykład dekodowania sekwencyjnego.

2. Metoda „miękka” (ang. soft). Możemy skorelować te sekwencje i wybrać jedną o najlepszej korelacji. Próg decyzyjny jest trochę rozmyty i pozostaje tu zawsze pewien margines niepewności. Jest to jeden z przykładów dekodowania metodą maksymalnego prawdopodobieństwa. Na takiej zasadzie działa np. dekodowanie Viterbiego.

Dekodowanie sekwencyjne

Polega na wędrowaniu ścieżką diagramu kratowego i liczeniu ewentualnych błędnych decyzji. Gdy błędów będzie zbyt wiele – cofamy się i wybieramy inną ścieżkę. Liczbę błędów zapamiętuje licznik, a maksymalną ilość błędnych decyzji ustalamy sami. Pomimo odebrania zakłóconego sygnału, dekoder jest w stanie zdekodować go poprawnie.

Dekodowanie sekwencyjne używane jest gdy mamy do czynienia z dużymi zakłóceniami i słabym sygnałem użytecznym (gdzie odstęp sygnał-szum jest mały). Często spotykane w systemach satelitarnych, np. FEC.

Dekodowanie metodą maksymalnego prawdopodobieństwa

Metoda ta korzysta z algorytmu Viterbiego. Polega on na analizowaniu wszystkich ścieżek i porównaniu ich z sekwencją odebraną. Patrzymy przy tym na liczbę pozycji, na których się różnią i wybieramy oczywiście ścieżkę najbardziej podobną do odebranej sekwencji. Metoda ta jest stosowana w systemach gdzie błędy występują stosunkowo rzadko – małe jest prawdopodobieństwo przekłamania bitów, oraz błędy występują zupełnie przypadkowo a prawdopodobieństwo błędu podwójnego jest o wiele mniejsze od prawdopodobieństwa wystąpienia błędu pojedynczego.

Linki zewnętrzne

• opis kodów splotowych. complextoreal.com. [zarchiwizowane z tego adresu (2003-03-20)]. (ang.)
• programowa implementacja kodów korekcyjnych (ang.)

Encyklopedie internetowe (kod korekcyjny):

• Britannica: topic/convolutional-code