Codarea Turbo

Codarea turbo

CAPITOLUL 1

ABSTRACT

TURBO codurile reprezinta schema de codare prin care ne putem apropia cel mai mult de limita Shannon. Interleaver-ul folosit in TURBO coduri joaca un rol crucial in performanta acestora. Este important deci ca TURBO codurile sa aibe interlevere cu o structura foarte buna. In aceasta lucrare analizam performantele TURBO codurilor pentru diferite structuri si marimi de interleaver, din punct de vedere al ratei erorii de bit (BER). Marimea si tipul intretesatorului joaca un rol major in performanta TURBO codurilor. Vom discuta despre mai multe tipuri de interleavere folosite in codurile TURBO in incercarea de a-l gasi pe cel optim. Vom simula codarea pentru mai multe structuri de intretesatoare. Canalul va fi supus unui zgomot alb gausian (AWGN).

INTRODUCERE

Codarea turbo reprezintă o tehnică foarte puternică de control a erorii, care a început să aibă un impact semnificativ la sfârșitul anilor 90 și care permite comunicații foarte aproape de capacitatea canalului. Capacitatea foarte puternică de corectare a erorii a codurilor turbo a fost recunoscută și acceptată în aproape toate tipurile de canale; aceasta duce la creșterea ratelor de date și îmbunătațește calitatea serviciului. Codurile turbo pot lucra la 0.1dB de capacitatea limită a lui Shannon depășind orice altă tehnică de codare cunoscută până în prezent.

Codurile turbo au fost introduse în 1993 și primul modem proiectat pentru o aplicație comercială a fost testată în 1997.

S-a efectuat o cercetare bogată în folosirea codurilor turbo în comunicațiile în spațiu, comunicațiile mobile celulare și prin sateliți, legăturile de microunde, paging și arhitecturile OFDM și CDMA. Codurile turbo depășesc toate schemele de codare cunoscute anterior indiferent de canalul țintă. Câștigul de codare suplimentar oferit de codurile turbo poate fi folosit fie pentru a salva lărgimea de bandă sau fie pentru reducerea cerințelor de putere.

Mai multe standarde bazate pe codurile turbo au fost deja definite sau sunt în stadiu de cercetare. Vom încerca să prezentăm de ce codurile turbo sunt superioare și să rezumăm aplicațiile curente.

Îmbunătățirea calității transmisiunii se poate face prin îmbunătățirea canalului, sursa principală de erori în transmisiunile de date.

Ct = , unde este durata medie a unui simbol (1.5)

Capacitatea canalului raportată la timp se măsoară în biți pe secundă.

Dacă avem o sursă de entropie maximă, adică toate simbolurile generate au aceeași probabilitate, avem de a face cu simboluri ce se numesc simboluri de informație. Se realizează astfel o codare a sursei prin care se încearcă înlăturarea biților redundanți.

După codarea sursei, pentru o mai bună protecție a informației se introduc o serie de simboluri redundante. Aceste simboluri vor fi transmise împreună cu simbolurile de informație astfel încât la recepție să se poată evalua erorile apărute și mai ales să se poată corecta. Aceste simboluri se numesc simboluri de control.

Teorema lui Shannon

Dacă avem o sursă cu un debit de informație R biți/s și un canal de capacitate C biți/s și dacă R < C, există un cod cu cuvinte de lungime n astfel încât probabilitatea unei erori de decodare PE să fie:

PE ≤ 2 -nE(R) unde n lungimea cuvântului de cod

E(R) o funcție nenegativă numită exponentul erorii

Deci indiferent de nivelul perturbațiilor din canal se poate face transmisiunea cu o probabilitate a erorii oricât de mică. [1]

Fig. 1.1. Caracteristica probabilității de eroare de decodare în funcție de debitul de informație

Pe baza acestei teoreme s-au dezvoltat o serie de metode de codare-decodare astfel încât probabilitatea de eroare să se micșoreze cât mai mult posibil.

Un exemplu în dezvoltarea codoarelor îl reprezintă codorul bloc. Acestea sunt coduri fară memorie, cuvântul de cod depinzînd numai de mesajul curent. Principalul dezavantaj al acestui codor este ca odată cu lungimea mesajului, ce trebuie codat, crește foarte mult și complexitatea.

Dezvoltarea codoarelor a continuat cu codurile convoluționale; în acest caz procesul de codare se desfășoară în mod continual spre deosebire de codurile bloc în care procesarea de date se face prin gruparea în blocuri distincte. Datele cu rata de R1 sunt codate convoluțional și la ieșirea din decodor au o rată R2, cu R2> R1. Acest tip de codare este mai eficientă decât codarea bloc, permițînd un câștig de codare mai mare la aceeași complexitate.

În această dezvoltare continuă a metodelor de codare au apărut turbo codurile, coduri convoluționale concatenate cu performanțe mult mai bune, acestea apropiindu-se de limita teoremei lui Shannon. Turbocodul este construit prin concatenarea a două codoare Convoluționale Sistematice Recursive (RSC) și un decodor care este implementat ca o structură pipeline, avînd o buclă de reacție.

Performanțele acestui tip de codor sunt foarte bune tinzînd spre limita teoremei lui Shannon. Se definește eficiența spectrală: ES = rb/B bit/sec/hz, unde rb este rata de transmisie și B banda .

Eficiența spectrală maximă ESmax = log2M∙R

Raportul semnal-zgomot = log2M∙R∙, (1.6)

unde M este M-modulație, R rata codorului și reprezintă raportul dintre energia de bit și densitatea spectrală de putere a zgomotului.

Teorema lui Shannon spune că se poate realiza o probabilitate de eroare de bit oricât de mică prin codare-decodare dacă rb < C, unde C este capacitatea canalului

C = B log2 (1+) (1.7)

Dacă rb = C atunci ES = log2 (1+) . (1.8)

De aici rezultă că eficiența spectrală maximă este: ESmax=log2 (1+ESmax∙) => = – reprezintă raportul minim dintre energia de bit și densitatea spectrală de putere a zgomotului necesar pentru transmisie.

Se poate arata că în funcție de capacitățile interleaverului (întrețesătorului) puterea de corectare a erorilor se poate aduce pâna la limita teoremei lui Shannon. Acest întrețesător trebuie să aibă o mărime corespunzatoare. O îmbunătățire a proprietăților întrețesătorului poate duce la o corecție mai bună a erorilor. Se folosesc o serie de întrețesători, unul dintre cel mai folosit este întrețesătorul neuniform care a dus la rezultate mai bune decât un întrețesător uniform.

O limitare a câștigului codorului (puterea codorului de a corecta erori) este dată și de memoria acestuia. Complexitatea decodorului nu este o funcție liniară cu memoria codorului, aceasta crește exponențial cu creșterea memoriei.

După cum s-a putut vedea performanțele arătate de turbocodare sunt momentan superioare oricărei alte metode de codare. Pentru îmbunătățirea acestora se pot exploata problemele legate de proiectarea unui interleaver mai eficient, sau găsirea unei soluții privind memoria codorului. O astfel de soluție s-a dovedit a fi concatenarea. Dacă la început s-a folosit concatenarea între un codor (de exemplu Reed-Solomon) și un cod convoluțional, s-a trecut ulterior la ceea ce se cheama turbocodare adică concatenarea în paralel a două coduri sistematice recursive convoluționale (RSC). Se mai foloseste și concatenarea serială și hibridă. În ceea ce privește interleaverul, se folosesc de la întrețesătoare de tip bloc până la întrețesătoare aleatoare care duc la performanțe foarte ridicate.

CAPITOLUL 2

STRUCTURA TURBOCODORULUI

În acest capitol introductiv se face o prezentare sumară a codoarelor de tip bloc și de tip convoluțional, avînd în vedere structura și mai ales modul de funcționare a unui turbocodor.

2.1. CODURI BLOC

2.1.1. Noțiuni introductive

Codurile bloc sunt coduri fără memorie. Acestea primesc un mesaj format din k simboluri și transformă această secvență de intrare într-una mai lungă, formată din n simboluri numită cuvânt de cod. Astfel avem de a face cu un cod bloc de tipul (n, k). Coduri bloc intalnite frecvent sunt codurile Hamming, Golay, BCH si Reed Solomon (care folosesc simboluri non-binare).Codul bloc (n,k) are 2k mesaje distincte și 2k cuvinte de cod, între acestea existînd o corespondența unu la unu. Rata codului este . (2.1)

Un cod bloc este liniar dacă:

suma modulo 2 a două cuvinte de cod este un alt cuvânt de cod

există cuvântul de cod (0…0).

Un cod bloc liniar (n, k) poate fi generat de un set de k vectori liniar independenți g0, g1, … gk-1. Cuvântul de cod se obține ca o combinație liniară a acestor k vectori.

Dacă avem mesajul c = (c0 c1 … ck-1), atunci cuvântul de cod corespunzator este:

v = c0g0 + c1g1 + … + ck-1gk-1 (2.2)

Pe baza acestor k vectori se poate construi o matrice numită generatoare:

(2.3)

Deci v = c∙G (2.4)

Coduri bloc liniare sistematice

Codul liniar sistematic are o structură adițională astfel încât secvența de mesaj face parte din cuvântul de cod. Într-o astfel de codare avem n-k digiți care reprezintă secvența de verificare a parității sau secvența de control.

(c0, c1, …ck-1) (v0, v1, … vn-k-1, c0, c1, … ck-1) (2.5)

Matricea generatoare pentru un astfel de cod este . (2.6)

Ik este matricea unitate (k×k), iar P este o matrice (k×(n-k)) de forma:

, unde pij = {0,1} (2.7)

Se definește matricea de verificare a parității matricea H de tip

((n-k)×n):

(2.8)

Această matrice se folosește la detectarea unui cuvânt recepționat dacă este cuvânt de cod sau nu. Acesta trebuie să verifice egalitatea: v∙HT = 0.

2.1.3. Distanța minimă a unui cod bloc

Ponderea Hamming a unui cuvânt de cod v se definește ca fiind numărul total de nonzerouri din cuvânt. Distanța Hamming d(v,n) între două cuvinte de cod diferite se definește ca fiind numărul de locuri unde cele două cuvinte diferă.

Distanța Hamming minimă sau distanța minimă, dmin se definește ca distanța Hamming cea mai mică dintre două cuvinte de cod. dmin a unui cod liniar este cuvântul de cod cu ponderea cea mai mică. dmin este foarte importantă, ea determinînd capacitatea de corectare a erorilor.

2.1.4. Decodare cu plauzibilitate maximă pentru canal gaussian.

Fie un cod bloc (n,k) și o modulație binară antipodală. Această modulație înlocuiește simbolurile binare vi cu simboluri modulate xi după regula:

(2.9)

Semnalul este inundat de zgomot aditiv gaussian alb (ZAGA).

, unde ni este un eșantion din zgomot

Cum demodulatorul nu produce ieșire binară decodorul va lua decizii soft. Decodarea cu decizii soft și plauzibilitate maximă calculează probabilitatea condiționată P(r|v) pentru fiecare cuvânt de cod și selectează cuvântul de cod cu probabilitatea condiționată cea mai mare ca estimat al transmisiei. P(r|v) pentru un canal cu zgomot care afectează fiecare eșantion este:

(2.10)

unde xi este a i-a componentă din secvența x obținută din modularea lui v.

Expresia este maximă când este minimă. Suma este distanța euclidiană între secvența de eșantioane primite și cuvântul de cod modulat. Regula de decodare de plauzibilitate maximă pentru canal gaussian poate fi realizată după cum urmează. Decodorul calculează distanța euclidiană dintre secvențe și selectează cuvântul de cod cu distanța minimă ca fiind estimatul cuvântului de cod transmis. Metoda este impracticabilă pe codurile lungi.

Acesta este pricipalul dezavantaj al codării bloc, lungimea secvenței de intrare nu poate fi foarte mare, complexitatea codorului crescînd cu creșterea acesteia .

2.1.5. Probabilitatea de eroare

Modelul unei transmisii printr-un canal cu ZAGA

Fig. 2.1. Modelul sistemului de codare

Secvența de cod de lungime n este: v = (v0, v1, … vn-1), secvența modulată devine x = (x0, x1, … xn-1). La recepție avem r = (r0, r1 … rn-1).

Semnalul recepționat la momentul i este: ri = xi + ni, dacă avem zgomot de medie nulă și dispersie σ2 : n = (n0, n1 …nn-1). Decodorul reface o secvență care maximizează probabilitatea P(r|v). Probabilitatea ca decodorul să ia decizii incorecte prin selectarea unei secvențe eronate se numește probabilitate de eroare.

(2.11)

unde d este distanța Hamming între cuvinte de cod pereche.

, (2.12)

unde R este rata codului și funcția Q(x) se numește funcția complementară erorii: . (2.13)

Probabilitatea de eroare de bit este:

, (2.14)

unde Bd este coeficientul de eroare, adică numărul de biți eronați cauzați de transmisii între cuvântul de cod 0 și cuvintele de cod cu pondere d (d≥dmin).

2.1.6. Câștigul codării

Sistemele codate obțin aceeași probabilitate de eroare de bit ca la sistemele necodate la un raport semnal zgomot mult mai mic. Diferența dintre RSZ pentru care un sistem codat obține aceeași probabilitate de eroare ca un sistem necodat se numește câștigul codului. Câștigul codului al unui sistem care folosește decodarea cu decizie soft față de un sistem de referință necodat, dacă cele două sisteme au aceeași lărgime de bandă, se definește:

, (2.15)

unde și reprezintă varianța zgomotului gaussian pentru sistemul codat și cel necodat.

2.2. CODURI CONVOLUȚIONALE

2.2.1. Noțiuni introductive

O altă metodă de codare folosită în controlul și corecția erorilor este codarea convoluțională. Spre deosebire de codurile bloc prezentate anterior, unde informația era prelucrată pe cadre, codurile convoluționale prelucrează informația în mod continual. Un șir de date de rată R1 este transformat într-un șir de date de rată R2, unde R2 > R1. Acest tip de codare este mai eficientă decât codarea bloc deoarece permite o prelucrare în mod continual și se obține un câștig de codare mai mare la o complexitate asemănătoare.

Decodarea se bazează, ca și la codurile bloc, pe principiul că secvența estimată de decodor este acea secvență pentru care probabilitatea de a fi transmisă este maximă.

Codurile convoluționale sunt generate cu ajutorul unui registru de deplasare cu k celule și a n sumatoare modulo 2. k este numărul de biți ce intră în codor la un moment dat, iar n reprezintă numărul de biți ca apar la ieșirea codorului. Deci rata acestui codor este . (2.16)

