Zobrazení zdroje stránky Turbokód

'''Turbokódy''' ({{Vjazyce2|fr|''Turbocodes''}}, {{Vjazyce2|en|''turbo codes''}}) jsou v [[teorie informace|teorii informace]] třídou vysoce výkonných [[Samoopravný kód|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 [[Shannonova–Hartleyova věta|Shannonovu limitu]], teoretickému maximu [[Kódový poměr|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 [[Long Term Evolution|LTE]]) a pro komunikaci s [[Kosmická sonda|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ód]]y (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 [[Turbodmychadlo|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á.<ref>{{Citace elektronické monografie
 | url = http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf
 | jméno = Joachim
 | příjmení = Joachim Hagenauer
 | titul = Iterative Decoding of Binary Block and Convolutional Code
 | datum přístupu = 2014-03-20
 | url-status = mrtvý
 | url archivu = https://web.archive.org/web/20130611235418/http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf
 | datum archivace = 2013-06-11
}}</ref>

== Historie ==
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ě [https://www.google.com/patents/US5446747 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''“,<ref>{{Citace monografie
 | url = https://www.researchgate.net/publication/360427
 | jméno = Claude
 | příjmení = Berrou
 | jméno2 = Alain
 | příjmení2 = Glavieux
 | jméno3 = Punya
 | příjmení3 = Thitimajshima
 | titul = Near Shannon Limit Error – Correcting
 | datum přístupu = 2010-02-11
}}</ref> 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í [[École Nationale Supérieure des Télécommunications de Bretagne|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ý zřetězený konvoluční kód|sériového zřetězeného konvolučního kódu]] a [[Opakovací akumulační kód|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 [[Reedovy–Solomonovy kódy|Reedova–Solomonova kódu]] s vnější opravou chyb kombinovaného s vnitřním [[Konvoluční kód|konvolučním kódem]] dekódovaným pomocí [[Viterbiho algoritmus|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, [[Joachim Hagenauer|Joachima Hagenauera]] a P. Hoehera, kteří na konci 80. let zdůrazňovali význam pravděpodobnostního zpracování.“ Uvádí, že „[[Robert G. Gallager|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é.<ref>{{Citace monografie
 | jméno = Claude
 | příjmení = Berrou
 | titul = The ten-year-old turbo codes are entering into service
 | místo = Bretagne, France
 | datum přístupu = 2010-02-11
 | url = https://www.researchgate.net/publication/3199004
}}</ref>

== 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. Druhá skupina je ''n/2'' paritních bitů datového pole vypočítaných pomocí rekurzivního systematického [[Konvoluční kód|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 {{nowrap|''m'' + ''n''}} bitů a kódový poměr je {{nowrap|''m''/(''m'' + ''n'')}}. [[Permutace|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ů, С<sub>1</sub> a C<sub>2</sub>, 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 d<sub>k</sub> objevují ve změněném pořadí.
Při první iteraci se vstupní posloupnost ''d''<sub>k</sub> objevuje na obou výstupech kodéru, ''x''<sub>k</sub> a'' y''<sub>1k</sub> nebo ''y''<sub>2k</sub> díky systematické povaze kodéru. Pokud se kodéry ''C''<sub>1</sub> a ''C''<sub>2</sub> používají v ''n''<sub>1</sub> a ''n''<sub>2</sub> iteracích, jejich poměry jsou rovny

:<math>\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}</math>

== 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ě. Dekodér <math>\textstyle DEC_1</math> pracuje nižší rychlostí (tj. <math>\textstyle R_1</math>), a je tedy určen pro kodér <math>\textstyle C_1</math>; analogicky <math>\textstyle DEC_2</math> je pro <math>\textstyle C_2</math>. <math>\textstyle DEC_1</math> dává [[Turbokód#Přístup s měkkým rozhodnutím|měkké rozhodnutí]], který způsobuje zpoždění <math>\textstyle L_1</math>. Stejné zpoždění je způsobené zpožďovací linkou v kodéru. Funkce <math>\textstyle DEC_2</math> způsobuje zpoždění <math>\textstyle L_2</math>.

[[Soubor:turbo decoder.svg]]

Prokladač vložený mezi dekodéry rozptyluje shluky chyb pocházející z výstupu <math>\textstyle DEC_1</math>. 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 <math>\textstyle DEC_1</math> nebo <math>\textstyle DEC_2</math>. Ve stavu OFF se na <math>\textstyle y_{1k}</math> i <math>\textstyle y_{2k}</math> přívádějí výplňkové bity (nuly).

Uvažujme bezpaměťový kanál s [[Aditivní bílý gaussovský šum|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:

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

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

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

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

:<math>\Lambda(d_k) = \log\frac{p(d_k = 1)}{p(d_k = 0)}</math>

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

Zobrazená struktura však není optimální, protože <math>\textstyle DEC_1</math> 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''. 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í {{nowrap|''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.

== Ř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. 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řížovka|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í.

== 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ý práh|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 [[High Speed Paket Access|HSPA]], [[EV-DO]] a 3GPP [[Long Term Evolution|LTE]]
* v pozemním systému mobilní televize [[MediaFLO]] firmy [[Qualcomm]]
* v systémech [[Telekomunikační družice|satelitní komunikace]] se [[Zpětný kanál|zpětným kanálem]], jako například [[DVB-RCS]]<ref>[http://www.etsi.org/deliver/etsi_en/301700_301799/301790/01.05.01_60/en_301790v010501p.pdf Digital Video Broadcasting (DVB); Interaction channel for Satellite Distribution Systems], ETSI EN 301 790, V1.5.1, May 2009.</ref> a [http://www.dvb.org/standards/dvb-rcs2 DVB-RCS2] {{Wayback|url=http://www.dvb.org/standards/dvb-rcs2 |date=20170624210148 }}
* novější meziplanetární lety [[NASA]], jako například [[Mars Reconnaissance Orbiter]], používají turbokódy jako alternativu k [[Reedovy–Solomonovy kódy|RS]]-[[Viterbi dekodér|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|umělé inteligence]] lze turbokódy považovat za instanci smyčkového [[šíření přesvědčení]] ({{Vjazyce2|en|''belief propagation''}}) v [[Bayesovská síť|bayesovských sítích]].<ref>{{Citace monografie
 | příjmení = McEliece
 | jméno = Robert J.
 | příjmení2 = MacKay
 | jméno2 = David J. C.
 | příjmení3 = Cheng
 | jméno3 = Jung-Fu
 | titul = Turbo decoding as an instance of Pearl's "belief propagation" algorithm
 | periodikum = IEEE Journal on Selected Areas in Communication
 | ročník = 16
 | číslo = 2
 | strany = 140–152
 | rok = 1998
 | issn = 0733-8716
 | doi = 10.1109/49.661103
 | postscript = .
 | url = https://authors.library.caltech.edu/6938/1/MCEieeejstc98.pdf
}}</ref>

== Odkazy ==

=== Reference ===
{{Překlad|en|Turbo code|962946292}}<references />

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

=== Literatura ===
{{refbegin}}

=== Publikace ===
* Battail, Gérard. "A conceptual framework for understanding turbo codes." 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.
{{Autoritní data}}

{{DEFAULTSORT:Turbo Code}}
[[Kategorie:Detekce a oprava chyb]]
[[Kategorie:Kódy blížící se kapacitě kanálu]]