Cod turbo

Codul turbo este un cod sistematic de blocuri paralele în cascadă care poate corecta erorile care apar atunci când informațiile digitale sunt transmise printr- un canal de comunicare zgomotos . Turbocode este sinonim cu termenul binecunoscut din teoria codificării - cod concatenat ( propus de D. Forney în 1966).

Un cod turbo constă dintr-o cascadă de coduri sistematice conectate în paralel. Aceste componente se numesc coduri de componente. Codurile convoluționale , codurile Hamming , codurile Reed -Solomon , codurile Bowes-Chowdhury-Hokvingham și altele pot fi folosite ca coduri componente . În funcție de alegerea codului de componentă, codurile turbo sunt împărțite în coduri turbo convoluționale ( Turbo Convolutional Codes, TCC ) și coduri de produs bloc ( Turbo Product Codes , TPC ) [1] .

Codurile Turbo au fost dezvoltate în 1993 și reprezintă o clasă de coduri de corectare a erorilor extrem de eficiente , utilizate în inginerie electrică și comunicații digitale și și-au găsit, de asemenea, aplicarea în comunicațiile prin satelit și în alte domenii în care este necesar să se obțină maximul maxim. rata de transfer de date pe un canal de comunicație cu zgomot în banda de frecvență limitată .

Istorie

Până la apariția codului turbo, metoda de codare concatenată a fost larg răspândită, în care datele erau codificate mai întâi prin codul Reed-Solomon , iar apoi prin codul convoluțional . Se apropie suficient de granița Shannon și combină un bloc de corectare a erorilor folosind codul Reed-Solomon și un bloc de coduri convoluționale decodificate folosind algoritmul Viterbi .

Codurile turbo au fost propuse de C. Berrou, A. Glavieux și P. Thitimajshima de la École Nationale Supérieure des Télécommunications de Bretagne (ENST Bretagne) , Școala Națională Superioară de Telecomunicații din Bretania ( Franța )) în 1993 în lucrarea „ Aproape. Shannon Limit Error- correction Coding and Decoding : Turbo-code” [ 2] , publicat în IEEE Proceedings . Într-o lucrare ulterioară [3] , Burrow creditează intuiția lui G. Battail , J. Hagenauer și P. Hoeher , care au prezis teoretic procesarea probabilistică a datelor la sfârșitul anilor 1980 . Burrow mai menționează că Robert Gallagher și M. Tanner ( M. Tanner ) reprezentau încă la un moment dat metode de codificare și decodare cu principii generale foarte apropiate de codurile turbo, dar la acel moment capabilitățile de calcul necesare nu erau disponibile .

Structura codului turbo

Potrivit lui Shannon , cel mai bun cod este cel care transmite un mesaj într-un timp infinit de lung, generând elemente de cod aleatorii în fiecare moment de timp. . Receptorul are versiuni infinite ale unui mesaj alterat aleatoriu. Din aceste copii, decodorul trebuie să selecteze copia cea mai apropiată de mesajul transmis. Acesta este un cod teoretic ideal care poate corecta toate erorile dintr-un semnal. Turbocode este un pas în această direcție. Este clar că nu ar trebui să trimitem un mesaj informațional pentru o perioadă infinită de timp. Dublarea sau triplarea timpului de transfer este suficientă pentru o performanță acceptabilă, ceea ce va oferi rezultate destul de decente pentru canalele de comunicare.

O caracteristică a codurilor turbo este o structură paralelă constând din coduri recursive sistematice convoluționale ( RSC) care funcționează în paralel și utilizează crearea unei versiuni aleatorii a mesajului. Structura paralelă utilizează două sau mai multe coduri RSC , fiecare cu un intercalator diferit . Scopul intercalatorului este de a oferi fiecărui codificator o versiune necorelată sau aleatorie a informaţiei , prin care biţii de paritate ai fiecărui RSC devin independenţi .

În codurile turbo, blocurile sunt de ordinul a câțiva kbiți în lungime. Scopul acestei lungimi este de a randomiza eficient secvența care merge la al doilea encoder. Cu cât dimensiunea blocului este mai mare, cu atât este mai bună corelația sa cu mesajul primului codificator, adică corelația este mică.

Există mai multe scheme de cod turbo:

PCCC - în cazul concatenării codurilor convoluționale paralele
SCCC este o schemă de conexiune serială de coduri convoluționale, codurile SCCC au performanțe ridicate la raporturi semnal-zgomot ridicate
TPC - cod de produs turbo , folosește coduri bloc în loc de coduri convoluționale; două coduri bloc diferite (de obicei coduri Hamming ) sunt conectate în serie fără un intercalator intermediar . Deoarece cele două coduri sunt independente și funcționează în rânduri și coloane, ceea ce în sine oferă o randomizare rezonabil de bună, nu este necesar niciun intercalator .