Schema generală a unui codor convoluțional:

Fig. 2.2. Schema generală a unui codor convoluțional

Principala caracteristică a codurilor convoluționale este că acestea au memorie. Fiecare simbol de la ieșire depinde de bitul curent de intrare, dar și de k-1 biți de intrare anteriori.

2.2.2. Descrierea codorului convoluțional pe baza polinoamelor generatoare

Un cod convoluțional este determinat dacă se cunosc polinoamele generatoare care dau:

numărul de celule ale registrului de deplasare (gradul maxim al polinoamelor)

numărul de sumatoare modulo 2

conexiunile între celulele registrului și aceste sumatoare

Fie două polinoame generatoare g1(D) și g2(D):

g1(D) = g + gD + … + gDj + …

g2(D) = g + gD + … + gDj + … (2.17)

Avem secvența de intrare w = [w0, w1 , … wj …] . (2.18)

Secvența de intrare se poate scrie și astfel:

w(D) = w0 + w1D +… + wjDj + …, (2.19)

unde wj {0,1} reprezintă biții de intrare. Biții de intrare sunt introduși în registrul de deplasare de la stânga la dreapta. Pentru fiecare un bit de intrare sunt generați doi biți la ieșirea sumatoarelor modulo 2.

Secvențele la ieșirea celor două sumatoare sunt:

x1(D)=g1(D)w(D) = x1,0 + x1,1D + … + x1,jDj + …x1=[x1,0, x1,1, …x1,j …]

(2.20)

x2(D)=g2(D)w(D) = x2,0 + x2,1D + … + x2,jDj + … x2=[x2,0, x2,1, …x2,j …]

(2.21)

Cele două ieșiri sunt întrețesute pentru a genera secvența de ieșire:

x = [x1,0, x2,0, x1,1, x2,1, … x1,j, x2,1, …] (2.22)

Codurile convoluționale pot fi sistematice sau nesistematice. Cele sistematice presupun ca un polinom generator să fie 1, astfel încât secvența de intrare să se regăsească la ieșire. Cum codurile sistematice au o complexitate mai mică ca cele nesistematice, în condiții de performanțe asemănătoare, cele sistematice sunt preferate în detrimentul celor nesistematice.

Se definește lungimea v de constrângere a codului ca fiind gradul maxim al polinoamelor generatoare.

v = 1 + numărul de celule ale registrului codorului

Exemplu:

Fie g1(D) = 1 + D + D2 g1 = [1 1 1]

și g2(D) = 1 + D2 g2 = [1 0 1] (2.23)

Să se determine cuvântul de cod dacă secvența de date este w = [1 0 1 1]

w(D) = 1 + D2 + D3 (2.24)

Deci

x1(D) = g1(D)w(D) = (1 + D2 + D3)( 1 + D + D2) = 1 + D + D5

x1 = [1 1 0 0 0 1] (2.25)

x2(D) = g2(D)w(D) = (1 + D2 + D3)( 1 + D2) = 1 + D3 + D4 + D5

x2 = [1 0 0 1 1 1] (2.26)

Secvența de cod generată este:

v = [1 1 1 0 0 0 0 1 0 1 1 1] (2.27)

2.2.3. Descrierea codorului convoluțional prin diagrama trellis

Codoarele convoluținale pot fi descrise și cu ajutorul diagramelor trellis care permit o vizualizare a evoluției atât în spațiul stărilor cât și în timp. Pe verticală se reprezintă toate stările posibile ale codorului, la fiecare moment de timp. În funcție de bitul de intrare se determină trecerea codorului în altă stare, această trecere va fi reprezentată printr-o linie (continuă dacă bitul de intrare a fost “0” sau punctată dacă bitul de intrare a fost “1”) ce unește starea de pornire de la momentul discret t cu starea următoare de la momentul t+1. Deasupra liniilor se trec biții ce se întâlnesc la ieșirea codorului.

Diagrama trellis pentru exemplul anterior

Fig. 2.3. Diagrama trellis

Se observă că pentru t > 3 diagrama trellis se repetă, ramurile între t = 2 și

t = 3 sunt identice cu cele ce urmează. Ieșirea se poate determina din această diagramă determinînd ramurile parcurse pe baza secvenței de intrare și citind secvența generată înscrisă deasupra liniilor care marchează tranzițiile. Deci pentru secvența de intrare de la exemplul anterior

w = [1 0 1 1], secvența de ieșire este:

v = [1 1 1 0 0 0 0 1] (2.28)

2.2.4. Matricea generatoare a codului convoluțional

Dacă avem polinoamele generatoare

g1(D) = g + gD + … + gDj g1(D) = (g, g, … g) (2.29)

g2(D) = g + gD + … + gDj g2(D) = (g, g, … g) (2.30)

Se poate scrie matricea generatoare, G:

(2.31)

Operația de codare poate fi scrisă în formă matriceală astfel:

v = w ∙ G, unde w este secvența de intrare, iar secvența de ieșire este v.

Se observă că fiecare rând din cadrul matricei G este obținut prin shiftarea precedentului rând cu 2, unde 2 reprezintă numărul de polinoame generatoare. Matricea G este semiinfinită deoarece se presupune că secvența de intrare este infinită.

Similar se poate genera un cod (n,1) prin shiftarea cu n a rândurilor în cadrul matricei generatoare. A i-a secvență de ieșire (i = 1, n) se obține prin convoluția secvenței de intrare cu a i-a secvență generatoare.

vi = c * gi , i = 1, 2, … n (2.32)

2.2.5. Distanța liberă a codului

Distanță Hamming minimă dintre două cuvinte de cod este cea care determină performanțele codului convoluțional din punct de vedere al probabilității de eroare. Pentru aceasta este necesară alegerea polinoamelor generatoare astfel încât cuvintele de cod generate să fie separate cât mai mult posibil din punct de vedere al distanței Hamming. În plus, perechile de cuvinte de cod separate de distanța Hamming minimă trebuie să difere cât mai puțin posibil unul de altul.

Se definește distanța liberă (df) a codului ca fiind distanța Hamming minimă dintre oricare două cuvinte de cod. Ea este de asemenea și distanța minimă care separă două căi din trellis care diverg dintr-un anume punct și converg într-un alt punct. Pe baza acesteia se poate determina numărul de erori t pe care le poate corecta un astfel de cod:

. (2.33)

2.2.6. Decodarea codului convoluțional

Rolul decodorului este de a estima secvența de date de la intrarea codorului cu un număr cât mai mic de erori. Decodarea codurilor convoluționale se bazează pe algoritmul Viterbi prezentat pentru prima data de A.J.Viterbi în 1967. Acest algoritm este o metodă sistematică de a decodifica o secvență de date codată convoluțional în sensul maximului de plauzibilitate. În esență acest algoritm constă în compararea secvenței recepționate începînd cu momentul t0 cu toate secvențele posibile rezultate din analiza diagramei trellis. Dacă mai multe căi din trellis converg în aceeași stare la un moment de timp ulterior t1, se va păstra aceea care are gradul de corelație maxim cu secvența recepționată (metrica maximă). Această cale se va numi cale supraviețuitoare. În cazul unui canal binar simetric cu probabilitate mai mică decât 0.5, metrica maximă se poate exprima în funcție de distanța Hamming minimă. În acest caz este suficientă determinarea numărului de diferențe dintre secvența recepționată și secvențele corespunzătoare din trellis alegîndu-se aceea care are numărul minim de diferențe.

În funcție de tipul canalului și de caracteristicile alfabetului de la emisie, respectiv recepție decodarea se poate face hard sau soft.

dacă alfabetele de intrare și de ieșire sunt binare, cele două simboluri de la emisie au probabilități egale și transmisia se face printr-un canal binar simetric, regiunile de decizie la recepție sunt egale și decodarea se face cu ajutorul unui filtru adaptat, după fiecare bit transmis. În acest caz decizia se face “hard”.

dacă alfabetul de ieșire nu este binar și/sau probabilitățile simbolurilor la emisie sunt diferite, regiunile de decizie nu mai sunt egale; în plus fiecărui simbol de intrare îi corespunde o secvență de simboluri la ieșire. Decizia se face “soft”.

2.2.7. Codorul Recursiv Sistematic Convolutional (RSC)

Se obtine dintr-un codor conventional (ne-recursive si ne-sistematic) prin alimetarea uneia dintre intrari la una din iesirile sale. Figura 2.4 arata un codor convolutional conventional.

Fig 2.4 Codor convolutional conventional cu r=1/2 si K=3.

Fig 2.5 Codor RSC obtinut din Fig 2.4 cu r=1/2 si K=3.

Codoarele utilizate în turbocoduri sunt în special cele recursive și sistematice. În Figura 2.6 este prezentat un codor convoluțional recursiv, sistematic, având matricea generatoare:

G=[1, (1+D2)/(1+D+D2)].

Deși codurile nerecursive, nesistematice au o distanță liberă dfree, mai mare decât cele recursive și sistematice (RSC), și astfel utilizate în varianta clasică (fără a fi concatenate) oferă rezultate mai bune din punct de vedere al ratei erorii, totuși în componența turbocodurilor se dovedesc a avea performanțe superioare codurile recursive și sistematice.

Acest fapt se datorează unei ponderi mai mari pentru RSC. În contrast cu codorul convoluțional, care are o implementare hard simplă, după cum se vede în Figura 2.6, un decodor, pentru a putea fi component al unui turbocod, trebuie să accepte intrare soft și, de asemenea, să ofere ieșire soft.

Fig. 2.6.Codor convoluțional recursiv, sistematic, cu G=[1, (1+D2)/(1+D+D2)]

2.3. TURBOCODURI

2.3.1. Introducere

După cum s-a amintit în capitolul introductiv, un compromis între câștigul codului și complexitatea sa se poate realiza printr-o concatenare. Astfel se poate realiza un cod concatenat cu performanțe vizibil mai bune. Un cod concatenat este un cod care aplică două nivele de codare, o codare interioară și una exterioară legate printr-un interleaver. Un prim astfel de cod a fost folosit în comunicațiile spațiale prin concatenarea unui cod interior convoluțional cu un cod exterior Reed-Solomon. Principalul avantaj al folosirii unui cod concatenat este realizarea unei rate a erorii mai mici cu o complexitate generală a decodării mai mică decât una necesară pentru un singur cod care dă aceeași performanță. Complexitatea mică este realizată prin decodarea fiecărei componente de cod separat.

Diferența dintre un cod concatenat și un turbocod este că acesta din urmă realizează o concatenare a două coduri convoluționale în paralel. Aceste coduri convoluționale sunt sistematice. Codorul exterior nu transmite biții de la intrare, acest fapt ducînd la micșorarea ratei codului.

Legătura dintre cele două codoare sistematice convoluționale este făcută de un bloc numit întrețesător (interleaver). Acesta are un rol foarte important în funcționarea cât mai eficientă a turbocodorului. Dacă decodorul primește erori în bloc, greu de corectat, întrețesătorul reușește să “împrăștie” aceste erori, realizînd o decorelare a simbolurilor primite. Mărimea întrețesătorului are o mare influență asupra performanțelor codorului; cu cât acesta este mai lung cu atât va crește și câștigul codorului.

Decodarea cuprinde și ea tot două decodoare concatenate, corespunzătoare celor două codoare de la emisie interconectate prin același întrețesător. Decodarea la turbocodare se bazează pe algoritmii de decodare a codurilor sistematice recursive convoluționale din care e format un turbocod, adică algoritmul maximului probabilității aposteriori (MAP – maximum a posteriori) sau algoritmul Viterbi cu ieșire soft (SOVA – soft output Viterbi algorithm). Decodarea se realizează printr-un proces iterativ prin care se face un schimb de informație între cele două decodoare componente. Dacă numărul de iterații crește atunci crește și performanța decodorului ajungînd la limita capacității Shannon.

2.3.2. Codorul turbo

Codorul turbo este format din două codoare convoluționale sistematice recursive (RSC – recursive systematic codes) interconectate printr-un întrețesător.

Schema de principiu a unui turdocodor este:

Fig. 2.3.1. Codorul turbo

Matricea generatoare a unui cod sistematic convoluțional se poate scrie:

(2.3.1)

unde g0(D) și g1(D) sunt polinamele corespunzătore reacțiilor negativă, respectiv pozitivă.

Informația în codorul turbo este codată de două ori prin intermediul întrețesătorului. Primul codor realizează codarea secvenței de intrare notată cu x.

= (0, 1, … n) (2.3.2)

Acesta are două ieșiri una cu biții de informație v0, codorul este sistematic, și una cu biții de paritate v1.

v0 = (v, v, … v)

și v1 = (v, v, … v) (2.3.3)

După interleaver secvența de intrare este modificată într-o altă secvență de date prin permutarea biților din componența secvenței de intrare.

= (, , … ) (2.3.4)

Cu această nouă secvență de intrare al doilea codor RSC realizează codarea și scoate la ieșire numai secvența de verificare a parității v2.

v2 = (v, v, … v) (2.3.5)

Secvența codată rezultă prin multiplexarea acestor trei secvențe de la ieșirea celor două codoare. Rata totală a unui astfel de codor este 1/3.

v = (v, v, v, v, v, v, … v, v, v) (2.3.6)

Din cauza întrețesătorului care duce la prelucrarea biților secvențial se poate spune că un turbocod lucrează ca un cob bloc. Prin folosirea codurilor convoluționale sistematice recursive nu se poate termina trellisul prin introducerea unor k biți de 0. Un trellis terminat înseamnă că trellisul conduce la starea 0. Acest lucru este necesar pentru că starea inițială pentru următorul bloc să fie tot 0. Pentru a conduce trellisul în starea 0 se introduc, după n biți de informație, v biți de final.

Biții de final depind de starea codorului după biții de informație.

O soluție pentru această problemă este sugerată în următoare figură:

Fig. 2.3.2. Terminația trellis

Pentru n biți de informație poziția comutatorului este “1” timp în care are loc decodarea propriu-zisă și aflarea ultimei stări după scurgerea celor n biți. După aceasta poziția comutatorului trece pe “2”. După v cicluri starea finală a codorului va deveni 0.

În mod uzual doar primul codor este forțat să se termine în starea 0. Terminarea celui de al doilea codor într-o formă neștiută nu influențează performanța într-un mod evident, care să justifice un surplus de biți.

Un turbocodor de rată 1/3 terminat trellis cu o lungime a interleaverului de n este echivalent cu un cod bloc liniar sistematic de forma (3(n+v),n).

Exemplu:

Fie un turbocodor de rată . Schema lui bazată pe codoare convoluționale sistematice recursive (2,1,4) este prezentată în figura 2.3.3.

