Turbo kode

Turbokode er en parallel kaskadedelt blok systematisk kode , der kan rette fejl, der opstår, når digital information transmitteres over en støjende kommunikationskanal . Turbocode er synonymt med det velkendte udtryk i kodningsteori - sammenkædet kode ( foreslået af D. Forney i 1966).

En turbokode består af en kaskade af systematiske koder forbundet parallelt. Disse komponenter kaldes komponentkoder. Konvolutionskoder , Hamming-koder , Reed-Solomon- koder , Bowes-Chowdhury-Hokvingham-koder og andre kan bruges som komponentkoder . Afhængigt af valget af komponentkoden opdeles turbokoder i foldningsturbokoder ( Turbo - konvolutionskoder, TCC ) og blokproduktkoder (Turboproduktkoder , TPC ) [1] .

Turbokoder blev udviklet i 1993 og er en klasse af højeffektive fejlkorrigerende fejlkorrigerende koder , brugt i elektroteknik og digital kommunikation , og har også fundet deres anvendelse i satellitkommunikation og andre områder, hvor det er nødvendigt at opnå det maksimale dataoverførselshastighed over en kommunikationskanal med støj i begrænset frekvensbånd .

Historie

Indtil fremkomsten af turbokoden var den sammenkædede kodningsmetode udbredt, hvor dataene først blev kodet af Reed-Solomon-koden og derefter af foldningskoden . Den kommer tæt nok på Shannon-grænsen og kombinerer en fejlkorrektionsblok ved hjælp af Reed-Solomon-koden og en blok af foldningskoder afkodet ved hjælp af Viterbi-algoritmen .

Turbokoderne blev foreslået af C. Berrou , A. Glavieux og P. Thitimajshima fra École Nationale Supérieure des Télécommunications de Bretagne (ENST Bretagne) , The Higher National School of Telecommunications of Bretagne ( Frankrig )) i 1993 i avisen " Near Shannon Limit Error- correcting Coding and Decoding : Turbo-code" [ 2] , offentliggjort i IEEE Proceedings . I et efterfølgende papir [3] krediterer Burrow intuitionen af G. Battail , J. Hagenauer og P. Hoeher , som teoretisk forudsagde probabilistisk databehandling i slutningen af 1980'erne . Burrow nævner også, at Robert Gallagher og M. Tanner ( M. Tanner ) stadig på et tidspunkt repræsenterede metoder til kodning og afkodning med generelle principper meget tæt på turbokoder, men på det tidspunkt var de nødvendige beregningsmuligheder ikke tilgængelige .

Turbokodestruktur

Ifølge Shannon er den bedste kode den , der transmitterer en besked på uendelig lang tid, og genererer tilfældige kodeelementer på hvert tidspunkt. . Modtageren har uendelige versioner af en tilfældigt ødelagt besked. Fra disse kopier skal dekoderen vælge den kopi, der er tættest på den sendte besked. Dette er en teoretisk ideel kode , der kan rette alle fejl i et signal. Turbocode er et skridt i den retning. Det er klart, at vi ikke skal sende en informativ besked i uendelig lang tid. En fordobling eller tredobling af overførselstiden er nok til acceptabel ydeevne, hvilket vil give ret anstændige resultater for kommunikationskanalerne.

Et træk ved turbokoder er en parallel struktur bestående af rekursive systematiske foldningskoder (RSC) , der fungerer parallelt og bruger oprettelsen af en tilfældig version af beskeden. Den parallelle struktur bruger to eller flere RSC- koder , hver med en forskellig interleaver . Formålet med interleaveren er at tilbyde hver indkoder en ukorreleret eller tilfældig version af informationen , hvorved paritetsbittene for hver RSC bliver uafhængige .

I turbokoder er blokke i størrelsesordenen flere kbits lange. Formålet med denne længde er effektivt at randomisere sekvensen, der går til den anden indkoder. Jo længere blokstørrelsen er, jo bedre er dens korrelation med meddelelsen fra den første indkoder, det vil sige, at korrelationen er lille.

Der er flere turbokodeskemaer:

PCCC - i tilfælde af sammenkædning af parallelle foldningskoder
SCCC er et seriel forbindelsesskema af foldningskoder, SCCC -koder har høj ydeevne ved høje signal-til-støj-forhold
TPC - turbo produktkode , bruger blokkoder i stedet for foldningskoder; to forskellige blokkoder (normalt Hamming-koder ) er forbundet i serie uden en mellemliggende interleaver . Da de to koder er uafhængige og fungerer i rækker og kolonner, hvilket i sig selv giver en rimelig god randomisering, er der ikke behov for interleaver .

Kodning

