Turbokode - Turbo code

I informationsteorien er turbokoder (oprindeligt på franske turbocodes ) en klasse af højtydende fremadrettede fejlkorrektionskoder (FEC), der blev udviklet omkring 1990-91, men først offentliggjort i 1993. De var de første praktiske koder, der tæt nærmer sig den maksimale kanal kapacitet eller Shannon-grænse , et teoretisk maksimum for kodehastigheden, hvor pålidelig kommunikation stadig er mulig givet et specifikt støjniveau. Turbo koder bruges i 3G / 4G mobilkommunikation (fx i UMTS og LTE ) og i ( deep space ) satellit -kommunikation samt andre applikationer, hvor designere søger at opnå pålidelige oplysninger overførsel over bandwidth- eller ventetid-begrænsede kommunikationsforbindelser i tilstedeværelse af datakorruptionsstøj. Turbokoder konkurrerer med LDPC- koder med lav densitet (LDPC), som giver lignende ydeevne.

Navnet "turbokode" opstod fra den tilbagekoblingssløjfe, der blev brugt under normal turbokodeafkodning, som blev analogiseret med den udstødningsfeedback, der blev brugt til motor turboladning . Hagenauer har hævdet, at udtrykket turbokode er en misvisende betegnelse, da der ikke er nogen feedback involveret i kodningsprocessen.

Historie

Den grundlæggende patentansøgning om turbokoder blev indgivet den 23. april 1991. Patentansøgningen viser Claude Berrou som den eneste opfinder af turbokoder. Patentindgivelsen resulterede i flere patenter inklusive amerikansk patent 5.446.747 , som udløb 29. august 2013.

Det første offentlige papir om turbokoder var " Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes ". Dette papir blev offentliggjort i 1993 i Proceedings of IEEE International Communications Conference. 1993-papiret blev dannet af tre separate indlæg, der blev kombineret på grund af pladsbegrænsninger. Fusionen fik papiret til at liste tre forfattere: Berrou, Glavieux og Thitimajshima (fra Télécom Bretagne, tidligere ENST Bretagne , Frankrig). Det fremgår imidlertid klart af den oprindelige patentansøgning, at Berrou er den eneste opfinder af turbokoder, og at de andre forfattere af papiret bidrog med andet materiale end kernebegreberne.

Turbokoder var så revolutionerende på tidspunktet for deres introduktion, at mange eksperter inden for kodning ikke troede på de rapporterede resultater. Da forestillingen blev bekræftet, fandt en lille revolution i verden af kodning sted, der førte til undersøgelse af mange andre typer iterativ signalbehandling.

Den første klasse af turbokode var den parallelle sammenkædede opløsningskode (PCCC). Siden introduktionen af de originale parallelle turbokoder i 1993 er der opdaget mange andre klasser af turbokoder, herunder serielle versioner serielle sammenkædede foldningskoder og gentagne akkumuleringskoder . Iterative turbodekodningsmetoder er også blevet anvendt på mere konventionelle FEC-systemer, herunder Reed-Solomon-korrigerede foldningskoder, selvom disse systemer er for komplekse til praktiske implementeringer af iterative dekodere. Turboudligning strømmede også fra begrebet turbokodning.

Ud over turbokoder opfandt Berrou også rekursive systematiske foldningskoder (RSC), som anvendes i eksemplet på implementering af turbokoder beskrevet i patentet. Turbokoder, der bruger RSC-koder, synes at fungere bedre end turbokoder, der ikke bruger RSC-koder.

Før turbokoder, de bedste konstruktioner var serielle konkatenerede koder baseret på en ydre Reed-Solomon fejlkorrektion kode kombineret med en indre Viterbi-dekodes korte begrænsningslængde foldningskode , også kendt som RSV koder.

I et senere papir gav Berrou æren til intuitionen fra "G. Battail, J. Hagenauer og P. Hoeher, der i slutningen af 80'erne fremhævede interessen for sandsynlig behandling." Han tilføjer " R. Gallager og M. Tanner havde allerede forestillet sig kodning og afkodningsteknikker, hvis generelle principper er nært beslægtede," skønt de nødvendige beregninger var upraktiske på det tidspunkt.