Secvența de intrare este x = (1 0 1 1 0 0 1).

Codoarele convoluționale sunt identice.

Matricea generatoare este:

(2.3.7)

Fig. 2.3.3. Codorul turbo cu rata 1/3

În urma codării secvenței de intrare de primul codor vor rezulta două secvențe de ieșire:

v0 = (1 0 1 1 0 0 1) biții de informație (aceeași cu biții de intrare deoarece codorul convoluțional este sistematic)

și v1 = (1 1 1 0 0 0 1) biții de paritate (rezultați în urma codării)

Secvența de intrare este introdusă în întrețesător rezultînd o altă secvență ce va fi codată de cel de al doilea codor.

Fig. 2.3.4. Procesul de întrețesere

Deci în urma întrețeserii rezultă secvența:

= (1 1 0 1 0 1 0) (2.3.8)

În urma celei de a două codare rezultă alte două secvențe de ieșire:

v0’ = (1 1 0 1 0 1 0) biții de informație (2.3.9)

și v2 = (1 0 1 1 0 0 0) biții de paritate (2.3.10)

Biții de informație de la al doilea codor nu sunt transmiși (aceștia sunt biții de intrare puși în altă ordine) pentru îmbunătățirea ratei. Astfel se transmit doar biții de paritate.

Prin multiplexare se realizeză secvența ce va fi transmisă:

v = (1 1 1, 0 1 0, 1 1 1, 1 0 1, 0 0 0, 0 00 , 1 1 0) (2.3.11)

2.3.3. Întrețesătorul

Acest bloc are un rol foarte important în ceea ce privește performanțele turbocodorului. Principala funcție a interleaverului este de decorela intrările în cele două codoare. Astfel apariția unor erori în bloc, cât și consecințele pe care aceste le aduc sunt evitate prin folosirea unui bloc de întrețesere care amestecă o astfel de secvență. Deoarece decodarea se face iterativ este foarte important ca intrările în decodoare să fie decorelate. Acest lucru duce la posibilitatea ca erorile rămase în urma decodării de primul decodor, să poată fi corectate de cel de al doilea. Structura întrețesătorului trebuie să fie bine știută la recepție.

Opusul operatiei de intretesere se numeste de-intretesere si reda secventei receptionate ordinea initiala.

Dispozitivul de întrețesere (interleaver) este o componentă indispensabilă a oricărui turbocod. Datorită întrețeserii secvenței furnizate celui de-al doilea codor, se obține o decorelare între diferitele intrări ale unui decodor component, mai precis între secvențele: provenite din canal și cea provenită de la celălalt decodor component (informația intrinsecă).Un dispozitiv de întrețesere realizează o permutare a unei secvențe de numere. Altfel spus, un dispozitiv de întrețesere implementează o funcție bijectivă de forma:

π : I → I, cu I = {1,2, … N}, (2.3.12)

unde N reprezintă lungimea secvenței ce trebuie întrețesută. Pentru refacerea ordinii inițiale se utilizează un dispozitiv pereche, de de-întrețesere, ce implementează funcția inversă:

π -1 : I → I, cu π -1( π( i)) = i, i (2.3.13)

Astfel, dacă i reprezintă poziția elementului xi al secvenței de intrare în dispozitivul de întrețesere, în secvența de ieșire același element se va regăsi pe poziția j = π(i).

Un parametru important al dispozitivului de întrețesere îl constituie distanța minimă de întrețesere, dmin, definită ca minimul distanțelor dintre pozițiile rezultate după întrețesere a doi vecini din secvența de intrare:

dmin=(2.3.14)

Este de dorit ca dmin să fie cât mai mare. Un alt deziderat al întrețeserii îl constituie creșterea ponderilor secvențelor binare cu ponderi mici [6] Adică: un codor convoluțional răspunde unor anumite configurații de secvențe de intrare (binare) sărace în unu-uri (de ponderi mici) cu secvențe codate (binare) bogate în unu-uri. Rolul întrețeserii ar fi să „aranjeze” secvențele de pondere mică încât să devină din categoria celor pe care codorul le îmbogățește în pondere. Acest deziderat se obține printr-o împrăștiere cât mai bună a secvenței originale.

Dispozitivele de întrețesere se împart în principal în două categorii. Prima categorie o constituie dispozitivele de întrețesere având o structură regulată, iar a doua categorie o constituie dispozitivele de întrețesere de tip aleator.

Alegerea dimensiunii interleaverului pentru diferite SNR joaca un rol important pentru performata turbocodorului. Pentru a reduce nivelul de erori din TURBO cod, se creste dimensiunea intreleverului. Eroarea de bit pentru un cod TURBO peste un canal afecat de un zgomot alb gausian este limitata superior de urmatoarea ecuatie:

(2.3.15)

unde Bd este coeficientul de eroare,

dmin – distanta libera

Eb/N0 – raportul semnal zgomot.

Interleaverul poate reduce coefientul de eroare a cuvintelor de cod scurte printr-un proces numit Subțiere spectrala [6]. Rezultatul acestui process este o reducere a probabilitatii erorii de bit cu 1/N – castigul interleaverului, unde N este marimea intretesatorului.

La un raport mic al RSZ-ului, dimesnsiune interleaverului este singururl factor determinat, deoarece performanta codului e dominata de castigul interleaverului. Efectele modificarii structurii interleaverului la valori mici ale RSZ sunt nesemnificative. In schimb in momentul in care RSZ este ridicat, ceea ce determina performantele codorului este structura interleaverului. Structura interleaverului afecteaza ordinea secventelor de la iesirea intretesatorului si deci si primele distante ale spectrului distantelor turbo codului. Aceast joaca un rol important in determinarea performatelor codului la un RSZ ridicat.

Întrețesătorul de tip par – impar.

Acest tip de întretesator schimba ordinea biților de intrare punand biții de rang par la inceput și pe cei de rang impar la sfarsit.

Exemplu :

X=[x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14] (2.3.16)

Secventa intretesuta rezultata va fi :

X1=[ x2,x4,x6,x8,x10,x12,x14,x1,x3,x5,x7,x9,x11,x13] (2.3.17)

Întrețesătorul de tip elicoidal

Aceasta metoda transforma creaza o matrice de intretesere pornind de la o scriere matriceala a biților de intrare.

Exemplu :

X=[ x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16] (2.3.18)

Matricea formata( am ales pentru acest caz o matrice 4*4) este:

x1 x2 x3 x4

x5 x6 x7 x8

x9 x10 x11 x12

x13 x14 x15 x16 (2.3.19)

Folosind metoda elicoidala vom obtine secventa:

X1=[ x13,x10,x7,x4,x9,x6,x3,x16,x5,x2,x15,x12,x1,x14,x11,x8] (2.3.20)

Întrețesătorul obtinut prin shiftare

In matrice informația se scrie pe coloane . Se alege un pas de shiftare P. Se alege o valoare initiala B ( numarul de pozitii cu care este shiftat primul rand) .Se realizeaza o shiftare pe randuri cu B pozitii pentru primul rand , apoi pentru fiecare rand se mareste valoarea initiala prin adaugarea pasului B=B+P. Secventele shiftate formeaza matricea de intretesere și datele sunt citite tot pe coloane.

Exemplu:

X=[ x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18] (2.3.21)

x1 x4 x7 x10 x13 x16 x1 x4 x7 x10 x13 x16

x2 x5 x8 x11 x14 x17 => x14 x17 x2 x5 x8 x11

x3 x6 x9 x12 x15 x18 x9 x12 x15 x18 x3 x6 (2.3.22)

Astfel secventa rezultata este:

X1=[ x1,x14,x9,x4,x17,x12,x7,x2,x15,x10,x5,x18,x13,x8,x3,x16,x11,x6] (2.3.23)

Pentru acest exemplu am considerat B=0 și P=2 .

Întrețesătorul bloc

Denumit și rectangular, dispozitivul de întrețesere bloc este primul tip utilizat în schemele de turbocoduri, prezenând cea mai simplă structură. În Figura de mai jos este prezentat un dispozitiv de întrețesere bloc (rectangular) având lungimea N=10×10. Datele de intrare sunt introduse în dispozitiv linie cu linie. Citirea se va face pe coloane, schimbându-se astfel ordinea biților. După întrețesere secvența devine: x1, x11, x21, … x91, x2, x22, … x90, x100.

Oricare doi biți aflați inițial la mai puțin de 10 (numărul de coloane) poziții unul de celălalt vor fi depărtați la cel puțin 10 (numărul de linii) poziții.

Pentru o mai bună împrăștiere a erorilor, după interschimbare se poate recurge la permutări între linii sau coloane, rezultând astfel un dispozitiv de întrețesere neuniform, însă cu performanțe mai bune.

Fig 2.3.4 Întrețesere bloc (rectangulară)

Întrețesătorul diagonal

Dispozitivul de întrețesere diagonal este un dispozitiv de întrețesere de tip regulat însă oferă o mai bună împrăștiare decît cel rectangular, fapt ce conduce la o mărire a capacității de corecție a turbo-codurilor. În Figura de mai jos este ilustrat procesul de întrețesere diagonală pentru o matrice pătratică de dimensiuni 10 x 10.

La fel ca și pentru dispozitivul de întrețesere rectangular și în cazul celui diagonal se poate utiliza un procedeu de amestecare a diagonalelor.

Fig 2.3.5 Întrețesere diagonală

Dispozitiv de întrețesere pseudo-aleator de distanță 8

Face parte din recomandarea CCSDS (Consultative Comittee for Space Data Systems) denumită “CCSDS Recomandation for Telemetry Channel Coding” și care este dedicată dezvoltării sistemelor de codare a canalului utilizate în comunicațiile spațiale. Denumirea dispozitivului provine de la faptul că permutările nu sunt aleatoare în adevăratul sens al cuvântului (avem de-a face cu o dezordine controlată), asigurându-se o distanță minimă de întrețesere egală cu 8. Este un dispozitiv de întrețesere performant, care îmbină avantajele furnizate de interleaverele aleator și bloc, adică prezintă o bună împrăștiere la o distanță minimă suficient de mare. În recomandare se specifică utilizarea unui turbocod de tip paralel cu două codoare convoluționale recursive de rată 1/2, 1/3, 1/4, sau 1/6.

Întrețeserea pseudo-aleatoare este sugerată schematic în Figura de mai jos.

Fig 2.3.6 Întrețesere pseudo-aleatoare

Permutarea pentru fiecare secvență de lungime N a blocului este dată de o reordonare particulară a biților 1, 2, … N, generată de următorul algoritm:

N = k1⋅k2 unde k1=8 (parametru fix), iar k2 variază în funcție de lungimea dispozitivului de întrețesere;

pentru s de la 1 la N (poziția curentă înainte de interschimbare) se efectuează următoarele operații și se obțin permutările π(s) [JEZ]:

m=(s-1) mod 2

q= t mod 8 +1

c=(pq*j + 21m) mod k2

În care [ ] – parte întreagă

mod – operație modulo (clase de resturi)

q = 1÷8 și p1 =31, p2 =37, p3=43,p4=47, p5=53,p6=59, p7=61, p8=67

Problema interleaverelor pseudo-aleatoare, în special a celor cu lungime mare a

blocurilor este memorarea modelelor (structurilor) lor. De aceea sunt de preferat algoritmi simpli de generare a interleaverelor [TAC].

Întrețesătorul aleator

Pentru realizarea unui întretesator aleator se alege dimensiunea dorita și se genereaza pozitiile aleator.

Exemplu:

X=[ x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15]

X1=[ x3,x8,x1,x14,x9,x6,x12,x5,x15,x2,x4,x11,x7,x10,x13]

Dispozitivul de întrețesere aleator, sau pur aleator, este relativ simplu de realizat, oferă cea mai bună împrăștiere a secvenței originale, însă are în general dmin = 2, adică cea mai mică valoare posibilă.

Un alt dezavantaj major al întrețeserii aleatoare este nereproductibilitatea procedeului de generare al funcției π: o dată generată funcția de tip aleator ea trebuie memorată pentru a putea fi reprodusă.

2.3.4. Turbocoduri cu rată mare – Puncturarea

În cazul în care ambele codoare au aceași rată, de exemplu 1/2 cum s-a prezentat în exemplul anterior, atunci rata totală a turbocodului este 1/3, unii din biții de informație nu au fost transmiși.

Se poate ca cele două codoare a turbocodului să nu aibă aceeași rată. Unul poate avea rata R1, iar celălalt rata R2. În acest caz rata totală a turbocodului este:

(2.3.20)

Micșorarea ratei codorului se poate face și prin transmiterea sărită a secvențelor de paritate. Această operație poartă numele de puncturare (puncturing). Puncturarea este procedeul de ștergere a unor biți din secvența turbocodată în scopul măririi ratei de codare și implicit a eficienței transmisiei. Prețul acestei măriri a eficienței este binențeles o anumită degradare a performanței. [2] Puncturarea se aplică doar biților de paritate, biții de informație rămânînd neschimbați.

Astfel o parte din biții de paritate sunt sterși după o matrice numită matrice de puncturare P. Un cod cu rata 1/2 se poate obține dintr-un cod cu rata 1/3. O matrice de puncturare folosită în acest caz poate fi:

(2.3.21)

Ținînd cont de exemplul de mai sus biții v0 rămîn nemodificați, cei care suferă schimbări fiind secvențele v1 și v2.

Secvența transmisă devine:

v = (v, v, v, v, … v, v), unde i = {1,2} (2.3.22)

Din cauza întrețesătorului, prin care biții sunt prelucrați în blocuri, turbocodul poate fi privit ca un cod bloc. Din această cauză trebuie ca trellisul corespunzător codorului să se termine cu starea 0, pentru ca starea de început pentru următorul bloc să fie 0. Pentru aceasta se introduc v biți de control după biții de informație care conduc trellisul la starea 0.

2.3.5. Comparație între performanțele unui codor convoluțional și unul turbo

După cum s-a arătat în subcapitolele precedente un cod format printr-o concatenare de coduri are performanțe mai bune ca un simplu cod convoluțional. Principalul argument pentru această diferență de performanță îl reprezintă codarea informației de două nivele ceea ce permite o putere de corectare mai bună a decodorului. Astfel cu un turbocod se obține o rată de eroare mult mai mică decât în cazul unui codor convoluțional.

Rezultatele teoretice sunt susținute de simularea performanțelor pentru două coduri turbo, respectiv convoluțional.

Fig. 2.3.5. Performanțele probabilității de eroare de bit pentru un codor convoluțional, respectiv un turbocodor

Pentru această simulare s-a folosit un cod convoluțional (2,1,2) și un turbocodor de rată 1/3 cu același ordin de memorie.

