Viterbi konvolúciós dekódoló algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 14-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

1967-ben Andrew Viterbi kifejlesztett és elemzett egy dekódoló algoritmust , amely a maximális valószínűség elvén alapul . Az algoritmus optimalizálása egy adott kódrács szerkezeti jellemzőinek felhasználásával történik. A Viterbi dekódolás előnye a brute-force dekódolással szemben, hogy a Viterbi dekóder összetettsége nem a kódszó sorozatban lévő szimbólumok számától függ .

Az algoritmus magában foglalja a hasonlóság mértékének (vagy távolságának ) kiszámítását a t időpontban vett jel és a t időpontban minden állapotba belépő összes rácsút között . A Viterbi algoritmus nem veszi figyelembe azokat a rácsutakat, amelyek a maximum likelihood elv szerint nem lehetnek optimálisak. Ha két út ugyanabba az állapotba kerül, akkor a legjobb metrikával rendelkezőt választjuk ; az ilyen utat túlélésnek hívják . A túlélő utak kiválasztását minden állapothoz elvégezzük. Így a dekóder mélyebbre megy a rácsba, és a kevésbé valószínű utak kiküszöbölésével hoz döntéseket. A valószínűtlen utak előzetes elutasítása leegyszerűsíti a dekódolási folyamatot. 1969-ben Jim Omura kimutatta, hogy a Viterbi algoritmus alapja a maximális valószínűség becslése . Ne feledje, hogy az optimális útvonal-kiválasztási probléma kifejezhető egy maximális valószínűségi mérőszámmal vagy egy minimális távolságmérővel rendelkező kódszó kiválasztásával . ${\displaystyle t_{I))$ $t_{i}$

A módszer lényege

A korrekciós kódok legjobb dekódolási sémája a maximális valószínűségű dekódolás , amikor a dekódoló meghatározza az összes lehetséges kódvektornak megfelelő feltételes valószínűségek halmazát , és a maximumnak megfelelő kódszó mellett dönt . Memória nélküli bináris szimmetrikus csatornánál (olyan csatornánál, amelyben a 0 és 1 átviteli valószínűségek, valamint a 0 -> 1 és 1 -> 0 alakú hibavalószínűségek azonosak, a hibák a j-edik és az i- a kód szimbólumai függetlenek), a maximális valószínűségi dekóder a minimális Hamming-távolság dekóderére csökken . Ez utóbbi kiszámítja a Hamming-távolságot a vett r sorozat és az összes lehetséges kódvektor között , és a vett vektorhoz közelebbi vektor mellett dönt. Természetesen általános esetben egy ilyen dekóder még nagy kódméretek esetén is nagyon bonyolultnak bizonyul, és gyakorlatilag megvalósíthatatlan. A konvolúciós kódok jellegzetes struktúrája (a hosszúságú ablakon kívüli struktúra ismételhetősége ) lehetővé teszi egy olyan maximális likelihood dekóder létrehozását, amely komplexitás szempontjából meglehetősen elfogadható. $P(r/U_{i})$ $U_{i}$ $P(r/U_{i})$ $U_{i}$ $n$ $k$ $n$

A dekóder működési elve

A dekóder bemenete a szekvencia egy olyan szegmensét fogadja , amelynek hossza meghaladja a blokk kódhosszát . Nevezzük dekódoló ablaknak. Hasonlítsuk össze az adott kód összes kódszavát (hosszúságú szegmensen belül ) a fogadott szóval, és válasszuk ki a fogadotthoz legközelebb eső kódszót. A kiválasztott kódszó első információs kerete a dekódolt szó információs keretének becsléseként kerül vételre. Ezt követően az új szimbólumok bekerülnek a dekódolóba , és a korábban bevitt legrégebbi szimbólumokat eldobják, és a folyamat megismétlődik a következő információs keret meghatározásához. Így a Viterbi dekóder képkockáról képkockára szekvenciálisan dolgoz fel, a kódoló által használthoz hasonló rács mentén haladva. A dekódoló adott időpontban nem tudja, hogy melyik csomópontban van a kódoló, és nem kísérli meg dekódolni. Ehelyett a dekódoló meghatározza a vett sorozatból a legvalószínűbb útvonalat az egyes csomópontokhoz, és meghatározza az egyes ilyen útvonalak és a vett sorozat közötti távolságot. Ezt a távolságot az út divergenciájának mértékének nevezzük. A vett sorozat becsléseként a legkisebb eltérést mutató szegmens kerül kiválasztásra. A legkisebb eltérésű utat túlélő útnak nevezzük. $r$ $b$ $n$ $b$ $b$ $n_{0}$ $n_{0}$

Példa