Codificare

Pe fig. 1 este o diagramă bloc generală a unui codificator turbo M-block.

Mai întâi, un bloc de date cu o lungime de biți ajunge la intrarea PAD ( Packet Assembler / Disassembler ) . În modelul de pachete, la date sunt adăugați biți suplimentari de informații de serviciu, corespunzător standardului de formare a pachetelor utilizat și incluzând caracterele pentru începutul și sfârșitul acestuia [4] . Adică se obține un pachet format din biți. $U$ $k$ $(nk)$ $X_{0}$ $n$

Mai mult , secvența de biți intră în paralel pe ramurile care conțin intercalatorul și codificatorul component conectat în serie. Astfel, este folosit ca intrare de către toate codificatoarele componente simultan. $X_{0}$ $M$ $X_{0}$

Intercalare în coduri turbo

În intercalatorii , conform unei legi pseudo-aleatoare, biții de intrare sunt amestecați. Spre deosebire de intercalarea dreptunghiulară per simbol utilizată în codurile Reed-Solomon , codurile turbo folosesc intercalarea pe un singur bit , care este similară cu permutările aleatorii. Mai mult, mai târziu, în timpul operațiunilor de decodare, această lege de intercalare va fi considerată cunoscută. Secvențele rezultate sunt alimentate la intrările codificatoarelor.

Sarcina intercalatorului este de a transforma secvența de intrare astfel încât combinațiile de biți corespunzători cuvintelor de cod cu greutate redusă ( greutatea este numărul de biți diferit de zero ai cuvântului de cod) la ieșirea primului codificator să fie transformate în combinații care dau cuvinte de cod. cu greutate mare la ieșirile altor encodere. Astfel, codificatoarele scot cuvinte de cod cu greutăți diferite. La codificare, cuvintele cod sunt formate astfel încât să se obțină distanța medie maximă posibilă între ele ( distanța dintre două cuvinte cod este numărul de biți în care acestea diferă). Datorită faptului că blocurile de cod sunt formate din piese aproape independente, la ieșirea codificatorului turbo, distanța medie dintre cuvintele de cod este mai mare decât distanța minimă pentru fiecare encoder component și, prin urmare, eficiența de codare crește. $X_{0}$

Permutarea pentru fiecare lungime de bloc specificată este dată de o reordonare specifică a numerelor întregi , așa cum este furnizată de următorul algoritm ( ECSS -E-ST-50-01C) [5] . $k$ $1, 2..., k$

$k = 8 * k_0$ , unde una dintre următoarele valori: , , , , în funcție de adâncimea de intercalare necesară $k_0 =$ $223$ $223*2$ $223*4$ $223*5$

Următoarele operații sunt efectuate pe valori de la până la pentru a obține adresele de permutare . În ecuațiile de mai jos, denotă cel mai mare număr întreg mai mic sau egal cu , și denotă unul dintre următoarele patru numere prime : $s = 1$ $s = k$ $\boldsymbol \pi(s)$ $\mathcal{b} \boldsymbol x \mathcal{c}$ $simbol \bold 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$

Interpretarea permutării este că al -lea bit transmis de intercalator este al -lea bit al blocului de informații de intrare. Intercalatorul scrie bitul primit la adresa calculată. $\boldsymbols$ $\boldsymbol\pi(s)$

Rata codului

Rata codului - raportul dintre lungimea blocului de cod la intrare și lungimea blocului de cod transformat la ieșirea codificatorului.

În absența unui perforator (vezi Fig. 1), secvența originală este multiplexată cu secvențe de biți de paritate , formând un cuvânt de cod care trebuie transmis pe canal. Apoi valoarea ratei codului la ieșirea codificatorului turbo $X_{0}$ $V_1,\ldots,V_M$

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

Pentru a crește rata de codare, se folosește perforarea (perforarea) anumitor biți de verificare ai secvenței de ieșire. Astfel, rata codului crește la

$R = \frac{k}{n(N+1)}$ , unde , și poate fi fracțional dacă numărul de biți de verificare rămași după perforare nu este un multiplu de . $N<M$ $N$ $n$

Dacă luăm în considerare că codurile turbo operează cu blocuri de lungime mare c , atunci , iar rata de cod este egală cu $k > 10000$ $k \aprox n$

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