Se poate observa foarte clar diferența dintre performanțele celor două codoare. La un raport semnal zgomot de 3 dB diferența este de aproximativ 10-3 între cele două probabilitățile de eroare de bit.

CAPITOLUL 3

DECODAREA TURBOCODURILOR

3.1. DECODAREA CODURILOR LINIARE BAZATǍ PE TRELLIS

3.1.1. Introducere

În capitolul 2 s-au prezentat codurile bloc și cele convoluționale, precum și reprezentarea acestora prin trellis. În acest capitol se vor prezenta mai multe metode de decodare a codurilor liniare bazate pe trellis. Fiecare din aceste metode de decodare pot fi folosite ca blocuri componente în decodare turbocodurilor.

Algoritmii de decodare bazați pe trellis sunt niște metode recursive prin care se estimează secvența de date. O primă metodă de decodare o reprezintă algoritmul Viterbi. Acesta minimizează probabilitatea de eroare a secvenței de date. Ieșirea sa este o estimare hard a simbolurilor transmise care au probabilitatea cea mai mare de a fi secvență de cod. În sistemele concatenate, în care procesarea semnalului are mai multe stagii, performanțele totale la recepție sunt îmbunătățite dacă codorul interior produce o estimare soft la ieșire. Se va arata cum algoritmul Viterbi poate fi modificat astfel încât să genereze la ieșire informație soft. Acest algoritm este cunoscut ca algoritmul Viterbi cu ieșire soft (SOVA – soft output Viterbi algorithm). SOVA produce un estimat de siguranță pentru fiecare simbol recepționat, bazat pe criteriul maximei plauzibilități. Estimatele de siguranță nu sunt optime.

O altă clasă de decodoare se bazează pe criteriul de minimizare a probabilității de eroare de bit. Decodorul genereză estimate de sigurață optime sub forma unor probabilități aposteriori de simbol. Algoritmul este cunoscut ca decodarea cu probabilitate aposteriori maximă (MAP – maximum a posteriori probability). Există și două versiuni bazate pe acest algoritm de decodare care duc la performanțe mai bune și la o complexitate mai mică. Aceste versiuni se numesc Max-Log-MAP, respectiv Log-MAP.

3.1.2. Modelul sistemului

În acest subcapitol se va analiza modelul unui sistem de codare-decodare.

Schema unui astfel de sistem este prezentată în figura de mai jos:

Fig. 3.1.1. Modelul sistemului

Pentru a simplifica analiza modelului se presupune că avem un codor convoluțional de tip (n,1,v).

Avem o secvență binară de date notată cu c:

c = (c1, c2, … ct, … cN), (3.1.1)

unde ct este un simbol din mesaj la momentul t și N dă lungimea secvenței. Secvența este codată cu un cod liniar. Simbolurile ct nu sunt întotdeauna binare, dar pentru simplificarea modelului sunt presupuse binare și cu probabilități apriori egale. Procesul de codare poate fi reprezentat prin diagrame de stare sau diagrame trellis. În funcție de ct codorul generează la ieșire un alt simbol vt și își schimbă starea din St în starea următoare St+1, unde t+1 este momentul de timp următor. Procesul poate fi complet definit prin următoarele două funcții:

vt = f(St, ct, t)

și St+1 = g(St, ct, t) (3.1.2)

Funcțiile f și g sunt în funcție de timp.

Secvența de stare de la momentul 0 la t este notată cu S0t și este scrisă:

S0t = (S0, S1, … St) (3.1.3)

Probabilitatea de a trece în starea St+1 este

P(St+1| S0, S1, … St) = P(St+1| St), (3.1.4)

depinde doar de stare trecută St deoarece aceasta din urmă depinde și ea la rândul său de stările precedente.

Ieșirea codorului de la momentul de timp 1 la t este notată:

v1t = (v1, v2, … vt) (3.1.5)

unde vt = (vt,0, vt,1, …vt,n-1) (3.1.6)

este un cuvânt de cod de lungime n.

Secvența de cod v1t este modulată cu un modulator BPSK. Secvența modulată este notată cu x1t:

x1t = (x1, x2, … xt) (3.1.7)

unde xt = (xt,0, xt,1, …xt,n-1) (3.1.8)

și xt,i = 2vt,i -1 cu i = 0, 1, … n-1 (3.1.9)

Deoarece există o corespondență bidirecțională între secvența de cod și secvența modulată perechea codor/modulator poate fi reprezentată grafic printr-o diagramă trellis.

Secvența modulată x1t este transmisă printr-un canal cu zgomot aditiv gaussian alb (ZAGA) rezultînd la recepție secvența:

r1t = (r1, r2, … rt) (3.1.10)

unde rt = (rt,0, rt,1, …rt,n-1) (3.1.11)

și rt,i = xt,i + nt,i, i = 0, 1, … n-1 (3.1.12)

unde nt,i este un eșantion de zgomot gaussian de medie nulă și dispersie σ2. Se presupune că fiecare eșantion de zgomot este independent de celelalte.

Decodorul dă un estimat a intrări în decodor pe baza secvenței recepționate r1t. Problema decodării presupune găsirea secvenței modulate x1t sau a secvenței codate v1t. Deoarece există o funcție bijectivă între cele două secvențe, găsirea uneia dintre ele duce la aflarea celeilalte printr-o simplă mapare.

3.1.3. Criteriul de optimizare

În sistemul prezentat anterior s-a folosit o modulație BPSK, dar în general se poate folosi o M-modulație unde secvența de cod v este divizată în grupuri de log2M simboluri binare și fiecare dintre grupuri este mapat într-un M-simbol de modulator.

Presupunem că secvența modulată conține N’ M-simboluri:

x = (x1, x2, .. xN’) (3.1.13)

Secvența de cod corespunzătoare v este formată din N’ ∙ log2M simboluri binare:

v = (,…,,,…,,…,,…)

Secvența de mesaj este:

c = (c1, c2, …,cN) (3.1.14)

unde N = R∙N’∙log2M, iar R este rata codului.

Receptorul estimează secvența de mesaj c, rezultînd o secvență :

= (, , …,) (3.1.15)

Datorită corespondenței biunivoce între secvențele c, v și x estimatele cuvintelor de cod și a secvențelor modulate pot fi obținute printr-o simplă mapare. Acestea se pot scrie astfel:

= (, …,, , …,, …,, …)

și = (, , …,)

Receptorul optim este proiectat să minimizeze una din următoarele probabilități de eroare:

Rata erorii de cuvânt (WER – word error rate) care este definită ca probabilitatea ca v, unde v și sunt secvențele de cod transmise, respectiv estimate.

Rata erorii de simbol (SER – symbol error rate) care este definită ca probabilitatea ca xt, t = 1, 2, …, N’ , unde xt și sunt simbolurile modulate transmise, respectiv estimate la momentul de timp t.

Rata erorii de bit (BER – bit error rate) care este definită ca probabilitatea ca ct, unde ct și sunt biții transmiși, respectiv estimați la momentul de timp t.

Dacă apare o eroare de cuvânt, trebuie să existe cel puțin un simbol eronat. Dacă avem un simbol eronat atunci există sigur cel puțin un bit eronat. Aceste probabilități sunt folosite doar în estimarea hard.

Este posibil să proiectăm trei clase de receptoare optime care corespund minimizării probabilității de eroare de cuvânt, probabilității de eroare de simbol, respectiv probabilității de eroare de bit. Aceste receptoare au performanțe diferite în cazul unui raport semnal-zgomot mic, iar la un raport semnal-zgomot mare performanțele sunt aproape identice. Minimizarea probabilității de eroare de cuvânt produce minimizarea probabilității de eroare de simbol și a probabilității de eroare de bit.

În sistemele cu transmisiune binară probabilitatea de eroare de simbol este identică cu probabilitatea de eroare de bit. Chiar și în cazul sistemelor nebinare, receptoarele care minimizează probabilitatea de eroare de simbol au o structură identică ca acelea care minimizează probabilitatea de eroare de bit.

3.1.4. Algoritmul Viterbi

Algoritmul Viterbi este folosit în decodarea codurilor convoluționale, dar poate fi folosit pentru a rezolva diferite probleme de estimare ce apar în diferite tipuri de comunicații. În modelul prezentat anterior codorul/decodorul poate fi reprezentat printr-o diagramă trellis cu MS stări.

Inițial presupunem că procesul începe din starea 0 la momentul 0 și se termină în starea 0 la momentul de timp τ, unde τ este momentul terminal al trellis-ului.

Secvența stărilor poate fi scrisă:

S = (0, S1, S2 …,Sτ-1, 0) (3.1.16)

Algoritmul Viterbi găsește secvența de informație care corespunde secvenței modulate în diagrama trellis astfel încât probabilitatea de eroare de cuvânt, Pw să fie minimă. Probabilitatea de eroare de cuvânt se poate exprima:

(3.1.17)

unde r este secvența recepționată r = r1τ.

Minimizarea probabilității de eroare de cuvânt este echivalentă cu maximizarea celui de-al doilea termen din expresia probabilității de eroare de cuvânt, care este probabilitatea ca si cuvântul să fie corect.

este pozitivă și independentă de c, acest lucru duce mai departe la maximizarea probabilității aposteriori Pr(c|r). Receptorul care maximizează această probabilitate este cunoscut ca receptorul cu probabilitatea aposteriori maximă (MAP – maximum a posteriori probability).

Folosind regula lui Bayes:

(3.1.18)

Presupunînd că semnalele sunt egal probabile, este suficient pentru receptor să maximizeze funcția de plauzibilitate Pr(r|c). Decodorul care își selectează estimatul prin maximizarea funcției de plauzibilitate se numește decodorul de plauzibilitate maximă. (ML – maximum likelihood). Expresia de mai de sus ne arată că dacă secvențele sunt de probabilitate egală, decodoarele MAP și ML sunt echivalente din punct de vedere al probabilității de eroare de cuvânt.

Probabilitatea Pr(r|c) a unei secvențe recepționate de lungime τ, se poate scrie astfel:

(3.1.19)

Pentru a simplifica operațiile, se introduce un logaritm log Pr(r|c) :

(3.1.20)

Pentru canal Gaussian expresia log Pr(r|c) devine:

(3.1.21)

Expresia (3.1.21) ne arată că maximizarea Pr(r|c) este echivalentă cu minimizarea distanței Euclidiene

dintre secvența recepționată și secvența modulată din diagrama trellis.

Se atribuie fiecărei ramuri la momentul t pe calea x din trellis distanța Euclidiană numita metrica ramurei, notată cu după cum urmează:

(3.1.22)

Metrica căii corespunzătoare căii x, notată este dată de relația:

(3.1.23)

Minimizarea distanței Euclidiene este echivalentă cu maximizarea expresiei care este o altă definiție a metricii căii.

Algoritmul Viterbi este un mod eficient în gasirea unei căi în trellis care are metrica căii cea mai mică. El se bazează pe ideea că printre căile ce converg către o stare în trellis doar cele mai probabile căi trebuiesc salvate în vederea procesării decodării, celelalte căi putînd fi omise fără ca această operație să influențeze decodarea.

Procesul de decodare se bazează pe reținerea doar a unei căi pentru fiecare nod. Acestă cale este cea cu metrica cea mică. Acestă cale se numește supraviețuitor.

Decizia asupra mesajului estimat c este luată la final, adică la ultimul moment de timp τ. Calea cu plauzabilitate maximă corespunde căii , decodorul va selecta secvența binară corespunzătoare acestei căi și va estima hard secvența transmisă c.

3.1.4.1. Prezentarea algoritmului Viterbi

Se setează următorele valori:

t = 0; S0 = 0; (S0 = 0) = 0; ( S0 0) =

2. Se crește momentul de timp t cu 1

– Se calculează metricele ramurilor pentru toate ramurile care intră într-un nod la momentul de timp t.

– Se calculează metricele căilor pentru toate căile care intră într-un nod la momentul de timp t, prin adunarea metricii ramurii ce intră în nod la metrica căii corespunzătoare căii supraviețuitoare de la nodul anterior de la momentul de timp t-1.

– Se compară metricile căilor pentru toate căile ce intră într-un nod și se găsește supraviețuitorul pentru fiecare nod. Pentru fiecare nod se memorează calea supraviețuitoare și metrica sa.

– Se repetă 2. până t = τ

3. Supraviețuitorul de la nodul Sτ este calea de plauzibilitate maximă.

Când lungimea secvenței este lungă sau infinită este necesar să trunchiem supraviețuitorii astfel încât să avem un control asupra lungimii. Acestă operațiune poartă numele de decizia de adâncime, notată cu D.

Decodorul ia decizii asupra transmiterii simbolului ct la momentul t’ = D + t

În general, dacă D este destul de mare există o probabilitate mare ca toți supraviețuitorii să provină de la ramură la momentul t. Simbolul de plauzibilitate maximă la momentul t poate fi găsit printr-o decizie a algoritmului. Decizia asupra căii cu plauzibilitate maximă la momentul t’ = t + D poate fi unul dintre supraviețuitori sau supraviețuitorul cu metrica cea mai mică. Când D este destul de mare (cam de șase ori mai mare ca ordinul de memorie) efectul alegerii unui anumit supraviețuitor asupra performanței este neglijabil.

Dacă timpul t devine foarte mare este necesară o normare a metricilor căilor supraviețuitorilor.

Algoritmul Viterbi poate începe fără să se știe starea inițială. În acest caz algoritmul trebuie inițializat cu o valoare cum ar fi (l) = 0, unde l = 1, 2, … MS pentru toate stările l. În mod uzual după o astfel de inițializare toți supraviețuitorii vor converge către calea corectă. Algoritmul Viterbi se sincronizează singur fără nici o procedură specială.

Algoritmul Viterbi necesită MS∙D unități de memorie pentru a reține supraviețuitorii și metricile lor. Pentru un cod convoluțional (n,k) există 2k ramuri care intră într-un nod. Algoritmul calculează MS∙2k metrici de ramuri și execută MS∙2k adunări și MS∙2k comparări pentru fiecare moment de timp.

Memoria este proporțională cu numărul de stări și complexitatea este proporțională cu numărul de ramuri și numărul de stări.

Exemplu. Vom considera codorul convoluțional sistematic recursiv din figura. 3.1.2.

Fig. 3.1.2. Shema unui codor convoluțional (2,1,1)

Diagrama trellis corespunzătoare acestui cod este reprezentată în figura 3.1.3.

Fig. 3.1.3. Diagrama trellis corespunzătoare codului din figura 3.1.2.

Presupunem că secvența recepționată este

r = [(1,-1), (0.8,1), (-1,1), (-1,1), (1,-1)]