Et eksempel på en indkoder

Der er mange forskellige forekomster af turbokoder, der bruger forskellige komponentkodere, input / output-forhold, interleavers og punkteringsmønstre. Dette eksempel på implementering af koderen beskriver en klassisk turbokoder og demonstrerer det generelle design af parallelle turbokoder.

Denne kodningsimplementering sender tre underblokke af bits. Den første underblok er m- bit blok af nyttelastdata. Den anden underblok er n / 2 paritetsbits til nyttelastdata, beregnet ved hjælp af en rekursiv systematisk foldningskode (RSC-kode). Den tredje underblok er n / 2 paritetsbits til en kendt permutation af nyttelastdataene, igen beregnet ved anvendelse af en RSC-kode. Således sendes to overflødige, men forskellige underblokke af paritetsbit med nyttelasten. Den komplette blok har m + n bits data med en kodehastighed på m / ( m + n ) . Den permutation af nyttelasten data udføres af en enhed kaldet en interleaver .

Hardware-wise, denne turbokodeindkoder består af to ens RSC-kodere, C ₁ og C ₂ , som vist i figuren, som er forbundet med hinanden ved hjælp af en sammenkædning ordning, kaldet parallel sammenkædning :

I figuren er M et hukommelsesregister. Forsinkelseslinjen og interleaver tvinger inputbitene _dk til at vises i forskellige sekvenser. Ved første iteration, inputsekvensen d _k vises ved begge udgange på koderen, x _k og y _1k eller y _2k grund indkoderens systematiske karakter. Hvis koderne C ₁ og C ₂ anvendes i n ₁ og n ₂ iterationer, er deres satser henholdsvis lig med

{\ displaystyle {\ 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}}}

Dekoderen

Dekoderen er bygget på samme måde som ovennævnte encoder. To elementære dekodere er forbundet med hinanden, men i serie, ikke parallelt. Den dekoderen fungerer på lavere hastighed (dvs. ), således, det er beregnet til encoder, og er for tilsvarende. giver en blød beslutning, der forårsager forsinkelse. Den samme forsinkelse skyldes forsinkelseslinjen i koderen. Funktionen forårsager forsinkelse. ${\ displaystyle \ textstyle DEC_ {1}}$ ${\ displaystyle \ textstyle R_ {1}}$ ${\ displaystyle \ textstyle C_ {1}}$ ${\ displaystyle \ textstyle DEC_ {2}}$ ${\ displaystyle \ textstyle C_ {2}}$ ${\ displaystyle \ textstyle DEC_ {1}}$ ${\ displaystyle \ textstyle L_ {1}}$ ${\ displaystyle \ textstyle DEC_ {2}}$ ${\ displaystyle \ textstyle L_ {2}}$

En interleaver installeret mellem de to dekodere bruges her til at sprede fejlburst fra output. DI- blok er et demultiplexerings- og indsættelsesmodul. Det fungerer som en switch, der omdirigerer inputbits til i et øjeblik og til et andet. I OFF-tilstand føder den begge og input med polstringsbits (nuller). ${\ displaystyle \ textstyle DEC_ {1}}$ ${\ displaystyle \ textstyle DEC_ {1}}$ ${\ displaystyle \ textstyle DEC_ {2}}$ ${\ displaystyle \ textstyle y_ {1k}}$ ${\ displaystyle \ textstyle y_ {2k}}$

Overvej en hukommelsesløs AWGN- kanal, og antag, at ved k- th iteration modtager dekoderen et par tilfældige variabler:

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

hvor og er uafhængige støjkomponenter med samme varians . er en k- th bit fra encoder output. ${\ displaystyle \ textstyle a_ {k}}$ ${\ displaystyle \ textstyle b_ {k}}$ ${\ displaystyle \ textstyle \ sigma ^ {2}}$ ${\ displaystyle \ textstyle Y_ {k}}$ ${\ displaystyle \ textstyle y_ {k}}$

