Mřížkové kódování Ivan Pravda
Autor: Ivan Pravda Název díla: Mřížkové kódování Zpracoval(a): České vysoké učení technické v Praze Fakulta elektrotechnická Kontaktní adresa: Technická 2, Praha 6
Inovace předmětů a studijních materiálů pro e-learningovou výuku v prezenční a kombinované formě studia
Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti
VYSVĚTLIVKY
Definice
Zajímavost
Poznámka
Příklad
Shrnutí
Výhody
Nevýhody
ANOTACE Modul se podrobně věnuje problematice a významu kódování v současných telekomunikačních sítích. Modul zahrnuje popis konvolučních kódů a vysvětlení principu jejich vlastností. Dále je zde uvedena problematika paralelního zřetězení související s implementací moderních typů kódovacích předpisů známých dnes jak tzv. TURBO kódy a zmíněny možnosti detekce prvků přenášené informační posloupnosti.
CÍLE Student má možnost se podrobněji seznámit s problematikou kódování využívaného napříč různými typy telekomunikačních sítí. Výklad je v modulu podrobněji věnován konvolučním kódům v návaznosti na jejich možné paralelní zřetězení, které je promítnuto do implementace moderních TURBO kódů. Student zde najde popis a definici konvolučních kódů, chování kodérů a dekodérů příslušných kódů. V neposlední řadě jsou zde uvedeny možnosti a navržena možná řešení pro detekci jednotlivých prvků přenášené informační posloupnosti, tzv. tvrdé a měkké rozhodování.
LITERATURA [1]
Vlček, K.: Komprese a kódová zabezpečení v multimediálních komunikacích (2.vydání). Nakladatelství BEN – technická literatura, Praha 2004. 260 str. ISBN 807300-134-9.
[2]
Dobeš, J.; Žalud, V.: Moderní radiotechnika (1.vydání). Nakladatelství BEN – technická literatura, Praha 2006. 768 str. ISBN 80-7300-132-2.
[3]
Schlegel, Ch.: Trellis Coding. IEEE Press, New York 1997. 274 p. ISBN 0-7803-10527.
[4]
Adámek, J.: Kódování. Státní nakladatelství technické literatury (SNTL), Praha 1989. 191 str.
[5]
Adámek, J.: Foundations od Coding: Theory and Applications of Error-Correcting Codes With an Introduction to Cryptography and Information Theory. John Wiley & Sons, Inc. 1991. 352 p. ISBN 0-471-62187-0.
Obsah 1 Konvoluční kódy................................................................................................................... 6 1.1
Vlastnosti konvolučního kódování ............................................................................. 6
1.2
Rozdíl v popisu konvolučních kódů a kodérů ............................................................ 8
1.3
Definice konvolučního kódu ...................................................................................... 9
1.4
Definice kodéru konvolučního kódu ........................................................................ 11
1.5
Popisy chování konvolučního kodéru ...................................................................... 13
1.6
Minimální kódová vzdálenost konvolučního kódu .................................................. 16
1.7
Dekódování konvolučního kódu .............................................................................. 17
1.8
Konvoluční kódy řešitelné pomocí syndromu.......................................................... 19
1.9
Tvrdé a měkké rozhodování ..................................................................................... 21
1.10
Kódování konvolučního WA-kódu .......................................................................... 23
1.11
Dekódování a oprava chyb u WA-kódu ................................................................... 25
1.12
Kodér WA-kódu ....................................................................................................... 27
1.13
Dekódování konvolučního WA-kódu ...................................................................... 29
1.14
Srovnání účinnosti Hammingova kódu a WA-kódu pro TV .................................... 31
2 TURBO kódy ...................................................................................................................... 33 2.1
Paralelní zřetězení .................................................................................................... 33
2.2
Rekurzivní kodér ...................................................................................................... 35
2.3
Kodér TURBO kódu ................................................................................................ 36
2.4
Dekódování .............................................................................................................. 38
2.5
Dekodér TURBO kódu ............................................................................................. 39
2.6
Výkonnost TURBO kódu ......................................................................................... 41
2.7
Závěrečný test........................................................................................................... 44
1 Konvoluční kódy 1.1 Vlastnosti konvolučního kódování Obecně lze říci, že hlavním účelem zavádění různých typů kódů a kódovacích schémat, je zvýšení spolehlivosti přenosu informací nezávisle na metodách jeho zabezpečení (parita, cyklické kódy), což ve svém důsledku přináší podstatné zvýšení pravděpodobnosti bezchybného rozpoznání přijatého signálového prvku. Kodéry lze v zásadě rozdělit na dvě kategorie. První kategorii kodérů lze označit jako tzv. zdroje zpráv bez paměti. Toto označení vychází z rozboru činnosti kodérů. Jako zdroje zpráv bez paměti jsou označovány ty kodéry, které vždy, když je na jejich vstup přivedena informační posloupnost, se na jejich výstupu objeví kódová posloupnost. Jinými slovy řečeno, n-tice kódové posloupnosti je závislá POUZE na k-tici aktuální (právě zpracovávané) informační posloupnosti. Druhá kategorie kodérů je označována jako tzv. zdroje zpráv s pamětí. Do této kategorie spadají i konvoluční kodéry. Konvoluční kódy jsou předpisem pro kódový systém, který generuje kódová slova na základě obsahu rámce několika vstupních slov. To, jakým způsobem bude zakódována určitá informační posloupnost, tedy závisí nejenom na aktuální vstupní informační posloupnosti, ale také na m předchozích informačních slovech. Konvoluční kódy lze popsat pomocí generujících polynomů a generujících matic. Ze znalosti generujících polynomů, resp. generujících matic, lze odvodit postupy dekódování, které umožňují provádět vlastní opravu chyb. Nejznámějším postupem je tzv. Viterbiho algoritmus. Základní vlastností konvolučních kódů je LINEARITA. Tuto vlastnost je možné matematicky popsat pomocí následující relace – v ( x ) = K u ( x ) . Pro předpis kódování K, má-li splňovat požadavky exaktní řešitelnosti, pak musí platit, že: 1. Kód K je lineární, tj. K u ( x ) + u´( x ) = K u ( x ) + K u´( x ) a K t ⋅ u ( x ) = t ⋅ K u ( x ) .
2. Kód K je časově invariantní (stálý, neměnný), tzn. že časové zpoždění o k kroků na vstupu kodéru vyvolá odpovídající časové zpoždění o n kroků
na výstupu kodéru. Časová zpoždění jsou vyjádřena pomocí polynomů K x k ⋅ u ( x ) = x k ⋅ K u ( x ) . 3. Kód K nevyžaduje zdroj s pamětí, jestliže je kódové slovo závislé pouze na aktuální k-tici informační posloupnosti a nikoliv na k-ticích, které byly na vstupu v době vytvoření předešlých kódových slov. V souvislosti s bodem 2., ve kterém je popisována podmínka časové invariantnosti, to znamená, že změna k symbolů informačního slova u na vstupu kodéru způsobí pouze změnu prvních n symbolů kódové zprávy na výstupu kodéru.
7
1.2 Rozdíl v popisu konvolučních kódů a kodérů Při popisu konvolučního kódování se často směšují definice pojmů konvoluční kód a konvoluční kodér. Pojmy konvoluční kód a konvoluční kodér jsou sice v úzkém vztahu, ale jsou to zároveň rozdílné pojmy. Abychom zabránili tomuto směšování, je nezbytné, abychom porozuměli rozdílům mezi příbuznými pojmy: •
konvoluční kodér,
•
operace konvolučního kódování a
•
konvoluční kód.
Kodér je součástka nebo stroj, operace kódování je prováděna kodérem. Objekty, které jsou kódovány, jsou informační posloupnosti a odpovídající výstupy jsou kódové posloupnosti. Konečně pak konvoluční kód je soubor kódových posloupností, které odpovídají všem možným informačním posloupnostem.
V souhrnu to znamená, že konvoluční kodér specifikuje strukturu obvodového zapojení a konvoluční kód pak udává strukturu kódových posloupností. Definice konvolučního kodéru, které lze nalézt v literatuře, se liší podle stupně zobecnění. Existují dvě úrovně – matematická a obvodově realizační. Je zde však také i otázka pořadí, v nichž jsou pojmy kód a kodér definovány. V literatuře se opět objevují dva přístupy. První přístup definuje nejdříve pojem kód, a to jako k-rozměrný podprostor n-rozměrného vektorového prostoru nad vhodným tělesem, pojem kodér pak definuje jako matici o rozměrech n × k, jejíž řádky jsou tvořeny bází kódu. Druhý přístup definuje pojem kodér jako lineární sekvenční obvod LSC (Linear Sequential Circuit) s k-vstupy a n-výstupy a pojem kód jako soubor výstupních posloupností generovaných kodérem pro všechny možné vstupní posloupnosti. Dle prvního přístupu je kód řádkem v generující matici kodéru, dle druhého přístupu realizuje LSC zobrazení mezi k-rozměrným a n-rozměrným vektorovým prostorem, jehož obrazovým souborem je kód. Srovnáním obou těchto přístupů zjistíme, že oba popisují totéž, i když v různém pořadí.
8
1.3 Definice konvolučního kódu Předpis pro konvoluční kódování K je vyjádřen linearitou a časovou invariantností. Podmínka, popisovaná jako zdroj zpráv bez paměti, pro konvoluční kódy NEPLATÍ. Na základě těchto poznatků je možné vyslovit nejobecnější definici konvolučního kódu. Nechť F je konečné těles. Jako konvoluční (n, k)-kód je míněn takový předpis K, který přiřazuje pro každý mnohočlen u(x) nad tělesem F mnohočlen K[u(x)], který je lineární a časově invariantní.
Definice může být popsána také zapojením kodéru konvolučního kódu. Takový popis je pak ekvivalentní popisu pomocí tzv. generujícího polynomu. Konvoluční kodér může být tvořen ze dvou klopných obvodů posuvného registru, ze tří obvodů pro sčítání MODULO 2 a z dvoubitové výstupní vyrovnávací paměti, která v každém kroku, ve kterém kodér přijímá jeden bit informačního slova, vysílá dva bity kódového slova. Mezi vstupním a výstupním slovem je lineární vztah. Ke zpracování jsou použity pouze lineární prvky.
Kodér konvolučního (2, 1)-kódu s g(x) = 1 + x + x2 + x3 + x5
Časová invariance obvodu se projevuje tím, že je-li před vstupní informační slovo zařazena jedna prodleva, tzn. jedna nula navíc, projeví se to na výstupu kodéru dvěma nulami před odpovídajícím kódovým slovem. Zadaný kodér realizuje konvoluční (2, 1)-kód. Na začátku pozorování je v posuvném registru nulový obsah. Odezva na symbol 1 na vstupu kodéru je kombinace symbolů 11 na výstupu kodéru. Při prvním posuvu je odezvou rovněž kombinace symbolů 11. Při druhém posuvu je odezva na výstupu kodéru kombinací symbolů 01. Při třetím posuvu jsou v posuvném registru již pouze symboly 0. Použijeme-li pro zápis mnohočlenů, můžeme předchozí operace zapsat následovně – K[1] = 111101 = 1 + x + x2 + x3 + x5. Platí časová invariantnost – K[01] = 00111101, K[001] = 0000111101, atd. Linearitu 9
kódu je možné ověřit tím, že vytvoříme rozklad slova 101 = 100 + 001 a platí – K[101] = K[1] + K[001] = 1111101101. Konvoluční kodéry jsou nejčastěji realizovány posuvnými registry s odlišnou rychlostí posuvu (viz následující obrázek). V jednom kroku, ve kterém je vytvořeno kódové slovo, dojde k posuvu na vstupu kodéru o k bitů informačního slova, ale na výstupu kodéru bude posuv o n bitů kódového slova.
Obecné blokové schéma konvolučního kodéru
Přepínač na vstupu kodéru slouží k převodu sériové bitové posloupnosti na vstupní paralelní kombinaci ut a přepínač na výstupu kodéru převádí kombinaci vt zpět na sériovou bitovou posloupnost. Významným parametrem konvolučních kódů je tzv. omezující délka (Constraint Length), která udává, kolik k-tic zdrojových symbolů ovlivňuje jednu n-tici kódových symbolů, respektive kolik ntic kódových symbolů je ovlivňováno jednou k-ticí zdrojových symbolů. Kódový poměr je pak vyjadřován podílem k/n.
10
1.4 Definice kodéru konvolučního kódu Kodér je stroj, který přijímá k-tice ui jako vstupy v čase i a vytváří n-tice vi jako výstupy rovněž v čase i. Stroj má paměť tj. n-tice vi je výslednicí působení nejen k-tice ui, ale také informací obsažených v k-ticích uj, kde j ≠ i.
Závislost kódové posloupnosti na zdrojové posloupnosti popisuje generující matice. Jako příklad kodéru konvolučního kódu je zadán následující kodér. Generující posloupnost kódu vypočítáme přivedením 1 na vstup. Výsledkem je posloupnost 11101100…, které odpovídá generující mnohočlen 2 4 5 g ( x ) = 1 + x + x + x + x . Z generujících mnohočlenů je sestavena generující matice. V případě, že generujících mnohočlenů je více, jsou napsány pod sebou bez posunutí a tvoří blok o stejné délce. Další pokračování generující matice je vytvořeno s ohledem na počet výstupních bitů kódového slova v jednom kroku kódování. V tomto případě jsou v každém kroku vytvářeny dva bity, posunutí dalšího pokračování bude tedy o dvě pozice doprava. Generující matice má tedy tvar:
1 0 0 G= 0 .. ..
1 1 0 1 1 0 0 .. .. 0 1 1 1 0 1 1 .. .. 0 0 0 1 1 1 0 .. .. 0 0 0 0 0 1 1 .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Generující matice není ukončena, protože konvoluční kódy nemají blokovou strukturu. Pro zachycení zdrojové posloupnosti jsou většinou rozměry matice nepraktické. Pro výpočet kódových slov jsou výhodnější vyjádření pomocí mnohočlenů. Názornou grafickou možností popisu je tzv. mřížkový diagram (trellis diagram).
Mřížkový diagram je grafickým znázorněním, které je ekvivalentní úplnému kódovému stromu, ale má sloučené shodné stavy. Pro kodér z předchozího příkladu je mřížkový diagram znázorněn na následujícím obrázku. Jednotlivé posloupnosti stavů jsou nazývány pojmem cesta (path). Nechť zdrojová posloupnost je 10011. Kódová posloupnost je 1110111101. Kodér je na počátku zprávy v nulovém stavu. Začátku zprávy odpovídá prvních pět kroků (0 až 4) v levé části obrázku. Pravá část obrázku ukazuje konec zakódované zprávy. Zdrojová posloupnost 10011 byla doplněna o nuly, které se nazývají pojmem 11
konec zprávy (tail of the message). Kódová posloupnost pokračuje tak, aby se kodér dostal po odeslání zdrojových bitů zpět do nulového stavu. Počet připojených nul je k(K-1). Výstupní kódová posloupnost je tedy 11101111010111.
Začátek a konec zprávy konvolučního kodéru (2, 1)-kódu s generujícím mnohočlenem g(x) = 1 + x + x2 + x4 + x5
12
1.5 Popisy chování konvolučního kodéru Popis pomocí tabulky V následující tabulce se ukážeme odezvu na posloupnost u = [u0; u1; u2] = [1;0;0] pro kodér podle obrázku 1 uvedeného v kapitole 3. Výstup za prvým registrem typu D je označen ut-1, výstup za druhým registrem ut-2. Ve výchozím klidovém stavu jsou oba registry vynulovány (ve sloupcích B a C tabulky jsou nuly) a na vstup přichází hodnota u0 =1 (sloupec A tabulky), což odpovídá řádku 2 tabulky. Odezvou budou jedničky ve sloupcích F a G, tedy v01 =1; v02 =1. V následném stavu přejdeme podle hodnot v řádku 2 sloupců D a E ut-1 =1 a ut-2 = 0 a vstupní hodnotu u1 = 0 do řádku 5 tabulky, kde se uvedená kombinace vyskytuje ve sloupcích A, B, C. Odezvou bude ve sloupcích F a G v11 =1; v12 =0. Obdobně získáme přechodem do řádku 3 hodnoty v21 =1; v22 =1. Tím jsme obdrželi dílčí výstupní posloupnosti v1 = [1;1;1], v2= [1;0;1] a multiplexováním, tj. proložením bit po bitu obdržíme výstupní posloupnost v = [1;1;1;0;1;1]. Popis chování konvolučního kodéru pomocí tabulky
Zdrojové bity A
Výchozí stav
Následný stav
Výstup
B
C
D
E
F
G
ut
ut-1
ut-2
ut-1
ut-2
v1
v2
1
0
0
0
0
0
0
0
2
1
0
0
1
0
1
1
3
0
0
1
0
0
1
1
4
1
0
1
1
0
0
0
5
0
1
0
0
1
1
0
6
1
1
0
1
1
0
1
7
0
1
1
0
1
0
1
8
1
1
1
1
1
1
0
Popis pomocí stavového diagramu Další možností pro popis funkce konvolučního kodéru je stavový diagram, který je opět pro stejný příklad z obrázku 1 uvedeného v kapitole 3. Stavy S0, S1, S2, S3, jsou stavy kodéru a odpovídají kombinacím ut-1 a ut-2 na výstupu registrů [0;0],[0;1],[1;0],[1;1]. Každý příchod vstupního bitu způsobí přechod do nového stavu. Stavový diagram má 2k větví vycházejících z každého stavu, každá větev je označena vstupními/výstupními hodnotami ut/v1v2. Každá větev odpovídá jednomu řádku dle předchozí tabulky.
13
Stavový diagram konvolučního kodéru
Popis pomocí mřížkového diagramu Znázorněním stavového diagramu v závislosti na čase dojdeme k reprezentaci tzv. mřížkovým diagramem (viz následující obrázek). Odtud také pochází název mřížkový kód resp. trellis kód. Větev je popsána vstupními/výstupními hodnotami kodéru stejně jako větve ve stavovém diagramu. Cesta zvýrazněná čárkovanou čarou odpovídá příkladu vstupní posloupnosti u = [1;0;0], pro kterou se prochází sledem stavů z počátečního S0 přes S2 a S1 zpět do výchozího stavu S0. Cesta zvýrazněná plnou čarou je příklad pro vstupní sekvenci u = [0;1;1;0;0]. Odpovídající výstupní posloupnost je pak v = [0;0;1;1;0;1;0;1;1;1]. Všechny uvedené způsoby popisu chování konvolučního kodéru jsou ekvivalentní, nicméně znázornění pomocí mřížkového diagramu je názorné s ohledem na přiblížení průběhu dekódování konvolučního kódu.
14
Mřížkový diagram konvolučního kodéru
15
1.6 Minimální kódová vzdálenost konvolučního kódu Konvoluční kódy jsou lineární, proto platí, že minimální kódová vzdálenost je rovna nejmenší Hammingově vzdálenosti nenulového kódového slova.
Kódovým slovem je ovšem celá posloupnost, minimální kódová vzdálenost je rovna nejmenší Hammingově vzdálenosti nenulové kódové posloupnosti, která začíná a končí nulou.
Tato minimální kódová vzdálenost je nazývána jako volná kódová vzdálenost a bývá označována dfree.
U jednoduchých kodérů můžeme tuto posloupnost stanovit přímo z grafického zobrazení. Hledaná kódová cesta v předchozím obrázku je vyjádřena kódovou posloupností 111011. Minimální kódová vzdálenost je tedy dfree = 5 (kódová posloupnost obsahuje pět jedniček). Z toho můžeme poznat, že kód opravuje až dvojnásobné chyby v kódové posloupnosti.
16
1.7 Dekódování konvolučního kódu U konvolučních kódů není možné při dekódování zprávy stanovit dekódování deterministicky. Pracuje se pouze s nejpravděpodobnějším předpokladem toho, jaká zpráva byla vyslána. Zpráva s poruchou obsahuje chybu. I v této situaci jsme tedy pracovali s nejpravděpodobnějším řešením, když jsme stanovovali informační slova dekódováním.
Pro nalezení nejpravděpodobnějšího odhadu slouží u konvolučních kódů tzv. Viterbiho algoritmus. Je to však jen jeden z několika možných způsobů dekódování konvolučního kódu odvozený již v roce 1967.
Princip Viterbiho algoritmu je založen na vyhledávání nejmenší Hammingovy vzdálenosti dekódované posloupnosti od posloupnosti přijaté. Obrázek uvedený v kapitole 4 ukazuje všechny cesty, se kterými konvoluční kodér pracuje. Cesta, kterou hledáme, bude postupně zkoumána podle tohoto kritéria. Souhrn všech kroků této cesty se nazývá přijatá cesta. Předpokládejme nyní, že jsme ji určili pro každý stav mřížkového diagramu. Porovnáním kódových vzdáleností přijatých cest můžeme určit nejpravděpodobnější cestu, a tím i zdrojovou posloupnost pro daný časový úsek. Po příjmu dalších kódových n-tic se však může situace změnit. Rozhodnutí je proto potvrzeno až na konci zprávy.
Po přijetí celé zprávy má být kodér v nulovém stavu. Jeho přijatá cesta určuje hledanou posloupnost. Je-li zdrojová posloupnost 10011 zakódována do posloupnosti 11101111010111 kodérem konvolučního (2, 1)-kódu s generujícím polynomem g ( x ) = 1 + x + x 2 + x 4 + x 5 , pak při přenosu došlo ke dvěma chybám. Přijata byla totiž posloupnost 111010110111111. Při určování nejpravděpodobnější cesty bude nyní použit Viterbiho algoritmus. Pro znázornění postupu řešení je použit mřížkový diagram. V následujícím obrázku jsou v mřížkovém diagramu plnou čarou znázorněny přijaté cesty a přerušovanou čarou zamítnuté cesty, a to v každém kroku řešení. Výrazně zesílenou čarou je vyznačen výsledný odhad.
17
Znázornění činnosti Viterbiho algoritmu
U každého stavu jsou vyznačeny minimální vzdálenosti v daném okamžiku dekódování. Cestě s minimální vzdáleností odpovídá správná posloupnost zdrojových znaků 1001100. Obě chyby jsou tedy opraveny. Viterbiho algoritmus poskytuje nejpravděpodobnější odhad vyslané zprávy až po přijetí celé zprávy. Zdlouhavost vyhodnocování cesty s minimální vzdáleností může způsobovat neúměrně velká zpoždění zprávy. U dlouhých posloupností vznikají velké nároky na kapacitu paměti, do které se ukládá pro každý stav cesta s minimální vzdáleností.
18
1.8 Konvoluční kódy řešitelné pomocí syndromu Nevýhodou Viterbiho algoritmu je jeho náročnost na počet numerických operací. Počet operací potřebný k dekódování L-znakové zdrojové posloupnosti je roven L ⋅ 2k ( K −1) .
Proto se Viterbiho algoritmu používá pro dekódování kódů s relativně krátkými omezujícími délkami. Pro ilustraci je možné uvést, že při omezující délce K=7 konvolučního kódu je obvodová náročnost přibližně 8000 hradel. Závislost počtu operací na omezující délce K je exponenciální. Největší omezující délka, pro kterou bylo vytvořeno zapojení v podobě podpůrné paralelně pracující výpočetní jednotky, byla K=10. Nicméně velkých volných vzdáleností je možné dosáhnout jen při velkých omezujících délkách. Proto jsou pro dekódování kódů s velkými omezujícími délkami používány algoritmy, jejichž závislost je na omezující délce konstantní, a jsou označovány jako tzv. sekvenční algoritmy. Sekvenční algoritmus vychází ze známé pravděpodobnosti p chyby každého kódového symbolu. Vzdálenost cesty je pak v každém i-tém kroku přibližně rovna součinu i·n·p. Odhad cesty je volen ten, jehož kódová n-tice má nejmenší Hammingovu vzdálenost. Pro správnou funkci sekvenčního algoritmu je důležité správně zvolit práh rozhodování. Při malém prahu se dekodér neustále vrací zpět a při velkém prahu je špatná cesta detekována příliš pozdě. Nejpoužívanější sekvenční algoritmus je Fanoův algoritmus. Výčet konvolučních kódů, jejichž kodéry a dekodéry jsou snadno obvodově řešitelné, není příliš rozsáhlý. Řešení pro opravy vícenásobných chyb jsou velmi náročná. Většina z účinných konvolučních kódů byla objevena pomocí počítačové simulace. V dalším textu bude nejdříve popsána obecná třída konvolučních kódů, které jsou schopny opravovat jednoduché chyby. Na příkladu aplikace pak budou následovat experimentální výsledky, které ukazují, že kódy této třídy jsou účinné i při výskytu shlukových chyb. Třída konvolučních kódů, které opravují jednoduché chyby, nese název Wynerovy-Ashovy kódy (WA-kódy). Vlastnostmi jsou blízké Hammingovým kódům. Pro každé kladné m existuje Wyner-Ashův ((m+1)2m, (m+1)(2m – 1))-kód. Kód je definován pomocí tzv. kontrolní matice H´ Hammingova (2m – 1, 2m – 1 – m)-kódu. To je kontrolní matice m × (2m – 1), ve které je každý ze sloupců nenulový. Sestavme tedy následující matici. Řádky jsou definovány jako soustava 1 × (2m-1) matic P1T, …, PmT. Nechť P0T je řádkový vektor, jehož všechny (2m-1) prvky jsou jedničky. Potom úplná kontrolní matice Wynerova-Ashova kódu má následující tvar:
19
P0T T P1 P2T H = ... PT m 0 ...
1 0 0
0 P1T P1T
0 1 0
0 0 P0T
0 0 1
0 0 0
0 0 0
... ... ...
... 0 0
...
...
P1T
...
...
...
...
...
PmT
0
... ... ... ...
Zkrácená kontrolní matice je pak zapisována jako:
H =
P0T
1
0
0
0
0
P1T P2T
0 0
P0T P1T
1 0
0 P0T
0 1
... PmT
... 0
... PmT−1
... 0
PmT− 2
0
...
...
P0T
1
Minimální vzdálenost Wynerova-Ashova kódu je d=3, a to znamená, že se jedná o konvoluční kód, který opravuje jednu chybu.
20
1.9 Tvrdé a měkké rozhodování V digitálních přijímačích většinou nemá výstupní signál demodulátoru vlivem šumu a interferencí zřetelnou podobu diskrétního binárního signálu, nýbrž spíše připomíná spojitý náhodný signál. Proto za demodulátorem následuje tzv. rozhodovací obvod, který rozhoduje, jakou logickou úroveň má demodulovaný signál v aktuálním bitovém intervalu. Tento obvod může vlastní proces rozhodování implementovat dvojí způsobem. Tvrdé rozhodování HD (Hard Decision), zvané též „rozhodování bit po bitu“, realizuje rozhodovací proces za pomoci prahového detektoru, který může být implementován např. jako napěťový komparátor. Jeho výstup je jednoznačně buď logická 1 (log 1), nebo logická 0 (log 0), a to podle toho zda úroveň vyhodnocovaného bitu je nad nebo pod jeho specifikovanou rozhodovací úrovní.
Prahový detektor, obecně rozhodovací obvod, tedy kvantuje demodulovaný signál pouze do dvou hladin, tzn. binárně. Výstup rozhodovacího obvodu je následně přiveden na kanálový dekodér, který musí být uzpůsoben pro tento tvrdý vstup HI (Hard Input). Odhadnutý vzorek se poté ihned eliminuje a přistupuje se k odhadu vzorku následujícího.
Tvrdé rozhodování má velkou výhodu v relativně jednoduché implementaci.
Bohužel se při jeho aplikaci nevyužívají dva důležité typy informace, které v sobě demodulovaný signál nese. Nebere se v úvahu jednak kvalita zpracovávaného signálu, tj. jeho skutečná velikost, resp. energie, apod. Kromě toho se nevyužívá určitý typ korelace mezi po sobě následujícími symboly, kterou v sobě může obsahovat již vysílaný signál a k níž může dále přispívat i radiový kanál. Tím se ztrácí určité množství kontextuální (související) informace. Oba výše uvedené faktory ve svých důsledcích snižují věrohodnost rozhodovacího procesu.
Měkké rozhodování SD (Soft Decision), zvané též „rozhodování po kódových slovech“, provádí opět rozhodovací obvod. Ten však oproti předchozímu typu rozhodovacího procesu kvantuje vzorky výstupního signálu demodulátoru nikoliv binárně, nýbrž do více kvantizačních úrovní než dvou.
Předpokládejme, že je demodulovaný signál polární, to znamená, že úrovni log 1 odpovídá například napětí +1 V a úrovni log 0 následně napětí -1 V. V praxi se u takových binárních signálů často vystačí s „tříbitovým“ kvantováním, poskytujícím množinu celkem osmi kvantizačních úrovní, označených čísly (-4, 3, -2, -1, 0, 1, 2, 3, 4). Tato čísla reprezentují tzv. spolehlivostní faktor (reliability factor), resp. spolehlivostní metriku (reliability metric), poskytující přídavné 21
informace (side information, likelihood information, log-likelihood ratios) o amplitudě a případně i o dalších důležitých vlastnostech zpracovávaného bitu resp. symbolu.
Čím vyšší je absolutní hodnota spolehlivostního faktoru, tím vyšší je i míra jistoty, že daný bit zaujímá uvažovanou aktuální pozici. Tedy např. hodnoty +4 resp. -4 poskytují vysokou míru důvěry, že úroveň bitu je +1 V resp. -1 V, kdežto např. při hodnotách +2 resp. -2 je důvěra v hodnotu bitu +1 V resp. -1 V podstatně nižší. Druhým přídavným činitelem uplatňujícím se při měkkém rozhodování je kontextuální (související) informace. Ta může být využita spolu se spolehlivostním faktorem různými způsoby, např. pro zvýšení věrohodnosti příjmu přijímaných bitů, resp. symbolů.
Dokonalejší metoda dekódování s měkkým rozhodováním aplikuje jako metriku Euklidovu vzdálenost a díky tomu bere v úvahu nejen prostou velikost (amplitudu) jednotlivých bitů přijatého kódového slova, nýbrž i jejich poměr signál/šum.
Ve výše uvedeném příkladu bylo uvažováno tříbitové, tj. osmiúrovňové kvantování výstupu demodulátoru. Některé systémy však aplikují mnohem dokonalejší téměř optimální kvantování do podstatně většího počtu úrovní. Tak například v buňkovém systému GSM se uplatňuje osmibitové kvantování výstupu demodulátoru do 256 úrovní. Výstup rozhodovacího obvodu potom přináší velice detailní přídavnou informaci o kvalitě zpracovávaného bitu resp. symbolu.
Využití měkkého rozhodování je snadné u konvolučních kódů. Naproti tomu u blokových kódů je implementace této techniky obtížnější, i když vývoj z posledních let naznačuje, že principy měkkého rozhodování bude možné úspěšně aplikovat i zde. Měkké rozhodování přináší výrazné zlepšení tzv. kódového zisku, a to zejména při malých poměrech odstupu signálu od šumu. V kanálech se šumem AWGN je to o cca 2 až 3 dB, v kanálech postižených navíc únikem vedoucím ke shlukům chyb potom dokonce o 4 až 6 dB.
22
1.10 Kódování konvolučního WA-kódu Jak vyplývá z předchozích kapitol, jsou kontrolní bity konvolučních kódů vytvářeny jak vzhledem k informačním k bitům právě přenášeného bloku, tak k informačním bitům N-1 předcházejících bloků. Skupinu N bloků použitých k vytvoření zabezpečujících kontrolních bitů označujeme skupinovou délkou bloku. Při kódování se kontrolní bity přenášeného bloku vytvářejí ve vztahu k informačním bitům všech bloků obsažených ve skupině. Toto rozdělení konvolučního kódu na části zprávy je zavedeno kvůli snadnějšímu technickému řešení kodéru a dekodéru.
Při dekódování se dekódované slovo vytváří ve vztahu k informačním bitům právě přenášeného kódového slova a kontrolním bitům celé skupiny. Takto uspořádané kódování a dekódování se nazývá kanálové kódování a kanálové dekódování. V praxi používaným kódem je Wynerův-Ashův konvoluční kód (WA-kód). Uspořádání WA-kódu tedy představuje konvoluční (n, k)-kód, který pro p = 1, 2, 3, … vyhovuje podmínkám definovaným následujícími rovnicemi: •
počet bitů výsledného zabezpečeného slova je n = 2p,
•
počet informačních bitů v bloku je k = 2p – 1 = n – 1,
•
délka skupiny zabezpečovaných bloků je N = p + 1.
Každému kódovému slovu o n bitech tedy přísluší jeden kontrolní bit pro celou skupinovou délku o N = p + 1 slovech. Kontrolní bit se vytváří funkcí XOR z vybraných informačních bitů bloku.
Princip vytváření WA-kódu: a) kódování, b) dekódování
23
Při použití konvolučního kódu je zřejmé, že dekódovaná informace bude k dispozici až po dokončení přenosu skupiny bitů, ze kterých jsou vytvářeny kontrolní bity. Dekódované slovo je tedy možné získat až po uplynutí „dopravního zpoždění“, které vzniká při sériovém přenosu zprávy.
24
1.11 Dekódování a oprava chyb u WA-kódu Příklad konvolučního (8,7)-kódu ukazuje, že řádky vybraných pozic předcházejících N-1 kódových slov skupiny určuje ve dvojkové reprezentaci číslo odpovídající poloze informačních bitů v N-tém slově skupiny. Toho se využívá při dekódování. Při dekódování se vypočítávají bity syndromu na základě porovnání přijatých kontrolních bitů a kontrolních bitů odvozených z přijatých informačních bitů jednotlivých N kódových slov skupiny. Odvození probíhá podle stejných pravidel jako na straně vysílání zprávy.
Pokud nevznikne během přenosu chyba, oba kontrolní bity souhlasí a syndrom odpovídá hodnotě „0“. Nastane-li ovšem během přenosu chyba, kontrolní bity pak nesouhlasí a syndrom odpovídá hodnotě „1“. Syndrom tedy lokalizuje přesnou polohu chyby ve dvojkovém vyjádření zprávy. Tato vlastnost vyplývá z konstrukce konvolučního kódu, neboť přijatý kontrolní bit je vytvářen funkcí XOR s ohledem na polohu informačních bitů v jednotlivých kódových slovech. V kódových slovech (posloupnostech) následujících za právě dekódovanou kódovou posloupností se příslušný kontrolní bit vytváří z chybně přenesené výchozí posloupnosti. V takovém případě bude chyba například v poloze prvního informačního bitu indikována nesouhlasem kontrolních bitů a lokalizována trojicí syndromů „100“, neboť chyba v poloze prvního informačního bitu ovlivní kontrolní bit pouze následující kódové posloupnosti. Chyba v poloze druhého informačního bitu by ovlivnila pouze kontrolní bit druhého kódového slova. Projeví se tedy syndromem „010“, atd. Jako ilustrace výše uvedených skutečností je uveden jednoduchý příklad pro N=4 (viz následující obrázek).
Konvoluční kód o N kódových slovech
V příkladu ilustrovaném na předchozím obrázku vyžaduje detekce a korekce jedné chyby celkem čtyř kontrolních bitů ve skupině bloků N=4, který má celkem 32 bitů (z toho 28 bitů je informačních). Teoretické omezení WA-kódu je na jednotlivou chybu ve 32 symbolech zprávy. Je zřejmé, že kód nevyžaduje zvláštní zabezpečování přenosu kontrolních bitů, neboť detekuje i chybu v kontrolním
25
bitu. Takovému případu odpovídá skupina syndromů tvořená symboly „1000“, v nichž „1“ signalizuje chybu v bloku „000“ nultou polohu chybného bitu v kódové posloupnosti. Wynerův-Ashův konvoluční (8,7)-kód je využit např. ke zlepšení kvality televizního vysílání podle normy PAL. S ohledem na vysoké přenosové rychlosti se v této aplikaci předpokládá demultiplexování sériového PCM kódu. Přenos kontrolních bitů se provádí formou společného osmibitového slova kontrolních bitů. Kontrolní slovo obsahuje 2×4 bity pro dva informační bloky. Tímto uspořádáním se výrazně sníží šířka pásma výsledného multiplexovaného signálu, která by byla nutná, pokud by byla slova přenášena jako osmibitová. Vzorkovací kmitočet fvz = 13,3 MHz se zvýší pouze na hodnotu (15/14)·13,3 = 14,25 MHz. Hodnota zaváděné redundance je přitom pouze 1/15 = 0,07. Přitom je možné dosáhnout opravy jedné chyby v posloupnosti patnácti kódových slov.
26
1.12 Kodér WA-kódu Princip uspořádání vlastního kodéru blokového WA-kódu, který pracuje podle pravidel uvedených v předchozí kapitole, je znázorněn na následujícím obrázku. Posloupnost informačních bitů paralelního přenosového kanálu zaplní postupně sedmibitový posuvný registr PR. V posuvném registru jsou ukládány informační bity téže váhy ze sedmi po sobě následujících slov. Pro každý takový informační blok jsou provedeny operace logickou funkcí XOR a je uložen kontrolní bit S do paměťového obvodu P, jehož výstup je zpracováván operací logické funkce XOR s bitem, který vznikl jako kontrolní bit následujícího informačního slova.
Skupinové schéma zapojení kodéru konvolučního (8,7)-kódu
Tak je postupně vytvořen výsledný kontrolní bit, aniž je nutné vytvářet simultánní bloky celé skupiny N. Přitom je však nutné, aby paměťové obvody pracovaly rychlostí, která je rovna 1/7 rychlosti výstupních informačních bitů. Úplné uspořádání kodéru WA-kódu využívá pro čtyři nejvýznamnější bity kodéry z následujícího obrázku.
27
Skupinové schéma úplného kodéru WA-kódu
V nezabezpečovaných kanálech, které jsou tvořeny nižšími čtyřmi bity, jsou zařazeny pouze posuvné registry pro vyrovnání časového zpoždění. Součástí úplného uspořádání kodéru je obvod pro vytváření sériového toku dat, který provádí multiplexování informačních a kontrolních bitů do formátu, v němž jsou všechny kontrolní bity dvou bloků seřazeny do osmibitového slova.
Multiplexní obvod vytváří zprávu popsaného uspořádání na základě sdružení bitů informačních (MSB (Most Significant Bit) + LSB (Least Significant Bit)) a kontrolních bitů jednotlivých paralelních kanálů sdružených do společného osmibitového kontrolního slova. Výstupní paralelně-sériový převodník vytváří výslednou zabezpečenou zprávu v sériovém tvaru.
28
1.13 Dekódování konvolučního WA-kódu Dekódování konvolučního (8,7)-kódu spočívá ve vytvoření syndromů pro korekci chyb v kódové zprávě. Dekodér proto obsahuje základní Wynerův-Ashův kodér, který má za úkol generovat kontrolní bity zprávy na přijímací straně. Výstup tohoto kodéru se porovnává s příslušným přeneseným kontrolním bitem. Kontrolní bity se na přijímací straně ukládají postupně do N-členného posuvného registru PR.
Výpočet bitů syndromu je zřejmý z následujícího obrázku. Při výpočtu je použit čítač, který vytváří dvojková čísla 001 až 111 rychlostí shodnou s rychlostí posuvu posuvného registru ve funkci vyrovnávací paměti. Obvody s logickou funkcí XOR vytvářejí logickou hodnotu „1“ v případě neshody hodnoty syndromu a výstupu dvojkového čítače. Je-li současně detekována chyba ve skupině bloků, je první syndromový bit nastaven na hodnotu „1“, je na výstupu logického obvodu součinu H1 korekční signál v hodnotě „1“. Tím je zajištěna oprava chyby v posloupnosti přenášené zprávy. Aby byl opravován správný bit zprávy obvodem H2 a logickou funkcí XOR, je nutné, aby procházející zpráva byla zpožděna přídavným posuvným registrem, který zpozdí zprávu právě o dvacet jedna taktů zdroje synchronizace. Teprve potom je opravován právě chybný symbol.
Schéma zapojení dekodéru Wynerova-Ashova (8,7)-kódu v jednom kanále
V zapojení obvodu dekodéru je použito zapojení kodéru WA-kódu. V předchozím obrázku je nakreslen jako blok v místě vstupu přijaté zprávy. Skupinové schéma dekodéru pro všechny přenosové kanály je na následujícím obrázku. Zpráva vstupuje prostřednictvím sériově-paralelního převodníku do 29
obvodu demultiplexoru, ve kterém jsou nejdříve vytvořeny paralelní kanály informačních bitů.
Skupinové schéma Wynerova-Ashova dekodéru (8,7)-kódu
Každý ze zabezpečovaných kanálů bitů MSB obsahuje vlastní Wynerův-Ashův dekodér. Blok zpracování kontrolních bitů vytváří jednotlivé kontrolní bity ze složeného kontrolního slova. V nezabezpečovaných kanálech bitů LSB se provádí přídavným časovým zpožděním vyrovnávání skupiny příslušných bitů MSB a LSB.
30
1.14 Srovnání účinnosti Hammingova kódu a WA-kódu pro TV Použití blokových a konvolučních kódů, které umožňují detekci a opravu jednotlivých chyb, a po použití prokladu i krátkých skupinových chyb, je velmi často požadováno proto, že neodstraněné chyby způsobují po zpracování přijatého TV signálu rozsáhlé poškození tohoto signálu. Tento jev je možné vysvětlit tím, že před vlastním přenosem je signál podroben kompresi, aby nebylo nutné rozšiřovat šířku pásma TV kanálu. Zpráva podrobená kompresi tak obsahuje podstatně více informací, tj. je výrazně omezena redundance bitů a symbolů v přenášeném signálu (zprávě). Výskytem chyb je tedy přenášený komprimovaný signál poškozován mnohem více. V příjmu digitálního TV signálu se při dostatečném pokrytí území uvažuje jen malá pravděpodobnost výskytu chyby. Pro takové případy platí experimentální vztah pc = β ⋅ p 2 , kde pc udává pravděpodobnost chyby v bitu p. Činitel β je přitom možné považovat za kritérium kvality pro hodnocení kódů. Pro Hammingův kód je činitel kvality kódu β H =
βWA =
n ⋅ (2 N − 1) − 1 . 2
n −1 , pro konvoluční WA-kód je 2
Odvození přechozích vztahů uvádí s velmi pečlivě provedenými experimentálními zkouškami prováděnými britskou BBC literární prameny [4] a [5]. Platí, že kvalitnější zabezpečovací kód se vyznačuje nižší hodnotou činitele β. Oba typy kódů jsou pro srovnání uvedeny v následující tabulce. Je zde také uvedeno i množství zaváděné redundance. Srovnání účinnosti Hammingova a WA-kódu pro TV
Hammingův kód Typ (n,k) (7,4)
Wynerův-Ashův kód Délka Typ (n,k) Redundance N (2,1) 2 0,500
0,429
Činitel βH 3
(15,11)
0,267
7
(4,3)
3
0,250
9,5
(31,26)
0,161
15
(8,7)
4
0,125
27,5
(63,57)
0,095
31
(16,15)
5
0,063
71,5
Redundance
Činitel βWA 2,5
Podle údajů uvedených v tabulce je možné konstatovat, že při zhruba stejné hodnotě redundance je Hammingovým kódem dosaženo lepšího činitele β. Realizace Hammingova kódu je však obvodově složitější. Pro účely použití při zabezpečení TV kanálu jsou vhodné Hammingův (31,26)-kód a Wynerův-Ashův (8,7)-kód. Z těchto dvou možností byl BBC doporučen Wynerův-Ashův (8,7)31
kód, a to nejen z hlediska jednodušší implementace, ale také proto, že má vhodnější vlastnosti při ochraně zpráv před vlivem skupinových chyb. Obojí vyplývá z kontextu výše uvedených zkoušek.
Z výsledků provedených zkoušek dále vyplynulo, že vliv opravy skupinové chyby výrazněji ovlivňuje kvalitu obrazu než oprava chyb jednotlivých. Experimentální výsledky jsou dokladem o vhodnosti řešení a o dostatečné účinnosti implementačně relativně jednoduchého WA-kódu pro aplikaci v přenosových kanálech PCM s chybovostí do hodnoty 10-5.
Při přenosu nebo záznamu TV obrazu jsou nejčastější chyby skupinové, postihující najednou několik symbolů přenášené zprávy. Vysoká přenosová rychlost v digitální televizi však dovoluje aplikovat pouze implementačně jednoduché zabezpečovací kódy. Wynerův-Ashův kód vykazuje přijatelnou míru obvodové složitosti a přitom zajišťuje v dostatečné míře opravu jak u jednotlivých, tak u skupinových chyb.
32
2 TURBO kódy 2.1 Paralelní zřetězení Před uvedením TURBO kódů byly nároky na vysokou účinnost potlačení chyb v informačním kanálu řešitelné například konvolučním kódem s velkou hodnotou omezující délky kódu (tzv. délka kódového omezení). Podmínkou zde však byla velká délka vnitřní paměti kodéru konvolučního kódu. Dekódování takového konvolučního kódu bylo velmi komplikované. V roce 1993 byly poprvé popsány tzv. TURBO kódy. Dnes patří TURBO kódy k nejvýznamnějším objevům v teorii kódování. Jejich vlastnosti je řadí k nejdůležitějším efektivně použitelným kódům. TURBO kódy se stávají nejvážnějšími kandidáty nových průmyslových standardů pro připravované systémy v oblasti bezdrátového přenosu informace. TURBO kódy jsou vytvářeny jako paralelně zřetězené konvoluční kódy. Kodéry i dekodéry jsou tvořeny zřetězením dvou nebo více modulů. Moduly dekodérů jsou nazývány SISO (Soft-Input Soft-Output). Moduly SISO jsou propojeny rovněž navzájem několika bloky na proklad (Interleaver) a zpětný proklad (Deinterleaver) informace ve zprávě. Moduly dekodéru spolupracují podle interaktivního algoritmu, při kterém dochází k výměně dílčích výsledků dekódování mezi jednotlivými SISO moduly. Dekodér je v tomto uspořádání schopen se přiblížit, při dlouhých posloupnostech prokladu informace, hodnotám velmi blízkým limitní kapacitě kanálu. V dalších kapitolách bude vysvětlen základní princip TURBO kódů včetně řízení vlastností kódu, analýzy a zlepšování mezních parametrů návrhu základních kodérů a bloku prokladu informace ve zprávě. Základem účinnosti dekodéru je tzv. algoritmus interaktivního dekódování. Další principy zřetězení a použití prokladu, které zahrnuje sériové a hybridní zřetězení dekodérů je uváděno v souvislosti s typickými hodnotami využití limitních hodnot kapacity informačního kanálu. TURBO kódy jsou intenzivně zkoumány v souvislosti s použitím komunikace s omezeným výkonem zdroje zpráv (Space Communication). Téměř hotov je nový standard pro kódování telemetrických spojů. Doporučení pro CCSDS (Consultative Committee for Space Data Systems), pro ATM (Asynchronous Transfer Mode) i pro bezdrátové aplikace, pro kanály s velkým únikem, s digitálním satelitním přenosem a pro další aplikace digitálních komunikací jsou ve velmi pokročilém stádiu příprav. TURBO kódy představují novou třídu kódů pro kódové zabezpečení, jejichž dekódování je řešeno praktickou implementací. Srovnání vlastností bude v dalším textu provedeno v souvislosti s kodérem a dekodérem konvolučního kódu. Konvoluční kód může být realizován například kodérem s poměrem r = ½ s omezující délkou (Constraint Length) K = 3, která označuje celkový počet bitů informační zprávy zpracovávaných do výstupní kódové zprávy.
33
Pro popis kodéru konvolučního kódu je možné použít vstupní posloupnosti u a posloupností, které se podílí na výstupní kódové posloupnosti v(1) a v(2). V časovém okamžiku i se vstupní informační bit ui rozkládá na dva prvky uložené ve vnitřní paměti kodéru: ui-1 a ui-2. Popis zachycuje posloupnost hodnot, ze kterých jsou vytvářeny hodnoty výstupní. S ohledem na to, že se jedná o popis nekauzálního systému, je výhodnější používat pro popis vstupní posloupnosti mnohočlenu u(D), a pro popis výstupní posloupnosti mnohočlenu v(D), kde D je proměnná v obrazovém definičním oboru.
Konvoluční kodér s poměrem r = 1/2 a s délkou kódového omezení K = 3
Generující matici kodéru konvolučního kódu dle předchozího obrázku je potom možné zapsat jako: G ( D ) = g (1) ( D ) g ( 2 ) ( D ) , G ( D ) = 1 + D 2 1 + D + D 2 .
Kódovou posloupnost v(D) odpovídající vstupní posloupnosti u(D) je možné zapsat jako u ( D ) G ( D ) = u ( D ) g (1) ( D ) u ( D ) g ( 2 ) ( D ) . Stejná kódová posloupnost
vzniká
také
tehdy,
je-li
u '( D ) = u ( D ) g (1) ( D ) ,
přitom
g (2) ( D) u ( D )G ( D ) = u ( D ) g ( D )G R ( D ) , kde GR ( D) = 1 . (1) g ( D) (1)
Generující matice GR(D) se nazývá rekurzivní generující matice RGM (Recursive Generating Matrix).
34
2.2 Rekurzivní kodér Kodér konvolučního kódu pracující podle rekurzivní matice je označován jako kodér RSC (Recursive Systematic Convolutional encoder).
Kódy mohou být konstruovány pomocí této rekurzivní matice jako systematické, u kterých je neměnné umístění kontrolních bitů v kódové posloupnosti.
Systematický konvoluční kód má stejnou volnou kódovou vzdálenost jako konvoluční kód s nerekurzivní generující maticí v uspořádání dle obrázku z předchozí kapitoly. Uspořádání RSC kodéru rekurzivního systematického konvolučního kódu je na následujícím obrázku.
RSC kodér
35
2.3 Kodér TURBO kódu TURBO kódy jsou kódovány paralelně zřetězenými kodéry RSC kódů. Kodéry jsou odděleny blokem prokladu dat. Příklad kodéru TURBO kódu je na následujícím obrázku. Zde jsou paralelně zřetězeny dva identické 1/2 RSC kodéry.
Příklad kodéru TURBO kódu
Horní kodér přijímá informační posloupnost přímo, zatímco spodní kodér přijímá data upravená v bloku prokladu podle funkce permutace α. Proklad je pseudonáhodný, to znamená, že symbol v poloze i je transformován do polohy α(i) podle předem daných, ale přesto náhodných pravidel. Blok prokladu pracuje na daném úseku posloupnosti symbolů.
Dochází k výměně L bitů v jedné dávce zpracování, to znamená, že TURBO kódy jsou ve skutečnosti blokové kódy. Protože oba kodéry jsou systematické a pracují se stejnými symboly (přestože jsou tyto symboly přeházené permutací), je zřejmé, že může být odeslána pouze jedna kódová zpráva a přesto je možné ji dekódovat. Výsledný systematický kód je obvykle výstupem horního kodéru, zatímco systematický kód spodního kodéru není přenášen. Nicméně kontrolní symboly (bity) obou kodérů přenášeny jsou. Celkový kódový poměr dvou paralelně zřetězených systematických kódů s poměrem 1/2 je r = 1/3.
Kódový poměr se může zlepšit tzv. zúžením (puncturing), což je proces vypuštění některých kontrolních bitů. Kódový poměr TURBO kódů je zpravidla zlepšen na 36
r = 1/2 tím, že jsou přenášeny pouze liché kontrolní bity horního kodéru a sudé kontrolní bity spodního kodéru (spolu se všemi informačními bity z horního kodéru).
37
2.4 Dekódování Dekodér konvolučního kódu pracuje tak, že hledá nejpravděpodobnější posloupnosti bitů v kódové posloupnosti, která je porušena chybami. Tzv. Viterbiho algoritmus řeší tento úkol s nejvyšší mírou pravděpodobnosti.
{
}
mˆ = arg m ax P [ m | y ] m
ˆ představuje posloupnost bitů, která je získána z přijaté posloupnosti y. Symbol m Rovnice je řešena například pomocí Viterbiho algoritmu. Je tím získána maximálně pravděpodobná přijatá posloupnost ML (Maximal Likelihood). U konvolučních kódů je možné získat řešení ML posloupnosti použitím předcházející rovnice, která je řešitelná Viterbiho algoritmem. Složitost tohoto algoritmu je úměrná hodnotě O(2L), kde L je velikost datového rámce (velikost bloku prokladu). Pro příliš velkou složitost výpočtu ML posloupnosti je u TURBO kódů využito suboptimálního řešení, které vyžaduje mnohem menší složitost výpočtu. Dobré výsledky poskytuje řešení následující soustavy rovnic Λ i(1) = log
P m i = 1 | y ( 0 ) , y (1) , z ( 2 )
( 0 ) (1) ( 2 ) a Λ ( 2 ) = log P m i = 1 | y , y , z , i P m i = 0 | y ( 0 ) , y (1) , z ( 2 ) P m i = 0 | y ( 0 ) , y (1) , z ( 2 )
kde y(0) jsou přijaté informační bity, y(1) jsou přijaté kontrolní bity prvního kodéru a y(2) jsou přijaté kontrolní bity druhého kodéru. Vlnovka nad veličinou představuje hodnotu s prokladem, to znamená, že ỹ je hodnota odpovídající prokladu hodnoty y. Symbol Λ je aposteriorní logaritmický nejpravděpodobnější poměr LLR (Log-Likelihood Ratio) a z je tzv. extrinzická informace. Extrinzická informace je ve vztahu k LLR dle následujících rovnic:
(2) − y (0) − z (1) . zi(1) = Λ i(1) − yi(0) − zi(2) a zi(2) = Λ i i i Soustava posledních čtyř rovnic je řešitelná iterativním postupem, který je naznačen v blokovém schématu dekodéru TURBO kódu v následující kapitole. (2) . Každým z dekodérů prochází Dekodér 1 určuje řešení Λ(1) a dekodér 2 řeší Λ informace ke druhému dekodéru a v něm dochází ke zlepšování aposteriorní pravděpodobnosti použitím informace odvozené v předcházejícím dekodéru. Konečného zlepšení přijatých dat zprávy je dosaženo po potřebném počtu iterací výpočtu. Výstup informace je vyveden obvykle z druhého dekodéru.
38
2.5 Dekodér TURBO kódu Algoritmus aposteriorní pravděpodobnosti LLR je možné vypočítat přímo pomocí tzv. MAP (Maximum A Posteriori) algoritmu. Výpočet však má velmi vysokou složitost a je citlivý k vyjádření čísel s konečnou přesností.
Tyto problémy se zmírnily prováděním algoritmu v logaritmickém vyjádření veličin. Výsledný algoritmus je označovaný názvem Log-MAP algoritmus. Tyto algoritmy jsou sestaveny ze dvou Viterbiho algoritmů: jeden je prováděn v dopředné rekurzi a druhý ve zpětnovazební rekurzi (princip viz následující obrázek). Složitost Log-MAP algoritmu je tedy asi dvojnásobná ve srovnání s Viterbiho algoritmem.
TURBO dekodér
Blok prokladu informace ve zprávě je možné obecně znázornit jako paměťovou matici, do které se zapisuje po řádcích, a ze které se čte informace po sloupcích (příklad činnosti bloku prokladu viz následující obrázek).
39
Příklad činnosti bloku prokladu
40
2.6 Výkonnost TURBO kódu Proklad informace v přenášené zprávě hraje při návrhu TURBO kódu důležitou úlohu. Jestliže je velikost bloku prokladu velká, zlepšuje se schopnost kódu opravovat chyby. Jestliže se blok prokladu zmenšuje, schopnost kódu opravovat chyby klesá. Předchozí skutečnosti tak mohou vést k jednoduché úvaze, že je nejlepší použít co největší blok prokladu.
Velikostí paměti využité v bloku prokladu se však výrazně prodlužuje tzv. latentní doba dekodéru. Simulovaný výkon TURBO kódu uvedený v následujícím obrázku ukazuje, jak se mění potlačení chyb s narůstajícím počtem iterací při dekódování. Všechny průběhy jsou simulovány při velikosti bloku prokladu L = 65536. Při počtu iterací je hodnota mírně pod 0,7 dB. Se zlepšujícím se odstupem signálu od šumu se počet chyb zmenšuje.
Výkon TURBO kódu s r = 1/2, K = 5 a L = 65536 s různým počtem iterací i
41
Na dalším obrázku je pak znázorněna závislost potlačení počtu chyb při měnící se délce bloku prokladu L. Všechny průběhy jsou simulovány pro počet iterací i = 18.
Výkon TURBO kódu s r = 1/2, K = 5 a i = 18 s různými délkami bloku prokladu L
Mimořádná schopnost TURBO kódů potlačovat vliv chyb v přenášené zprávě je zřejmá ze srovnání výsledků konvolučního kódu bez zřetězení a TURBO kódu. Pro dosažení stejných výsledků by musel být zkonstruován dekodér konvolučního kódu s mezní kódovou vzdáleností K = 15. Takový dekodér je však podle Viterbiho algoritmu příliš složitý a jen velmi obtížně realizovatelný. Tuto skutečnost potvrzuje i tzv. asymptotická hodnota volné kódové vzdálenosti, kterou lze teoreticky vypočítat pro oba typy kódů.
Potlačování chyb je u konvolučního kódu dosažitelné pouze zvyšováním volné kódové vzdálenosti, která je definována jako nejmenší Hammingova váha všech nejkratších nenulových kódových posloupností. Naopak u TURBO kódů se nabízí možnost opakovaného řešení procesu dekódování při iterativním výpočtu algoritmu dekódování. Dekodér přitom nedosahuje tak velkých nároků na složitost obvodového řešení.
42
Volná kódová vzdálenost TURBO kódů nemusí být tak velká, neboť míru účinku potlačení chyb ovlivňuje kombinace tří faktorů: pseudonáhodný proklad, rekurzivní algoritmus a paralelní zřetězení kódu. Vlivem rekurzivního charakteru RSC kodéru TURBO kódu vykazuje většina vstupních posloupností velkou Hammingovu váhu. Asymptotická hodnota volné kódové vzdálenosti má proto u TURBO kódů mnohem příznivější průběh.
43
2.7 Závěrečný test 1. Jaký je hlavní účel zavádění různých typů kódů a kódovacích schémat? a) odstranění redundatních informací v přenášené datové posloupnosti b) zvýšení spolehlivosti přenosu informací c) ochrana dat před zneužitím d) zvýšení rychlosti přenosu dat správné řešení: b
2. Které typy kodérů jsou označovány jako zdroje zpráv bez paměti? a) U nichž je n-tice kódové posloupnosti závislá POUZE na k-tici aktuální (právě zpracovávané) informační posloupnosti. b) U nichž je n-tice kódové posloupnosti závislá na předchozích k-ticích informační posloupnosti. c) U nichž je n-tice kódové posloupnosti závislá na všech předchozích k-ticích informační posloupnosti. d) U nichž není n-tice kódové posloupnosti závislá POUZE na k-tici aktuální (právě zpracovávané) informační posloupnosti. správné řešení: a
3. Kódové slovo konvolučního kódu je: a) nezávislé na aktuální vstupní informační posloupnosti a na m předchozích informačních slovech b) závislé na aktuální vstupní informační posloupnosti c) závislé na aktuální vstupní informační posloupnosti a na m předchozích informačních slovech d) závislé na m předchozích informačních slovech správné řešení: c
4. Jakým způsobem lze popsat konvoluční kódy? a) pomocí Taylorových řad b) pomocí Fourierových řad c) pomocí diferenciálních rovnic d) pomocí generujících polynomů, resp. matic správné řešení: d
44
5. Jak se nazývá nejznámější postup pro dekódování konvolučních kódů? a) Fubiniho algoritmus b) Viterbiho algoritmus c) Wyner-Ashův algoritmus d) Fanoův algoritmus správné řešení: b
6. Základní vlastností konvolučních kódů je: a) linearita b) asociativita c) kauzalita d) homogenita správné řešení: a
7. Jaká je definice konvolučního kódu? a) Konvoluční kód je soubor kódových posloupností, které odpovídají všempravděpodobným informačním posloupnostem. b) Konvoluční kód je soubor kódových posloupností, které odpovídají všem možným kódovým posloupnostem. c) Konvoluční kód je soubor kódových posloupností, které odpovídají všem možným informačním posloupnostem. d) Konvoluční kód je soubor kódových posloupností, které odpovídají všem náhodným informačním posloupnostem. správné řešení: c
8. Co je specifikováno konvolučním kodérem? a) struktura informačních posloupností b) struktura konvolučního kódu c) struktura kódových posloupností d) struktura obvodového zapojení správné řešení: d
45
9. Jak způsobem bývají nejčastěji realizovány konvoluční kodéry? a) posuvnými registry s plynule proměnnou rychlostí posuvu b) posuvnými registry s odlišnou rychlostí posuvu c) posuvnými registry se stejnou rychlostí posuvu d) posuvnými registry s konstantní rychlostí posuvu správné řešení: b
10. Jaký je významný parametr konvolučních kódů? a) omezující délka b) generující polynom c) úroveň zabezpečení d) generující matice správné řešení: a
11. Co popisuje generující matice? a) závislost výstupní posloupnosti na kódové posloupnosti b) závislost zdrojové posloupnosti na kódové posloupnosti c) závislost kódové posloupnosti na zdrojové posloupnosti d) závislost vstupní posloupnosti na kódové posloupnosti správné řešení: c
12. Názorným grafickým popisem generující matice je: a) kondiciogram b) Vennův diagram c) fázový diagram d) mřížkový diagram správné řešení: d
46
13. Jaká je nevýhoda Viterbiho algoritmu používaného pro dekódování konvolučních kódů? a) obtížně realizovatelné uspořádání dekodéru b) náročnost na počet numerických operací c) nemožnost dekódování kódů s relativně krátkými omezujícími délkami d) rozměrná kontrolní matice správné řešení: b
14. O který typ rozhodování se jedná v případě „rozhodování bit po bitu“? a) tvrdé rozhodování b) klouzavé rozhodování c) měkké rozhodování d) logické rozhodování správné řešení: a
15. Jaká je výhoda tvrdého rozhodování? a) relativně krátká rozhodovací doba b) nenáročnost na počet numerických operací c) relativně jednoduchá implementace d) rychlost rozhodovacího procesu správné řešení: c
16. O který typ rozhodování se jedná v případě „rozhodování po kódových slovech“? a) tvrdé rozhodování b) logické rozhodování c) klouzavé rozhodování d) měkké rozhodování správné řešení: d
47
17. Doplňte - Měkké rozhodování oproti rozhodování tvrdému kvantuje vzorky výstupního signálu demodulátoru a) do více kvantizačních úrovní b) pouze binárně c) s ohledem na kvalitu výstupního signálu pouze binárně d) s ohledem na kvalitu výstupního signálu pouze do více kvantizačních úrovní správné řešení: a
18. Jaká metrika rozhodováním?
je
aplikována
u metody
dekódování
s měkkým
a) Pythagorova vzdálenost b) Euklidova vzdálenost c) Taylorova vzdálenost d) Viterbiho vzdálenost správné řešení: b
19. Jaká je výhoda měkkého rozhodování? a) zlepšení účinnosti kódu b) zjednodušení výpočtu jednotlivých symbolů konvolučního kódu c) zlepšení kódového zisku d) zvýšení rychlosti rozhodovacího procesu správné řešení: c
20. Kterou logickou operací jsou vytvářeny kontrolní bity? a) OR b) AND c) NOR d) XOR správné řešení: d
48
21. Čím lze lokalizovat přesnou polohu chyby ve dvojkovém vyjádření zprávy? a) pomocí syndromu b) pomocí kontrolního bitu c) pomocí kontrolního symbolu d) pomocí kontrolního bytu správné řešení: a
22. Jakým způsobem jsou vytvářeny TURBO kódy? a) jako logicky zřetězené konvoluční kódy b) jako paralelně zřetězené konvoluční kódy c) jako konvolučně zřetězené konvoluční kódy d) jako sériově zřetězené konvoluční kódy správné řešení: b
23. Jakou zkratkou jsou označovány moduly dekodérů TURBO kódů? a) FIFO b) SOSI c) SISO d) LIFO správné řešení: c
24. Kodér konvolučního kódu pracující podle rekurzivní matice je označován jako: a) Reed-Solomonův kodér b) Read Slow kodér c) Random Seek kodér d) RSC kodér správné řešení: d
49
25. Který blok odděluje jednotlivé paralelně zřetězené RSC kodéry implementující TURBO kód? a) blok prokladu b) blok překladu c) zpožďovací člen d) vyrovnávací paměť správné řešení: a
26. Doplňte - TURBO kódy jsou kódy a) systematické b) blokové c) konvoluční d) symbolové správné řešení: b
27. Jakým způsobem lze zlepšit kódový poměr? a) tzv. rozšířením, což je proces přidání dalších kontrolních bitů b) tzv. zúžením, což je proces vypuštění všech kontrolních bitů c) tzv. zúžením, což je proces vypuštění některých kontrolních bitů d) tzv. rozšířením, což je proces přidání dalších kontrolních symbolů správné řešení: c
28. Doplňte - Jestliže je velikost bloku prokladu velká, a) zvyšuje se rychlost opravy chyb v TURBO kódu. b) schopnost TURBO kódu opravovat chyby zůstává stejná. c) zhoršuje se schopnost TURBO kódu opravovat chyby. d) zlepšuje se schopnost TURBO kódu opravovat chyby. správné řešení: d
50
29. Velikostí paměti využité v bloku prokladu se výrazně prodlužuje a) latentní doba dekodéru b) iterační doba dekodéru c) Hammingova doba dekodéru d) asymptotická doba dekodéru správné řešení: a
51