Vom aplica algoritmul trellis de decodare pentru a estima secvența transmisă. Se vor calcula metricile brațelor și metricile căilor, rezultatele fiind în figura 3.1.4.

Fig. 3.1.4. Metricile ramurilor

Pe baza metricilor se vor stabili supraviețuitorii

Fig. 3.1.5. Supraviețuitorii și metricile căilor din exemplu de mai sus

Astfel secvență estimată pe baza secvenței recepționate este c = [0 1 0 0 1]

3.1.5. Algoritmul Viterbi cu ieșire soft bidirecțional

SOVA este un algoritm care nu necesită cunoștințe asupra zgomotului și este ușor de implementat mai ales în cazul sistemelor care prelucrează datele în bloc. SOVA estimează informația soft pentru fiecare simbol binar transmis bazîndu-se pe funcția de log-plauzibilitate (ct), care este definită de relația următoare:

(3.1.24)

unde r1 este secvența recepționată și Pr(ct=i|r1), i = 0,1 este probabilitatea aposteriori a simbolului transmis.

Decodorul SOVA ia o decizie hard prin compararea lui (ct) cu un prag egal cu 0:

(3.1.25)

Decodorul selectează calea cu metrica căii minimă ca fiind calea de plauzibiliate maximă ca în cazul algoritmului Viterbi. Probabilitatea de a selecta această cale este proportională cu:

(3.1.26)

Să notăm cu metrica minimă a căilor corespunzătoare simbolului complementar simbolului de plauzibilitate maximă la momentul t. Dacă simbolul de plauzibilitate maximă este 1 la momentul t, atunci simbolul complementar este 0.

Deci ecuația (3.1.26) se poate scrie:

(3.1.27)

Logaritmul raportului dintre cele două probabilități de mai sus este:

(3.1.28)

Se notează cu t1 metrica minimă dintre toate căile pentru care ct este egal cu 1 și t0 metrica minimă pentru căile pentru care ct este egal cu 0. Dacă estimatul de plauzibiliate maximă este 1 la momentul t, atunci simbolul său complementar este 0 la momentul t. t1 =,min și t0 =t,c și raportul de log-plauzibilitate devine:

(3.1.29)

O altă posibilitate este ca estimatul de plauzibilitate maximă să fie 0 la momentul t, atunci simbolul său complementar este 1 și t0 =,min și t1 =t,c. Raportul de log-plauzibilitate devine în acest caz:

(3.1.30)

Din ecuațiile (3.1.29) și (3.1.30) se poate vedea , din puncte de vedere al estimatului hard de plauzibilitate maximă, că raportul log-plauzibil se poate exprima:

(3.1.31)

Ieșirea soft a decodorului se obține astfel ca diferența dintre metrica căii mimine calculate dintre toate căile cu simbolul 0 la momentul t și metrica căii minime dintre toate căile cu simbolul 1 la momentul t. Semnul raportului (ct) determină estimatul hard la momentul t și valoarea sa absolută reprezintă informația de ieșire soft care se folosește în procesul de decodare la următorul pas.

Dacă decizia se ia pentru un cuvânt de cod de lungime finită, ca în cazul codurilor bloc, a turbocodurilor sau a codurilor convoluționale din sistemele TDMA, atunci SOVA poate fi implementat cu o metodă recursivă bidirecțională care implica metode recursive pozitivă și negativă:

3.1.5.1. Prezentarea algoritmului Viterbi cu ieșire soft

I Recursivitatea pozitivă

1. Se setează valorile inițiale

t = 0; S0 = 0; 0(x) (S0 = 0) = 0; 0(x) (S0 0) = ; S = 0

2. Se crește momentul de timp cu 1

Se calculează metricile ramurilor pentru toate ramurile care intră într-un nod la momentul t.

Se calculează metricile căilor pentru toate căile care intră într-un nod la momentul de timp t

Se compară metricile căilor și se găsește supraviețuitorul pentru fiecare nod

Se memorează supraviețuitorul și metrica căii pentru fiecare nod

Se repetă 2. până când t = .

Supraviețuitorul de la nodul S este corespunzător căii de plauzibilitate maximă și metrica sa este: ,min.

II Recursivitatea negativă

Se setează valorile inițiale

t = ; S = 0; (x) (S = 0) = 0; (x) (S0 0) = ; S0 = 0

Se decrementează momentul de timp cu 1

Se calculează metricile ramurilor pentru toate ramurile care intră într-un nod la momentul t.

Se calculează metricile căilor pentru toate căile care intră într-un nod la momentul de timp t

Se compară metricile căilor și se găsește supraviețuitorul pentru fiecare nod

Se memorează metrica căii corespunzătoare supraviețuitorului pentru fiecare nod

Se repetă 2. până când t = 0.

III Decizia soft

Se setează t = 0

Se crește momentul de timp cu 1

La momentul t se identifică estimatul de plauzibilitate maximă

ct = i, i = 0, 1

Se determină ti

ti = ,min

Se găsește metrica căii tc, , unde este suma modulo 2, astfel:

(3.1.32)

unde l’, l = 0,1, … Ms – 1, t-1f(l’ ) este metrica căii pentru supraviețuitorul forward la momentul t – 1 și nodul l’, tc(l’,l) este metrica ramurei la momentul t pentru simbolurile complementare c de la nodul l’ la nodul l, tb(l) este metrica căii pentru supraviețuitorul negativ la momentul t și nodul l.

Se calculează (ct) astfel:

(ct) = t0-t1 (3.1.33)

Se pot realiza pașii de la recursivitatea negativă și de la decizia soft simultan, fapt ce duce la reducerea complexității de decodare.

Exemplu. Considerăm codorul din figura 3.1.2. Secvența recepționată este

r = [(1,1), (-1,1), (0.8,-1), (-1,-1)]

Se calculează metricile ramurilor, rezultatele sunt prezentate în figura 3.1.6

Fig. 3.1.6. Metricile ramurilor

Se calculează metricile căilor pentru recursivitatea pozitivă:

Fig. 3.1.7. Recursivitatea pozitivă

Calea de plauzibilitate maximă este reprezentată cu linie mai îngroșată. Metrica acestei căi este 4,min = 0.04

Rezultatele recursivității negative sunt prezentate în figura 3.1.8.

Fig. 3.1.8. Recursivitatea negativă

La momentul t=1 estimatul hard de plauzibiliatate maximă este c1 = 1. Astfel 11 = 4,min = 0.04. 10 este metrica minimă a căilor care au 0 la momentul 1. Există o singură cale cu 0 la momentul 1 și metrica este calculată din figura 3.1.8 ca sumă a supraviețuitorilor recursivităților pozitive și negative la nodul 0.

10 = 8 + 4.04 = 12.04

Raportul de plauzibilitate la momentul t=1 este:

(c1) = 10-11 = 12.04 – 0.04 = 12

La momentul t=2 estimatul hard de plauzibiliatate maximă este c2 = 0. Metrica căii minime este 20 = 0.04. Calea simbolului complementar la momentul 2 se obține din formula:

21 = min {1f(l’) + v21(l’,l) + 2b(l)}

unde 1f(l’) este metrica supraviețuitoare a recursivității pozitive la momentul 1 și nodul l’ = 1, 0, v21(l’,l) este metrica ramurei la momentul 2 pentru simbol de intrare 1, iar 2b(l) este supraviețuitorul recursivității negative la momentul 2 la nodul l = 1,0.

Astfel:

21 = min {(0 + 8 + 3.24), (8 + 4 + 0.04)} = 11.24

Raportul de plauzibilitate corespunzător momentului 2 este:

(c2) = 20-21 = 0.04 – 11.24 = -11.2

Momentul t=3 estimatul este c3 = 1. Metrica căii minime este 31 = 0.04. Calea simbolului complementar la momentul 3 se obține din formula:

30 = min {2f(l’) + v30(l’,l) + 3b(l)}

Deci:

30 = min {(0 + 7.24 + 4), (8 + 3.24 + 0)} = 11.24

Raportul de plauzibilitate corespunzător momentului 3 este:

(c3) = 30-31 = 11.24 – 0.04 = 11.2

La momentul t=4 estimatul hard de plauzibiliatate maximă este c4 = 0. Metrica căii minime este 40 = 0.04. Calea simbolului complementar este:

41 = 0 + 7.24 + 4 = 11.24

Deci raportul de plauzibilitate devine:

(c4) = 40-41 = 0.04 – 11.24 = -11.2

Pe baza rezultatelor rapoartelor de plauzibiliate se ia decizia hard după regula dată de (3.1.25), astefel secvența estimată este ct = [1 0 1 0]

3.1.6. Algoritmul Viterbi cu ieșire soft cu ferestre glisante (SOVA)

Decodorul Viterbi selectează o cale din trellis care are metrica minimă. Procesul de decizie se bazează pe păstrarea doar a unei căi pe nod, acea cale care are metrica cea mai mică. Deciziile sunt luate cu o întârziere care depinde de ordinul de memorie al codului. Metrica căii minime este selectată dintre căile minime corespunzătoare celor Ms supraviețuitori, unde Ms este numărul de stări din trellis.

Întârzierea în standardul SOVA este egală cu lungimea secvenței recepționate. Pentru lungimi mari ale secvenței, memoria pentru implementarea decodorul este foarete mare. În acest algoritm deciziile se fac pe baza recursivităților pozitive și negative. Rezultatele ambelor recursivități trebuie memorate. Recursivitățile pozitive și negative sunt realizate pe întrega secvență, astfel decodorul trebuie să memoreze τ × Ms supraviețuitori și metricile în fiecare direcție.

Algoritmul SOVA se poate modifica astfel încât să se micșoreze memoria necesară. Aceasta se poate reduce folosind același principiu ca și cazul decodării Viterbi a codurilor convoluționale când adâncimea este de șase ori mai mare ca memoria codorului. Algoritmul Viterbi poate să înceapă din orice stare; dacă la început metricile căilor nu sunt cele adevărate, după câteva lungimi de memorie rezultatul se apropie de cel căutat, adică rezultatul corespunzător începerii algoritmului din nodul inițial.

În SOVA pentru ambele recursivități pozitivă și negativă, decizia asupra unui simbol poate fi făcută cu întârziere și cu o lungime de aproape șase ori mai mare ca memoria. Fie decizia la o anumită adâncime pentru o singură componentă a codului convoluțional notată cu D. Decodorul nu trebuie să pornească de la nodul inițial. El poate porni de la oricare nod și decizia ce se ia la o anumită adâncimea este aceeași ca cea pentru care algoritmul pornește de la nodul inițial.

Simplificarea operației de decodare este prezentată în cele ce urmează:

Se divizează secvența recepționată în câteva sub-blocuri de lungime D. Recursivitățile pozitivă și negativă se aplică pentru fiecare ieșire din sub-bloc generînd metricile căilor.

Procesarea pozitivă a algoritmului pornește din starea 0 și calculează metricile căilor pentru fiecare nod la fiecare moment de timp. La momentul 2D se selectează calea cu metrica cea mai mică, adica calea de plauzibilitate maximă, și se face decizia hard pentru primul sub-bloc. Recursivitatea negativă începe de la momentul 2D și merge invers setînd fiecare metrică la aceeași valoare fără să memoreze ceva până la momentul D. La acest moment a fost găsită metrica căii potrivite. Procesul este reprezentat grafic mai jos:

Fig. 3.1.9. Procesul pozitiv și negativ pentru SOVA simplificat

În figură liniile punctate reprezintă metricile căilor nesigure. Recursivitatea negativă continuă de la momentul D până ajunge la momentul inițial 0. De îndată ce recursivitatea ajunge la momentul D, decodorul începe să proceseze decizia soft pentru primul sub-bloc bazată de recursivitatea pozitivă și negativă.

Deoarece deciziile soft sunt calculate în același timp cu recursivitatea negativă nu este nevoie de memorarea tuturor metricilor negative ci doar câte una pentru fiecare nod.

După ce decizia soft a fost generată toate metricile căilor corespunzătoare primul sub-bloc sunt șterse din memorie, iar celule de memorie sunt ocupate cu metricile celui de al doilea bloc calculate de ultima recursivitate pozitivă. Recursivitatea pozitivă calculează metricile căilor de la momentul 2D+1 la momentul 3D și selectează metrica căii mimimă pentru cel de al doilea sub-bloc. Recursivitatea negativă începe de la momentul 3D și construiește stările sigure până la momentul 2D. În același timp cu recursivitatea negativă se ia decizia soft de la momentul 2D la momentul D bazată de ambele recursivități.

Recursivitatea pozitivă trebuie să memoreze 2D × MS metrici, iar această memorie este refolosită odată cu trecerea la alt sub-bloc. Recursivitatea negativă are nevoie să memoreze doar 1 × MS metrici.

Dezavantajul acestui algoritm este că necesită un timp mai mare de calcul datorită calculării de două ori a recursivității negative. Totuși o comparație între algoritmul SOVA standard și algoritmul SOVA simplificat ne arată că aceast dezavantaj al creșterii timpului este neglijabil.

3.1.7. Algoritmul MAP

Algoritmul MAP (maximum a posteriori probability) minimizează probabilitatea de eroare de simbol (sau de bit). Pentru fiecare simbol transmis algoritmul generează un estimat hard și o ieșire soft sub forma unei probabilități aposteriori bazată pe secvența recepționată r. Se calculează raportul log-plauzibil:

pentru , unde este lungimea secvenței recepționată.

(3.1.34)

Se compară valoarea raportului cu un prag 0 determinîndu-se astfel estimatul hard :

(3.1.35)

Valoarea reprezintă informația soft asociată estimatului hard . Aceasta valoare a raportului de log-plauzibilitate se poate folosi în următorul pas al decodării.

Considerăm modelul prezentat în figura 3.1.1. Pentru simplificare se presupune că secvența binară c de lungime N este codată de un cod convoluțional sistematic cu rata 1/n. Procesul de codare este descris de o diagramă trellis cu Ms stări. Presupunem starea inițială S0 = 0 și stare finală Sτ = 0. Secvența recepționată r este influențată de zgomot Gaussian de medie nulă și de dispersie σ2.

Pentru înțelegerea algoritmului se va folosi un exemplu de codor convoluțional recursiv sistematic de ordin 2 și rată 1/2 prezentat în figura 3.1.10.

Fig. 3.1.10. Codor 2 RSC de rată 1/2

Conținutul regiștrilor de shiftare al codorului la momentul t este starea St. Acesta trece în St+1 ca răspuns la secvența de intrare ct+1, iar ieșirea codorului devine vt+1. Tranziția stărilor este prezentată în diagrama de stare din figura 3.1.11.