Overflødige oplysninger demultiplexes og sendes via DI til (hvornår ) og til (hvornår ). ${\ displaystyle \ textstyle DEC_ {1}}$ ${\ displaystyle \ textstyle y_ {k} = y_ {1k}}$ ${\ displaystyle \ textstyle DEC_ {2}}$ ${\ displaystyle \ textstyle y_ {k} = y_ {2k}}$

${\ displaystyle \ textstyle DEC_ {1}}$ giver en blød beslutning; dvs.

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

og leverer det til . kaldes logaritmen for sandsynlighedsforholdet (LLR). er den efterfølgende sandsynlighed (APP) for databitten, som viser sandsynligheden for at fortolke en modtaget bit som . At tage LLR i betragtning giver en hård beslutning; dvs. en afkodet bit. ${\ displaystyle \ textstyle DEC_ {2}}$ ${\ displaystyle \ textstyle \ Lambda (d_ {k})}$ ${\ displaystyle \ textstyle p (d_ {k} = i), \, i \ in \ {0,1 \}}$ ${\ displaystyle \ textstyle d_ {k}}$ ${\ displaystyle \ textstyle d_ {k}}$ ${\ displaystyle \ textstyle i}$ ${\ displaystyle \ textstyle DEC_ {2}}$

Det er kendt, at Viterbi-algoritmen ikke er i stand til at beregne APP, og den kan derfor ikke bruges i . I stedet for det anvendes en modificeret BCJR-algoritme . For , at Viterbi-algoritmen er en passende én. ${\ displaystyle \ textstyle DEC_ {1}}$ ${\ displaystyle \ textstyle DEC_ {2}}$

Imidlertid er den afbildede struktur ikke optimal, fordi den kun bruger en ordentlig brøkdel af den tilgængelige overflødige information. For at forbedre strukturen anvendes en tilbagekoblingssløjfe (se den stiplede linje på figuren). ${\ displaystyle \ textstyle DEC_ {1}}$

Blød beslutningstilgang

Dekoderfrontfronten producerer et heltal for hver bit i datastrømmen. Dette heltal er et mål for, hvor sandsynligt det er, at bit er 0 eller 1 og også kaldes soft bit . Heltallet kunne tegnes fra området [−127, 127], hvor:

−127 betyder "bestemt 0"
−100 betyder "meget sandsynligt 0"
0 betyder "det kan være enten 0 eller 1"
100 betyder "meget sandsynligt 1"
127 betyder "bestemt 1"

Dette introducerer et sandsynligt aspekt til datastrømmen fra frontenden, men det formidler mere information om hver bit end bare 0 eller 1.

For eksempel skal forenden af en traditionel trådløs modtager for hver bit afgøre, om en intern analog spænding er over eller under et givet tærskelspændingsniveau. For en turbokodekoder vil frontenden tilvejebringe et heltal mål for, hvor langt den interne spænding er fra den givne tærskel.

For at afkode m + n- bitblokken af data opretter dekoderfrontfronten en blok med sandsynlighedsmål med et sandsynlighedsmål for hver bit i datastrømmen. Der er to parallelle dekodere, en til hver af de n ⁄ 2- bit paritets underblokke. Begge dekodere bruger delblokken af m sandsynligheder for payload data. Dekoderen, der arbejder på den anden paritetsunderblok, kender permutationen, som koderen brugte til denne underblok.

Løsning af hypoteser for at finde bits

Den vigtigste innovation i turbokoder er, hvordan de bruger sandsynlighedsdataene til at afstemme forskelle mellem de to dekodere. Hver af de to foldede dekodere genererer en hypotese (med afledte sandsynligheder) for mønsteret af m bits i nyttelast-underblokken. Hypotesebitmønstrene sammenlignes, og hvis de adskiller sig, udveksler dekoderne de afledte sandsynligheder, de har for hver bit i hypoteserne. Hver dekoder inkorporerer de afledte sandsynlighedsestimater fra den anden dekoder for at generere en ny hypotese for bitene i nyttelasten. Derefter sammenligner de disse nye hypoteser. Denne iterative proces fortsætter, indtil de to dekodere kommer med den samme hypotese for nyttelastens m- bit mønster, typisk i 15 til 18 cyklusser.

