Rok / Year: 2013
Svazek / Volume: 15
Číslo / Issue: 2
Turbo Blokové Kódy Turbo block codes Jakub Šedý, Pavel Šilhavý, Ondřej Krajsa, Ondřej Hrouza
[email protected] Fakulta elektrotechniky a komunikačních technologií VUT v Brně
Abstrakt: Článek se zabývá problematikou turbo blokových kódů, kódování těmito kódy, a také princip iterativního dekódování využívající Viterbiho algoritmus s tzv. měkkým výstupem. Dále je zhodnocena výkonnost turbo kódů na základě provedených simulací, které jsou založeny na různých parametrech kódu ovlivňující kódový zisk, bitovou chybovost a výpočetní náročnost.
Abstract: The article deals with turbo block codes, encoding these codes, and also the principle of iterative decoding using the Viterbi algorithm with soft output. In addition, it assesses the performance of turbo codes based on the simulations, which are based on different parameters affecting codes code gain, bit error rate and computational complexity.
VOL.15, NO.2, APRIL 2013
Turbo Blokové Kódy Jakub Šedý , Pavel Šilhavý , Ondřej Krajsa , Ondřej Hrouza Fakulta elektrotechniky a komunikačních technologií VUT v Brně Email:
[email protected]
Abstrakt – Článek se zabývá problematikou turbo blokových kódů, kódování těmito kódy, a také princip iterativního dekódování využívající Viterbiho algoritmus s tzv. měkkým výstupem. Dále je zhodnocena výkonnost turbo kódů na základě provedených simulací, které jsou založeny na různých parametrech kódu ovlivňující kódový zisk, bitovou chybovost a výpočetní náročnost.
Tabulka 1: Zkrácená tabulka BCH kódů. n
k
dmin
7 15
4 11 7 26 21 16
3 3 5 3 5 7
31
1
Úvod
Turbo kódy vykazují velký kódový zisk při vysokých datových rychlostech, a to i při relativně jednoduché realizaci. Díky svým vlastnostem mohou tyto kódy zajistit nízkou chybovost při nízkých hodnotách odstup signál šum, blížícího se Shannonovu limitu. Běžně se v turbo kódech používá jako dílčí kód, kód konvoluční, a to konkrétně RSC (Recursive Systematic Convolutional – rekurzivní systematický konvoluční)[3]. Je ale možné možné použít i kódy blokové BCH (Bose-Chaudhuri-Hocquenghem)[3] s kódovým poměrem (code rate) blížící se jedné. Pro tento kódový poměr jsou blokové kódy vhodnější. Při použití kódu s kódovým poměrem blížícím se 2/3 narůstá složitost dekódování. Z tohoto důvodu je vhodnější pro kódový poměr nižší jak 2/3 použít turbo kódy s konvolučními kodéry. Turbo blokové kódy [2] [3] je možné dekódovat pomocí algebraického dekódování, nebo pomocí mřížového nebo-li pravděpodobnostního dekódování, které bude rozebráno v tomto článku. Příkladem mřížového dekódování je SOVA (Viterbiho algoritmus s měkký výstupem – Soft-Output Viterbi Algorithm) nebo MAP (Maximum A-Posteriori) algoritmus [1] [2] [3] [4] [5].
2
g(x)octal 13 23 721 45 3551 107657
Protože BCH kódy jsou cyklické kódy, lze je implementovat použitím posuvných registrů. Kódy mohou být buď nesystematické, anebo systematické. Protože turbo kódy používají pouze systematické kódy, bude dále rozebírán pouze systematický BCH kód. Pro systematické kódy lze vytvářecí mnohočlen g(x) zapsat, jak uvádí (2) [3]: g(x) = g0 + g1 x + g2 x2 + . . . + gn−k−1 xn−k−1 + gn−k xn−k . (2) Vytvářecí mnohočlen g(x) určuje n bitů kódového slova, a to tak, že se přidává ke k informačním bitům (n − k) paritních bitů. Kodér N používá (n − k) Lposuvných registrů, viz obrázek 1, kde je násobení a je modulo - 2 (XOR). Paritní bity se počítají z bitů informačních, přenášených dat, dle pravidel daných vytvářecím mnohočlenem. Proces
BCH kódy
BCH kodér přijímá vstupní posloupnost o k bitech a generuje n výstupních bitů. Minimální Hammingova vzdálenost kódového slova je dmin . BCH kód je proto označen jako BCH (n, k, dmin ). V tabulce 1, která je převzata z [3], nalezneme zkrácený výpis často používaných BCH kódů s vytvářecími mnohočleny g(x). Koeficient g(x) je zadán v osmičkové soustavě, a proto je nutné ho převést do soustavy binární a následně do tvaru polynomu, viz (1). g(x)octal
=
13
g(x)bin
=
1011
g(x)
= x3 + x + 1.
(1)
Obrázek 1: Kodér BCH (n, k, dmin ) s (n – k ) posuvnými registry. kódování je následující. Přepínač 1 je sepnutý po dobu prvních k posunů. Informační bity d(x) se posouvají v pořadí přes posuvné registry a zároveň přepínač 2 je ve spodní pozici přičemž se informační data d(x) v podstatě zkopírují
100
VOL.15, NO.2, APRIL 2013
do výstupu c(x). Po k-tém posunu se přepínač 1 rozepne a přepínač 2 přepne do horní polohy. Následně se vyčistí posuvné registry, a to tak, že jejich aktuální hodnoty se použijí jako paritní bity.
3
informací pro druhý dekodér. Stejným způsobem se vnější informace z druhého dekodéru vrací zpět do prvního dekodéru jako vnitřní informace. Oba dekodéry si vzájemně napomáhají vyměňováním informací souvisejících s datovými bity, proto se jedná o iterativní dekódování.
Turbo BCH kodér
Základní struktura turbo BCH kodéru je zobrazena na obrázku 2. Jsou zde použity dva BCH kodéry, mezi které je vložen prokladač. Je zde možno použít blokové nebo náhodné prokládání.
Obrázek 3: Schéma turbo BCH dekodéru.
Obrázek 2: Blokové schéma turbo BCH kodéru. Výstup z obou kodérů je následně multiplexován a může být i zúžen. Vhodným návrhem zúžení a multiplexování je možné dosáhnout stejného celkového kódového poměru, jako u původního BCH kódu. Avšak tento způsob zvyšování kódového poměru se nedoporučuje z důvodu degradace výkonnosti kódu. Výstupní posloupnost z kodéru při použití BCH kódu s parametry (7, 4, 3) bude obsahovat čtyři systematické a šest paritních bitů a bude mít následu1 2 1 2 1 2 jící podobu y1s , y2s , y3s , y4s , y1l , y1l , y2l , y2l , y3l , y3l , kde 1 2 yks jsou systematické bity a ykl , ykl jsou paritní bity z prvního a druhého kodéru.
4
Turbo BCH dekodér
Obrázek 3 uvádí strukturu turbo blokového dekodéru. Jednotlivé vstupy a výstupy jsou popsány následovně: z jsou přijaté vzorky, uk dekódované bity, Lc yk demultiplexovaný měkký výstup, L(uk ) vnitřní informace (a-priori informace), Le (uk ) vnější informace a L(uk | y) a-posteriori informace. Z obrázku je zřejmé, že turbo dekodér používá dva BCH dekodéry. Vzhledem k tomu, že použijeme metodu mřížového dekódování, je tedy možné použít algoritmy jako je SOVA nebo MAP [1] [2] [3]. Dekodér používá měkký výstup z kanálu Lc y a vnitřní informaci L(uk ) k tomu, aby mohl následně poskytnout na výstupu a-posteriori informaci L(uk | y). Vnější informace Le (uk ) je dána odečtením měkkého výstupu kanálu Lc y a vnitřní informace L(uk ) od a-posterioni informace L(uk | y) dle vztahu (3). Le (uk ) = L(uk | y) − Lc yk − L(uk ).
(3)
4.1
Viterbiho algoritmus
Implementace Viterbiho algoritmu s měkkým výstupem SOVA pro dekódování turbo BCH kódů je velmi podobná implementaci SOVA v turbo kódech využívající konvoluční kódy [6]. SOVA má v případě turbo dekodéru dvě modifikace. První modifikace říká, že metrika cesty je modifikována tak, aby počítala s vnitřní informací L(uk ). Druhá modifikace pro algoritmus je poskytování a-posteriori informace L(uk | y) pro každý dekódovaný bit. Kódové slovo BCH kódu, je složeno z datových a paritních bitů. V turbo blokovém dekódování projde přes dekodér pouze měkký výstup původních datových bitů do dalšího dekodéru. Není zde vnitřní informace L(uk ) pro paritní bity. Výpočet metriky cesty je tedy [3]: M (sk ) = M (sk−1 ) +
uk {L(uk ) + Lc yk } . 2
(4)
Nyní se budeme věnovat výše uvedené druhé modifikaci Viterbiho algoritmu, a to a-posteriori informaci L(uk | y), pomocí které počítáme vnější informaci Le (uk ). V mřížovém diagramu, kde dvě cesty dosahují stavu Sk = s, bude cesta s nižší metrikou vyřazena. Přežívající cesta se značí sk a nepřežívající (vyřazená) ˆsk . Rozdíl metrik těchto cest se vypočítá, jak uvádí [3]: ∆k = M (sk ) − M (ˆsk ) ≥ 0.
(5)
LLR (Log Likelihood Ratio – logaritmicko pravděpodobnostní poměr) rozhodnutí ML cesty sk se vypočítá:
Poté, co je bitová posloupnost dle obrázku 3 proložena nebo zpětně proložena, se vnější informace Le (uk ) stává vnitřní
101
L{P (sk )} = ln
P (sk ) = ∆k . 1 − P (sk )
(6)
VOL.15, NO.2, APRIL 2013
v tabulce 2. Kód byl zvolen BCH(31,26,3). Uspořádání dílčích kodérů je paralelní a prokládání je pseudonáhodné. Turbo kodér má kódový poměr R = 0, 72 tzn., že nebylo aplikováno zúžení. Dekodér používá k dekódování SOVA algoritmus a zpravidla bylo provedeno šest iterací dekódování. V následujících simulacích budou v grafech vždy vynášeny šesté iterace dekódování. Simulace předpokládá přenos s pomocí modulace BPSK přes přenosový kanál AWGN. Výkonnost turbo kódů je možno ovlivnit mnoha parametry: • Počet iterací, které provede dekodér při dekódování.
Obrázek 4: Zjednodušený mřížový diagram pro BCH de-
• Použití zúžení při kódování.
kódování.
• Volba dekódovacího algoritmu.
Nyní je zapotřebí získat LLR dekódovaných bitů. Na obrázku 4 je znázorněn zjednodušený mřížový diagram, kde ML cesta představuje posloupnost nul. Z obrázku je zřejmé, že cesta c −→ b −→ a, tedy cesta sˆk a cesta c −→ c −→ b −→ a ˆsk+1 jsou cesty nepřežívající v poˆ s u ˆkk
• Volba kódu.
Tabulka 2: Parametry turbo kodeku pro simulace.
ˆ s u ˆkk+1
zici k a k + 1. Tedy jsou dekódované bity ve a stavu k, které by byly výstupem pro vyřazené cesty ˆsk a ˆsk+1 v případě, že by tyto cesty nebyly vyřazeny. Jak je ˆ s vidět na obrázku uk a u ˆkk jsou odlišné. Z tohoto důvodu je LLR aktuálně dekódovaného bitu uk roven ∆k . Naopak ˆ s pro bit uk a u ˆkk+1 by nedošlo k chybě, protože dekódovaná hodnota bitu je stejná, bez ohledu na to, jestli by vybraná cesta byla sk nebo ˆsk+1 . Pak by byla hodnota LLR pro bit uk rovna ∞. Vztah pro LLR bitu uk , beroucí v úvahu nepřežívající cestu ˆsk+i , je definován jako: ( Lˆsk+i (uk ) = uk ·
∞ ∆k
když uk když uk
Kanál Modulace Kodér Parametry BCH kódu Zúžení Dekodér P. iterací
ˆ s
= u ˆkk+i ˆ s 6 = u ˆkk+i ,
(7)
5.1
kde i ≥ 0. Nicméně vztah (7) pracuje pouze s jednou nepřežívající cestou, zatímco podél ML cesty může být více nepřežívajících cest. Je tedy výhodnější počítat LLR L(uk | y) podle následujícího vzorce: L(uk | y) = uk ·
min j=k···n
ˆ s uk 6=u ˆkj
∆j .
Vliv počtu iterací BER v závislosti na Eb/N0
-1
10
(8)
-2
10 BER
Algoritmus zkoumá, jestli nedošlo k chybnému rozhodnutí v mřížovém diagramu. Tyto potenciálně nespolehlivé rozhodnutí jsou spojené s vyřazením cesty s podobnou metrikou, jakou měla cesta přežívající, a tedy se tyto cesty vyznačují malými rozdíly mezi metrikami ∆. Z tohoto důvodu hledá algoritmus uzly, kde byl tento rozdíl nejmenší a prověřuje tyto vyřazené cesty, aby nedošlo ke špatnému dekódování bitu.
5
AWGN BPSK Dva identické paralelně řazené BCH kodéry n = 31, k = 26, dmin = 3, není použito R = 0, 72 SOVA 6
-3
10
nekódované 1. iterace 2. iterace 4. iterace 6. iterace 8. iterace 14. iterace
-4
10
0
1
2
3 Eb/N0 [dB]
4
5
6
Výkonnost turbo BCH kódů
V této kapitole se budeme věnovat simulacím provedených za použití různých parametrů kódu, které mohou ovlivnit výkonnost. Základní nastavení kodeku je znázorněno
Obrázek 5: Výkonnost turbo blokových kódů v závislosti na použitém počtu iterací dekodéru.
102
VOL.15, NO.2, APRIL 2013
Na obrázku 5 je znázorněna výkonnost turbo blokového kódu v závislosti na použitém počtu iterací dekodéru. Dále je v obrázku vynesena závislost pro nekódovanou posloupnost. S narůstajícím počtem iterací narůstá i výkonnost turbo blokového kódu, podobně jako tomu je v turbo konvolučních kódech [6]. Rozdíl výkonnosti mezi první a druhou iterací na hodnotě BER 10−4 je 0,5 dB. Jak narůstá počet iterací, rozdíl mezi jednotlivými iteracemi se snižuje až k šesté iteraci. Nárůst výkonnosti mezi 6. a 14. iterací je prakticky nulový. Z obrázku 5 je tedy možné odvodit, že nárůst výkonnosti je od určitého počtu iterací zanedbatelný.
5.3
Vliv dekódovacího algoritmu
Na obrázku 7 je zobrazeno porovnání výkonnosti turbo blokového kódu v závislosti na použitém dekódovacím algoritmu. Jedná se o algoritmus SOVA a algoritmus Log-MAP. Log-MAP dosahuje lepší výkonnosti jak SOVA, a to o 0,3 dB na hodnotě BER 10−4 .
BER v závislosti na Eb/N0
-1
10
-2
10
Vliv zúžení
BER
5.2
Vlivem zúžení je možné snížit počet paritních bitů před vstupem do přenosového kanálu. V našem případě byl počet paritních bitů snížen na polovinu, což ovlivnilo kódový poměr turbo blokového kodéru na hodnotu R = 0, 84. Na obrázku 6 je zobrazena výkonnost turbo blokového kódu v závislosti na použití zúžení. Rozdíl mezi turbo kódem používající zúžení a turbo kódem nepoužívající zúžení je na hodnotě BER 10−3 téměř 0,75 dB. Může se zdát, že použití zúžení v případe turbo blokových kódů je výhodné jako u turbo konvolučních kódů [6]. Pokud bychom porovnali výkonnost klasického BCH(31,26,3) kódu [3], pak by výkonnost turbo blokového kódu za použití zúžení byla minimálně srovnatelná nebo horší jak u klasického BCH kódu.
-3
10
nekódované Log-MAP SOVA -4
10
0
0.5
1
1.5
2
2.5 3 Eb/N0 [dB]
3.5
4
4.5
5
Obrázek 7: Výkonnost turbo blokových kódů v závislosti na použitém dekódovacím algoritmu.
5.4
Vliv volby kódu
BER v závislosti na Eb/N0
-1
10
BER v závislosti na Eb/N0
-1
10
-2
10
-2
BER
BER
10
-3
10
-3
10 nekódované Nezúžené, R=0,72 Zúženo 5 paritních bitů, R=0,84
nekódované BCH(7,4,3), R=0,40 BCH(15,11,3), R=0,58 BCH(31,26,3), R=0,72 BCH(63,57,3), R=0,83
-4
10
0
0.5
1
1.5
2
2.5 3 Eb/N0 [dB]
3.5
4
4.5
5 -4
10
0
0.5
1
1.5
2
2.5 3 Eb/N0 [dB]
3.5
4
4.5
5
Obrázek 6: Výkonnost turbo blokových kódů v závislosti na použití zúžení.
Obrázek 8: Výkonnost turbo blokových kódů v závislosti na zvoleném BCH kódu.
103
VOL.15, NO.2, APRIL 2013
Obrázek 8 uvádí závislost turbo blokového kódu na zvoleném BCH kódu. Jako první kód byl zvolen BCH (7, 4, 3) s kódovým poměrem R = 0, 4. Tento kód dosáhl hodnoty BER 10−4 na hodnotě Eb /N0 4,5 dB. Dalším zvoleným kódem je BCH (63, 57, 3) s kódovým poměrem R = 0, 83, a pro tento kód dosahoval turbo kodér nejhorších výsledků. Na hodnotu BER 10−4 dosáhl až na Eb /N0 5,2 dB. Třetí zvolený kód by byl použit pro všechny simulace a jedná se o kód BCH (31, 26, 3) s kódovým poměrem R = 0, 72, který dosahuje hodnot BER 10−4 na hodnotě Eb /N0 4,8 dB. Posledním zvoleným kódem je BCH (15, 11, 3) s kódovým poměrem R = 0, 58. Turbo kód používající tento kód dosahoval v simulaci nejlepší výkonnosti, která byla na hodnotě BER 10−4 o 0,4 dB od BCH (7, 4, 3), 0,8 dB od BCH (31, 26, 3) a 1,1dB od BCH (63, 57, 3).
6
[4] HUANG, F. Iterative Turbo Decoder. [online]. [cit. 2013-01-24]. Dostupné z: http://scholar.lib.vt.edu/theses/available/etd-7189715815/unrestricted/chap4.pdf [5] MOON, T. K. Error correction coding: mathematical methods and algorithms. Hoboken: John Wiley, 2004, 756 s. ISBN 0-471-64800-0. [6] ŠEDÝ, J., Turbo konvoluční kódy. Elektrorevue - Internetový časopis (http://www.elektrorevue.cz), 2011, roč. 2011, č. 35, s. 1-6. ISSN: 1213- 1539.
Závěr
Tento článek byl věnován problematice turbo blokových kódů. Bylo popsáno kódování pomocí BCH kódů a jejich aplikace do turbo kodéru a uvedeny základní matematické vztahy pro dekódovací algoritmus SOVA. Rovněž byla na základě simulací analyzována výkonnost turbo blokových kódů. Na základě těchto simulací je možné říci, že výkonnost turbo kódu roste se zvyšujícím se počtem provedených iterací dekódování a vhodnou volbou kódu, tj. vytvářecího mnohočlenu. Výkonnost turbo kódů naopak klesá při použití zúžení, které má kritický dopad na výkonnost turbo blokových kódů narozdíl od turbo konvolučních kódů. Je tedy možné sestavit kodér s vysokou výkonností pří relativně vysokém kódovém poměru blížícím se k jedné. Cenou je však rostoucí výpočetní náročnost vlivem vysokého počtu iterací nebo způsobená volbou kódu.
Poděkování Popsaný výzkum byl realizován v laboratořích podpořených z projektu SIX; registrační číslo CZ.1.05/2.1.00/03.0072, operační program Výzkum a vývoj pro inovace a za podpory Technické Agentury České Republiky, projekt č. TA02020856.
Literatura [1] FARELL, P. G. MOREIRA, J. C. Essentials of ErrorControl Coding. John Wiley, 2006, ISBN-13 978-0-47002920-6. [2] GLAVIEUX, A. Channel coding in communication networks: from theory to turbocodes. London: ISTE, 2007, xvii, 418 s. ISBN 190520924x. [3] HANZO, L. LIEW, T. YEAP, B. Turbo coding, turbo equalisation and space-time coding: for transmission over fading chanels. Chichester: John Wiley, 2002, 748 s. ISBN 0470847263.
104
