Dekodowanie sekwencyjne

Uznane przez Johna Wozencrafta , dekodowanie sekwencyjne jest techniką ograniczonej pamięci do dekodowania kodów drzewa. Dekodowanie sekwencyjne jest używane głównie jako przybliżony algorytm dekodowania dla długich kodów splotowych o ograniczonej długości . To podejście może nie być tak dokładne jak algorytm Viterbiego , ale może zaoszczędzić znaczną ilość pamięci komputera. Został użyty do rozszyfrowania kodu splotowego w Pioneer 9 w 1968 roku .

Dekodowanie sekwencyjne eksploruje kod drzewa w taki sposób, aby spróbować zminimalizować koszty obliczeniowe i wymagania dotyczące pamięci do przechowywania drzewa.

Istnieje szereg metod sekwencyjnego dekodowania opartych na wyborze metryki i algorytmu. Metryki obejmują:

• Metryka fanowska
• Metryka Zigangirowa
• Metryka Gallagera

Algorytmy obejmują:

• Algorytm stosu
• Algorytm Fano
• Algorytm pełzania

Metryka fanowska

Biorąc pod uwagę częściowo zbadane drzewo (reprezentowane przez zestaw węzłów, które są granicą eksploracji), chcielibyśmy znać najlepszy węzeł, z którego można dalej eksplorować. Metryka Fano (nazwana na cześć Roberta Fano ) pozwala obliczyć, który węzeł jest najlepszy do dalszej eksploracji. Ta metryka jest optymalna, biorąc pod uwagę brak innych ograniczeń (np. pamięć).

Dla binarnego kanału symetrycznego (z prawdopodobieństwem błędu $metrykę$ Fano można wyprowadzić za pomocą twierdzenia Bayesa . Jesteśmy zainteresowani $.$ najbardziej prawdopodobną ścieżką, $zbadany$$uwagę$ stan drzewa odebraną sekwencję Używając języka rachunku prawdopodobieństwa i twierdzenia Bayesa chcemy wybrać maksimum nad ${\ Displaystyle i}$ z:

${\ Displaystyle \ Pr (P_ {i} | X, {\ mathbf {r}}) \ propto \ Pr({\mathbf {r}}|P_{i},X)\Pr(P_{i}|X)}$

Wprowadzimy teraz następującą notację:

• ${\ displaystyle N}$ do reprezentowania maksymalnej długości transmisji w oddziałach
• ${\ displaystyle b}$ do reprezentowania liczby bitów w gałęzi kodu (mianownik współczynnika kodowania , R $\ displaystyle R}$ ).
• ${\ displaystyle d_ {i}}$ do reprezentowania liczby błędów bitowych na ścieżce ( odległość Hamminga między etykietami gałęzi a odebraną sekwencją) ${\ displaystyle P_ {i} }$
• ${\ displaystyle n_ {i}}$$być$ w .

Wyrażamy prawdopodobieństwo $re$${\ Displaystyle p ^ {d_ {i}} (1-p) ^ {n_ {i} bd_ {i}} 2 ^ {- (Nn_ {i}) b}}$ - (przy użyciu prawdopodobieństwa binarnego kanału symetrycznego dla pierwszego ${\ displaystyle n_ {i} b}$ bity, po których następuje jednolity przeor nad pozostałymi bitami).

Pr $X)}$ Displaystyle \ Pr (P_ {i} | ​​w kategoriach liczby dokonanych wyborów gałęzi, $}$ liczba gałęzi z każdego węzła ${\ Displaystyle 2 ^ {Rb}}$ .

Dlatego:

${\ Displaystyle {\ rozpocząć {wyrównane} \ Pr (P_ {i} | X, {\ mathbf {r}}) i \ propto p ^ {d_ {i}} ( 1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}2^{-n_{i}Rb}\\&\propto p^{d_ {i}}(1-p)^{n_{i}b-d_{i}}2^{n_{i}b}2^{-n_{i}Rb}\end{wyrównane}}}$

Możemy równoważnie zmaksymalizować logarytm tego prawdopodobieństwa, tj

${\ Displaystyle {\ rozpocząć {wyrównane} i d_ {i} \ log _ {2} p + (n_ {i} bd_ {i}) \ log _ {2}(1-p)+n_{i}b-n_{i}Rb\\=&d_{i}(\log _{2}p+1-R)+(n_{i}b-d_{ i})(\log _{2}(1-p)+1-R)\end{wyrównane}}}$