Tranzițiile stărilor codorului sunt influențate de probabilități de tranziție:

; 0 ≤ l, l’ ≤ Ms – 1 (3.1.36)

Ieșirea codorului este determinată de probabilitățile:

; 0 ≤ l, l’ ≤ Ms – 1 (3.1.37)

Din cauza corespondenței bijective între xt și vt:

; 0 ≤ l, l’ ≤ Ms – 1 (3.1.38)

Fig. 3.1.11. Diagrama stărilor pentru codorul (2,1,2) RSC

Pentru codorul din figura 3.1.3 este 0.5 când există o conexiune între

St-1 = l’ și St = l , sau este 0 dacă nu avem conexiune între cele două stări. este de asemenea 0 sau 1.

De exemplu:

, ,

, . (3.1.39)

și

(3.1.40)

Pentru o secvență de intrare

c = (c1, c2,… cN)

procesul de codare începe la starea inițială S0 = 0 și produce o secvență de ieșire x1τ care se termină la stare finală Sτ = 0, unde τ = N + v. Intrarea în canal este x1τ și ieșirea este r1τ = (r1, r2, …rN).

Probabilitățile de tranziție într-un canal Gaussian sunt definite:

(3.1.41)

unde (3.1.42)

și (3.1.43)

(3.1.44)

unde σ2 este dispersia zgomotului

Fie ct bitul de informație asociat tranziției de la St-1 la St producînd la ieșire vt. Decodorul dă un estimat al intrării pe baza examinării secvenței recepționate rtτ. Algoritmul MAP furnizează raportul Λ(ct) pe baza secvenței recepționate r1τ după cum indică ecuația (3.1.34). Decodorul ia decizia prin compararea raportulul log-plauzibil cu un prag egal cu 0.

Se calculează cele două probabilități ale raportului:

(3.1.45)

unde este mulțimea de tranziții din starea St-1 în starea St cauzate de bitul de intrare ct = 0. De exemplu corespunzătoare figurii 3.1.4 este

= {(0,0), (3,1), (1,2), (2,3)}

(3.1.46)

unde este mulțimea de tranziții din starea St-1 în starea St cauzate de bitul de intrare ct = 1. De exemplu corespunzătoare figurii 3.1.11 este

= {(0,2), (2,1), (1,0), (3,3)}

Fig. 3.1.12. Diagrama trellis pentru codorul (2,1,2) RSC

Probabilitatea aposteriori a bitului ct poate proveni de la probabilitatea asociată, definită astfel:

, l’,l = 0, 1, …, Ms – 1

Ecuațiile (3.1.45) și (3.1.46) pot fi scrise:

(3.1.47)

(3.1.48)

Raportul de log-plauzibilitate devine:

(3.1.49)

Raportul reprezintă ieșirea soft a decodorului MAP. Acest raport poate fi folosit ca intrare în alt decodor dintr-o schemă concatenată, sau pentru următoarea iterație în cazul unui decodor iterativ. Operația finală constă în luarea deciziei hard, adică compararea raportului cu pragul 0.

3.1.7.1. Definirea probabilităților α, β și y

Pentru a calcula probabilitatea asociată cerută în calcularea raportului , relația (3.1.49), se definesc următoarele probabilități:

(3.1.50)

(3.1.51)

; i = 0, 1 (4.52)

Definind următoarele probabilități, se poate exprima probabilitatea asociată :

(3.1.53)

Raportul de log-plauzibilitate poate fi scris astfel:

(3.1.54)

3.1.7.2. Obținerea probabilității α

Probabilitatea α definită în relația (3.1.50) se poate exprima:

; pentru t = 1, 2, …τ. (3.1.55)

Pentru t = 0 avem de a face cu condițiile la limită α0(0) = 1 și α0(l) = 0 pentru l0.

3.1.7.3. Obținerea probabilității β

Probabilitatea β definită în relația (3.1.51) se poate exprima:

; pentru t = τ-1, …,1, 0. (3.1.56)

Condițiile la limită sunt βτ(0) = 1 și βτ(l) = 0 pentru l 0.

3.1.7.4. Obținerea probabilității y

Probabilitatea se poate defini:

Putem exprima astfel:

(3.1.57)

unde este probabilitatea apriori a ct = i și este ieșirea codorului asociată tranziției de la starea St-1 = l’ la starea St = l și ieșirea ct = i. Expresia R(rt|xt) este normată prin multiplicarea relației (3.1.42) cu .

3.1.7.5. Prezentarea algoritmului MAP

I Recursivitatea pozitivă

1. Se inițializează , l = 0, 1, …, MS – 1

și , pentru l 0

2. Pentru t = 1, 2, …τ, l = 0,1,…, MS – 1 și pentru toate ramurile i trellis-ul calculează

, pentru i= 0, 1 (3.1.58)

unde pt(i) este probabilitatea apriori a fiecărui bit de informație,

d2(rt, xt) este pătratul distanței Euclidiene dintre rt și simbolul modulat din trellis xt.

Pentru i = 0, 1 se reține

Pentru t = 1, 2,…,τ și l = 0, 1, …, MS – 1 se calculează și se reține :

(3.1.59)

Reprezentarea grafică a recursivității pozitive este dată în figura 4.13.

II Recursivitatea negativă

1. Se inițializează , l = 0, 1, …, MS – 1

și , pentru l 0

2. Pentru t = τ-1,…1, 0 și l = 0,1,…, MS – 1 se calculează

(3.1.60)

unde a fost calculat în recursivitatea pozitivă.

Pentru t < τ se calculează raportul de log-plauzibilitate :

(3.1.61)

Reprezentarea grafică a recursivității negative este prezentată în figura 3.1.14.

Deoarece ecuația (3.1.61) este un raport, valorile pentru și pot fi normate la oricare dintre nodurile pe care nu le-au depășit.

Fig. 3.1.13. Reprezentarea grafică a recursivității pozitive

Fig. 3.1.14. Reprezentarea grafică a recursivității negative

Algoritmul MAP poate fi aplicat numai dacă lungimea secvenței τ este finită, în timp ce algoritmul Viterbi poate fi folosit pentru secvențe de orice lungime, prin trunchierea supraviețuitorilor.

Este posibil să aplicăm decodarea MAP cu ferestre glisante ca la decodarea SOVA descrisă în subcapitolul 3.1.6 pentru a obține o economisire de memorie.

Algoritmul MAP are nevoie de MS × τ unități de memorie pentru a stoca rezultatele recursivității pozitive. Spațiul memoriei crește liniar cu lungimea secvenței τ. Dacă numărul de ramuri care intră și ies din fiecare nod este Nb = 2k, unde k este numărul biților de informație de la intrarea codorului, atunci pentru fiecare moment de timp sunt necesare MS × Nb înmulțiri și MS(Nb – 1) adunări atât pentru recursivitatea pozitivă, cât și pentru cea negativă. Complexitatea la un anumit moment de timp este constantă și independentă de lungimea secvenței τ. Metrica ramurei pentru algoritmul MAP este dată de ecuația (3.1.58).

Comparînd această expresie cu ecuația (3.1.22), putem observa că metrica ramurei pentru algoritmul MAP este mai greu de calculat decât cea pentru algoritmul Viterbi.

Merită menționat că metrica ramurei depinde de varianța zgomotului σ2 , în timp ce metrica ramurei pentru algoritmul Viterbi și SOVA nu depinde.

Dacă starea finală a diagramei trellis nu este cunoscută, atunci probabilitatea βτ(l) poate fi inițializată astfel:

, (3.1.62)

3.1.8. Algoritmul Max – Log – MAP

Decodarea MAP necesită memorie mare și un număr mare de operații care necesită volum mare de calcul cum ar fi exponențialele și înmulțirile. Algoritmul este considerat prea complex pentru implementarea sa în anumite sisteme de comunicații.

O cale în simplificarea complexității este lucrul cu logaritm din probabilitățile , și rezultatele fiind notate cu , și .

Probabilitatea este dată de relația:

(3.1.63)

Ținînd cont de ecuația (3.1.55) se poate exprima probabilitatea astfel:

(3.1.64)

în care condițiile inițiale sunt și pentru

Similar se definește și , ținînd seama de ecuația (3.1.56):

(3.1.65)

în care condițiile inițiale sunt și pentru

Prin înlocuirea valorilor prabilităților , și în ecuația (3.1.54) raportul se poate scrie:

(3.1.66)

Expresia poate fi simplificată prin folosirea următoarei aproximări:

(3.1.67)

unde poate fi calculat prin calcularea succesivă a (n-1) funcții maxime peste două valori.

Raportul de log-plauzibilitate poate fi aproximat prin:

(3.1.68)

Calcularea probabilităților și din ecuația (3.1.68) este echivalentă cu calcularea mericilor căilor din recursivitățile pozitive și negative în algoritmul Viterbi, unde metricile ramurilor sunt .

pentru și

pentru și

Operațiile care sunt implicate în calculul lui și sunt aceleași operații de adunare și comparare care apar din algoritmul Viterbi. Înmulțirile din algoritmul MAP sunt înlocuite de adunările din algoritmul Max-Log-MAP.

Pentru fiecare bit, algoritmul Max-Log-MAP calculează două tipuri de matrici Viterbi și o alege pe cea mai mare.

3.1.9. Algoritmul Log-MAP

Folosirea aproximației (4.67) a dus la simplificarea algoritmului MAP, dar algoritmul Max-Log-MAP nu este optim. Acest algoritm se poate înbunătăți prin folosirea algoritmuli Jacobian:

(3.1.69)

unde funcția fc este funcția de corelație.

Expresia poate fi calculată recursiv ca în ecuația (3.1.69) astfel:

(3.1.70)

Acestă procedură recursivă poate fi aplicată în calcularea raportului :

(3.1.71)

pentru n = 0, 1,…, MS – 1 și i = 0,1.

Performanțele algoritmului Log-MAP sunt identice cu cele ale algoritmul MAP. Totuși, prin calcularea funcției fc la fiecare pas se observă creșterea timpului în detrimentul complexității. Pentru a simplifica calculele, funcția fc este memorată într-o tabelă precalculată.

3.1.10. Comparații între algoritmii de decodare

În calcularea raportului de log-plauzibilitate pentru fiecare simbol, algoritmul MAP folosește toate căile din trellis. Aceste căi sunt divizate în două, una din căi se ocupă de bitul 1 la un anumit moment iar cealaltă de bitul 0. Raportul de plauzibilitate este calculat din aceste două căi.

Algoritmul Max-Log-MAP ia în cosiderare doar două căi pentru fiecare pas: cea mai bună cale cu bitul 0 și cea mai bună cale cu bitul 1 de la momentul t. Se calculează raportul de plauzibilitate pentru fiecare dintre căi și se returnează diferența dintre ele. De la nod la nod una dintre aceste căi se poate schimba, dar doar una dintre ele va fi calea de plauzibilitate maximă.

Și algoritmul SOVA ia în considerație doar două căi. Una este calea de plauzibilitate maximă, iar cealaltă este calea cea mai bună cu simbol complementar la momentul t. Astfel aceste căi sunt identice cu cele două căi luate în cosiderare de algoritmul Max-Log-MAP. [8]

Fie un cod convoluțional (n,k). Ordinul memoriei este v. În tabelul 3.1.1 sunt prezentate diferențele dintre complexitățile algoritmilor prezentați.

Se poate spune că algoritmul Log-MAP este de trei ori mai complex ca algoritmul SOVA și algoritmul Max-Log-MAP este cam de două ori mai complex ca SOVA.

Cum algoritmii MAP și Log-MAP sunt aproape identici, ca și algoritmii Max-Log-MAP și SOVA se vor studia diferențele între algoritmii SOVA și Log-MAP ținînd cont de probabilitatea de eroare BER.

Se observă în figura 3.1.15 o diferență între probabilitatea de eroare de bit a celor doi algoritmi de aproape 2∙10-2 . Această diferență se înregistrează la o valoare mică a raportului semnal zgomot și în cazul unei codări cu o mărime a întrețesătorului mică (N=10).

Pentru o lungime a întrețesătorului mai mare (N = 200) se poate vedea mai clar această diferență între algoritmul SOVA și algoritmul Log-MAP. Cu cât raportul semnal zgomot crește, cu atât se marește și diferența dintre probabilitățile de eroare de bit. La un raport semnal zgomot de aproximativ 2dB există o diferență între probabilitățile de eroare de bit de 10-1, după cum se poate vedea în figura 3.1.16.

În concluzie algoritmul SOVA este mai puțin performant ca algoritmul MAP, dar principalul său avantaj constă în faptul că este mai puțin complex, de aproximativ trei ori, ca algoritmul MAP.

Fig. 3.1.15. Comparație între algoritmii SOVA și Log-MAP, lungimea întrețesătorului N= 10, rata turbocodorul 1/3

Fig. 3.116. Comparație între algoritmii SOVA și Log-MAP, lungimea întrețesătorului N = 200, rata turbocodorul 1/3

3.2. DECODAREA ITERATIVǍ A TURBOCODURILOR

Turbocodurile pot fi decodate printr-o decodare MAP sau o decodare bazată pe plauzibilitate maximă, folosind diagrama trellis. Aceste decodoare se pot implementa doar pentru mărimi ale întrețesătorului mici; dacă mărimea acestuia crește decodoarele devin mult prea complexe. În acest capitol se vor prezenta niște algoritmi de decodare iterativă pentru turbocoduri. Acești algoritmi nu garantează performanțe optime la decodare. În funcție de numărul de iterații performanțele decodării converg către metodele optime de decodare MAP și plauzibilitate maximă. Se vor prezenta rezultate ale decodării iterative și se vor compara acestea cu performanțele limită. Datorită faptului că mărimea întrețesătorului afectează performanțele codorului este de preferat folosirea unui interleaver de mărime mare. Acest fapt duce la o complexitate mare a decodorului și astfel se impune utilizarea decodării iterative.

3.2.1. Decodarea optimă a turbocodurilor

Fie un codor format din două codoare convoluționale sistematice recursive de rată 1/2, astfel rata totală a codului este 1/3 (Fig. 3.2.1). Presupunem că secvența de intrare c este un vector binar ale cărui componente sunt independente și identic distribuite.

(3.2.1)

Secvențele recepționațe de la primul decodor sunt r0 și r1 și reprezintă intrarea în primul decodor:

(3.2.2)

La recepție există un dezîntrețesător care reface secvența întrețesută de la emisie . Împreună cu acesta, pentru intrarea în al doilea decodor există și secvența codată de la al doilea codor r2, împreună :

(3.2.3)