Tekintsük a Viterbi dekóder működését egy egyszerű példa segítségével. Úgy gondoljuk, hogy a kódolás konvolúciós (7,5) kóddal történik . A kódoló rácsos diagramját használva próbáljuk meg néhány szegmens segítségével követni a kódoló legvalószínűbb útvonalát. Ebben az esetben a rácsos diagram minden szakaszánál feljegyezzük az egyes csomópontokhoz vezető út eltérésének mértékét. Tegyük fel, hogy az U = (00000000…) kódsorozat kerül továbbításra, és a vett sorozat r = (10001000…) alakú, vagyis a kódszó első és harmadik keretében hiba történt. Amint azt már láttuk, a dekódolási eljárás és az eredmény nem függ a továbbított kódszótól, és csak a vett sorozatban található hiba határozza meg. Ezért a legegyszerűbb azt feltételezni, hogy a nulla szekvencia kerül átvitelre, azaz U = (00000000 ...). Miután megkapta az első szimbólumpárt (10), a dekóder meghatározza a divergencia mértékét a rács első szakaszára, miután megkapta a következő szimbólumpárt (00), a második szakaszra stb. Az egyes csomópontokban szereplő utakat kisebb divergenciával hagyjuk el, mivel a nagyobb áramdivergenciajú út a jövőben már nem rövidülhet. Vegye figyelembe, hogy a vizsgált példában a negyedik szinttől kezdve a nulla útvonal metrikája (vagy eltérés mértéke) kisebb, mint bármely más metrika. Mivel nem volt több hiba a csatornában, egyértelmű, hogy végül ezt az utat választják válaszul. Ez a példa is azt mutatja, hogy a fennmaradt utak meglehetősen hosszú ideig különbözhetnek egymástól. A hatodik vagy hetedik szinten azonban az összes fennmaradt ösvény első hét széle egybeesik egymással. Ebben a pillanatban a Viterbi algoritmus szerint döntés születik a továbbított szimbólumokról, mivel minden fennmaradt út ugyanabból a csúcsból jön ki, azaz egy információs szimbólumnak felel meg. $r$

Azt, hogy a fennmaradt utak milyen mélységben egyesülnek, előre nem számítható ki; ez egy valószínűségi változó, amely a csatornában előforduló hibák többszörösétől és valószínűségétől függ. Ezért a gyakorlatban az ember általában nem vár az útvonal-összevonásra, hanem beállít egy fix dekódolási mélységet.

Az i) lépésben a helyes és a hibás útvonal metrikái közötti különbség mértéke kellően nagy ( , ), vagyis ebben az esetben a dekódolási mélységet -ra korlátozni lehetne . De néha az adott szakaszhoz vezető út a legrövidebbnek bizonyulhat, ezért nem kell különösebben elragadtatnia a b dekódoló ablak méretének csökkentését a dekódoló munkájának egyszerűsítése érdekében. A gyakorlatban a dekódolási mélységet általában a tartományban választják meg , ahol az adott kód által kijavított hibák száma. Annak ellenére, hogy a vett töredékben két hiba is előfordult, a dekódolás hiba nélkül ment végbe, és a továbbított nulla sorozatot válaszként elfogadjuk. $d_{correct}=2$ $d_{error}=4$ $b<=6$ $n<b<n+l$ $l$

Lásd még

Viterbi algoritmus

Irodalom

"Error Bounds for Convolutional Codes and an Asymptoticically Optimum Decoding Algorithm", IEEE Transactions on Information Theory, IT-13. kötet, 260-269. o., 1967. április.
Viterbi A. D., Omura J. K. A digitális kommunikáció és kódolás alapelvei / Per. angolról. szerk. K. Sh. Zigangirova. - M .: Rádió és kommunikáció, 1982. - 536 p.
Zolotarev V. V., Ovechkin G. V. Zajgátló kódolás. Módszerek és algoritmusok: Kézikönyv / Under. szerk. Levelező tag RAS Yu. B. Zubarev. - M .: Hotline-Telecom, 2004.
Kartashevsky V. G., Mishin D. V. Kódolt jelek vétele memóriával rendelkező csatornákon - Rádió és kommunikáció, 2004.
Morelos-Zaragoza R. A hibajavító kódolás művészete. Módszerek, algoritmusok, alkalmazás / per. angolról. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 p. — (A kommunikáció világa). - 2000 példányban. — ISBN 5-94836-035-0 .
Bernard Sklar. Digitális kommunikáció. Elméleti alapok és gyakorlati alkalmazás = Digital Communications: Fundamentals and Applications. - 2. kiadás - M . : "Williams" , 2007. - S. 1104. - ISBN 0-13-084788-7 .