Kody splotowe
Zastosowanie
Niekiedy potrzeba buforowania fragmentu wiadomości przed zakodowaniem, tak jak to ma miejsce
w koderze blokowym, jest przeszkodą, gdyż dane do zakodowania napływają strumieniem. Wtedy
wyjściem jest zastosowanie kodera splotowego, który przetwarza dane w sposób ciągły. W praktyce
kodery splotowe są stosowane np. jako sposób korekcji błędów przy zapisie na płytach DVD.
Opis działania
Działanie kodera splotowego można porównać do działania maszyny o skończonej liczbie stanów.
Składa się ona z:
1. M-stopniowego rejestru przesuwnego (składającego się z M przerzutników),
2. n sumatorów modulo 2,
3. multipleksera.
L-bitowy ciąg wiadomości jest kodowany w n(L+M) -bitowy ciąg wyjściowy.
Def. Stopa kodu kodu splotowego wyraża się wzorem:
r
=
L
n
LM
bitów
/symbol
Zazwyczaj L » M, więc przyjmuje się w przybliżeniu:
r
=
1
n
.
Def. Długość ograniczona kodu splotowego jest równa liczbie przesunięć, podczas których
pojedynczy bit wiadomości może wpłynąć na wyjście kodera. Dla kodera o M-stopniowym
rejestrze przesuwnym, długość ograniczona kodu K = M + 1.
Przykład
Schemat przykładowego kodera splotowego dla n=2 oraz K=3 przedstawiony jest poniżej:
Kod generowany przez ten koder jest kodem niesystematycznym. W przeciwieństwie do kodów
blokowych, zazwyczaj stosuje się niesystematyczne kody splotowe.
Niech wiadomość do zakodowania ma postać: 10011. Przy rozpoczęciu kodowania zakładamy, że
koder jest wyzerowany, czyli we wszystkich przerzutnikach znajdują się wartości 0. Kolejne bity
wiadmości “wsuwamy” z lewej strony, po czym “wędrują” one zgodnie z kierunkiem strzałek, po
drodze zapamiętywane w kolejnych przerzutnikach rejestru przesuwnego. Wynik dodawania
(zgodnie ze schematem) w sumatorach modulo dwa przechodzi do multipleksera, a stąd na wyjście.
Zauważmy, że multiplekser, na schemacie umieszczony jako “przełącznik”, w każdym swoim
położeniu definiuje aktywną ścieżkę w koderze (w tym przypadku są dwie, również zaznaczone na
schamacie). Prześledźmy kolejne fazy kodowania wiadomości 10011 dla pierwszej ścieżki:
Zauważmy, że gdy wyczerpią się bity z ciągu wejściowego, kodowanie przebiega dalej, aż do
wyzerowania rejestru przesuwnego. Zakładamy wtedy, że na wejście kodera wchodzi cały czas
wartość 0, jest to tzw ogon wiadomości. Zbierając dane z wyjścia kodera otrzymujemy ciąg
1111001. Postępując analogicznie dla drugiej ścieżki, otrzymamy 1011111. Multiplekser ustawia w
ciąg wyjściowy naprzemiennie bity napływające z kolejnych ścieżek, więc w rezultacie
otrzymujemy:
c = (11 10 11 11 01 01 11)
jako zakodowany ciąg wyjściowy.
Kodowanie z wykorzystaniem odpowiedzi impulsowych kodera
Każdą ścieżkę od wejścia do wyjścia kodera można scharakteryzować za pomocą odpowiedzi
impulsowej, czyli odpowiedzi danej ścieżki na symbol 1 podany na wejście (przy założeniu, że
wszystkie przerzutniki były początkowo wyzerowane):
g
0
i
, g
1
i
, g
2
i
, ... , g
M
i
.
Kompletny koder splotowy jest opisany przez zbiór wielomianów generujących (zbiór generujący):
{
g
1
D , g
2
D , ... , g
n
D
}
, gdzie
g
i
D=g
0
i
g
1
i
D
g
2
i
D
2
...g
M
i
D
M
,
D – zmienna opóźnienia jednostkowego (analogiczna do X przy kodowaniu cyklicznym).
Splot w dziedzinie czasu transformuje się na mnożenie w dziedzinie częstotliwości. Wielomian
kodowy dla i-tej ścieżki jest więc równy:
c
i
D= g
i
Dm D
,
gdzie m(D) jest wielomienem wiadomości do zakodowania.
Dla podanego wyżej przykładu kodera mamy:
Odpowiedzi impulsowe ścieżek i odpowiadajęce im wielomiany generujące:
g
i
=111 ; g
i
D=1DD
2
g
i
=101 ; g
i
D=1 D
2
Ciąg wiadomości i wielomian wiadomości:
m
=10011; m D=1D
3
D
4
Z tego wyliczamy wielomiany kodowe dla każdej ze ścieżek:
c
1
D=g
1
D⋅m D=1DD
2
⋅1 D
3
D
4
=1D D
2
D
3
D
6
c
2
D=g
1
D⋅m D=1D
2
⋅1D
3
D
4
=1D
2
D
3
D
4
D
5
D
6
Po zamianie wielomianów na ciągi i zmultipleksowaniu otrzymamy dokładnie taki sam wynik jak
w powyższym przykładzie. Wynika z tego, że do pełnej charakterystyki kodera splotowego, która
wystarczy do zakodowania dowolnej wiadomości, wystarczy podać zbiór odpowiedzi
impulsowych dla wszystkich scieżek, czyli zbiór generujący.
Diagramy: stanu oraz kratowy
Na początku niniejszego opracowania działanie kodera splotowego zostało porównane do maszyny
o skonczonej liczbie stanów. Stan kodera określony jest jednoznacznie przez zawartość rejestru
przesuwnego. Tak więc koder o M-stopniowym rejestrze przesuwnym ma
2
M
różnych stanów.
Przejście od jednego do drugiego stanu odbywa się po podaniu na wejście bitu danych – wynika z
tego, że z danego stanu koder może przejść w jednym kroku maksymalnie do jednego z dwóch
innych stanów (na wejściu 1 albo 0), może też pozostać w obecnym stanie. Wszystkie możliwe
stany oraz przejścia pomiędzy nimi ilustruje diagram stanów kodera. Powracając do naszego
przykładu – diagram stanów dla niego ma postać:
Węzły diagramu to kolejne stany. Linia ciągła oznacza przejście ze stanu do stanu spowodowane
podaniem na wejście wartości 0. Linia przerywana – analogicznie wartości 1. Przy liniach
dodatkowo umieszczone są wartości podawane na wyjście kodera (dla obydwu ścieżek). Umożliwia
to zakodowanie wiadomości przy pomocy diagramu – rozpoczynamy w węźle oznaczającym stan
00 i poruszamy się po odpowiednich liniach w zależności od tego, czy na wejściu pojawia się 0 czy
1, “zbierając” po drodze wartośći z wyjścia. Po wyczerpaniu bitów wiadomości kodujemy ogon
złożony z zer, aż zatrzymamy się ponownie w węźle 00.
Innym typem diagramu jest diagram kratowy. Nazwa wzięła się z regularnie rozmieszczonych
węzłów, pomiędzy którymi rozpięte są krzyżujące się linie przejść pomiędzy stanami. Kolejnym
stanom odpowiadają kolejne wiersze kraty, natomiast kolejne kolumny to poziomy (nazywane też
głębokościami), które odpowiadają za kolejne kroki kodowania. W przeciwieństwie do diagramu
stanów, rozpiętość diagramu kratowego zależy od długości wiadomości do zakodowania. Oto
przykład (wciąż rozpatrujemy ten sam koder) dla wiadomości o długości L:
Dekodowanie – algorytm Viterbiego
Rozpatrzmy koder splotowy zdefiniowany przez diagram kratowy. Dekoder posiada (lub
rekonstruuje na podstawie innych danych) taki sam diagram i wykorzystuje go do dekodowania
oryginalnego ciągu. Odbierając kolejny podciąg n bitów dekoder porusza się w diagramie
wkratowym w prawo, wzdłuż linii oznaczonej tym ciągiem (który w koderze oznacza ciąg
wyjściowy), przechodząc do kolejnego stanu. Zauważmy, że z danego węzła diagramu nie są
osiągalne wszystkie stany, tak samo jak nie są dopuszczalne wszystkie kombinacje podciągów. Jeśli
dekoder napotka na taki “niedozwolony” ciąg, mamy do czynienia z przekłamamiem transmisji.
Ponieważ nie istnieje linia oznaczona odczytanym podciągiem, musimy znaleźć algorytm
decyzyjny, który wybierze dalszą drogę w grafie.
W praktyce, nie możemy polegać jedynie na istnieniu odpowiedniej ścieżki w grafie z aktualnego
punktu, gdyż przypadkowa zamiana jednego dozwolonego podciągu na inny, też dozwolony
wprawdzie pozwoli nam posunąć się dalej, ale później spowoduje “lawinę” błędów i, w rezultacie,
błędną rekonstrukcję. Dlatego trzeba analizować wszystkie możliwe ścieżki, dzięki czemu
otrzymamy rezultat o maksymalnej wiarygodności dekodowania. Tak działa algorytm
Viterbiego, który do oceny wiarygodności dekodowania dla każdej ścieżki używa odległości
Hamminga pomiędzy odczytanym ciągiem a ciągiem zdekodowanym przy użyciu danej ścieżki.
Dla kolejnych poziomów w diagramie kratowym postępujemy wg następującego algorytmu:
Algorytm Viterbiego:
Dla każdego węzła na danym poziomie: wybierz tą ze ścieżek dochodzących do tego węzła,
która daje w wyniku najmniejszą sumaryczną odległość Hamminga pomiędzy
odczytanym ciągiem a ciągiem zdekodowanym. W przypadku, gdy wszystkie ścieżki dają
taki sam wynik, wybierz jedną losowo. Pozostałe ścieżki odrzuć, a sumaryczną odległość
Hamminga zapamiętaj w węźle, w celu wykorzystania w następnym kroku.
Ścieżki, które pozostają w diagramie po odrzuceniu pozostałych nazywają się ścieżkami
aktywnymi lub ścieżkami ocalenia. Algorytm startuje ze stanu wyzerowanego kodera (lewy
skrajny punkt diagramu kratowego) oraz sumarycznej odległości równej 0, zakończy się po dojściu
do puktu końcowego po prawej stronie, gdzie nastąpi ostateczny wybór ścieżki. W praktyce
zapamiętanie wszystkich ścieżek ocalenia, gdy ciąg do zakodowania jest bardzo długi (np ciąg
bitów w strumieniu danych na płycie DVD) jest niemożliwe, ze względu na szybko wzrastające
j=0
1
2
3
4
L
L+1
L+2
00
01
10
11
00
11
10
01
10
00
01
01
10
01
00
11
11
10
01
11
11
10
11
00
00
00
00
00
11
11
10
01
wymagania pamięciowe. Wtedy algorytm stosuje się sekwencyjnie na oknie o ograniczonej
długości. W tej wersji nie jest to już algorytm o maksymalnej wiarygodności dekodowania, ale przy
odpowiedniej długości okna (5 lub więcej razy długość K kodu), jest wystarczająco dobry.