У теорији информација, турбо кодови су класа кодова за исправљање грешака унапред (FEC) високих перформанси, развијених око 1990–91. године, али први пут објављених 1993. Они су били први практични кодови који су се приближили максималном капацитету канала или Шеноновом лимиту, теоријском максимуму за кодни однос при којем је поуздана комуникација још увек могућа уз дати ниво шума. Турбо кодови се користе у 3G/4G мобилним комуникацијама (нпр. у UMTS-у и LTE-у) и у комуникацијама са сателитима у дубоком свемиру, као и у другим применама где дизајнери настоје да постигну поуздан пренос информација преко комуникационих линкова са ограниченим пропусним опсегом или кашњењем у присуству шума који квари податке. Турбо кодови се такмиче са кодовима са провером парности ниске густине (LDPC), који пружају сличне перформансе. Док није истекао патент за турбо кодове, статус LDPC кодова без патента био је важан фактор за континуирану релевантност LDPC-а. "Још једна предност, можда и највећа од свих, јесте то што су патенти за LDPC истекли, па компаније могу да их користе без плаћања права на интелектуалну својину."
Назив „турбо код” настао је због повратне спреге која се користи током нормалног декодирања турбо кода, што је аналогно повратној спрези издувних гасова која се користи за турбопуњење мотора. Јоахим Хагенауер је тврдио да је термин турбо код погрешан назив, јер у процесу кодирања нема повратне спреге.
Историја Основни патент за турбо кодове поднет је 23. априла 1991. године. У пријави патента као једини проналазач турбо кодова наведен је Клод Беру. Пријава патента резултирала је са неколико патената, укључујући амерички патент 5,446,747, који је истекао 29. августа 2013. године.
Први јавни рад о турбо кодовима био је „Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes” (срп. Кодирање и декодирање за исправљање грешака близу Шеноновог лимита: Турбо-кодови). Овај рад је објављен 1993. године у зборнику радова са IEEE међународне конференције о комуникацијама. Рад из 1993. настао је из три одвојена поднеска који су комбиновани због просторних ограничења. Због спајања, рад наводи три аутора: Беру, Главје, и Титимајшима (са , бивше , Француска). Међутим, из оригиналне пријаве патента јасно је да је Беру једини проналазач турбо кодова и да су други аутори рада допринели материјалу који није обухватао основне концепте.
Турбо кодови су били толико револуционарни у време свог увођења да многи стручњаци у области кодирања нису веровали у објављене резултате. Када су перформансе потврђене, дошло је до мале револуције у свету кодирања која је довела до истраживања многих других типова итеративне обраде сигнала.
Прва класа турбо кодова био је паралелни конкатенирани конволуциони код (PCCC). Од увођења оригиналних паралелних турбо кодова 1993. године, откривене су многе друге класе турбо кодова, укључујући серијски конкатенирани конволуциони кодови и кодове са понављањем и акумулацијом. Итеративне методе турбо декодирања такође су примењене на конвенционалније FEC системе, укључујући конволуционе кодове исправљене Рид-Соломоновим кодом, иако су ови системи превише сложени за практичну примену итеративних декодера. Турбо еквилизација је такође проистекла из концепта турбо кодирања.
Поред турбо кодова, Беру је такође изумео рекурзивне систематске конволуционе (RSC) кодове, који се користе у примеру имплементације турбо кодова описаном у патенту. Чини се да турбо кодови који користе RSC кодове имају боље перформансе од турбо кодова који их не користе.
Пре турбо кодова, најбоље конструкције су били серијски конкатенирани кодови засновани на спољашњем Рид-Соломоновом коду за исправљање грешака комбинованим са унутрашњим Витерби-декодираним конволуционим кодом кратке дужине ограничења, познатим и као RSV кодови.
У каснијем раду, Беру је одао признање интуицији „Ж. Батаја, Ј. Хагенауера и П. Хехера, који су крајем 80-их истакли значај пробабилистичке обраде.” Он додаје: „Роберт Г. Галагер и М. Танер су већ замислили технике кодирања и декодирања чији су општи принципи уско повезани”, иако су неопходни прорачуни у то време били непрактични.
Пример кодера Постоји много различитих врста турбо кодова, који користе различите компонентне кодере, односе улаза и излаза, интерливере и шаблоне за бушење. Овај пример имплементације кодера описује класични турбо кодер и демонстрира општи дизајн паралелних турбо кодова.
Ова имплементација кодера шаље три под-блока битова. Први под-блок је m-битни блок корисних података. Други под-блок су n/2 паритетних битова за корисне податке, израчунатих помоћу рекурзивног систематског конволуционог кода (RSC код). Трећи под-блок су n/2 паритетних битова за познату пермутацију корисних података, такође израчунатих помоћу RSC кода. Дакле, два редундантна, али различита под-блока паритетних битова се шаљу са корисним подацима. Комплетан блок има битова података са кодним односом од . Пермутација корисних података се врши помоћу уређаја који се зове интерливер.
Хардверски, овај турбо кодер се састоји од два идентична RSC кодера, C1 и C2, као што је приказано на слици, који су међусобно повезани помоћу шеме конкатенације, назване паралелна конкатенација:
центар|600п|Шематски приказ турбо кодера.
На слици, M је меморијски регистар. Линија за кашњење и интерливер приморавају улазне битове dk да се појављују у различитим секвенцама. На првој итерацији, улазна секвенца dk се појављује на оба излаза кодера, xk и y1k или y2k због систематске природе кодера. Ако се кодери C1 и C2 користе у n1 и n2 итерација, њихови кодни односи су респективно једнаки:
Декодер Декодер је изграђен на сличан начин као и горенаведени кодер. Два елементарна декодера су међусобно повезана, али серијски, а не паралелно. декодер ради на нижој брзини (тј. ), па је намењен за кодер, а је за одговарајуће. даје меку одлуку која узрокује кашњење. Исто кашњење узрокује и линија за кашњење у кодеру. Операција декодера узрокује кашњење.
центар|600п|Шематски приказ турбо декодера.
Интерливер инсталиран између два декодера користи се овде да распрши низ грешака (енгл. error bursts) које долазе са излаза . DI блок је модул за демултиплексирање и уметање. Ради као прекидач, преусмеравајући улазне битове на у једном тренутку и на у другом. У OFF стању, он напаја оба улаза и са битовима за попуњавање (нулама).
Размотримо меморијски AWGN канал без меморије и претпоставимо да у k-тој итерацији декодер прима пар случајних променљивих:
где су и независне компоненте шума са истом варијансом . је k-ти бит са излаза кодера.
Редундантне информације се демултиплексирају и шаљу преко DI до (када је ) и до (када је ).
доноси меку одлуку; тј.:
и доставља је . се назива логаритам односа вероватноће (LLR). је а постериори вероватноћа (APP) бита података која показује вероватноћу интерпретације примљеног бита као . Узимајући у обзир LLR, доноси чврсту одлуку; тј. декодирани бит.
Познато је да Витербијев алгоритам не може израчунати APP, па се не може користити у . Уместо тога, користи се модификовани BCJR алгоритам. За , Витербијев алгоритам је одговарајући.
Међутим, приказана структура није оптимална, јер користи само мали део доступних редундантних информација. Да би се структура побољшала, користи се повратна спрега (погледајте испрекидану линију на слици).
Приступ меке одлуке Предњи део декодера производи цео број за сваки бит у току података. Овај цео број је мера вероватноће да је бит 0 или 1 и назива се и меки бит. Цео број може бити из опсега [−127, 127], где: −127 значи „сигурно 0” −100 значи „врло вероватно 0” 0 значи „може бити или 0 или 1” 100 значи „врло вероватно 1” 127 значи „сигурно 1”
Ово уводи пробабилистички аспект у ток података са предњег дела, али преноси више информација о сваком биту него само 0 или 1.
На пример, за сваки бит, предњи део традиционалног бежичног пријемника мора да одлучи да ли је унутрашњи аналогни напон изнад или испод датог прага напона. За турбо кодерски декодер, предњи део би пружио целобројну меру колико је унутрашњи напон удаљен од датог прага.
Да би се декодирао -битни блок података, предњи део декодера креира блок мера вероватноће, са по једном мером вероватноће за сваки бит у току података. Постоје два паралелна декодера, по један за сваки од -битних паритетних под-блокова. Оба декодера користе под-блок од m вероватноћа за корисне податке. Декодер који ради на другом паритетном под-блоку зна пермутацију коју је кодер користио за овај под-блок.
Решавање хипотеза за проналажење битова Кључна иновација турбо кодова је начин на који користе податке о вероватноћи да би усагласили разлике између два декодера. Сваки од два конволуциона декодера генерише хипотезу (са изведеним вероватноћама) за образац од m битова у под-блоку корисних података. Обрасци битова хипотеза се упоређују, и ако се разликују, декодери размењују изведене вероватноће које имају за сваки бит у хипотезама. Сваки декодер укључује изведене процене вероватноће од другог декодера да би генерисао нову хипотезу за битове у корисним подацима. Затим упоређују ове нове хипотезе. Овај итеративни процес се наставља док два декодера не дођу до исте хипотезе за m-битни образац корисних података, обично у 15 до 18 циклуса.
Аналогија се може повући између овог процеса и решавања укрштених референци попут укрштених речи или судокуа. Замислите делимично попуњену, можда искривљену укрштеницу. Два решавача (декодера) покушавају да је реше: један има само „вертикалне” трагове (паритетне битове), а други само „хоризонталне” трагове. За почетак, оба решавача погађају одговоре (хипотезе) на своје трагове, бележећи колико су сигурни у свако слово (бит корисних података). Затим упоређују белешке, размењујући одговоре и оцене сигурности, примећујући где и како се разликују. На основу овог новог знања, обојица долазе до ажурираних одговора и оцена сигурности, понављајући цео процес док се не усагласе око истог решења.
Перформансе Турбо кодови добро функционишу због атрактивне комбинације насумичног изгледа кода на каналу и физички оствариве структуре за декодирање. На турбо кодове утиче под грешке (error floor).
Практичне примене које користе турбо кодове Телекомуникације: Турбо кодови се увелико користе у 3G и 4G стандардима за мобилну телефонију; нпр. у HSPA, EV-DO и LTE. MediaFLO, земаљски мобилни телевизијски систем компаније Qualcomm. Интеракциони канал сателитских комуникационих система, као што су DVB-RCSDigital Video Broadcasting (DVB); Interaction channel for Satellite Distribution Systems, ETSI EN 301 790, V1.5.1, мај 2009. и DVB-RCS2. Недавне NASA мисије попут Mars Reconnaissance Orbiter користе турбо кодове као алтернативу Рид-Соломон кодовима за исправљање грешака-Витерби декодерима. IEEE 802.16 (WiMAX), стандард за бежичне градске мреже, користи блок турбо кодирање и конволуционо турбо кодирање.
Бајесова формулација Са становишта вештачке интелигенције, турбо кодови се могу сматрати примером ширења уверења у петљи у Бајесовим мрежама.
Види још BCJR алгоритам Конволуциони код Кодови за исправљање грешака унапред Интерливер Код са провером парности мале густине Серијски конкатенирани конволуциони кодови Декодирање са меком одлуком Турбо еквилизатор Витербијев алгоритам
Референце
Литература
Спољашње везе
"The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios" (International Journal of Wireless Information Networks)
"Pushing the Limit", чланак у Science News о развоју и настанку турбо кодова International Symposium On Turbo Codes Coded Modulation Library, библиотека отвореног кода за симулацију турбо кодова у Matlab-у "Turbo Equalization: Principles and New Results" , чланак у IEEE Transactions on Communications о коришћењу конволуционих кодова заједно са еквилизацијом канала. IT++ Home Page IT++ је моћна C++ библиотека која посебно подржава турбо кодове Публикације о турбо кодовима Дејвида Макеја