Dekodér Viterbi - Viterbi decoder
A Dekodér Viterbi používá Viterbiho algoritmus pro dekódování bitového toku, který byl kódován pomocí a konvoluční kód nebo mřížoví kód.
Existují další algoritmy pro dekódování streamů kódovaných konvolucí (například Algoritmus Fano ). Algoritmus Viterbi je nejvíce náročný na zdroje, ale dělá to maximální pravděpodobnost dekódování. Nejčastěji se používá k dekódování konvolučních kódů s délkami omezení k≤3, ale v praxi se používají hodnoty do k = 15.
Dekódování Viterbi vyvinul Andrew J. Viterbi a zveřejněny v příspěvku Viterbi, A. (duben 1967). "Chybné hranice pro konvoluční kódy a asymptoticky optimální dekódovací algoritmus". Transakce IEEE na teorii informací. 13 (2): 260–269. doi:10.1109 / tit.1967.1054010.
Viterbiho dekodér má hardwarovou (v modemu) i softwarovou implementaci.
Dekódování Viterbi se používá v iterativní Viterbiho dekódování algoritmus.
Hardwarová implementace
Hardwarový dekodér Viterbi pro základní (nepropíchnutý) kód se obvykle skládá z následujících hlavních bloků:
- Metrická jednotka větve (BMU)
- Cesta metrická jednotka (PMU)
- Jednotka Traceback (UTB)
Metrická jednotka větve (BMU)
Funkce pobočkové metrické jednotky je vypočítat pobočkové metriky, což jsou normované vzdálenosti mezi všemi možnými symboly v abecedě kódu a přijatým symbolem.
Existují tvrdé a měkké rozhodnutí Viterbi dekodéry. Tvrdé rozhodnutí Viterbiho dekodér přijímá na svém vstupu jednoduchý bitový tok, a Hammingova vzdálenost se používá jako metrika. Dekodér Viterbi s měkkým rozhodnutím přijímá bitový tok obsahující informace o spolehlivost každého přijatého symbolu. Například v 3bitovém kódování to spolehlivost informace lze kódovat následujícím způsobem:
hodnota | význam | |
---|---|---|
000 | nejsilnější | 0 |
001 | relativně silný | 0 |
010 | relativně slabý | 0 |
011 | nejslabší | 0 |
100 | nejslabší | 1 |
101 | relativně slabý | 1 |
110 | relativně silný | 1 |
111 | nejsilnější | 1 |
Samozřejmě to není jediný způsob, jak zakódovat údaje o spolehlivosti.
The na druhou Euklidovská vzdálenost se používá jako metrika pro dekodéry s měkkým rozhodováním.
Cesta metrická jednotka (PMU)
Jednotka metriky cesty shrnuje metriky větví, pro které lze metriky získat cesty, kde K je délka omezení kódu, z nichž jednu lze nakonec zvolit jako optimální. Každé hodiny rozhodnutí, zahazování vtipně neoptimálních cest. Výsledky těchto rozhodnutí se zapisují do paměti jednotky zpětného sledování.
Základními prvky PMU jsou ACS (Add-Compare-Select) Jednotky. Způsob, jakým jsou mezi sebou propojeni, je definován konkrétním kódem mřížoví diagram.
Protože metriky větví jsou vždy , musí existovat další obvod (není zobrazen na obrázku) zabraňující přetečení metrických čítačů. Alternativní metodou, která eliminuje potřebu sledovat růst metrik cesty, je umožnit „převrácení“ metrik cesty; k použití této metody je nutné se ujistit, že metrické akumulátory cesty obsahují dostatek bitů, aby zabránily tomu, aby se „nejlepší“ a „nejhorší“ hodnoty dostaly do 2(n-1) navzájem. Porovnávací obvod je v podstatě nezměněn.
Je možné monitorovat hladinu šumu na příchozím bitovém toku sledováním rychlosti růstu „nejlepší“ metriky cesty. Jednodušší způsob, jak toho dosáhnout, je monitorovat jedno místo nebo „stav“ a sledovat, jak prochází „nahoru“ řekněme čtyřmi diskrétními úrovněmi v dosahu akumulátoru. Jak prochází vzhůru každou z těchto prahových hodnot, zvyšuje se čítač, který odráží „šum“ přítomný na příchozím signálu.
Jednotka Traceback (UTB)
Jednotka zpětného trasování obnovuje (téměř) cestu maximální pravděpodobnosti z rozhodnutí učiněných PMU. Protože to dělá v opačném směru, obsahuje dekodér viterbi vyrovnávací paměť FILO (first-in-last-out) pro rekonstrukci správného pořadí.
Upozorňujeme, že implementace zobrazená na obrázku vyžaduje dvojnásobnou frekvenci. Existuje několik triků, které tento požadavek vylučují.
Problémy s implementací
Kvantování pro měkké dekódování rozhodnutí
Aby bylo možné plně využít výhod dekódování měkkého rozhodnutí, je třeba správně kvantifikovat vstupní signál. Optimální šířka kvantovací zóny je definována následujícím vzorcem:
kde je spektrální hustota šumového výkonu a k je řada bitů pro měkké rozhodnutí.
Euklidovský metrický výpočet
Na druhou norma () vzdálenost mezi přijatými a skutečnými symboly v abecedě kódu lze dále zjednodušit do podoby lineárního součtu / rozdílu, což z ní činí výpočetně méně náročné.
Zvažte 1/2 konvoluční kodér, který generuje 2 bity (00, 01, 10 nebo 11) pro každý vstupní bit (1 nebo 0). Tyto Návrat k nule signály jsou přeloženy do a Nenávrat k nule formulář zobrazený vedle.
abeceda kódu | vektorové mapování |
---|---|
00 | +1, +1 |
01 | +1, −1 |
10 | −1, +1 |
11 | −1, −1 |
Každý přijatý symbol může být reprezentován ve vektorové formě jako protir = {r0, r1}, kde r0 a r1 jsou měkké rozhodovací hodnoty, jejichž velikosti znamenají společná spolehlivost přijatého vektoru, protir.
Každý symbol v abecedě kódu může být také reprezentován vektorem protii = {±1, ±1}.
Skutečný výpočet euklidovské metriky vzdálenosti je:
Každý čtvercový člen je normovaná vzdálenost zobrazující energie symbolu. Například energie symbolu protii = {± 1, ± 1} lze vypočítat jako
Energetický člen všech symbolů v abecedě kódu je tedy konstantní (v (normalizováno) hodnota 2).
The Přidat-Porovnat-Vybrat (ACS) operace porovnává metrickou vzdálenost mezi přijatým symbolem || vr|| a jakékoli 2 symboly v abecedě kódu, jejichž cesty se slučují v uzlu v odpovídající mříži, || vi(0)|| a || vi(1)||. To je ekvivalentní porovnání
a
Ale shora víme, že energie z protii je konstantní (rovná se (normalizované) hodnotě 2) a energie z protir je v obou případech stejný. To snižuje srovnání s funkcí minima mezi 2 (uprostřed) Tečkovaný produkt podmínky,
protože a min operace se zápornými čísly lze interpretovat jako ekvivalent max operace na kladná množství.
Každý Tečkovaný produkt termín může být rozšířen jako
kde znaky každého výrazu závisí na symbolech, protii(0) a protii(1), ve srovnání. To znamená, že na druhou Euklidovský výpočet metrické vzdálenosti pro výpočet pobočková metrika lze provést jednoduchou operací sčítání / odčítání.
Vystopovat
Obecným přístupem ke zpětnému sledování je hromadit metriky cesty až pro pětinásobek délky omezení (5 (K. - 1)), najděte uzel s největší kumulovanou cenou a začněte zpětné sledování z tohoto uzlu.
Běžně používané pravidlo o zkrácení hloubky pětinásobku paměti (délka omezení K.-1) konvolučního kódu je přesné pouze pro kódy s rychlostí 1/2. Pro libovolnou míru je přesné pravidlo 2,5 (K. - 1)/(1−r) kde r je kódová sazba.[1]
Výpočet uzlu, který nashromáždil největší náklady (největší nebo nejmenší metrika integrální cesty), však zahrnuje nalezení maxima nebo minima několika (obvykle 2K.-1) čísla, která mohou být časově náročná, pokud jsou implementována na vestavěných hardwarových systémech.
Většina komunikačních systémů využívá Viterbiho dekódování zahrnující datové pakety pevné velikosti s pevným bit /byte vzor buď na začátku nebo na konci datového paketu. Použitím známého bit /byte vzor jako reference, počáteční uzel může být nastaven na pevnou hodnotu, čímž se během trasování získá dokonalá cesta maximální pravděpodobnosti.
Omezení
Fyzická implementace dekodéru viterbi nepřinese přesný stream maximální věrohodnosti kvůli kvantování metriky vstupního signálu, větve a cesty a konečné délka zpětného sledování. Praktické implementace se blíží do 1 dB od ideálu.
Výstup dekodéru Viterbi při dekódování zprávy poškozené aditivním gaussovským kanálem obsahuje chyby seskupené do skupin chyb.[2][3]Kódy opravující jednu chybu sám nemůže takové výbuchy opravit, takže buď konvoluční kód a dekodér Viterbi musí být navržen dostatečně výkonný, aby snižoval chyby na přijatelnou míru, nebo kódy pro opravu chyb série musí být použito.
Propíchnuté kódy
Hardwarový dekodér viterbi z propíchnutý kódy je běžně implementován takovým způsobem:
- Depuncturer, který transformuje vstupní proud na proud, který vypadá jako původní (nepropíchnutý) proud se značkami ERASE v místech, kde byly bity vymazány.
- Základní dekodér viterbi, který rozumí těmto značkám ERASE (tj. Nepoužívá je pro výpočet metriky větve).
Implementace softwaru
Jednou z časově nejnáročnějších operací je motýl ACS, který se obvykle implementuje pomocí montážní jazyk a příslušná rozšíření instrukční sady (např SSE2 ) pro urychlení doby dekódování.
Aplikace
Dekódovací algoritmus Viterbi je široce používán v následujících oblastech:
- Rádiová komunikace: digitální televize (ATSC, QAM, DVB-T, atd.), rádiové relé, satelitní komunikace, PSK31 digitální režim pro amatérské rádio.
- Dekódování mřížková kódovaná modulace (TCM), technika používaná v modemech telefonní linky k vymačkání na vysokou úroveň spektrální účinnost z analogových telefonních linek o šířce pásma 3 kHz.
- Počítačová paměťová zařízení jako např pevné disky.
- Automatické rozpoznávání řeči
Reference
- ^ B. Moision, „Pravidlo hloubky zkrácení pro konvoluční kódy,“ 2008 Information Theory and Applications Workshop, San Diego, CA, 2008, str. 555-557, doi:10.1109 / ITA.2008.4601052.
- ^ Stefan Host, Rolf Johannesson, Dmitrij K. Zigangirod, Kamil Sh. Zigangirod a Viktor V. Zyablod.„O distribuci délek trhlin s chybou výstupu pro Viterbiho dekódování konvolučních kódů“.
- ^ Curry, S. J .; Harmon, W. D."Vazba na délku shluku chyby dekodéru Viterbi".
externí odkazy
- Forney, G. David, Jr. (29. dubna 2005). „Viterbiho algoritmus: osobní historie“. arXiv:cs / 0504020.
- Podrobnosti o Viterbiho dekódování a bibliografii.
- Vysvětlení algoritmu Viterbi se zaměřením na problémy s implementací hardwaru.
- r=1/6 k= 15 kódování pro misi Cassini na Saturn.
- Online generátor optimalizovaného softwarového dekodéru Viterbi (GPL).
- Software dekodéru GPL Viterbi pro čtyři standardní kódy.
- Popis a k= 24 Viterbiho dekodér, považovaný za největší v praxi.
- Generický hardware dekodéru Viterbi (GPL).