Algoritmul de decodare bazat pe secvențele recepționate r’ și r’’ calculează raportul de log-plauzibilitate :

(3.2.4)

Regula de decizie este:

(3.2.5)

Fig. 3.2.1. Turbocodor de rată 1/3

Dacă variabilele r’ și r’’ sunt necolerate:

(3.2.6)

Raportul de plauzibilitate devine:

(3.2.7)

Calcularea raportului cu ajutorul formulei (3.2.7) necesită evaluarea tuturor secvențelor transmise. Dacă se aplică algoritmul MAP prezentat în capitolul anterior, complexitatea decodorului va crește liniar cu numărul de stări a diagramei trellis, cât și cu lungimea secvenței de informație. Diagrama trellis a unui turbocod este variabilă în timp și are un număr de stări care crește exponențial cu mărimea întrețesătorului. Decodarea MAP este posibilă doar pentru întrețesătoare de lungime mică.

3.2.2. Decodarea iterativă a turbocodurilor bazată pe algoritmul MAP

Decodarea iterativă a turbocodului constă în două decodoare concatenate în serie printr-un întrețesător identic cu cel de la codor. Schema de principiu este prezentată în figura 3.2.2.

Primul decodor MAP primește ca date de intrare secvența de informație r0 și secvența de verificare a parității r1. Decodorul produce o ieșire soft care este întrețesută și apoi folosită pentru îmbunătățirea estimatului probabilităților apriori a informației pentru cel de al doilea decodor.

Celelalte două intrări în al doilea decodor sunt secvența de informație întrețesută și secvența de verificare a parității produsă de cel de-al doilea codor r2. Al doilea decodor MAP produce și el o ieșire soft care este folosită pentru îmbunătățirea probabilității de apriori a secvenței de informație de la intrarea primului decodor. Performanțele decodorului pot fi îmbunătățite prin această operație iterativă. Bucla de reacție negativă este trăsătura principală a acestui decodor, numele de turbo provenind de la pricipiul de funcționare al motorului turbo.

După un număr anumit de iterații ieșirea soft a ambelor decodoare MAP nu va mai îmbunătății vizibil performanțele. Atunci în ultimul stadiu de funcționare a decodorului se ia decizia hard după deîntrețesere.

Fig. 3.2.2. Decodare iterativă a turbocodării bazată pe algoritmul MAP

Pentru simplificarea schemei din figura 3.2.2 întârzierea datorată celor două decodoare este considerată minimă, nefiind astfel luată în seamă.

Să examinăm primul decodor MAP din prima iterație pentru un cod component de rată 1/n. Raportul de plauzibilitate pentru primul decodor MAP este:

(3.2.8)

unde notațiile și sunt probabilitățile apriori pentru 1 și 0 la intrarea în primul decodor, iar și sunt probabilitățile apriori de la intrarea în cel de al doilea decodor.

Pentru inițierea operației de decodare la primul decodor se presupune că probabilitățile apriori sunt:

(3.2.9)

Se scrie raportul :

unde n-1 este numărul de digiți de paritate ai codului bloc.

Cum codul este sistematic , i = 0, 1 sunt independenți de trellis și de starea l. și . Raportul poate fi descompus:

(3.2.10)

unde

(3.2.11)

se numește informația extrinsecă. Este o funcție a informației redundante introdusă de codor. Nu conține informația de intrare a decodorului . Această cantitate poate fi folosită pentru a îmbunătăți probabilitatea apriori estimată pentru faza următoare de decodare.

Urmărim intrarea în cel de-al doilea decodor MAP. Din moment ce intrarea în cel de-al doilea decodor include versiunea întrețesută a lui , semnalul de informație recepționat este corelat cu ieșirea soft întrețesută din primul decodor, . De aceea, contribuția datorită lui trebuie extrasă din , pentru a elimina această corelație.

nu conține și poate fi folosit ca probabilitate apriori pentru decodare în faza a doua. Informația extrinsecă întrețesută de la primul decodor este probabilitatea apriori estimată pentru al doilea decodor:

(3.2.12)

Din ecuația (3.2.12) și din relația

(3.2.13)

putem scrie pentru probabilitățile apriori în cel de-al doilea decodor

(3.2.14)

și

(3.2.15)

În faza a doua de decodare decodorul MAP estimează raportul de plauzibilitate . Similar ca în (3.2.10), raportul de plauzibilitate pentru cel de-al doilea decodor MAP poate fi descompus în

(3.2.16)

Prin înlocuirea probabilităților apriorii din ecuația (3.2.12) în ecuația (3.2.16) obținem:

(3.2.17)

este informația extrinsecă pentru cel de-al doilea decodor care depinde de informația redundantă furnizată de cel de-al doilea codor, ca în ecuația (3.2.11). Informația extrinsecă a celui de-al doilea decodor poate fi folosită ca estimat al probabilităților apriori pentru primul decodor ca în (3.2.12). Raportul de plauzibilitate pentru primul decodor poate fi scris ca

(3.2.18)

3.2.2.1. Rezumatul metodei de decodare iterative MAP:

1. Inițializăm .

2. Pentru iterațiile r = 1, 2, …, I, unde I este numărul total de iterații

– Calculăm și folosind ecuația (3.2.8).

– Calculăm :

(3.2.19)

-Calculăm :

(3.2.20)

3. După I iterații se ia decizie hard asupra lui bazîndu-ne pe .

3.2.3. Decodarea interativă SOVA a turbocodurilor

Fie un turbo codor ca cel din figura 3.2.1 ale căror componente sunt coduri convoluționale sistematice recursive, de rată 1/2. Schema bloc a decodorului iterativ SOVA este prezentat în figura 3.2.3.

Pentru decodarea turbocodurilor se pot utiliza în decodarea iterativă și decodoare bazate pe algoritmul SOVA.

Primul decodor SOVA generează ieșire soft și sintetizează informația extrinsecă ca la decodorul MAP. Informația extrinsecă este întrețesută și folosită de cel de al doilea decodor SOVA ca estimat al probabilității apriori. Al doilea decodor SOVA produce de asemenea informație extrinsecă și o trimite primul decodor pentru a trece la următorul pas al decodării.

Expresia pentru metrica căii pentru algoritmul SOVA este obținută prin maximizarea probabilității aposteriori .

(3.2.21)

sau prin maximizarea logaritmului expresiei:

(3.2.22)

(3.2.23)

unde notațiile sunt aceleași ca în capitolul precedent. Ținind cont de asta probabilitățile apriori trebuie să se schimbe în funcție de numărul de iterații dintr-o decodare iterativă. Maximizarea lui este echivalentă cu maximizarea expresiei:

(3.2.24)

Se definește metrica ramurei atribuită unei ramuri a trelis-ului la momentul t:

(3.2.25)

Similar se definește metrica căii pentru o cale x din trellis:

(3.2.26)

Decodorul SOVA selectează o cale cu metrica minimă. Un decodor SOVA din schema 3.2.3 calculează ieșirea soft astfel:

(3.2.27)

unde și sunt metricile căilor minime cu simbolurile 0 și respectiv 1 la momentul t, este calea de plauzibilitate maximă și calea competitoare cea mai bună. Acestea se pot calcula după următoarea procedură.

La momentul t estimatul de plauzibilitate maximă ct este obținut din calea de plauzibilitatea maximă calculată folosind algoritmul Viterbi astfel:

(3.2.28)

(3.2.29)

unde

(3.2.30)

și este dată de relația:

(3.2.31)

unde este al i-lea semnal codat modulat din trellis generat de intrarea ct.

Metrica căii celui mai bun competitor , unde , se poate calcula astfel:

(3.2.32)

unde l’,l = 0, 1, …,Ms-1, este metrica căii supraviețuitorului pozitiv la momentul t-1 și nodul l’, este metrica căii supraviețuitorului negativă la momentul t, MS este numărul de noduri din trellis și este metrica ramurei complementare de la nodul l’ la nodul l. se poate exprima:

(3.2.33)

unde este un număr pozitiv similar cu cel din ecuația (3.2.30), și este dată de relația:

(3.2.34)

unde este al i-lea semnal codat modulat din trellis generat de intrarea c.

Prin înlocuirea metricilor căiilor din ecuațiile (3.2.29) și (3.2.33), în ecuația (3.2.27) se poate calcula ieșirea soft a primuli decodor :

(3.2.35)

unde , , și reprezintă valorile , , și corespunzătoare primul decodor.

Prin înlocuirea și din ecuațiile (3.2.31) și respectiv (3.2.34) în ecuația (3.2.35) și ținînd seama de faptul că și se obține raportul :

(3.2.36)

unde este informația extrisecă a primului decodor dată de relația:

(3.2.37)

și și sunt probabilitățile apriori pentru biții 1, respectiv 0, la intrarea în primul decodor.

Informația extrinsecă întrețesută de la primul decodor îmbunătățește probabilitatea apriori la intrarea în al doilea decodor SOVA:

(3.2.38)

unde și sunt probabilitățile apriori pentru biții 1, respectiv 0, la intrarea în cel de al doilea decodor la momentul t.

Al doilea decodor calculează ieșirea soft care poate fi scrisă astfel: (3.2.39)

unde este informația extrinsecă de la al doile decodor:

(3.2.40)

unde și reprezintă valorile pentru cel de al doilea decodor , respectiv .

Înlocuind informația extrinsecă de la primul decodor, din ecuația (3.2.38) în ecuația (3.2.39) se obține :

(3.2.41)

Informația extrinsecă de la cel de al doilea decodor întrețesută, este folosită ca estimat al probabilității la intrarea în următoarea iterație.

(3.2.42)

Astfel încât raportul de plauzibilitate pentru noua iterație să poată fi scris:

(3.2.43)

3.2.3.1. Rezumatul metodei de decodare iterative SOVA:

1. Inițializăm .

2. Pentru iterațiile r = 1, 2, …, I, unde I este numărul total de iterații

– Calculăm și folosind ecuația (3.2.27).

– Calculăm :

(3.2.44)

– Calculăm :

(3.2.45)

3. După I iterații se ia decizie hard asupra lui bazîndu-ne pe .

CAPITOLUL 4

APLICAȚII ALE TURBOCODǍRII

4.1. Comunicațiile spațiale

Poate cea mai potrivită aplicație a turbocodurilor este comunicația spațială. Acest tip de comunicație este considerată cea mai potrivită datorită faptului că ideea turbocodării provine de la o codare pentru comunicațiile spațiale, codare concatenată, între un cod convoluțional și un cod Reed-Solomon și folosită la expedițiile spațiale Gallileo și Voyager. Principalul avantaj al turbocodării este acela că un întrețesător de lungime mare duce la un câștig de codare foarte convenabil, problemele de întârziere ce apar în acest caz sunt practic inexistente. Un alt avantaj al turbocodării este că se pot combina mai mult de două codoare in diferite moduri eficiente pentru a creea un cod cu rata totală mică și cu o creștere neînsemnată a coplexității.

Agenția Spațială Europeană (ESA – European Space Agency) a studiat posibilitatea folosirii turbocodurilor în misiuni spațiale cum ar fi Rosetta, Mars Express sau SMART-1.

4.1.1. CCSDS

Un nou standard a Comitetului Consultativ pentru Sisteme de transmisiuni de Date Spațiale (CCSDS – Consultative Committee for Space Data Systems) a realizat o recomandare privind sisteme de codare a canalului spațiale. Conceptul de codare a canalului descris în această recomandare reprezintă baza comunicațiilor între o navă spațială și Pământ. El permite dezvoltarea unor standarde compatibile atât pentru sistemele de zbor cât și pentru sistemele de sol.

Codurile recomandate de CCSDS include turbocoduri, bazate pe codorul elementar din figura 4.1. Acest codor poate selecta una din ratele 1/2, 1/3, 1/4 sau 1/6 obținute prin puncturarea ieșirii de paritate. Turbocodul poate folosi un întrețesător de lungime mare, de la 1.784 biți până la 16.384 biți. Acest standard depașește cu 1.5 dB până la 2.8 dB anteriorul standard al CCSDS bazat pe concatenarea unui cod convoluțional cu rata 1/2 și un cod Reed-Solomon (225,223). Cadru este format din 48 biți ca header, biții de date și 16 biți de verificare a parității adăugați de un codor CRC.

Fig. 6.1. Codorul elementar pentru turbocodul propus de CCSDS

4.1.2. DSN

Transponderul pentru comunicații spațiale de nouă generație proiectat de NASA suportă turbocoduri. Implementarea turbocodoarelor în Rețelele de Comunicații Spațiale (DSN – Deep Space Network) se va face în anul 2003. Această nouă dezvoltare a comunicațiilor face parte dintr-un plan ce are ca punct terminus anul 2010 și vizează îmbunătățiri substanțiale în domeniul RF (Radio Frequency).

4.2. UMTS

Avantajul turbocodurilor față de codurile convoluționale în accesul multiplu cu diviziune în cod (CDMA) și în sistemele radio mobile GSM/DCS-1800 a fost definitiv demonstrat la un an după inventarea codurilor turbo.

Recent, recomandările tehnice pentru Universal Mobile Telecommunications System (UMTS) realizate de Third Generation Partnership Project (3GPP) propun includerea turbocodurilor printre tehnicile de codarea canalului. IMT-2000 este un reprezentant al sistemelor de comunicații mobile de generația a treia. Acest sistem vizează o rată de bit foarte mare necesară comunicațiile radio multimedia. El furnizează prin comutație de circuit și de pachete servicii cum ar fi trafic IP și imagini video real-time cu calitate a vocii foarte bună. Conceptul de Virtual Home Environment va permite utilizatorilor să mențină conexiunea cu datele de la birou sau de acasă oriunde ar fi acest utilizator în lume.

Turbocodorul constă în două codoare convoluționale recursive sistematice de rată 1/2 și 8 stări definite de matricea generatoare (1, n(D)/d(D)), unde n(D)=1+D+D2 și d(D)=1+D2+D3 . Aceste codoare se termină cu 3 biți finali pentru a impune o terminație trellis. Lungimea întrețesătorului N poate fi între 40 și 5114.

4.3. Inmarsat

Serviciu multimedia Inmarsat este un nou serviciu bazat pe turbocoduri și pe modulația 16QAM care permite utilizatorilor să comunice cu sistemul de sateliți Inmarsat-3 de la un terminal mobil cum este un calculator mobil la o rată de transfer de 64 kbiți/s. Tehnologia de bandă îngustă (Narrow Tehnology) bazată pe 16QAM și turbocoduri furnizează o reducere a benzii cu aproape 50% din banda cerută de sistemele de comunicații prin satelit, dar și o reducere a puterii terminalului pentru o astfel de comunicație.

