1

1

Algorytm Viterbiego

Algorytm Viterbiego

2

2

Wstęp

Wstęp

Jego pierwszym zastosowaniem było,

Jego pierwszym zastosowaniem było,

i nadal jest,

i nadal jest,

dekodowanie

dekodowanie

kodów splotowych

kodów splotowych

. Jednak stosowany

. Jednak stosowany

jest również w innych

jest również w innych

zaawansowanych technologiach

zaawansowanych technologiach

telekomunikacyjnych, np. jako

telekomunikacyjnych, np. jako

odbiornik

odbiornik

nieliniowy dla kanału z

nieliniowy dla kanału z

interferencją międzysymbolową

interferencją międzysymbolową

.

.

3

3

•

Działanie tego algorytmu oparte jest o

Działanie tego algorytmu oparte jest o

kryterium maksymalnej wiarygodności,

kryterium maksymalnej wiarygodności,

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

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

dojścia przez dekoder do aktualnego

dojścia przez dekoder do aktualnego

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

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

najmniejszej metryce dojścia do

najmniejszej metryce dojścia do

któregoś ze stanów poprzednich oraz

któregoś ze stanów poprzednich oraz

przejścia do aktualnego stanu. Jak widać

przejścia do aktualnego stanu. Jak widać

proces ten jest procesem iteracyjnym

proces ten jest procesem iteracyjnym

4

4

Dekodowane z maksymalną

Dekodowane z maksymalną

wiarygodnością - algorytm

wiarygodnością - algorytm

Viterbiego

Viterbiego

•

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

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

koderów możemy rozpatrzyć dekodowanie

koderów możemy rozpatrzyć dekodowanie

Viterbiego. (Istnieje wiele sposobów dekodowania

Viterbiego. (Istnieje wiele sposobów dekodowania

kodów splotowych. Dekodowanie sekwencyjne

kodów splotowych. Dekodowanie sekwencyjne

zaproponowali Wozencraft , Fano , Zigangirov i

zaproponowali Wozencraft , Fano , Zigangirov i

Jelinek . Dekodowanie metodą większościową

Jelinek . Dekodowanie metodą większościową

zaproponował Massey.)

zaproponował Massey.)

•

W roku 1967 Viterbi publikował swój algorytm

W roku 1967 Viterbi publikował swój algorytm

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

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

okazał się być algorytmem maksymalnej

okazał się być algorytmem maksymalnej

wiarygodności równoważnym rozwiązaniu

wiarygodności równoważnym rozwiązaniu

zagadnienia poszukiwania najkrótszej drogi

zagadnienia poszukiwania najkrótszej drogi

poprzez graf metodą programowania

poprzez graf metodą programowania

dynamicznego

dynamicznego

5

5

Zasada dekodowania z maksymalną

Zasada dekodowania z maksymalną

wiarygodnością

wiarygodnością

(ang. maximum likehood - ML)

(ang. maximum likehood - ML)

•

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

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

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

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