På fig. 1 er et generelt blokdiagram af en M-blok turbokoder.

Først ankommer en datablok med en bitlængde til PAD'ens input ( Packet Assembler / Disassembler ) . I pakkeformeren tilføjes yderligere bits af serviceinformation til dataene, svarende til den anvendte pakkedannelsesstandard og inklusive tegnene for dens begyndelse og slutning [4] . Det vil sige, at der opnås en pakke bestående af bits. $U$ $k$ $(nk)$ $X_{0}$ $n$

Yderligere indtræder sekvensen af bit parallelt på grenene, der indeholder den serielt forbundne interleaver og komponentkoderen. Den bruges således som input af alle komponentkodere på én gang. $X_{0}$ $M$ $X_{0}$

Interleaving i turbokoder

I interleavere , ifølge en pseudo-tilfældig lov, er de indkommende bits blandet. I modsætning til den per-symbol rektangulære interleaver , der bruges i Reed-Solomon- koder, bruger turbokoder single - bit interleaving , som ligner tilfældige permutationer. Desuden vil denne sammenfletningslov senere, under afkodningsoperationer, blive betragtet som kendt. De resulterende sekvenser føres til indkoderne.

Interleaverens opgave er at transformere inputsekvensen, således at kombinationer af bit svarende til kodeord med lav vægt ( vægt er antallet af ikke-nul bits af kodeordet) ved udgangen af den første indkoder transformeres til kombinationer, der giver kodeord med høj vægt ved udgangene af andre encodere. Indkodere udsender således kodeord med forskellig vægt. Ved kodning dannes kodeord, så den maksimalt mulige gennemsnitlige afstand mellem dem opnås ( afstanden mellem to kodeord er antallet af bits, hvori de adskiller sig). På grund af det faktum, at kodeblokkene er dannet af næsten uafhængige dele, ved udgangen af turbokoderen, er den gennemsnitlige afstand mellem kodeord større end minimumsafstanden for hver komponentkoder, og dermed øges kodningseffektiviteten. $X_{0}$

Permutationen for hver specificeret bloklængde er givet ved en specifik omarrangering af heltal som leveret af følgende algoritme ( ECSS -E-ST-50-01C) [5] . $k$ $1, 2..., k$

$k = 8 * k_0$ , hvor en af følgende værdier: , , , , afhængigt af den påkrævede interleaver- dybde $k_0 =$ $223$ $223*2$ $223*4$ $223*5$

Følgende operationer udføres på værdier fra til for at få permutationsadresserne . I ligningerne nedenfor angiver det største heltal mindre end eller lig med , og angiver et af følgende fire primtal : $s = 1$ $s = k$ $\boldsymbol \pi(s)$ $\mathcal{b} \boldsymbol x \mathcal{c}$ $\fed symbol x$ $\boldsymbol p_q$ $p_0 = 31,$ $p_1 = 37,$ $p_2 = 43,$ $p_3 = 47,$

$m = (s-1)\mod 2$

$i = \mathcal{b} \frac{ s-1 }{2*k_0} \mathcal{c}$

$j = \mathcal{b} \frac{ s-1 }{2} \mathcal{c} - i*k_0$

$q = (19*i+1) \mod 4$

$c = (p_q*j+21*m) \mod k_0$

$\boldsymbol\pi(s) = 2*(q + 4*c + 1) - m$

Fortolkningen af permutationen er, at den -te bit, der transmitteres af interleaveren , er den -te bit af inputinformationsblokken. Interleaveren skriver den modtagne bit til den beregnede adresse. $\fed symboler$ $\fedsymbol\pi(s)$

Kodehastighed

Kodehastighed - forholdet mellem længden af kodeblokken ved indgangen og længden af den transformerede kodeblok ved udgangen af koderen.

I fravær af en puncher (se fig. 1) multiplekses den oprindelige sekvens med sekvenser af paritetsbit , der danner et kodeord, der skal transmitteres over kanalen. Derefter værdien af kodehastigheden ved udgangen af turboencoderen $X_{0}$ $V_1,\ldots,V_M$

$R = \frac{k}{n(M+1)}$

For at øge kodehastigheden anvendes punktering (perforering) af visse kontrolbits i outputsekvensen. Kodehastigheden stiger således til

$R = \frac{k}{n(N+1)}$ , hvor , og kan være fraktioneret, hvis antallet af tilbageværende kontrolbit efter perforering ikke er et multiplum af . $N<M$ $N$ $n$

Hvis vi tager i betragtning, at turbokoder fungerer med blokke af stor længde c , så er , og kodehastigheden lig med $k > 10.000$ $k \ca n$

$R = \frac{1}{N+1}$