Din formulele de mai sus , se poate observa că, cu ajutorul unui perforator, perforarea unui număr diferit de biți de verificare, este posibilă reglarea ratei codului. Adică puteți construi un encoder care se adaptează canalului de comunicare. Când canalul este zgomotos, perforatorul perfora mai puțini biți, ceea ce determină o scădere a ratei de codare și o creștere a imunității la zgomot a codificatorului. Dacă canalul de comunicație este de bună calitate, atunci un număr mare de biți poate fi perforat, determinând o creștere a ratei de transfer de informații [6] .

Decodare

Algoritmul de decodare al probabilității posterioare maxime (MAP)

La efectuarea decodării cu corectarea erorilor, este esențial să se analizeze probabilitățile a priori și a posteriori de apariție a cuvântului de cod corect. A priori este informația pe care decodorul o are înainte de sosirea cuvântului cod, iar a posteriori este informația obținută în urma procesării cuvântului cod.

Burrow propune pentru utilizare în decodoarele turbo algoritmul Maximum of A -posteriori Probability (MAP ) , cunoscut și sub denumirea de algoritm Bala ( Bahl-Cocke-Jelinek-Raviv (BCJR) ). Algoritmul lui Bal oferă o estimare de încredere „ soft ” pentru bitul decodat. Adică, prezintă un grad de încredere în rezultatul decodării la ieșire. Spre deosebire de structura „ hard ”, în care doar cea mai probabilă valoare a bitului decodificat („0” sau „1”) se formează la ieșirea decodorului, atunci când se ia o decizie „soft”, o eșantionare mai detaliată este utilizat semnalul de ieșire care caracterizează probabilitatea recepționării corecte a bitului. Datorită utilizării deciziilor „soft” în decodoarele turbo, este eficient să folosiți mai multe iterații de decodare . Informația a posteriori obținută despre cuvântul cod la ieșirea primei iterații de decodare este alimentată la intrarea blocului următoarei iterații și este deja o probabilitate a priori pentru aceasta. Această abordare permite îmbunătățirea calității decodării de la iterație la iterație. Astfel, prin modificarea numărului de iterații de decodare, este posibil să se adapteze decodorul la starea curentă a canalului de transmisie și să se realizeze probabilitatea de eroare de biți necesară [6] .

Raportul de probabilitate a jurnalului (LLR)

Considerați bitul de informație ca o variabilă binară , adică valoarea la momentul respectiv . Raportul său log-probabilități (LLR) este definit ca logaritmul raportului dintre probabilitățile sale subiacente. $\boldsymbol u_k$ $\boldsymbol u$ $k$

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

Această măsurătoare este utilizată în majoritatea sistemelor de corectare a erorilor cu codare de corectare a erorilor și se numește raportul log-probabilității sau LLR . Este puțin mai bună decât metrica liniară , deoarece, de exemplu, logaritmul face mai ușor să gestionați valori foarte mici și foarte mari. Dacă probabilitățile de recepție ale lui „0” și „1” sunt egale, metrica este 0.

O iterație a decodorului turbo iterativ cu codare în două etape

Pe fig. 2, pentru ușurință de înțelegere, este prezentată o variantă a schemei unei iterații de decodificare turbo în codificare în două etape. Această schemă poate fi generalizată cu ușurință în cazul unui număr arbitrar de etape de codare.

Decodorul pentru o iterație conține o conexiune în cascadă a două decodoare elementare, fiecare dintre acestea, pe baza criteriilor pentru probabilitatea maximă a posteriori, ia o decizie „soft” cu privire la simbolul transmis. Primul decodor al primei iterații de la ieșirea demodulatorului primește soluții „soft” pentru simbolurile secvențelor și . Astfel, la ieșirea primului decodor, apare o estimare a simbolului informațional , care, după intercalarea ulterioară, intră în intrarea celui de-al doilea decodor și este a priori o informație pentru acesta. Folosind o decizie „soft” cu privire la secvența , al doilea decodor își formează estimarea [7] $X_{0}$ $X_{1}$ $X_{2}$

Decodor turbo cu trei iterații cu codare în două etape

De la ieșirea fiecărei iterații, soluția trece la intrarea următoarei. Organizarea muncii decodorului turbo cu trei iterații este prezentată în fig. 3. Din iterație în iterație, soluția este rafinată. În același timp, fiecare iterație funcționează cu estimări „soft” și oferă, de asemenea, estimări „soft” rezultatelor. Prin urmare, astfel de scheme sunt numite decodoare cu intrare soft și ieșire soft ( ing. Soft Input Soft Output (SISO) ) [8] . Procesul de decodare se oprește fie după ce toate iterațiile au fost finalizate, fie când probabilitatea de eroare a biților atinge valoarea necesară. După decodificare, soluția finală „dură” este produsă din soluția „moale” obținută [7] .

