Turbokód

Turbokódy (francouzsky Turbocodes, anglicky turbo codes) 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á.^[1]

První žádost o patent na turbokódy byla podána 23. dubna 1991. 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ě US Patent 5,446,747, který vypršel 29. srpna 2013.

První veřejný článek o turbokódech, „Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes“,^[2] 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). 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ů. 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. 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é.^[3]

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. 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ů, С₁ a C₂, které jsou vzájemně propojeny tak zvaným paralelním zřetězením, jak je ukázáno na obrázku:

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

${\displaystyle {\begin{aligned}~R_{1}&={\frac {n_{1}+n_{2}}{2n_{1}+n_{2}}}\\~R_{2}&={\frac {n_{1}+n_{2}}{n_{1}+2n_{2}}}\end{aligned}}}$

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ě. Dekodér ${\displaystyle \textstyle DEC_{1}}$ pracuje nižší rychlostí (tj. ${\displaystyle \textstyle R_{1}}$), a je tedy určen pro kodér ${\displaystyle \textstyle C_{1}}$; analogicky ${\displaystyle \textstyle DEC_{2}}$ je pro ${\displaystyle \textstyle C_{2}}$. ${\displaystyle \textstyle DEC_{1}}$ dává měkké rozhodnutí, který způsobuje zpoždění ${\displaystyle \textstyle L_{1}}$. Stejné zpoždění je způsobené zpožďovací linkou v kodéru. Funkce ${\displaystyle \textstyle DEC_{2}}$ způsobuje zpoždění ${\displaystyle \textstyle L_{2}}$.

Prokladač vložený mezi dekodéry rozptyluje shluky chyb pocházející z výstupu ${\displaystyle \textstyle DEC_{1}}$. Blok DI je modul demultiplexování a vkládání. Funguje jako přepínač, který střídavě přesměrovává vstupní bity na ${\displaystyle \textstyle DEC_{1}}$ nebo ${\displaystyle \textstyle DEC_{2}}$. Ve stavu OFF se na ${\displaystyle \textstyle y_{1k}}$ i ${\displaystyle \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:

${\displaystyle {\begin{aligned}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{k}\end{aligned}}}$

kde ${\displaystyle \textstyle a_{k}}$ a ${\displaystyle \textstyle b_{k}}$ jsou nezávislé šumové komponenty se stejným rozptylem ${\displaystyle \textstyle \sigma ^{2}}$. ${\displaystyle \textstyle Y_{k}}$ je k-tý bit výstupu kodéru ${\displaystyle \textstyle y_{k}}$.

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

${\displaystyle \textstyle DEC_{1}}$ dává měkké rozhodnutí, tj.:

${\displaystyle \Lambda (d_{k})=\log {\frac {p(d_{k}=1)}{p(d_{k}=0)}}}$

které využívá ${\displaystyle \textstyle DEC_{2}}$. ${\displaystyle \textstyle \Lambda (d_{k})}$ se nazývá logaritmus poměru věrohodnosti (LLR). ${\displaystyle \textstyle p(d_{k}=i),\,i\in \{0,1\}}$ je aposteriorní pravděpodobnost (APP) ${\displaystyle \textstyle d_{k}}$ datových bitů, která ukazuje pravděpodobnost interpretace přijetí ${\displaystyle \textstyle d_{k}}$ bitu jako ${\displaystyle \textstyle i}$. Pokud vezmeme v úvahu LLR, ${\displaystyle \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 ${\displaystyle \textstyle DEC_{1}}$. Místo toho se používá upravený BCJR algoritmus. Pro ${\displaystyle \textstyle DEC_{2}}$ lze Viterbiho algoritmus použít.

Zobrazená struktura však není optimální, protože ${\displaystyle \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ř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. 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ů. 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.

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. 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ě. 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í.

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.

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^[4] a DVB-RCS2 Archivováno 24. 6. 2017 na Wayback Machine.
• 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

Z pohledu umělé inteligence lze turbokódy považovat za instanci smyčkového šíření přesvědčení (anglicky belief propagation) v Bayesovských sítích.^[5]

V tomto článku byl použit překlad textu z článku Turbo code na anglické Wikipedii.

• 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

• "Closing In On The Perfect Code", IEEE Spectrum, March 2004
• "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios" Archivováno 20. 10. 2016 na Wayback Machine. (International Journal of Wireless Information Networks)
• MACKENZIE, Dana. Take it to the limit. [s.l.]: [s.n.], 2005. S. 38–41.  (preview Archivováno 30. 4. 2008 na Wayback Machine., kopie)
• "Pushing the Limit", vydání Science News o vývoji turbokódů
• International Symposium On Turbo Codes
• Coded Modulation Library, open source knihovna pro simulaci turbokódů v matlabu
• "Turbo Equalization: Principles and New Results" Archivováno 27. 2. 2009 na Wayback Machine., článek z IEEE Transactions on Communications o používání konvolučních kódu s kanálovou ekvalizací.
• IT++ Home Page The IT++ výkonná knihovna v C++, která mj. podporuje turbokódy
• Turbo codes publikace od Davida MacKaye
• AFF3CT Home Page (A Fast Forward Error Correction Toolbox) pro softwarové simulace vysokorychlostních turbokódů
• Turbo code autorů Dr. Sylvie Kerouédan a Dr. Claude Berrou (scholarpedia.org).
• 3GPP LTE Turbo Reference Design.
• Odhad BER výkonnosti Turbokódů v AWGN Archivováno 1. 2. 2019 na Wayback Machine. (MatLab).
• Parallel Concatenated Convolutional Coding: Turbo Codes (MatLab Simulink)