Ud fra ovenstående formler kan det ses, at ved hjælp af en perforator, der punkterer et andet antal kontrolbits, er det muligt at regulere kodehastigheden. Det vil sige, at du kan bygge en encoder, der tilpasser sig kommunikationskanalen. Når kanalen er støjende, punkterer perforatoren færre bits, hvilket forårsager et fald i kodehastigheden og en stigning i støjimmuniteten for indkoderen. Hvis kommunikationskanalen er af god kvalitet, så kan et stort antal bits punkteres, hvilket forårsager en stigning i informationsoverførselshastigheden [6] .

Afkodning

Maksimal posterior sandsynlighed (MAP) afkodningsalgoritme

Når man udfører afkodning med fejlkorrektion, er det væsentligt at analysere a priori og a posteriori sandsynligheden for ankomsten af det korrekte kodeord. A priori er den information, som dekoderen har før ankomsten af kodeordet, og a posteriori er informationen opnået efter behandling af kodeordet.

Burrow foreslår til brug i turbo-dekodere Maximum of A -posteriori Probability (MAP ) -algoritmen, også kendt som Bala-algoritmen ( Bahl-Cocke-Jelinek-Raviv (BCJR) ). Bals algoritme giver et " blødt " konfidensestimat for den afkodede bit. Det vil sige, at det giver en grad af tillid til afkodningsresultatet ved udgangen. I modsætning til den " hårde " struktur, hvor kun den mest sandsynlige værdi af den afkodede bit ("0" eller "1") dannes ved udgangen af dekoderen, når der træffes en "blød" beslutning, en mere detaljeret sampling af udgangssignalet bruges, hvilket karakteriserer sandsynligheden for korrekt modtagelse af bit. På grund af brugen af "bløde" beslutninger i turbo-dekodere, er det effektivt at bruge flere afkodningsiterationer . Den a posteriori-information, der opnås om kodeordet ved udgangen af den første dekodningsiteration, føres til indgangen af blokken i den næste iteration og er allerede en a priori sandsynlighed for den. Denne tilgang gør det muligt at forbedre kvaliteten af afkodningen fra iteration til iteration. Ved at ændre antallet af dekodningsiterationer er det således muligt at tilpasse dekoderen til transmissionskanalens aktuelle tilstand og opnå den nødvendige bitfejlssandsynlighed [6] .

Log Likelihood Ratio (LLR)

Betragt informationsbitten som en binær variabel , det vil sige værdien på det tidspunkt . Dens log-likelihood ratio (LLR) er defineret som logaritmen af forholdet mellem dets underliggende sandsynligheder. $\boldsymbol u_k$ $\fedsymbol u$ $k$

$L(u_k) = \ln \frac {Pr(u_k = 1)}{Pr(u_k = 0)}$

Denne metrik bruges i de fleste fejlkorrektionssystemer med fejlkorrigerende kodning og kaldes log-likelihood ratio eller LLR . Det er lidt bedre end den lineære metriske , fordi for eksempel logaritmen gør det lettere at håndtere meget små og meget store værdier. Hvis modtagelsessandsynlighederne for "0" og "1" er ens, er metrikken 0.

Én iteration af den iterative turbo-dekoder med to-trins kodning

På fig. 2, for at lette forståelsen, er der vist en variant af skemaet med én iteration af turbo-afkodning i to-trins kodning. Dette skema kan let generaliseres til tilfældet med et vilkårligt antal kodningstrin.

Dekoderen for én iteration indeholder en kaskadeforbindelse af to elementære dekodere, som hver, baseret på kriterierne for den maksimale a posteriori sandsynlighed, træffer en "blød" beslutning om det transmitterede symbol. Den første dekoder af den første iteration fra udgangen af demodulatoren modtager "bløde" løsninger for symbolerne for sekvenserne og . Ved udgangen af den første dekoder fremkommer således et estimat af informationssymbolet , som efter efterfølgende interleaving kommer ind i input af den anden dekoder og er a priori information for denne. Ved at bruge en "blød" beslutning om sekvensen danner den anden dekoder sit estimat [7] $X_{0}$ $X_{1}$ $X_{2}$

Tre-iterations turbo-dekoder med to-trins kodning

Fra outputtet af hver iteration går løsningen videre til input fra den næste. Organiseringen af arbejdet for tre-iterations turbo-dekoderen er vist i fig. 3. Fra iteration til iteration raffineres løsningen. Samtidig arbejder hver iteration med "bløde" estimater og giver også "bløde" til outputtet. Derfor kaldes sådanne skemaer dekodere med soft input og soft output ( eng. Soft Input Soft Output (SISO) ) [8] . Afkodningsprocessen stopper enten efter at alle iterationer er afsluttet, eller når bitfejlssandsynligheden når den krævede værdi. Efter afkodning fremstilles den endelige "hårde" opløsning ud fra den opnåede "bløde" opløsning [7] .