En analogi kan trækkes mellem denne proces og løsningen af krydsreferencer som krydsord eller sudoku . Overvej et delvist afsluttet, muligvis forvansket krydsord. To puslespilleløsere (dekodere) forsøger at løse det: den ene har kun de "ned" spor (paritetsbiter), og den anden har kun de "på tværs" ledetråde. For at starte, gætter begge løsere svarene (hypoteser) på deres egne spor, idet de bemærker, hvor sikre de er i hvert bogstav (nyttelastbit). Derefter sammenligner de noter ved at udveksle svar og tillidsvurderinger med hinanden og bemærke, hvor og hvordan de adskiller sig. Baseret på denne nye viden kommer de begge med opdaterede svar og tillidsvurderinger og gentager hele processen, indtil de konvergerer til den samme løsning.

Ydeevne

Turbokoder fungerer godt på grund af den attraktive kombination af kodens tilfældige udseende på kanalen sammen med den fysisk realiserbare afkodningsstruktur. Turbokoder påvirkes af et fejlgulv .

Praktiske applikationer ved hjælp af turbokoder

Telekommunikation:

Turbokoder bruges i vid udstrækning i 3G- og 4G- mobiltelefonistandarder; f.eks. i HSPA , EV-DO og LTE .
MediaFLO , jordbaseret mobil-tv-system fra Qualcomm .
Den interaktionskanal af satellitkommunikationssystemer systemer, såsom DVB-RCS og DVB-RCS2 .
Nylige NASA- missioner som Mars Reconnaissance Orbiter bruger turbokoder som et alternativ til Reed – Solomon-fejlkorrektion - Viterbi-dekoderkoder .
IEEE 802.16 ( WiMAX ), en trådløs hovedstadsnetværksstandard, bruger blokturbokodning og konvolverende turbokodning.

Bayesisk formulering

Fra et synspunkt af kunstig intelligens kan turbokoder betragtes som en forekomst af loopy trosformering i Bayesiske netværk .

Se også

Referencer

Yderligere læsning

Publikationer

Battail, Gérard. "En konceptuel ramme til forståelse af turbokoder." IEEE Journal on Selected Areas in Communications 16.2 (1998): 245-254.
Brejza, Matthew F., et al. "20 års turbokodning og energibevidste designretningslinjer for energibegrænsede trådløse applikationer." IEEE Communications Surveys & Tutorials 18.1 (2016): 8–28.
Garzón-Bohórquez, Ronald, Charbel Abdel Nour og Catherine Douillard. "Forbedring af turbokoder til 5G med paritets-punkterede begrænsede interleavers." Turbokoder og Iterativ informationsbehandling (ISTC), 9. 9. internationale symposium om 2016. IEEE, 2016.

eksterne links

"Closing in On The Perfect Code" , IEEE Spectrum, marts 2004
"UMTS Turbo-koden og en effektiv dekoderimplementering velegnet til softwaredefinerede radioer" ( International Journal of Wireless Information Networks )
Dana Mackenzie (2005), "Tag det til det yderste", New Scientist , 187 (2507): 38–41, ISSN 0262-4079 .( forhåndsvisning , kopi )
"Pushing the Limit" , en Science News- funktion om udvikling og oprindelse af turbokoder
Internationalt symposium om turbokoder
Coded Modulation Library , et open source-bibliotek til simulering af turbokoder i matlab
"Turboudligning: Principper og nye resultater" , en IEEE-transaktion på kommunikationsartikel om brug af foldningskoder sammen med kanaludligning.
IT ++ Home Page Den IT ++ er en kraftfuld C ++ bibliotek, som især understøtter turbo koder
Turbokoder publikationer af David MacKay
AFF3CT Hjemmeside (En hurtig fremad fejlkorrektionsværktøjskasse) til højhastigheds-turbokodesimuleringer i software
Turbo kode af Dr. Sylvie Kerouédan og Dr. Claude Berrou (scholarpedia.org).
3GPP LTE Turbo Reference Design .
Anslå Turbo-kode BER-ydeevne i AWGN (MatLab).
Parallel sammenkædet konvolusionskodning: Turbokoder (MatLab Simulink)

Languages

In other projects