Turbokód

Turbokódy jsou v teorii informace třídou vysoce výkonných samoopravných kódů vyvinutých v letech 1990-91 a publikovaných v roce 1993. Jde první praktické kódy, jejichž efektivita se blíží maximální kapacitě kanálu nebo Shannonovu limitu, teoretickému maximu kódového poměru, při níž je stále možná spolehlivá komunikace při dané úrovni šumu. Turbokódy se používají v 3G/4G mobilních komunikacních (například v Universal Mobile Telecommunications System a LTE) a pro komunikaci s kosmickými sondami i v dalších aplikacích, kde se návrháři snaží dosáhnout spolehlivého přenosu informací komunikačním spojem s omezenou šířkou pásma nebo latencí v přítomnosti šumu, který ovlivňuje signál. Turbokódy soupeří s LDPC kódy (s „nízkohustotní kontrolou parity“), které poskytují podobnou výkonnost.

Použití slova „turbo“ je inspirováno smyčkou zpětné vazby používanou při normálním dekódování turbokódu, která připomíná využití energie výfukových plynů pro pohon turbodmychadla ve spalovacích motorech. Joachim Hagenauer uvádí, že turbokód není vhodné pojmenování, protože při procesu kódování se zpětná vazba nepoužívá.

Historie

První žádost o patent na turbokódy byla podána 23. dubna 1991. +more V žádosti o patent je jako jediný objevitel turbokódů uveden Claude Berrou. Na základě žádosti bylo vydáno několik patentů včetně [url=https://www. google. com/patents/US5446747]US Patent 5,446,747[/url], který vypršel 29. srpna 2013.

První veřejný článek o turbokódech, „Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes“, byl publikován v roce 1993 v Proceedings of IEEE International Communications Conference. Článek byl kvůli prostorovým omezením rozdělen na tři samostatné příspěvky, jejichž autory byl Claude Berrou, Alain Glavieux a Punya Thitimajshima (z Télécom Bretagne, první ENST Bretagne, France). +more Z původní patentové přihlášky je však zřejmé, že objevitelem turbokódů je Claude Berrou, a další autoři článků přispěli jiným materiálem než hlavní myšlenkou.

Turbokódy byly natolik revoluční, že mnoho odborníků v oblasti kódování udávaným výsledkům nevěřilo. Potvrzení jejich výkonnosti vedlo k malé revoluci v oblasti kódování a objevům mnoha dalších typů iterativního zpracování signálu.

První třídou turbokódů je paralelní zřetězený konvoluční kód (PCCC). Po publikaci původních paralelních turbokódů v roce 1993 bylo objeveno mnoho dalších tříd turbokódů včetně sériové verze sériového zřetězeného konvolučního kódu a opakovacích akumulačních kódů. +more Iterativní metody turbo dekódování byly aplikovány i na obvyklejší samoopravné systémy, včetně Reedových-Solomonových opravných konvolučních kódů, které jsou však pro praktickou implementaci iterativními dekodéry příliš složité. Z konceptu turbo kódování vychází také turbo ekvalizace.

Kromě turbokódů vynalezl Berrou také rekurzivní systematické konvoluční (RSC) kódy, které použil v ukázkové implementaci turbokódů popsaných v patentu. Turbokódy používající RSC kódy mají lepší výkonnost.

Před objevem turbokódů byl nejlepším kódem sériový zřetězený kód vycházející z Reedova-Solomonova kódu s vnější opravou chyb kombinovaného s vnitřním konvolučním kódem dekódovaným pomocí Viterbiho algoritmu s omezenou délkou, který je znám pod jménem RSV kódy.

V pozdějším článku Berrou ocenil intuici „G. Battaila, Joachima Hagenauera a P. +more Hoehera, kteří na konci 80. let zdůrazňovali význam pravděpodobnostního zpracování. “ Uvádí, že „R. Gallager a M. Tanner už znali příbuzné techniky kódování a dekódování“, i když potřebné výpočty byly v té době těžko realizovatelné.

Ukázkový kodér

Následující ukázková implementace kodéru popisuje klasický turbo kodér a ukazuje obecné principy paralelních turbokódů. Existuje však mnoho variant turbokódů, které používají jiné kodéry komponent, vstupní/výstupní poměry, prokladače a vzorky pro zúžení kódu.

Tato implementace kodéru vytváří tři skupiny bitů. První skupina je m-bitový blok datového pole. +more Druhá skupina je n/2 paritních bitů datového pole vypočítaných pomocí rekurzivního systematického konvolučního kódu (RSC kód). Třetí skupina je n/2 paritních bitů pro známé permutace datového pole, opět vypočítaných pomocí RSC kódu. S datovým polem se tedy posílají dva různé nadbytečné skupiny paritních bitů. Kompletní blok má délku m + n bitů a kódový poměr je m/(m + n). Permutaci datového pole provádí zařízení nazývané prokladač.

V hardwarovém provedení sestává turbokodér ze dvou identických RSC kodérů, С1 a C2, které jsou vzájemně propojeny tak zvaným paralelním zřetězením, jak je ukázáno na obrázku:

Soubor:turbo encoder.svg

Na obrázku je písmenem M označen paměťový registr. Zpožďovací linka a prokladač způsobují, že se vstupní bity dk objevují ve změněném pořadí. +more Při první iteraci se vstupní posloupnost dk objevuje na obou výstupech kodéru, xk a y1k nebo y2k díky systematické povaze kodéru. Pokud se kodéry C1 a C2 používají v n1 a n2 iteracích, jejich poměry jsou rovny.

:\begin{align} ~R_1 &= \frac{n_1 + n_2}{2n_1 + n_2}\\ ~R_2 &= \frac{n_1 + n_2}{n_1 + 2n_2} \end{align}

Dekodér

Dekodér má podobnou strukturu jako výše uvedený kodér. Je tvořen dvěma propojenými elementárními dekodéry, které jsou na rozdíl od kodéru propojeny sériově. +more Dekodér \textstyle DEC_1 pracuje nižší rychlostí (tj. \textstyle R_1), a je tedy určen pro kodér \textstyle C_1; analogicky \textstyle DEC_2 je pro \textstyle C_2. \textstyle DEC_1 dává měkké rozhodnutí, který způsobuje zpoždění \textstyle L_1. Stejné zpoždění je způsobené zpožďovací linkou v kodéru. Funkce \textstyle DEC_2 způsobuje zpoždění \textstyle L_2.

Soubor:turbo decoder.svg

Prokladač vložený mezi dekodéry rozptyluje shluky chyb pocházející z výstupu \textstyle DEC_1. Blok DI je modul demultiplexování a vkládání. +more Funguje jako přepínač, který střídavě přesměrovává vstupní bity na \textstyle DEC_1 nebo \textstyle DEC_2. Ve stavu OFF se na \textstyle y_{1k} i \textstyle y_{2k} přívádějí výplňkové bity (nuly).

Uvažujme bezpaměťový kanál s aditivním bílým gaussovským šumem (AWGN) a předpokládejme, že v k-té iteraci dekodér přijímá dvojici náhodných proměnných:

:\begin{align} ~x_k &= (2d_k - 1) + a_k\\ ~y_k &= 2( Y_k - 1) + b_k \end{align}

kde \textstyle a_k a \textstyle b_k jsou nezávislé šumové komponenty se stejným rozptylem \textstyle \sigma^2. \textstyle Y_k je k-tý bit výstupu kodéru \textstyle y_k.

Nadbytečná informace je demultiplexována a pomocí DI odesílána do \textstyle DEC_1 (když \textstyle y_k = y_{1k}) nebo \textstyle DEC_2 (když \textstyle y_k = y_{2k}).

\textstyle DEC_1 dává měkké rozhodnutí, tj.:

:\Lambda(d_k) = \log\frac{p(d_k = 1)}{p(d_k = 0)}

které využívá \textstyle DEC_2. \textstyle \Lambda(d_k) se nazývá logaritmus poměru věrohodnosti (LLR). +more \textstyle p(d_k = i),\, i \in \{0, 1\} je aposteriorní pravděpodobnost (APP) \textstyle d_k datových bitů, která ukazuje pravděpodobnost interpretace přijetí \textstyle d_k bitu jako \textstyle i. Pokud vezmeme v úvahu LLR, \textstyle DEC_2 dává pevné rozhodnutí; tj. dekódovaný bit.

Je známo, že Viterbiho algoritmus není schopen vypočítat APP, a proto nemůže být používán jako \textstyle DEC_1. Místo toho se používá upravený BCJR algoritmus. +more Pro \textstyle DEC_2 lze Viterbiho algoritmus použít.

Zobrazená struktura však není optimální, protože \textstyle DEC_1 používá pouze část dostupné nadbytečné informace. Pro zlepšení struktury se používá smyčka zpětné vazby (která je na obrázku vyznačena čárkovaně).

Přístup s měkkým rozhodnutím

Přední část dekodéru produkuje pro každý bit datového proudu celé číslo, které udává, jak je pravděpodobné, že bit je 0 nebo 1. Toto číslo se nazývá měkký bit. +more Lze jej vybrat z rozsahu [−127, 127], kde: * −127 znamená „určitě 0“ * −100 znamená „velmi pravděpodobně 0“ * 0 znamená „se stejnou pravděpodobností 0 anebo 1“ * 100 znamená „velmi pravděpodobně 1“ * 127 znamená „určitě 1“.

To sice vnáší do datového proudu z přední části pravděpodobnostní aspekt, ale zároveň to přináší více informace o každém bitu, než kdyby to byla pouze 0 nebo 1.

Přední část tradičního bezdrátového přijímače musí u každého bitu rozhodnout, zda je interní analogové napětí větší nebo menší než daná referenční napěťová úroveň. V dekodéru turbokódu poskytuje přední část celočíselnou míru, jak moc se interní napětí liší od dané referenční úrovně.

Při dekódování m + n-bitového bloku dat přední část dekodéru produkuje pravděpodobnosti pro každý bit datového proudu. Existují dva paralelní dekodéry, jeden pro každý z n-/2bitových paritních segmentů. +more Oba dekodéry používají pro datové pole segment m věrohodnosti. Dekodér, který pracuje na druhém paritním segmentu zná permutace, které pro tento segment používal kodér.

Řešení hypotézy pro hledání bitů

Klíčovou inovací turbokódů je, jak se data o věrohodnosti používají pro vypořádání rozdílů mezi oběma dekodéry. Oba konvoluční dekodéry generují hypotézy (s odvozenou věrohodností) pro vzorek m bitů v datovém poli segmentu. +more Hypotetické bitové vzorky se porovnávají, a pokud se liší, dekodéry mění odvozené věrohodnosti, které mají pro každý bit hypotézy. Každý dekodér zahrnuje odvozené odhady věrohodnosti z druhého dekodéru a pro bity v datovém poli generuje nové hypotézy. Tyto nové hypotézy se pak porovnávají. Tento iterativní proces pokračuje tak dlouho, dokud se oba dekodéry neshodnou na stejné hypotéze pro m-bitový vzorek datového pole, typicky v 15 až 18 cyklech.

Existuje určitá analogie mezi popsaným procesem a řešením křížových problémů jako křížovky nebo sudoku. Uvažujme částečně vyluštěnou křížovku, v níž některá políčka mohou být vyplněna chybně. +more Dva lušticí stroje (dekodéry) se snaží tento problém řešit: jeden kontroluje pouze slova „svisle“ (paritní bity), druhý pouze slova „vodorovně“. Na začátku oba lušticí stroje odhadnou odpovědi (hypotézy) podle svých legend, a oznámí, jak si jsou jisté v jednotlivých písmenech (bitech datového pole). Pak porovnají poznámky, vzájemně si vymění odpovědi a odhady spolehlivosti, a zaznamenají, kde a jak se liší. Podle této nové znalosti oba přicházejí s aktualizovanými odpověďmi a odhady spolehlivosti, a celý proces se opakuje, dokud nedojdou ke stejnému řešení.

Provedení

Turbokódy mají dobrou výkonnost díky atraktivní kombinaci náhodného vzhledu kódu v kanálu spolu s fyzicky realizovatelnou dekódovací strukturou. Turbokódy jsou ovlivněny chybovým prahem.

Využití turbokódů v praxi

Turbokódy se využívají při rádiové komunikaci v telekomunikacích: * v sítích 3G a 4G mobilní telefonie; například v HSPA, EV-DO a 3GPP LTE * v pozemním systému mobilní televize MediaFLO firmy Qualcomm * v systémech satelitní komunikace se zpětným kanálem, jako například DVB-RCS a [url=http://www. dvb. +moreorg/standards/dvb-rcs2]DVB-RCS2[/url] * novější meziplanetární lety NASA, jako například Mars Reconnaissance Orbiter, používají turbokódy jako alternativu k RS-Viterbiho kódy * standard IEEE 802. 16 (WiMAX) pro bezdrátové metropolitní sítě používá blokové turbo kódy a konvoluční turbo kódy.

Bayesovské formulace

Z pohledu umělé inteligence lze turbokódy považovat za instanci smyčkového šíření přesvědčení v Bayesovských sítích.

Odkazy

Reference

Související články

Konvoluční kód * Viterbiho algoritmus * Dekódování s měkkým rozhodováním * Prokladač * BCJR algoritmus * Nízkohustotní kód s kontrolou parity * Sériový zřetězený konvoluční kód * Turbo Ekvalizer * Forward oprava chyb

Externí odkazy

[url=https://spectrum. ieee. +moreorg/computing/software/closing-in-on-the-perfect-code]"Closing In On The Perfect Code"[/url], IEEE Spectrum, March 2004 * [url=http://www. csee. wvu. edu/~mvalenti/documents/valenti01. pdf]"The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios"[/url] (International Journal of Wireless Information Networks) * ([url=https://www. newscientist. com/article. ns. id=mg18725071. 400]preview[/url] , [url=https://web. archive. org/web/20060902150939/http://geilenkotten. homeunix. org/TC_NS_09072005. pdf]kopie[/url]) * [url=http://www. sciencenews. org/articles/20051105/bob8. asp]"Pushing the Limit"[/url], vydání Science News o vývoji turbokódů * [url=http://www-turbo. enst-bretagne. fr/]International Symposium On Turbo Codes[/url] * [url=http://www. iterativesolutions. com/Matlab. htm]Coded Modulation Library[/url], open source knihovna pro simulaci turbokódů v matlabu * [url=http://www. ifp. uiuc. edu/~singer/journalpapers/tuchler_2002a. pdf]"Turbo Equalization: Principles and New Results"[/url], článek z IEEE Transactions on Communications o používání konvolučních kódu s kanálovou ekvalizací. * [url=http://itpp. sourceforge. net]IT++ Home Page[/url] The IT++ výkonná knihovna v C++, která mj. podporuje turbokódy * [url=http://www. inference. phy. cam. ac. uk/mackay/CodesTurbo. html]Turbo codes publikace od Davida MacKaye[/url] * [url=https://aff3ct. github. io]AFF3CT Home Page[/url] (A Fast Forward Error Correction Toolbox) pro softwarové simulace vysokorychlostních turbokódů * [url=http://www. scholarpedia. org/article/Turbo_codes]Turbo code[/url] autorů Dr. Sylvie Kerouédan a Dr. Claude Berrou (scholarpedia. org). * [url=https://www. intel. com/content/dam/www/programmable/us/en/pdfs/literature/an/an505. pdf]3GPP LTE Turbo Reference Design[/url]. * [url=https://www. mathworks. com/help/comm/ug/estimate-turbo-code-ber-performance-in-awgn. html]Odhad BER výkonnosti Turbokódů v AWGN[/url] (MatLab). * [url=https://www. mathworks. com/help/comm/examples/parallel-concatenated-convolutional-coding-turbo-codes. html]Parallel Concatenated Convolutional Coding: Turbo Codes (MatLab Simulink)[/url].

Literatura

Publikace

Battail, Gérard. "A conceptual framework for understanding turbo codes. +more" IEEE Journal on Selected Areas in Communications 16. 2 (1998): 245-254. * Brejza, Matthew F. , et al. "20 years of turbo coding and energy-aware design guidelines for energy-constrained wireless applications. " IEEE Communications Surveys & Tutorials 18. 1 (2016): 8-28. * Garzón-Bohórquez, Ronald, Charbel Abdel Nour, and Catherine Douillard. "Improving Turbo codes for 5G with parity puncture-constrained interleavers. " Turbo Codes and Iterative Information Processing (ISTC), 2016 9th International Symposium on. IEEE, 2016.

Kategorie:Detekce a oprava chyb Kategorie:Kódy blížící se kapacitě kanálu