Fordele og ulemper ved turbokoder

Fordele

Af alle moderne fejlkorrektionsmetoder i praksis, kommer turbokoder og lavdensitet paritetskontrolkoder tættest på Shannon - grænsen, den teoretiske grænse for den maksimale gennemstrømning af en støjende kanal. Turbokoder giver dig mulighed for at øge datahastigheden uden at kræve en stigning i sendereffekten , eller de kan bruges til at reducere den nødvendige effekt, når du sender med en given hastighed. En vigtig fordel ved turbokoder er uafhængigheden af afkodningskompleksitet fra længden af informationsblokken, hvilket reducerer sandsynligheden for afkodningsfejl ved at øge dens længde [9] .

Ulemper

Den største ulempe ved turbokoder er den relativt høje afkodningskompleksitet og høje latens, hvilket gør dem ubelejlige for nogle applikationer. Men for eksempel til brug i satellitkanaler er denne ulempe ikke afgørende, da længden af selve kommunikationskanalen introducerer en forsinkelse forårsaget af lyshastighedens endelighed .

En anden vigtig ulempe ved turbokoder er den relativt lille kodeafstand (det vil sige minimumsafstanden mellem to kodeord i betydningen af den valgte metrik ). Dette fører til det faktum, at selvom ydeevnen af turbokoden er høj, når inputfejlraten er stor (dvs. i en dårlig kanal), er turbokodens ydeevne ekstremt begrænset, når inputfejlraten er lav. [10] Derfor, i gode kanaler, bruges der ikke turbokoder, men LDPC-koder for yderligere at reducere fejlsandsynligheden .

Selvom kompleksiteten af de anvendte turbokodningsalgoritmer og manglen på open source-software har hindret vedtagelsen af turbokoder, bruger mange moderne systemer i øjeblikket turbokoder.

Anvendelse af turbokoder

France Télécom og Telediffusion de France har patenteret en bred klasse af turbokoder, hvilket begrænser muligheden for deres frie brug og samtidig stimulerer udviklingen af nye kodningsmetoder som f.eks. LDPC .

Turbokoder bruges aktivt i satellit- og mobilkommunikationssystemer , trådløs bredbåndsadgang og digitalt tv . [8] Turbokoder er godkendt i DVB-RCS satellitkommunikationsstandarden . Turbokoder har også fundet bred anvendelse i tredje generations mobilkommunikationssystemer ( CDMA2000 og UMTS-standarder ). [9]

Noter

↑ Zolotarev V.V., Ovechkin G.V., Ovechkin P.V. Multi-tærskeldekodning til digitale datatransmissionssystemer . Hentet 21. november 2008. Arkiveret fra originalen 30. januar 2012. (Russisk)
↑ Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limit fejlkorrigerende kodning og afkodning: Turbo-koder ( 1993). Hentet 21. november 2008. Arkiveret fra originalen 30. januar 2012.
↑ Berrou C. Ti år gamle turbokoder kommer i brug (engelsk) (2003). Hentet 21. november 2008. Arkiveret fra originalen 30. januar 2012.
↑ Semenov Yu. A. X.25 netværksprotokoller . (Russisk)
↑ ECSS- E -ST-50-01C . Arkiveret fra originalen den 30. januar 2012.
↑ 1 2 Zubarev Yu. B., Krivosheev M. I., Krasnoselsky I. N. Digital tv-udsendelse. Fundamentaler, metoder, systemer. - M .: Scientific Research Institute of Radio (NIIR), 2001. - S. 112-120.
↑ 1 2 . Komarov S. V., Postnikov S. A., Levshin V. I., Dremachev D. V., Artemiev N. V. Anvendelse af turbokoder i multimediekommunikationssystemer af tredje generation: Samling af artikler. Teori og teknologi for radiokommunikation. - 2003. - S. 112-119.
↑ 1 2 Arkhipkin A. Turbokoder - kraftfulde algoritmer til moderne kommunikationssystemer (Journal. Wireless Technologies) (2006). Hentet 21. november 2008. Arkiveret fra originalen 30. januar 2012. (Russisk)
↑ 1 2 Vargauzin V., Protopopov L. Turbokoder og iterativ afkodning: principper, egenskaber, anvendelse (2000). (Russisk)
↑ Moon, Todd K. Fejlkorrektionskodning: matematiske metoder og algoritmer. - John Wiley & Sons, 2005. - side 612.