Turbo koodi

Turbokoodi on rinnakkainen peräkkäinen lohkojärjestelmäkoodi , joka voi korjata virheet, jotka tapahtuvat siirrettäessä digitaalista informaatiota kohinaisen viestintäkanavan kautta . Turbokoodi on synonyymi koodausteoriassa hyvin tunnetulle termille - ketjutettu koodi ( ehdotti D. Forney vuonna 1966).

Turbokoodi koostuu rinnakkain kytkettyjen systemaattisten koodien sarjasta. Näitä komponentteja kutsutaan komponenttikoodeiksi. Konvoluutiokoodeja , Hamming-koodeja , Reed-Solomon- koodeja , Bowes-Chowdhury-Hokvingham-koodeja ja muita voidaan käyttää komponenttikoodeina . Komponenttikoodin valinnasta riippuen turbokoodit jaetaan konvoluutioturbokoodeihin ( Turbo Convolutional Codes, TCC ) ja lohkotuotekoodeihin ( Turbo Product Codes , TPC ) [1] .

Turbokoodit kehitettiin vuonna 1993 , ja ne ovat luokka erittäin tehokkaita virheenkorjauskoodeja , joita käytetään sähkötekniikassa ja digitaalisessa viestinnässä , ja ne ovat löytäneet sovelluksensa myös satelliittiviestinnässä ja muilla aloilla, joilla on tarpeen saavuttaa maksimi tiedonsiirtonopeus viestintäkanavalla, jossa on kohinaa rajoitetulla taajuuskaistalla .

Historia

Turbokoodin tuloon asti ketjutettu koodausmenetelmä oli laajalle levinnyt, jossa tiedot koodattiin ensin Reed-Solomon-koodilla ja sitten konvoluutiokoodilla . Se tulee tarpeeksi lähelle Shannonin rajaa ja yhdistää Reed-Solomon-koodia käyttävän virheenkorjauslohkon ja Viterbi-algoritmilla dekoodatun konvoluutiokoodin lohkon .

Turbokoodeja ehdottivat C. Berrou, A. Glavieux ja P. Thitimajshima Bretagnen (Ranska) École Nationale Supérieure des Télécommunications de Bretagnesta (ENST Bretagne) , Higher National School of Telecommunications of Bretagnesta ( Ranska ) vuonna 1993 artikkelissa " Near Shannon Limit Error- corrating Coding and Decoding : Turbo-code" [ 2] , julkaistu IEEE Proceedingsissa . Myöhemmässä artikkelissa [3] Burrow kiittää G. Battailin , J. Hagenauerin ja P. Hoeherin intuitiota , jotka ennustivat teoreettisesti todennäköisyyspohjaisen tiedonkäsittelyn 1980 -luvun lopulla . Burrow mainitsee myös, että Robert Gallagher ja M. Tanner ( M. Tanner ) edustivat vielä aikoinaan koodaus- ja dekoodausmenetelmiä, joiden yleisperiaatteet olivat hyvin lähellä turbokoodeja, mutta siihen aikaan tarvittavia laskentaominaisuuksia ei ollut saatavilla .

Turbo-koodin rakenne

Shannonin mukaan paras koodi on se , joka lähettää viestin äärettömän pitkässä ajassa ja tuottaa satunnaisia koodielementtejä kullakin hetkellä. . Vastaanottimella on äärettömät versiot satunnaisesti sekoitetusta viestistä. Näistä kopioista dekooderin on valittava lähetettyä viestiä lähinnä oleva kopio. Tämä on teoriassa ihanteellinen koodi , joka voi korjata kaikki signaalin virheet. Turbocode on askel tähän suuntaan. On selvää, että meidän ei pidä lähettää informaatioviestiä loputtomasti. Siirtoajan kaksin- tai kolminkertaistaminen riittää hyväksyttävään suorituskykyyn, mikä antaa melko kunnollisia tuloksia viestintäkanaville.

Turbokoodien ominaisuus on rinnakkainen rakenne, joka koostuu rekursiivisista systemaattisista konvoluutiokoodeista (RSC) , jotka toimivat rinnakkain ja käyttävät viestin satunnaisen version luomista . Rinnakkaisrakenne käyttää kahta tai useampaa RSC - koodia , joista jokaisella on eri lomittaja . Lomittajan tarkoituksena on tarjota jokaiselle kooderille korreloimaton tai satunnainen versio tiedosta , jolloin kunkin RSC:n pariteettibitit tulevat itsenäisiksi .