To ostatnie wyrażenie to metryka Fano. Należy zauważyć, że mamy tutaj dwa terminy: jeden oparty na liczbie błędnych bitów i jeden oparty na liczbie właściwych bitów. Dlatego możemy zaktualizować metrykę Fano po prostu dodając ${\ Displaystyle \ log _ {2} p + 1-R}$ dla każdego niedopasowanego bitu i ${\ displaystyle \ log _ {2} (1-p) + 1-R}$ dla każdego pasującego bitu.

Obliczeniowa stopa odcięcia

Dla sekwencyjnego dekodowania do dobrego wyboru algorytmu dekodowania, liczba eksplorowanych stanów chce pozostać mała (w przeciwnym razie algorytm, który celowo eksploruje wszystkie stany, np. algorytm Viterbiego, może być bardziej odpowiedni). Dla określonego poziomu szumu istnieje maksymalna szybkość kodowania, $obliczeniową$ szybkością odcięcia, przy której istnieje skończona granica cofania. Dla binarnego kanału symetrycznego:

${\ Displaystyle R_ {0} = 1 - \ log _ {2} (1 + 2 {\ sqrt {p (1-p)}} )}$

Algorytmy

Algorytm stosu

Najprostszym algorytmem do opisania jest „algorytm stosu”, w którym przechowywane są najlepsze $.$ znalezione ścieżki Dekodowanie sekwencyjne może wprowadzić dodatkowy błąd powyżej dekodowania Viterbiego, gdy poprawna ścieżka ma $;$ lub więcej ścieżek o wysokiej punktacji w tym momencie najlepsza ścieżka wypadnie ze stosu i nie będzie już brana pod uwagę.

Algorytm Fano

Słynny algorytm Fano (nazwany na cześć Roberta Fano ) ma bardzo niskie zapotrzebowanie na pamięć i dlatego nadaje się do implementacji sprzętowych. Algorytm ten bada wstecz i do przodu od pojedynczego punktu na drzewie.

1. Algorytm Fano to sekwencyjny algorytm dekodowania, który nie wymaga stosu.
2. Algorytm Fano może działać tylko na drzewie kodu, ponieważ nie może badać łączenia ścieżek.
3. Na każdym etapie dekodowania algorytm Fano zachowuje informacje dotyczące trzech ścieżek: bieżącej ścieżki, ścieżki jej bezpośredniego poprzednika i jednej z kolejnych ścieżek.
4. W oparciu o te informacje algorytm Fano może przejść z bieżącej ścieżki do ścieżki bezpośrednio poprzedzającej lub wybranej ścieżki następczej; stąd żaden stos nie jest wymagany do kolejkowania wszystkich badanych ścieżek.
5. Ruch algorytmu Fano jest kierowany dynamicznym progiem T , który jest całkowitą wielokrotnością ustalonej wielkości kroku ¢.
6. Tylko ścieżka, której metryka ścieżki jest nie mniejsza niż T, może być następnie odwiedzona. Zgodnie z algorytmem proces wyszukiwania słowa kodowego posuwa się naprzód wzdłuż ścieżki kodu, o ile metryka Fano wzdłuż ścieżki kodu nie maleje.
7. Gdy wszystkie kolejne metryki ścieżki są mniejsze niż T , algorytm cofa się do poprzedniej ścieżki, jeśli poprzednia metryka ścieżki jest większa od T ; następnie badanie progowe zostanie następnie przeprowadzone na innej ścieżce będącej następcą tego ponownie odwiedzonego poprzednika.
8. W przypadku, gdy poprzednia metryka ścieżki jest również mniejsza niż T , próg T jest obniżany o jeden krok tak, że algorytm nie jest uwięziony na bieżącej ścieżce.
9. W przypadku algorytmu Fano, jeśli ścieżka jest ponownie odwiedzana, obecnie badany próg dynamiki jest zawsze niższy niż chwilowy próg dynamiki podczas poprzedniej wizyty, co gwarantuje, że algorytm nie zapętli się i że algorytm może ostatecznie dotrzeć do końcowego węzła drzewo kodów i zatrzymaj się.

•   John Wozencraft i B. Reiffen, Dekodowanie sekwencyjne , ISBN 0-262-23006-2
•   Rolf Johannesson i Kamil Sh. Zigangirov, Podstawy kodowania splotowego (rozdział 6), ISBN 0-470-27683-5

Linki zewnętrzne

• " Drzewa korekcyjne " - symulator procesu korekcji wykorzystujący kolejkę priorytetową do wyboru maksymalnego węzła metrycznego (zwanego wagą)