Simulările și măsurătorile hard au arătat că datorită folosirii turbocodurilor și modulației 16QAM printr-o minimă amplificare a puterii terminalului mobil se pot obține rezultate optime. O importanță deosebită o are câștigul de codare de aproape 0.5 dB care poate fi obținut prin maparea biților de informație în pozițiile cele mai protejate ale simbolului 16QAM.

Codorul se poate implementa pe orice placă DSP și poate folosi un decodor bazat pe algoritmul MAP cu viteza de decodare de 800ns/bit ceea ce corespunde unei rate de date de 1.25 Mbiți/s.

4.4. DVB

Noul stadard european Digital Video Broadcasting (DVB) a adoptat de asemenea turbocodurile pentru legăturile downlink. Acest standard permite mai multor utilizatori să trimită semnale unei centrale poartă în timp ce primesc data IP prin legătura downlink. Utilizatorii trimit pachete mici folosind accesul multiplu cu diviziune în timp (TDMA) pentru a cere o legătură. După ce legătura este realizată este posibil transferul de date.

Turbocodul folosit în DVB permite transmisii de date la rate de la 144 kbiți/s până la 2 Mbiți/s și folosește codoare convoluționale sistematice recursive circulare (CRSC – Circular Recursive Systematic Convolutional code). Ratele codului pot fi selectate dintre 1/3, 2/5, 1/2, 2/3, 3/4, 4/5 și 6/7. Shema unui astfel de turbocod este prezentată în figura 4.2.

Fig. 4.2. Codor CRSC

Cel mai semnificativ bit este atribuit lui A, următorul bit lui B și așa mai departe. Intrarea în codor este un bloc de k biți organizat în N cupluri, N este un multiplu al lui 4. Primul stagiul al codării este când datele intră în codor în ordinea naturală după ce codorul a fost inițializat de starea circulară S2. Acest prim pas este urmat de intrarea in codor a datelor permutate care este inițializat de starea circulară S2.

Stările circulare S1 și S2 se obțin prin folosirea tabelului 4.1, funcției de N și ultima stare a codorului, SN-1, după un proces complet de codare prin prelucrarea datelor în mod normal și întrețesute care începe din starea 0.

Tabelul 4.1

Întrețeserea π(j), j = 0, …N-1 este făcută pe două nivele:

un prim nivel: dacă j mod 2 = 0 se inversează cuplul.

al doilea nivel, între cupluri: i = P0*j + P + 1mod N (unde P este definit astfel: dacă j mod 4 = 0 atunci P = 0

dacă j mod 4 = 1 atunci P = N/2 +P1

dacă j mod 4 = 2 atunci P = P2

dacă j mod 4 = 3 atunci P = N/2 +P3)

Parametrii P0, P1, P2 și P3 folosiți la întrețesere variază în funcție de N. Variația parametrilor în funcție de N este prezentată în tabelul 4.2

Tabel 4.2

Există mai multe căi de a realiza puncturarea secvențelor de verificare a parității în vederea obținerii ratelor din standard 1/3, 2/5, 1/2, 2/3, 3/4, 4/5 și 6/7. Puncturarea în vederea obținerii acestor rate este prezentate în tabelul 4.3.

Tabel 4.3

Există două de moduri de transmitere a datelor :

în ordine normală sunt transmise primele cuplurile (A, B), urmate de cuplurile (Y1, Y2) și apoi de cuplurile (W1, W2)

în ordine inversă sunt transmise primele cuplurile (Y1, Y2), urmate de cuplurile (W1, W2) și apoi de cuplurile (A, B)

CAPITOLUL 5

CONCLUZII

In aceasta lucrare am gasit structura de interleaver care da cele mai bune performante. Întretesatoarele aleatoare au fost gasite ca fiind cele mai bune.

Marimea si structura interleaverului afecteaza performanta codarii.

Am descoperit ca la valori mici ale RSZ marimea interleverului poate fi crescuta pentru a obtine performante mai bune. Marimea interleverului poate fi aleasa in functie de calitatea serviciului.

Prezența întrețesătorului în componența unui turbocod îl face pe acesta să se comporte ca un cod bloc. Astfel cu cât mărimea întrețesătorului este mai mare cu atât performanțele turbocodului cresc.

S-a simulat un codor cu lungimea întrețesătorului de N = 200 și s-a folosit algoritmul de decodare MAP. Performanțele celor trei codoare sunt aproape aceleași în cazul în care decodarea se bazează pe algoritmul MAP. La raport semnal zgomot mic (<1dB) diferențele dintre cele trei codoare devin vizibile; codorul cu circuit de întrețesere de tip elicoidal avînd performanțe mai bune ca celelalte codoare cu întrețesătoare de tip bloc sau par-impar

S-a simulat un codor cu lungimea întrețesătorului de N =128 și s-a folosit algoritmul de decodare MAP. Se observa superioritatea unui algoritm de tip aleator. Insa avand in vedere ca structura interleaverului trebuie stiuta la receptie folosirea unui proces aleator presupune un efort de calcul suplimentar si implicit un delay in procesul de transmisie.

Pe viitor vor putea fi concepute structuri mai eficiente de interleavere tinând cont de structura codului. Se vor putea atinge rezultate mai bune cu un interlever adaptat in functie de tipul de date transmise.

Datorită teoremei lui Shannon, cercetările găsirii unui tip de cod care să se apropie cât mai mult de limita Shannon au continuat culminînd cu dezvoltarea codării turbo. Deoarece codurile turbo lucrează cel mai aproape de limita lui Shannon, față de alte coduri, se poate spune că acest tip de codare este cea mai eficientă tehnică de codare a canalului.

Un turbocodor este construit prin interconectarea a două coduri convoluționale sistematice recursive cu ajutorul unui circuit de întrețesere.

Performanțele turbocodurilor sunt influențate de proprietățile circuitului de întrețesere și de ordinul memoriei codoarelor componente.

Unicitatea codurilor turbo conta in faptul ca nu necesita o reducere a ratei datelor si nici o extensie a largimii de banda ca in cazul altor scheme de codare.

Decodarea unui turbocod se face iterativ folosind două decodoare interconectate prin același întrețesător de la codare. Decodoarele componente sunt decodoare a codurilor convoluționale componente.

Decodoarele componente pot fi de mai multe feluri.

O primă metodă de decodare poate fi algoritmul Viterbi. Acest algoritm minimizează probabilitatea de eroare a secvenței de date. Ieșirea sa este o estimare hard a simbolurilor transmise care au probabilitatea cea mai mare de a face parte din secvența de cod. În sistemele concatenate, în care procesarea semnalului are mai multe stagii, performanțele totale la recepție sunt îmbunătățite dacă codorul interior produce o estimare soft la ieșire. Astfel acest algoritm este modificat astfel încât să avem o ieșire soft.

O a doua metodă de decodare este algoritmul Vitrebi cu ieșire soft (SOVA – soft output Viterbi algorithm). Algoritmul SOVA produce un estimat pentru fiecare simbol recepționat. Această estimare se face pe baza criteriului maximei plauzibilități.

O altă clasă de decodoare se bazează pe criteriul de minimizare a probabilității de eroare de bit. Decodorul genereză estimate sub forma unor probabilități aposteriori de simbol. Algoritmul este cunoscut ca decodarea cu probabilitate aposteriori maximă (MAP – maximum a posteriori probability).

Pentru simplificarea acestor algoritmi există și două versiuni ale acestora care au o complexitate mai mică. Aceste versiuni se numesc Max-Log-MAP, respectiv Log-MAP.

Algoritmul MAP duce la performanțe mai bune decât în cazul algoritmului SOVA. Diferența între performanțe nu este hotărâtoare în alegerea algoritmului de decodare, deoarece algoritmul MAP, deși duce la performanțe mai bune, este de aproximativ trei ori mai complex ca algoritmul SOVA.

Fig. 5.1. Comparație între algoritmii SOVA și MAP

Performanțele turbocodului sunt influențate de numărul de iterații pe care le realizează decodorul. Mărimea numărului de iterații duce la îmbunătățirea performanțelor de decodare până la un anumit punct. Peste un anumit număr de iterații performanțele nu mai se îmbunătățesc, facînd astfel inutilă mărirea numărului acestora. Acest prag depinde de mărimea întrețesătorului, cu cât lungimea întrețesătorului este mai mare cu atât numărul iterațiilor trebuie mărit. Pentru o simulare care să demonstreze acestă afirmație s-a folosit un codor de rată 1/3, cu mărimea întrețesătorului de N = 200 și algoritm de decodare SOVA.

Fig. 5.2. Performanța unui turbocodor de rată 1/3 cu 4 stări în funcție de numărul de iterații corespunzător decodării

Se poate observa că peste h = 5 (h – numărul de iterații) performanțele codorului rămân aproape neschimbate.

Principalii parametrii care influențează performanțele turbocodului sunt cei legați de circuitul de întrețesere, lungimea și felul acestuia, și respectiv ordinul memoriei codoarelor componente.

Cu cât lungimea lungimea întrețesătorului este mai mare cu atât și performanțele codării turbo se îmbunătățesc.

Principalele funcții ale circuitului de întrețesere sunt decorelarea secvențelor la intrarea în cele două decodoare și respectiv amestecarea secvenței de intrare în vederea evitării erorilor în bloc ce pot apărea pe canal. Astfel există mai multe feluri de circuite de întrețesere fiecare cu avantajele și dezavantajele lor. Întrețesătorul care s-a impus este cel de tip aleator.

Celălalt parametru care influențează performanța turbocodorului este ordinul memoriei codoarelor componente.

Fig. 5.3. Performanța BER pentru diferite ordine de mărime a memoriei

Cu cât ordinul memoriei este mai mare cu atât cresc și performanțele corespunzătoare probabilității de eroare de bit. Acest parametru nu poate fi modificat la infinit deorece crește complexitatea schemei.

Un turbocod este net favorabil din punct de vedere al performanțelor unui cod convoluțional, după cum se poate vedea în figura 5.4. Acest lucru este evident din cauza ratelor pe care le au cele două codoare 1/2 codorul convoluțional, respectiv 1/3 turbocodorul. Aici apare și principalul dezavantaj al codării turbo: o rata prea mare.

Metoda de a reduce rata unui turbocod se numește puncturare. Acesta permite transmiterea selectivă a biților de verificare a parității după o regulă prestabilită. Astfel rata 1/3 a unui turbocod poate fi redusă prin operația de puncturare la 1/2.

Pentru a demonstra superioritatea turbocodării față de codul convoluținal se vor compara două astfel de codoare având aceeași rată, figura 5.5.

Fig. 5.4. Performanțele probabilității de eroare de bit pentru un codor convoluțional, respectiv un turbocodor

Fig. 5.5. Performanțele probabilității de eroare de bit pentru un codor convoluțional, respectiv un turbocodor puncturat

Codurile turbo puncturate au performanțe mai slabe decât ale celor nepuncturate. Principalul lor avantaj constă în micșorarea ratei de transmisie.

Fig. 5.6. Performanțele probabilității de eroare de bit ale unui turbocod puncturat (rata 1/2), respectiv nepuncturat (rata 1/3) .

Faptul că turbocodarea este cea mai eficientă tehnică de codare a canalului, a dus la aplicarea acesteia într-o mulțime de aplicații cum ar fi: Comunicațiile spațiale, UMTS, Serviciu multimedia Inmarsat, Digital Video Broadcasting (DVB).

Latenta este punctul slab al turbo codurilor, care au nevoie de calcule repetale la receptie. Acesta este si motivul pentru care un cod simplu convolutional a fost preferat in transmisiunile de voce 3G. Din nefericire ca si in cazul codurilor bloc, decodorul trebuie sa astepte receptia unei intregi secvente pentru a-as incepe procesul iar aceasta este o limitare care cu greu va putea fi depasita.

Bibliografie

1. C. Berrou, A. Glavieux, P. Thitimajshima, „Near Shannon Limit Error –Correcting

Coding and Decoding: Turbo –Codes”, Proc. of ICC, Geneve, may 1993, pp.1064-1070

2. M.Öberg, P.H.Siegel, “The Effect of Puncturing in Turbo Encoders”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 184-187.

3. Consultative Committee for Space Data Systems “Telemetry Channel Coding”, Blue

Book, CCSDS 101.0-B-6, Oct 2002.

4. M. Jézéquel, C. Berrou, C. Douillard, „Turbo codes (convolutifs)”, seminar, Timisoara, Romania, 15-18 March, 2004, http://hermes.etc.utt.ro/cercetare/carti.html.

5. H. Balta, M. Kovaci – “The BER Performances of Convolutional Codes used in Turbo Codes”, Scientific Bulletin of the “Politehnica” University of Timișoara, România, Oct 2004, pp. 38 –43.

6. F.Daneshgaran, M.Mondin, “Design of Interleavers for Turbo Codes: Iterative Interleavers Growth Algorithms of Polynomial Complexity”, IEEE Transactions on Information Theory, vol.45 pp.1845-11859, September 1999.

7. Gérard Battail, “A conceptual framework for understanding turbo-codes”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 55-62.

8. P.Robertson, E.Villebrun, P.Hoeher, „A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain”, Proceedings of the International Conference on Communications, , pag. 1009-1013, iunie 1995

Bibliografie

1. C. Berrou, A. Glavieux, P. Thitimajshima, „Near Shannon Limit Error –Correcting

Coding and Decoding: Turbo –Codes”, Proc. of ICC, Geneve, may 1993, pp.1064-1070

2. M.Öberg, P.H.Siegel, “The Effect of Puncturing in Turbo Encoders”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 184-187.

3. Consultative Committee for Space Data Systems “Telemetry Channel Coding”, Blue

Book, CCSDS 101.0-B-6, Oct 2002.

4. M. Jézéquel, C. Berrou, C. Douillard, „Turbo codes (convolutifs)”, seminar, Timisoara, Romania, 15-18 March, 2004, http://hermes.etc.utt.ro/cercetare/carti.html.

5. H. Balta, M. Kovaci – “The BER Performances of Convolutional Codes used in Turbo Codes”, Scientific Bulletin of the “Politehnica” , România, Oct 2004, pp. 38 –43.

6. F.Daneshgaran, M.Mondin, “Design of Interleavers for Turbo Codes: Iterative Interleavers Growth Algorithms of Polynomial Complexity”, IEEE Transactions on Information Theory, vol.45 pp.1845-11859, September 1999.

7. Gérard Battail, “A conceptual framework for understanding turbo-codes”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 55-62.

8. P.Robertson, E.Villebrun, P.Hoeher, „A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain”, Proceedings of the International Conference on Communications, , pag. 1009-1013, iunie 1995