Turbokoodeissa lohkot ovat pituudeltaan useita kbittejä. Tämän pituuden tarkoitus on satunnaistaa tehokkaasti toiselle kooderille menevä sekvenssi. Mitä pidempi lohkokoko on, sitä paremmin se korreloi ensimmäisen kooderin viestin kanssa, eli korrelaatio on pieni.

On olemassa useita turbokoodijärjestelmiä:

PCCC - rinnakkaisten konvoluutiokoodien ketjuttamisen tapauksessa
SCCC on konvoluutiokoodien sarjakytkentäkaavio, SCCC -koodeilla on korkea suorituskyky korkeilla signaali-kohinasuhteilla
TPC - turbo tuotekoodi , käyttää lohkokoodeja konvoluutiokoodien sijaan; kaksi erilaista lohkokoodia (yleensä Hamming-koodia ) on kytketty sarjaan ilman välilomitinta . Koska nämä kaksi koodia ovat riippumattomia ja toimivat riveissä ja sarakkeissa, mikä itsessään tarjoaa kohtuullisen hyvän satunnaistuksen, lomittajaa ei tarvita.

Koodaus

Kuvassa Kuva 1 on yleinen lohkokaavio M-lohkon turbokooderista.

Ensin PAD : n ( Packet Assembler / Dassembler ) sisäänmenoon saapuu bittipituinen datalohko . Paketinmuotoilijassa dataan lisätään palveluinformaation lisäbittejä, jotka vastaavat käytettyä paketinmuodostusstandardia ja sisältävät sen alun ja lopun merkit [4] . Toisin sanoen saadaan biteistä koostuva paketti . $U$ $k$ $(nk)$ $X_{0}$ $n$

Lisäksi bittisekvenssi tulee rinnakkain haaroissa , jotka sisältävät sarjaan kytketyn limittimen ja komponenttikooderin. Siten kaikki komponenttienkooderit käyttävät sitä syötteenä kerralla. $X_{0}$ $M$ $X_{0}$

Interleaving turbokoodeissa

Lomittimissa , näennäissatunnaisen lain mukaan, saapuvat bitit sekoitetaan . Toisin kuin Reed-Solomon- koodeissa käytetty symbolikohtainen suorakaidelimittäjä , turbokoodit käyttävät yksibittistä lomittelua , joka on samanlainen kuin satunnaiset permutaatiot. Lisäksi myöhemmin, dekoodausoperaatioiden aikana, tämä lomituslaki katsotaan tunnetuksi. Tuloksena saadut sekvenssit syötetään kooderien tuloihin.

Limittimen tehtävänä on muuntaa syöttösekvenssi siten, että ensimmäisen kooderin lähdössä olevat pienipainoisia koodisanoja vastaavat bittiyhdistelmät ( paino on koodisanan nollasta poikkeavien bittien lukumäärä) muunnetaan yhdistelmiksi, jotka antavat koodisanoja. suurella painolla muiden kooderien lähdöissä. Siten kooderit tuottavat eri painoisia koodisanoja. Koodattaessa koodisanoja muodostetaan siten, että niiden välille saadaan suurin mahdollinen keskimääräinen etäisyys ( kahden koodisanan välinen etäisyys on niiden bittien lukumäärä, joilla ne eroavat). Koska koodilohkot on muodostettu lähes itsenäisistä osista, on turbokooderin lähdössä keskimääräinen koodisanojen välinen etäisyys suurempi kuin kunkin komponenttikooderin minimietäisyys, ja siten koodauksen tehokkuus kasvaa. $X_{0}$

Permutaatio kullekin määritetylle lohkon pituudelle saadaan tietyllä kokonaislukujen uudelleenjärjestelyllä seuraavan algoritmin ( ECSS -E-ST-50-01C) [5] mukaisesti . $k$ $1, 2..., k$

$k = 8 * k_0$ , jossa jokin seuraavista arvoista: , , , , vaaditusta limittimen syvyydestä riippuen $k_0 =$ $223$ $223*2$ $223*4$ $223*5$

