Algorytm Viterbiego

Wstęp

Jego pierwszym zastosowaniem było,

i nadal jest,

dekodowanie

kodów splotowych

. Jednak stosowany

jest również w innych

zaawansowanych technologiach

telekomunikacyjnych, np. jako

odbiornik

nieliniowy dla kanału z

interferencją międzysymbolową

•

Działanie tego algorytmu oparte jest o

kryterium maksymalnej wiarygodności,

a jego ideą jest to, że optymalna ścieżka

dojścia przez dekoder do aktualnego

stanu składa się ze ścieżki o

najmniejszej metryce dojścia do

któregoś ze stanów poprzednich oraz

przejścia do aktualnego stanu. Jak widać

proces ten jest procesem iteracyjnym

Dekodowane z maksymalną

wiarygodnością - algorytm

Viterbiego

•

Znając własności kodów splotowych i działanie

koderów możemy rozpatrzyć dekodowanie

Viterbiego. (Istnieje wiele sposobów dekodowania

kodów splotowych. Dekodowanie sekwencyjne

zaproponowali Wozencraft , Fano , Zigangirov i

Jelinek . Dekodowanie metodą większościową

zaproponował Massey.)

•

W roku 1967 Viterbi publikował swój algorytm

dekodowania kodów splotowych, który później

okazał się być algorytmem maksymalnej

wiarygodności równoważnym rozwiązaniu

zagadnienia poszukiwania najkrótszej drogi

poprzez graf metodą programowania

dynamicznego

Zasada dekodowania z maksymalną

wiarygodnością

(ang. maximum likehood - ML)

•

Załóżmy, że nadajnik transmituje jedną z sekwencji sygnałów należącą do zbioru

{s1(t), s2(t),..., sN(t)},

np. sekwencję sk(t), do której w kanale AWGN dodawany jest szum n(t).

•

Odbiornik o maksymalnej wiarygodności (ang. ML) zadecyduje, że nadana została

sekwencja, która maksymalizuje prawdopodobieństwo warunkowe

P[si(t)|r(t)]

po wszystkich i.

Stosując wzór Bayesa otrzymujemy następujący wzór

The maximum-likelihood decoding -

Viterbi algorithm

•

rys. 1.

pokazany jest model

binarnego kanału symetrycznego

(ang. binary symmetric channel -

BSC). Dla tego kanału niech q będzie

prawdopodobieństwem, że symbol

nadany został prawidłowo odebrany,

natomiast niech p=1-q będzie

prawdopodobieństwem, że symbol

nadany został odebrany błędnie.

•

Zakładamy, że q>p oraz, że p<1/2

•

Mówimy, że kanał jest kanałem

bezpamięciowym

, jeżeli kolejne symbole na wyjściu kanału nie sa od siebie zależne. W takim

kanale prawdopodobieństwo odebrania bloku symboli r z powodu nadania bloku symboli v dane jest wzorem

•

Kanał dyskretny

jest to taki kanał w którym liczność alfabetu wejściowego i wyjściowego jest skończona. Kanał, który jest

jednocześnie dyskretny i bezpamięciowy nazywany jest dyskretnym kanałem bezpamięciowym (ang. discrete memoryless channel -

(DMC).

Rozpatrzymy dwa przypadki algorytmu Viterbiego :

•

1. Dekodowanie twardodecyzyjne

Załóżmy najpierw, że przez kanał DMC transmitowana

jest sekwencja sk(t) równa słowu kodowemu v=(v1,

v2,...,vN) o długości N. Sekwencję odebraną oznaczmy

przez r=(r1,...,rN). Ponieważ kolejne próbki szumu w

kanale bezpamięciowym są od siebie niezależne więc

prawdopodobieństwo P(r|v) może być zapisane w

następujący sposób:

gdzie

P(ri|vi)

i jest elementem macierzy

prawdopodobieństw przejść.

Rozpatrzymy teraz dekodowanie

miękkodecyzyjne

Rozpatrzmy transmisję sygnału BPSK przez

kanał AWGN. Niech sekwencja sygnału

oznaczona jako

s=(s1, s2,...,sN)

reprezentuje słowo kodowe v

gdzie

i = {1,0}.

Wówczas funkcja wiarygodności

(prawdopodobieństwo warunkowe) P(r|s)

można zapisać następująco:

Dekodowanie z maksymalną

wiarygodnością - algorytm Viterbiego

( cd)

Do znalezienia najlepszego czyli najbardziej wiarygodnego

(ang. ML) sygnału możemy posłużyć się wykresem

kratowym. Dekoder musi o prostu znaleźć najlepszą

ścieżkę wzdłuż wykresu kratowego. Najlepsza ścieżka, a

właściwie sekwencja przyporządkowana tej ścieżce

najbardziej przypomina (w sensie odległości Hammiga)

odebraną sekwencję kodową. Próba bezpośredniego

rozwiązania tego zadania poprzez rozpatrzenie wszystkich

możliwych ścieżek wykresu kratowego i znalezienie

najlepszej z nich jest niemożliwa do realizacji ponieważ

liczba ścieżek poprzez kratę rośnie wykładniczo z długością

kraty. Nawet w przypadku prostego kodu splotowego

(2,1,2) i dość krótkiej sekwencji sygnału informacyjnego

liczącego N=100 bitów, dekoder musiałby sprawdzić

2100>1030 ścieżek!, co czyni taki sposób podejścia do

zagadnienia bezużytecznym.

Poszczególne kroki

Algorytmu

Viterbiego

Dla każdej kolejnej chwili czasu (nT)

–

Dla każdego stanu końcowego (po prawej stronie segmentu

kraty)

–

Dla każdej gałęzi dochodzącej do tego stanu

–

Oblicz odległość Hamminga odebranej sekwencji sygnału od

sekwencji przyporządkowanej tej gałęzi (stanowiącej jej

etykietę)

–

dodaj metrykę gałęzi (odległość Hamminga) do metryki

ocalonej ścieżki w poprzedni stanie, której gałąź jest

przedłużeniem

–

Wybierz ścieżkę o najmniejszej metryce i zapamiętaj ją jako

ścieżkę ocaloną, apamiętaj jej metrykę. (Pozostaw tylko jedną

ścieżkę ocaloną dochodzącą do każdego stanu. Porzuć

pozostałe ścieżki.)

–

Jeżeli ścieżki ocalałe pokrywają się z pewnym opóźnieniem w

stosunku do chwili bieżącej to możesz dane (bity

informacyjne) przyporządkowane tej części ścieżki uznać jako

najbardziej wiarygodne. Stanowią one wynik działania

dekodera Viterbiego

Działanie

----------------

Miękkodecyzyjny dekoder Viterbiego

(Krok 1)

Rys. 1. Dekodowanie Viterbiego. Liczby powyżej gałęzi oznaczają

metryki gałęzi, metryki ocalonych ścieżek są zapisane w ramkach.

Miękkodecyzyjny dekoder Viterbiego

(Krok 3)

Rys. 3. Dekodowanie Viterbiego. Liczby powyżej gałęzi oznaczają metryki

gałęzi, metryki ocalonych ścieżek i są zapisane w ramkach

Document Outline