np. sekwencję sk(t), do której w kanale AWGN dodawany jest szum n(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

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

sekwencja, która maksymalizuje prawdopodobieństwo warunkowe

sekwencja, która maksymalizuje prawdopodobieństwo warunkowe

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

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

po wszystkich i.

po wszystkich i.

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

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

6

6

The maximum-likelihood decoding -

The maximum-likelihood decoding -

Viterbi algorithm

Viterbi algorithm

•

Na

Na

rys. 1.

rys. 1.

pokazany jest model

pokazany jest model

binarnego kanału symetrycznego

binarnego kanału symetrycznego

(ang. binary symmetric channel -

(ang. binary symmetric channel -

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

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

prawdopodobieństwem, że symbol

prawdopodobieństwem, że symbol

nadany został prawidłowo odebrany,

nadany został prawidłowo odebrany,

natomiast niech p=1-q będzie

natomiast niech p=1-q będzie

prawdopodobieństwem, że symbol

prawdopodobieństwem, że symbol

nadany został odebrany błędnie.

nadany został odebrany błędnie.

7

7

Rys.1 Binary symmetric channel - BSC

Rys.1 Binary symmetric channel - BSC

8

8

•

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

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

•

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

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

bezpamięciowym

bezpamięciowym

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

, 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

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

•

Kanał dyskretny

Kanał dyskretny

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

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 -

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

(DMC).

(DMC).

9

9

Rozpatrzymy dwa przypadki algorytmu Viterbiego :

Rozpatrzymy dwa przypadki algorytmu Viterbiego :

•

1. Dekodowanie twardodecyzyjne

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

10

10

Rozpatrzymy teraz dekodowanie

Rozpatrzymy teraz dekodowanie

miękkodecyzyjne

miękkodecyzyjne

.

.

Rozpatrzmy transmisję sygnału BPSK przez

Rozpatrzmy transmisję sygnału BPSK przez

kanał AWGN. Niech sekwencja sygnału

kanał AWGN. Niech sekwencja sygnału

oznaczona jako

oznaczona jako

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

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

reprezentuje słowo kodowe v

reprezentuje słowo kodowe v

gdzie

gdzie

v

v

i = {1,0}.

i = {1,0}.

Wówczas funkcja wiarygodności

Wówczas funkcja wiarygodności

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

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

można zapisać następująco:

można zapisać następująco:

 

 

11

11

Dekodowanie z maksymalną

Dekodowanie z maksymalną

wiarygodnością - algorytm Viterbiego

wiarygodnością - algorytm Viterbiego

( cd)

( cd)

Do znalezienia najlepszego czyli najbardziej wiarygodnego

Do znalezienia najlepszego czyli najbardziej wiarygodnego

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

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

kratowym. Dekoder musi o prostu znaleźć najlepszą

kratowym. Dekoder musi o prostu znaleźć najlepszą

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

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

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

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

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

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

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

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

rozwiązania tego zadania poprzez rozpatrzenie wszystkich

rozwiązania tego zadania poprzez rozpatrzenie wszystkich

możliwych ścieżek wykresu kratowego i znalezienie

możliwych ścieżek wykresu kratowego i znalezienie

najlepszej z nich jest niemożliwa do realizacji ponieważ

najlepszej z nich jest niemożliwa do realizacji ponieważ

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

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

kraty. Nawet w przypadku prostego kodu splotowego

kraty. Nawet w przypadku prostego kodu splotowego

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

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

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

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

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

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

zagadnienia bezużytecznym.

zagadnienia bezużytecznym.

12

12

Poszczególne kroki

Poszczególne kroki

Algorytmu

Algorytmu

Viterbiego

Viterbiego

--

--

Dla każdej kolejnej chwili czasu (nT)

Dla każdej kolejnej chwili czasu (nT)

–

 

 

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

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

kraty)

kraty)

–

 

 

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

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

–

 

 

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

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

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

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

etykietę)

etykietę)

–

 

 

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

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

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

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

przedłużeniem

przedłużeniem

–

 

 

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

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

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

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

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

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

pozostałe ścieżki.)

pozostałe ścieżki.)

–

 

 

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

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

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

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

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

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

najbardziej wiarygodne. Stanowią one wynik działania

najbardziej wiarygodne. Stanowią one wynik działania

dekodera Viterbiego

dekodera Viterbiego

13

13

Działanie

Działanie

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

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

Miękkodecyzyjny dekoder Viterbiego

Miękkodecyzyjny dekoder Viterbiego

(Krok 1)

(Krok 1)

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

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

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

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

14

14

Miękkodecyzyjny dekoder

Miękkodecyzyjny dekoder

Viterbiego

Viterbiego

(Krok 2)

(Krok 2)

15

15

Miękkodecyzyjny dekoder Viterbiego

Miękkodecyzyjny dekoder Viterbiego

(Krok 3)

(Krok 3)

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

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

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

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

16

16

Miękkodecyzyjny dekoder Viterbiego

Miękkodecyzyjny dekoder Viterbiego

(Krok 4)

(Krok 4)

17

17

Miękkodecyzyjny dekoder Viterbiego

Miękkodecyzyjny dekoder Viterbiego

(Krok 5)

(Krok 5)

18

18

Miękkodecyzyjny dekoder Viterbiego

Miękkodecyzyjny dekoder Viterbiego

(Krok 6)

(Krok 6)

Sekwencja kodowa (binarna) przyporządkowana do tej ścieżki

Sekwencja kodowa (binarna) przyporządkowana do tej ścieżki

wynosi 11 10 00 01 01 11

wynosi 11 10 00 01 01 11

19

19

MAŁY, KRÓTKI TEŚCIK

MAŁY, KRÓTKI TEŚCIK





20

20

21

21

22

22

23

23

24

24

25

25

26

26

27

27