Inne wersje algorytmu Viterbiego

  1. Algorytm Viterbiego z miękkim wyjściem (ang. Soft Output Viterbi Algorithm - SOVA)

  Algorytm opisywany skrótem SOVA jest odmianą algorytmu Viterbiego. Wprowadza on do tradycyjnego algorytmu dwie modyfikacje. Po pierwsze, metryki stosowane do wybrania najbardziej wiarygodnej ścieżki przez wykres kratowy uwzględniają informację a-priori. Po drugie, algorytm jest tak zmodyfikowany, że dostarcza miękkiej decyzji dotyczącej każdego zdekodowanego bitu.

Rozpatrzmy działanie algorytmu Viterbiego. W każdej chwili t dla każdego stanu następuje wybór najlepszej ścieżki (najbardziej prawdopodobnej) dochodzącej do tego stanu. Po przejściu algorytmu Viterbiego "do przodu" przez wykres kratowy uzyskuje się najbardziej prawdopodobną ścieżkę (ML). Do znalezienia ścieżki ML algorytm Viterbiego potrzebuje znajomości metryk gałęzi w każdym segmencie kraty. Metryka gałęzi może być wyrażona jako dt2-logPi , gdzie d2 jest kwadratem odległości elementu sygnału odebranego od elementu sygnału przypisanego gałęzi, natomiast P i jest prawdopodobieństwem a-priori symbolu informacyjnego i-tego przypisanego tej gałęzi. Metryką gałęzi może być także iloczyn prawdopodobieństw, tak jak to zostało zaproponowane w przykładzie algorytmu Max-Log-MAP.

Hagenauer i Hoehr zauważyli, że prawdopodobieństwo, że decyzja algorytmu Viterbiego jest poprawna jest odwrotnie proporcjonalne do tego jak blisko algorytm znajdował się od podjęcia innej decyzji.

 

Rys. 1. Przykład wykresu kratowego dla binarnego kodu dekodowanego dekoderem SOVA

 

Rozpatrzmy sytuację na rys. 1. Algorytm SOVA znalazł ścieżkę ML. Dla chwili t chce znaleźć miękką informację o wiarygodności podjętej decyzji w chwili t-D, gdzie D jest głębokością decyzji algorytmu Viterbiego. W tym celu dekoder cofa się wzdłuż ścieżki ML zapamiętując wszystkie metryki ścieżek odrzuconych ale dochodzących do ścieżki ML, które zawierają w chwili t-D gałąź z przypisanym bitem informacyjnym przeciwnym do bitu informacyjnego przypisanego ścieżce ML w chwili t-D. Następnie algorytm oblicza różnice pomiędzy metrykami na ścieżce ML i metrykami ścieżek znalezionych w trakcie cofania się od chwili t do chwili t-D. Najmniejsza z tych różnic określa prawdopodobieństwo prawidłowości podjętej decyzji Oczywiście prawdopodobieństwa muszą być znormalizowane, tzn.

Pt (1;O) + Pt(0;O) =1.

Rezultaty algorytmu SOVA , czyli prawdopodobieństwa P(u;O) są bliskie optymalnym wartościom uzyskanym przez algorytm MAP za wyjątkiem małych SNR, kiedy wyniki SOVA stają się zbyt optymistyczne.