Avantajele și dezavantajele codurilor turbo

Beneficii

Dintre toate metodele moderne de corectare a erorilor din practică, codurile turbo și codurile de verificare a parității cu densitate scăzută se apropie cel mai mult de limita Shannon , limita teoretică a debitului maxim al unui canal zgomotos. Codurile Turbo vă permit să creșteți rata de date fără a necesita o creștere a puterii emițătorului sau pot fi folosite pentru a reduce puterea necesară atunci când transmiteți la o anumită rată. Un avantaj important al codurilor turbo este independența complexității decodării față de lungimea blocului de informații, ceea ce reduce probabilitatea erorilor de decodare prin creșterea lungimii acestuia [9] .

Dezavantaje

Principalul dezavantaj al codurilor turbo este complexitatea relativ mare a decodării și latența mare, ceea ce le face incomode pentru unele aplicații. Dar, de exemplu, pentru utilizarea în canale prin satelit, acest dezavantaj nu este decisiv, deoarece lungimea canalului de comunicație în sine introduce o întârziere cauzată de caracterul finit al vitezei luminii .

Un alt dezavantaj important al codurilor turbo este distanța relativ mică de cod (adică distanța minimă dintre două cuvinte de cod în sensul metricii alese ). Acest lucru duce la faptul că, deși performanța codului turbo este ridicată atunci când rata de eroare de intrare este mare (adică, într-un canal prost), performanța codului turbo este extrem de limitată atunci când rata de eroare de intrare este scăzută. [10] Prin urmare, în canalele bune, pentru a reduce și mai mult probabilitatea de eroare, nu se folosesc coduri turbo, ci coduri LDPC .

Deși complexitatea algoritmilor de codare turbo utilizați și lipsa software-ului open source au împiedicat adoptarea codurilor turbo, multe sisteme moderne folosesc în prezent coduri turbo.

Aplicarea codurilor turbo

France Télécom și Telediffusion de France au brevetat o clasă largă de coduri turbo, care limitează posibilitatea utilizării lor gratuite și, în același timp, stimulează dezvoltarea de noi metode de codare, cum ar fi, de exemplu, LDPC .

Codurile Turbo sunt utilizate în mod activ în sistemele de comunicații prin satelit și mobile , accesul wireless în bandă largă și televiziunea digitală . [8] Codurile Turbo sunt aprobate în standardul de comunicații prin satelit DVB-RCS . Codurile Turbo au găsit, de asemenea, o largă aplicație în sistemele de comunicații mobile de a treia generație ( standardele CDMA2000 și UMTS ). [9]

Note

↑ Zolotarev V.V., Ovechkin G.V., Ovechkin P.V. Multi-threshold decoding for digital data transmission systems . Consultat la 21 noiembrie 2008. Arhivat din original la 30 ianuarie 2012. (Rusă)
↑ Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limit error-correcting coding and decoding: Turbo-codes ( 1993). Consultat la 21 noiembrie 2008. Arhivat din original la 30 ianuarie 2012.
↑ Berrou C. Ten-year-old Turbo Codes are Entering Service (English) (2003). Consultat la 21 noiembrie 2008. Arhivat din original la 30 ianuarie 2012.
↑ Protocoale de rețea Semenov Yu. A. X.25 . (Rusă)
↑ ECSS- E -ST-50-01C . Arhivat din original la 30 ianuarie 2012.
↑ 1 2 Zubarev Yu. B., Krivosheev M. I., Krasnoselsky I. N. Transmisie de televiziune digitală. Fundamente, metode, sisteme. - M .: Institutul de Cercetare Științifică a Radioului (NIIR), 2001. - P. 112-120.
↑ 1 2 . Komarov S. V., Postnikov S. A., Levshin V. I., Dremachev D. V., Artemiev N. V. Aplicarea codurilor turbo în sistemele de comunicații multimedia din a treia generație: colecție de articole. Teoria și tehnologia comunicațiilor radio. - 2003. - P. 112-119.
↑ 1 2 Arkhipkin A. Codurile Turbo - algoritmi puternici pentru sistemele moderne de comunicare (Journal. Wireless Technologies) (2006). Consultat la 21 noiembrie 2008. Arhivat din original la 30 ianuarie 2012. (Rusă)
↑ 1 2 Vargauzin V., Protopopov L. Codurile turbo și decodarea iterativă: principii, proprietăți, aplicare (2000). (Rusă)
↑ Moon, Todd K. Codificarea corectării erorilor: metode și algoritmi matematici. - John Wiley & Sons, 2005. - pagina 612.