Seuraavat toiminnot suoritetaan arvoille välillä - permutaatioosoitteiden saamiseksi . Alla olevissa yhtälöissä tarkoittaa suurinta kokonaislukua, joka on pienempi tai yhtä suuri kuin , ja tarkoittaa yhtä seuraavista neljästä alkuluvusta : $s = 1$ $s = k$ $\boldsymbol \pi(s)$ $\mathcal{b} \boldsymbol x \mathcal{c}$ $\lihavoitu symboli 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$

Permutaation tulkinta on, että limittimen lähettämä -. bitti on syötetietolohkon -:s bitti. Lomittaja kirjoittaa vastaanotetun bitin laskettuun osoitteeseen. $\boldsymbols$ $\boldsymbol\pi(s)$

Koodinopeus

Koodinopeus - sisääntulossa olevan koodilohkon pituuden suhde kooderin lähdössä olevan muunnetun koodilohkon pituuteen.

Lävistimen puuttuessa (katso kuvio 1) alkuperäinen sekvenssi multipleksoidaan pariteettibittien sarjoilla , jolloin muodostuu kanavan yli lähetettävä koodisana. Sitten koodinopeuden arvo turbokooderin lähdössä $X_{0}$ $V_1,\ldots,V_M$

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

Koodinopeuden lisäämiseksi käytetään lähtösekvenssin tiettyjen tarkistusbittien lävistämistä (rei'itystä). Siten koodinopeus kasvaa arvoon

$R = \frac{k}{n(N+1)}$ , jossa , ja voi olla murtoluku, jos rei'ityksen jälkeen jäljellä olevien tarkistusbittien määrä ei ole :n kerrannainen . $N<M$ $N$ $n$

Jos otamme huomioon, että turbokoodit toimivat suuripituisilla c lohkoilla , niin , ja koodinopeus on yhtä suuri kuin $k > 10 000$ $k \noin n$

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

Yllä olevista kaavoista voidaan nähdä, että rei'ittimen avulla, lävistämällä eri määrä tarkistusbittejä, on mahdollista säätää koodinopeutta. Eli voit rakentaa kooderin, joka mukautuu viestintäkanavaan. Kun kanava on kohinainen, perforaattori lävistää vähemmän bittejä, mikä aiheuttaa koodinopeuden laskun ja kooderin kohinansietokyvyn lisääntymisen. Jos viestintäkanava on hyvälaatuinen, suuri määrä bittejä voidaan puhkaista, mikä lisää tiedonsiirtonopeutta [6] .

Dekoodaus

Maksimaalisen posteriorisen todennäköisyyden (MAP) dekoodausalgoritmi

Kun dekoodaus suoritetaan virheenkorjauksella, on olennaista analysoida a priori ja a posteriori oikean koodisanan saapumisen todennäköisyydet. A priori on tieto, joka dekooderilla on ennen koodisanan saapumista, ja jälkikäteen koodisanan käsittelyn jälkeen saatu informaatio.

Burrow ehdottaa käytettäväksi turbodekoodereissa Maximum of A -posteriori Probability (MAP ) -algoritmia, joka tunnetaan myös Bala-algoritmina ( Bahl-Cocke-Jelinek-Raviv (BCJR) ). Balin algoritmi antaa " pehmeän " luottamusarvion dekoodatulle bitille. Toisin sanoen se antaa tietyn luotettavuuden dekoodaustulokseen lähdössä. Toisin kuin " kovassa " rakenteessa, jossa dekooderin ulostuloon muodostetaan vain dekoodatun bitin todennäköisin arvo ("0" tai "1"), "pehmeää" päätöstä tehtäessä tarkempi näytteistys lähtösignaalista käytetään, mikä kuvaa bitin oikean vastaanoton todennäköisyyttä. Koska turbodekoodereissa käytetään "pehmeitä" päätöksiä, on tehokasta käyttää useita dekoodausiteraatioita . Ensimmäisen dekoodausiteraation lähdössä koodisanasta saatu jälkikäteen saatu informaatio syötetään seuraavan iteraation lohkon sisäänmenoon ja se on jo a priori todennäköisyys sille. Tämä lähestymistapa mahdollistaa dekoodauksen laadun parantamisen iteraatiosta iteraatioon. Siten muuttamalla dekoodausiteraatioiden määrää on mahdollista sovittaa dekooderi lähetyskanavan nykyiseen tilaan ja saavuttaa vaadittu bittivirhetodennäköisyys [6] .

Log Likelihood Ratio (LLR)

Tarkastellaan informaatiobittiä binäärimuuttujana eli ajankohtana . Sen log-likelihood-suhde (LLR) määritellään sen taustalla olevien todennäköisyyksien suhteen logaritmiksi. $\boldsymbol u_k$ $\boldsymbol u$ $k$

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

Tätä mittaria käytetään useimmissa virheenkorjausjärjestelmissä, joissa on virheenkorjaava koodaus, ja sitä kutsutaan log-todennäköisyyssuhteeksi tai LLR:ksi . Se on hieman parempi kuin lineaarinen metriikka , koska esimerkiksi logaritmi helpottaa hyvin pienten ja erittäin suurten arvojen käsittelyä. Jos vastaanottotodennäköisyydet "0" ja "1" ovat yhtä suuret, mittari on 0.

Yksi iteraatio iteratiivisesta turbodekooderista kaksivaiheisella koodauksella

Kuvassa Kuviossa 2 esitetään ymmärtämisen helpottamiseksi muunnelma turbodekoodauksen yhden iteraation kaaviosta kaksivaiheisessa koodauksessa. Tämä menetelmä voidaan helposti yleistää tapaukseen, jossa on mielivaltainen määrä koodausvaiheita.

Yhden iteroinnin dekooderi sisältää kahden alkeisdekooderin kaskadiyhteyden, joista kumpikin tekee "pehmeän" päätöksen lähetetystä symbolista a posteriori suurimman todennäköisyyden kriteerien perusteella. Ensimmäisen iteraation ensimmäinen dekooderi demodulaattorin lähdöstä vastaanottaa "pehmeitä" ratkaisuja sekvenssien ja symboleille . Siten ensimmäisen dekooderin lähdössä ilmestyy arvio informaatiosymbolista , joka myöhemmän lomituksen jälkeen tulee toisen dekooderin sisäänmenoon ja on sille a priori informaatiota. Käyttäen "pehmeää" päätöstä sekvenssistä , toinen dekooderi muodostaa arvionsa [7] $X_{0}$ $X_{1}$ $X_{2}$

Kolmen iteroinnin turbodekooderi kaksivaiheisella koodauksella

Kunkin iteraation lähdöstä ratkaisu siirtyy seuraavan syötteeseen. Kolmen iteroinnin turbodekooderin työn organisointi on esitetty kuvassa. 3. Iteraatiosta iteraatioon ratkaisua jalostetaan. Samanaikaisesti jokainen iteraatio toimii "pehmeillä" arvioilla ja antaa myös "pehmeitä" ulostulolle. Siksi tällaisia järjestelmiä kutsutaan dekoodereiksi, joissa on pehmeä tulo ja pehmeä lähtö ( eng. Soft Input Soft Output (SISO) ) [8] . Dekoodausprosessi pysähtyy joko sen jälkeen, kun kaikki iteraatiot on suoritettu, tai kun bittivirhetodennäköisyys saavuttaa vaaditun arvon. Dekoodauksen jälkeen lopullinen "kova" ratkaisu tuotetaan saadusta "pehmeästä" liuoksesta [7] .

Turbokoodien edut ja haitat

Edut

Kaikista nykyaikaisista virheenkorjausmenetelmistä käytännössä turbokoodit ja matalatiheyksiset pariteettitarkistuskoodit ovat lähimpänä Shannonin rajaa , kohinaisen kanavan maksimiläpäisykyvyn teoreettista rajaa . Turbokoodien avulla voit lisätä tiedonsiirtonopeutta ilman lähettimen tehon lisäystä , tai niitä voidaan käyttää tarvittavan tehon vähentämiseen lähetettäessä tietyllä nopeudella. Turbokoodien tärkeä etu on dekoodauksen monimutkaisuuden riippumattomuus informaatiolohkon pituudesta, mikä vähentää dekoodausvirheiden todennäköisyyttä lisäämällä sen pituutta [9] .

Haitat

Turbokoodien suurin haittapuoli on suhteellisen korkea dekoodauksen monimutkaisuus ja korkea latenssi, mikä tekee niistä hankalia joissakin sovelluksissa. Mutta esimerkiksi satelliittikanavissa käytettäessä tämä haitta ei ole ratkaiseva, koska itse viestintäkanavan pituus aiheuttaa valonnopeuden äärellisyydestä johtuvan viiveen .

Toinen turbokoodien tärkeä haittapuoli on suhteellisen pieni koodietäisyys (eli kahden koodisanan välinen vähimmäisetäisyys valitun metriikan merkityksessä ). Tämä johtaa siihen, että vaikka turbokoodin suorituskyky on korkea, kun syöttövirhesuhde on suuri (eli huonossa kanavassa), turbokoodin suorituskyky on erittäin rajoitettu, kun syöttövirhesuhde on alhainen. [10] Siksi hyvissä kanavilla virhetodennäköisyyden vähentämiseksi edelleen ei käytetä turbokoodeja, vaan LDPC-koodeja .

Vaikka käytettyjen turbokoodausalgoritmien monimutkaisuus ja avoimen lähdekoodin ohjelmistojen puute ovat estäneet turbokoodien käyttöönottoa, monet nykyaikaiset järjestelmät käyttävät tällä hetkellä turbokoodeja.

Turbokoodien käyttö

France Télécom ja Telediffusion de France ovat patentoineet laajan luokan turbokoodeja, mikä rajoittaa niiden vapaata käyttöä ja samalla stimuloi uusien koodausmenetelmien, kuten esimerkiksi LDPC :n, kehitystä .

Turbokoodeja käytetään aktiivisesti satelliitti- ja matkaviestinjärjestelmissä , langattomassa laajakaistayhteydessä ja digitelevisiossa . [8] Turbokoodit on hyväksytty DVB-RCS- satelliittiviestintästandardissa . Turbokoodit ovat löytäneet laajan sovelluksen myös kolmannen sukupolven matkaviestinjärjestelmissä ( CDMA2000- ja UMTS-standardit ). [9]

Muistiinpanot

↑ Zolotarev V.V., Ovechkin G.V., Ovechkin P.V. Multi-threshold dekoodaus digitaalisille tiedonsiirtojärjestelmille . Haettu 21. marraskuuta 2008. Arkistoitu alkuperäisestä 30. tammikuuta 2012. (Venäjän kieli)
↑ Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limit error-correcting koodaus ja dekoodaus: Turbo-codes ( 1993). Haettu 21. marraskuuta 2008. Arkistoitu alkuperäisestä 30. tammikuuta 2012.
↑ Berrou C. Kymmenen vuotta vanhat turbokoodit ovat tulossa palveluun (englanniksi) (2003). Haettu 21. marraskuuta 2008. Arkistoitu alkuperäisestä 30. tammikuuta 2012.
↑ Semenov Yu. A. X.25 verkkoprotokollat . (Venäjän kieli)
↑ ECSS- E -ST-50-01C . Arkistoitu alkuperäisestä 30. tammikuuta 2012.
↑ 1 2 Zubarev Yu. B., Krivosheev M. I., Krasnoselsky I. N. Digitaalinen televisiolähetys. Perusteet, menetelmät, järjestelmät. - M .: Radion tieteellinen tutkimuslaitos (NIIR), 2001. - P. 112-120.
↑ 1 2 . Komarov S. V., Postnikov S. A., Levshin V. I., Dremachev D. V., Artemiev N. V. Turbokoodien käyttö kolmannen sukupolven multimediaviestintäjärjestelmissä: Artikkelikokoelma. Radioviestinnän teoria ja tekniikka. - 2003. - s. 112-119.
↑ 1 2 Arkhipkin A. Turbokoodit - tehokkaat algoritmit nykyaikaisiin viestintäjärjestelmiin (Journal. Wireless Technologies) (2006). Haettu 21. marraskuuta 2008. Arkistoitu alkuperäisestä 30. tammikuuta 2012. (Venäjän kieli)
↑ 1 2 Vargauzin V., Protopopov L. Turbokoodit ja iteratiivinen dekoodaus: periaatteet, ominaisuudet, sovellus (2000). (Venäjän kieli)
↑ Moon, Todd K. Virheenkorjauskoodaus: matemaattiset menetelmät ja algoritmit. - John Wiley & Sons, 2005. - sivu 612.