turbocoduri - uptshannon.etc.upt.ro/docs/cercetare//teze_doctorat/tcoduri.pdfÎn celebra sa lucrare...

Turbocoduri

Referat nr.3

Conducător ştiinţific: Prof. dr. ing. Miranda Naforniţă Doctorand: as.ing. Horia Balta

Turbo-coduri Referat nr.3 Horia Balta

Cuprins

1. Introducere 1.1 Scurt istoric asupra codării canalului I.1 2.2 Principiul „turbo” I.4 3.3 Turbodecodorul I.5 4.4 Configuraţii de turbocoduri I.7 5.5 Limite teoretice I.9

2. Turbocoduri convoluţionale

1.1 Algoritmi utilizaţi în decodoarele componente II.1 1.1.1 Logaritmul raportului de plauzibilitate II.2 2.1.2 Algoritmul MAP II.4 3.1.3 Algoritmul Max-Log-MAP II.12 4.1.4 Algoritmul Log-MAP II.14 5.1.5 Algoritmul SOVA cu secvenţă memorată („up-date”) II.15 6.1.6 Algoritmul SOVA bidirecţional II.19 7.1.7 Informaţia extrinsecă II.19

2.2 Întreţeserea II.23 1.2.1 Dispozitiv de întreţesere aleator II.23 2.2.2 Dispozitiv de întreţesere bloc II.25 3.2.3 Dispozitiv de întreţesere diagonal II.25 4.2.4 Dispozitiv de întreţesere pseudo-aleator de distanţă 8 II.26 5.2.5 Dispozitiv de întreţesere de tip „S” (S-interleaver) II.27

2.3 Puncturarea II.27 2.4 Decodarea optimală a turbocodurilor. Super-trellisul II.28 2.5 Performanţe. Concluzii II.30

3. Turbocoduri bloc 1.1 Trellisul codurilor bloc III.1 2.2 Decodarea „soft” a codurilor bloc III.4 3.3 Turbocoduri bloc III.6

4. Interfaţă grafică în MATLAB pentru simularea funcţionării turbocodurilor convoluţionale

1.1 Prezentare generală IV.1 2.2 Posibilităţile interfeţei IV.4 3.3 Instrucţiuni de utilizare a interfeţei IV.6 4.4 Indicaţii-propuneri pentru dezvoltarea altor programe utilizând

funcţiile-subrutină aferente interfeţei IV.7


Anexa A Lista programelor MATLAB Anexa B Programe pentru construcţiei interfeţei grafice

„tccGUI.m” B.1 „textcc.m” B.5 „trastrls.m” B.7 „schimbrb.m” B.7 „afcodor.m” B.8 „afdpLLR.m” B.8 „afdpsr.m” B.9 „afschPSH.m” B.9 „coment.m” B.10 „polgen.m” B.11

Anexa C Program ce execută codare convoluţională

„CodorConv.m” C.1 Anexa D Programe ce servesc decodării „dbSOVA.m” D.1 „decLogMAP.m” D.2 „LogSumExp.m” D.3 „decMAP.m” D.3 „decMLMAP.m” D.4 „duSOVA.m” D.4 Anexa E Programe pentru întreţesere „ilvA.m” E.1

„ilvD.m” E.1 „ilvP.m” E.1 „ilvR.m” E.2 „ilvS.m” E.2

Anexa F Programe utilitare „cuant.m” F.1 „matnatMN.m” F.1 „octbin.m” F.1 „sum2.m” F.1 „trellis.m” F.2 „zecbin.m” F.2 Anexa G Program exemplu de simulare a unui turbocod „exemplu.m” G.1 Bibliografie Planşe


I.1

1. Introducere

1.1 Scurt istoric asupra codării canalului

Codarea canalului sau codarea FEC (Forward Error Correction) are scopul de a proteja informaţia transmisă în sistemele de comunicaţie digitale. În celebra sa lucrare din 1948 „A mathematical theory of communication”, [SHA], Shannon a demonstrat că o comunicaţie sigură este posibilă printr-un canal oricât de zgomotos dacă e îndeplinită condiţia ca rata de transmisie să fie mai mică decât capacitatea canalului. Shannon considera că o comunicaţie sigură va fi realizabilă cu ajutorul codării canalului prin adăugarea de informaţie redundantă mesajelor transmise. Totuşi, Shannon nu a propus soluţii explicite de codare a canalului pentru implementări practice. În plus, cu toate că redundanţa adăugată face să crească întârzierea secvenţei transmise, el nu a specificat întârzierea maximă ce poate fi tolerată pentru a fi posibilă comunicarea în apropierea limitei lui Shannon [HLY].

Din rezultatul teoremei lui Shannon a codării canalului zgomotos, este clar că se poate alege un cod cu o lungime foarte mare a blocului de date pentru a se obţine o performanţă foarte bună. Din păcate complexitatea decodării creşte exponenţial cu lungimea blocului. Astfel, vreme de 50 de ani cercetătorii au creat coduri limitate ca performanţă de complexitatea decodării şi de complexitatea canalului.

Unul dintre primele coduri corectoare de erori implementate practic a fost codul Hamming corector de o eroare, cod bloc propus în 1950. Codurile convoluţionale corectoare de erori datează din 1955, când au fost descoperite de P. Elias.

Mai târziu, Wozencraft şi Reiffen ca şi Fano şi Massey au propus diverşi algoritmi pentru decodarea lor. Prima aplicaţie practică a codurilor convoluţionale a fost propusă de Heller şi Jacobs în anii ’70.

Un moment important în istoria codurilor convoluţionale îl reprezintă descoperirea algoritmului de estimare a secvenţei de probabilitate maximă de către Viterbi în 1967. Un algoritm de decodare cu rata de eroare pe bit minimă a fost propus în 1974 de Bahl, Cocke, Jelinek şi Raviv, şi a fost numit algoritmul „maximum aposteriori”-MAP. Algoritmul MAP, datorită complexităţii sale ridicate, a fost foarte rar folosit în practică până la descoperirea, în 1993, a turbocodurilor de către Berrou, Glavieux şi Thitimajshima [BGT]. Revenind la codurile bloc, codul Hamming corector de o eroare a avut performanţe prea scăzute pentru aplicaţii practice. În practică un moment important îl reprezintă descoperirea familiei de coduri bloc binare corectoare de erori multiple cunoscute sub numele de BCH (Bose-Chaudhuri-Hocquenghem) în 1959. În 1970 Peterson a arătat că aceste coduri prezintă o structură ciclică, adică toate versiunile permutate ciclic ale unui cuvânt de cod sunt de asemenea cuvinte de cod.

Prima metodă de construire a trellis-urilor pentru coduri bloc liniare a fost propusă de Wolf în 1978. Având o complexitate crescută a fost o cercetare limitată doar la decodarea trellis a codurilor bloc liniare.

În 1988 Forney a arătat că unele coduri bloc au structuri trellis relativ simple [FOR]. Motivaţi de această descoperire, Honary, Markarian şi Farrel au propus diverse metode pentru


I.2

reducerea complexităţii asociate. Algoritmul Chase este una dintre cele mai cunoscute tehnici propuse pentru decodarea codurilor bloc.

În 1961 Gorenstein şi Zierler au extins teoria codării binare pentru a putea fi tratate şi codurile non-binare, unde simbolurile de cod sunt formate dintr-un număr de biţi. Ei au descoperit de asemenea o combinaţie de algoritmi, algoritmul Peterson-Gorenstein-Zierler (PGZ).

În 1960 o subcategorie foarte importantă de coduri BCH non-binare a fost descoperită de Reed şi Solomon –numite coduri Reed-Solomon după numele inventatorilor lor. Aceste coduri au proprietăţi optime, cuvintele de cod au distanţa minimă cea mai mare posibilă pentru o rată de cod dată. Aceasta nu garantează, oricum, obţinerea ratei erorii pe bit cea mai mică posibil. La decodarea codurilor RS binare poate fi folosit şi decodorul PGZ.

Algoritmi de decodare puternici pentru codurile RS au fost găsiţi de Berlekamp şi Massey. În ultimii ani codurile RS şi-au găsit aplicaţii practice la realizarea CD-playerelor şi în transmisia video digitală – “Digital Video Broadcasting” standardizată de ETSI sub denumirea DVB. Inspirată de vechea teorie a Sistemului numerelor reziduale (Residue Number System), sistem avantajos pentru operaţii aritmetice rapide, în 1967 a fost introdusă o nouă clasă de coduri non-binare. Şi anume Sistemul numerelor reziduale redundante (Redundant RNS). Un cod RRNS este un cod bloc ce maximizează distanţa minimă şi prezintă proprietăţi de distanţă similare cu codurile RS. Watson şi Hastings precum şi Krishna ş.a. au exploatat proprietăţile RRNS pentru detecţia şi corectarea unei singure erori şi de asemenea pentru detecţia de erori multiple.

La începutul anilor ’70 codurile corectoare de erori au fost implementate în diferite sisteme de comunicaţii prin satelit sau în spaţiu şi în anii ’80 în sistemele radio mobile celulare. Totuşi, pentru o lungă perioadă de timp codurile corectoare de erori şi modulaţia au fost tratate ca subiecte diferite în sistemele de comunicaţii. Prin integrarea acestor coduri şi a modulaţiei în 1987 Ungerboeck a propus modulaţia codată trellis (Trellis Coded Modulation), cu care se pot obţine câştiguri de codare semnificative într-un mediu de transmisie de putere şi bandă limitată. Un moment istoric de maximă importanţă îl constituie inventarea turbocodurilor de către Berrou, Glavieux şi Thitimajshima [BGT] care a facilitat operarea sistemelor de comunicaţii aproape de limita Shannon. De la recenta lor descoperire turbocodurile au evoluat într-un ritm fără precedent şi s-au consacrat în doar câţiva ani datorită eforturilor intense ale oamenilor de ştiinţă. Ca rezultat al acestei evoluţii foarte rapide, turbocodurile au fost deja introduse în sisteme standardizate ca de exemplu a III-a generaţie a sistemelor radio mobile (3G). De asemenea, performanţe impresionante s-au obţinut cu turbocodurile şi în sistemele de transmisie video. Mai precis, în schema propusă de Berrou şi colaboratorii săi s-a folosit concatenarea paralelă a două coduri convoluţionale sistematice recursive, plasând un dispozitiv de întreţesere între cele două codoare. La decodor s-a introdus o structură iterativă ce foloseşte o versiune modificată a algoritmului MAP clasic minim inventat de Bahl ş.a. pentru a decoda aceste coduri paralele concatenate. Începând cu 1993 s-au depus eforturi mari în vederea reducerii complexităţii decodorului asociat. Un algoritm de decodare de complexitate redusă este, de exemplu, algoritmul Maximum-Logarithm-MAP propus de Koch şi Bayer sau algoritmul Logarithm-MAP sugerat de Robertson, Willbrun şi Hocher [RVH]. Performanţele excelente ale turbocodurilor au fost repede remarcate şi datorită eforturilor lui Benedetto şi Montorsi sau Perez, Geghers şi Costello care au publicat lucrări în acest domeniu.


I.3

Figura 1.1 Evoluţia cercetării în domeniul codării canalului în ultimii 50 de ani, de la legendara decoperire a lui Shannon până în zilele noastre.

La mijlocul anilor ’90 Hagenauer, Offer şi Papke [HOP] au extins conceptul la coduri bloc concatenate paralel. Nickl, Hagenauer şi Burkett au arătat că limita Shannon poate fi atinsă în cadrul unui raport semnal/zgomot de 0,27 dB folosind un turbocod Hamming simplu,

Coduri bloc Limita Shannon (1948) Coduri convoluţionale Codul Hamming 1950

1955 Elias, Codurile convoluţionale Codurile BCH Codurile Reed-Solomon 1960 Algoritmul PGZ Algoritmul Berlekamp-Massey 1965 Codurile RRNS Algoritmul Viterbi 1970 Algoritmul Chase Bahl, Algoritmul MAP 1975 Wolf, Coduri bloc Trellis 1980 1985 Ungerboeck, TCM Hagenauer, SOVA 1990 Koch, Algoritmul Max-Log-MAP Pyndiah, Algoritmul SISO Chase Berrou, Turbocodurile

Hagenauer, Turbocoduri BCH Robertson, Algoritmul Log-MAP Nickl, Turbocoduri Hamming

Alamouti, Codul bloc spaţiu-timp Robertson , TTCM Tarokh, Coduri Trellis spaţiu-timp 2000 Acikel, Turbocoduri puncturate


I.4

iar Jung şi Narshan au studiat performanţele turbocodurilor în funcţie de constrângerea reprezentată de lungimea scurtă a cadrelor de transmisie, caracteristică sistemelor audio. În 1998 Alamouti a inventat un cod bloc spaţiu-timp care oferă o complexitate scăzută cu preţul unei degradări neînsemnate a performanţei. Această invenţie i-a motivat pe Tarokh ş.a. să generalizeze schema la un număr arbitrar de antene de emisie. Apoi cercetările asupra codurilor spaţiu-timp s-au extins de la canalele de bandă îngustă la canalele dispersive. Acikel şi Ryan au propus în 1999 o procedură eficientă pentru proiectarea unor structuri de puncturare pentru turbo-codurile convoluţionale de rată mare.

1.2 Principiul „turbo” Denumirea de „turbocod”, dată de inventatorii săi [BGT], provine din faptul că ideea de bază a unui turbodecodor este aceeaşi cu cea după care funcţionează un motor termodinamic supraalimentat prin turbină (motorul turbo). În acest paragraf este prezentat succint principiul motorului turbo, ilustrat în Figura 1.2, [BRW]. Pistonul 2, aflat în timpul IV (Evacuare) al ciclului termodinamic, elimină gazele arse prin supapa de evacuare, galeria de evacuare spre eşapament. Pistonul 1, aflat în timpul I (Admisie) al ciclului termodonamic absoarbe aer1 din galeria de admisie. Volumul de aer înmagazinat în piston va influenţa în mod direct compresia, adică forţa cu care va fi apăsat pistonul în timpul III (Ardere). Rolul turbinei ataşată motorului este de a favoriza admisia unui volum de aer mai mare în piston, pe seama energiei gazelor evacuate. Astfel: gazele evacuate de pistonul 2, în drumul lor dinspre galeria de evacuare spre eşapament, antrenează turbina prin elicea ei din stânga, forţând-o să se invârtă la turaţii foarte mari. La rândul ei, turbina, prin elicea ei din dreapta, antrenează aerul în galeria de admisie, jucând rolul unei pompe de aer. Din galerie, aerul comprimat este forţat să intre în pistonul 1. Admisie Evacuare Compresie Ardere

Figura 1.2 Ilustrarea principiului „turbo” 1 aer (în cazul motoarelor cu aprindere prin compresie, ex: motorul diesel) sau amestec de aer cu vapori de benzină (în cazul motoarelor cu aprindere prin scânteie). În acest ultim caz amestecul provine din carburator.


I.5

În concluzie, dacă în lipsa turbinei, pistonul (în timpul său de admisie) îşi „trage” aer prin depresiunea creată de el, în prezenţa turbinei admisia este mult amplificată de „pompa de aer” pe care o reprezintă turbina. Acest fapt conduce la o amplificare remarcabilă a puterii motorului turbo1 datorită reutilizării energiei gazelor arse. La rândul său, pistonul 1, în timpul său IV, va antrena turbina, beneficiar fiind pistonul aflat în timpul de admisie (3 în acest cazul motorului din Figura 1.2). Asupra celor prezentate sunt demne de remarcat două observaţii: 1) motorul supra-alimentat prin turbină poate fi asimilat cu un sistem cu reacţie pozitivă; reacţia este constituită de transferul energiei mecanice de la un piston la altul prin turbină; 2) efectul de amplificare al puterii prin reacţia definită mai sus prezintă o anumită întârziere, fapt ce nu este neglijabil la viteze mari2. Atât principiul de funcţionare al motorului turbo cât şi cele două observaţii de mai sus sunt valabile şi pentru decodorul turbo ce va fi prezentat în paragraful următor. 1.3 Turbodecodorul În Figura 1.3 se prezintă schematic structura unui turbocod, [BGT]. Secvenţa de informaţie, notată u, este codată de către codorul C1 rezultând secvenţa de paritate x1. Aceeaşi secvenţă de biţi, u, este furnizată, însă în altă ordine prin întreţesere cu ajutorul dispozitivului de întreţesere „I”, codorului C2, care generează la rândul său, secvenţa de paritate x2. Codurile pe care le implementează C1 şi C2 pot fi bloc sau convoluţionale. Însă trebuie remarcat că, datorită necesităţii de a întreţese secvenţa u, şi codoarele convoluţionale vor segmenta secvenţa de informaţie încât şi codul convoluţional va putea fi privit ca şi unul bloc. Secvenţele rezultate x0=u, x1 şi x2, prin multiplexare şi modulare (operaţii ce nu au fost simbolizate în Figura 1.3 pentru simplitate) constituie ieşirea turbocodorului, semnal ce va fi emis în canal. La ieşirea acestuia, prin demodulare şi demultiplexare (operaţii de asemenea omise în Figura 1.2) rezultă secvenţele (nebinare) recepţionate, corespunzătoare, y0, y1 şi y2.

Figura 1.3 Turbocod (Cod concatenat paralel) 1 ansamblul pieselor conţinute în carcasa turbinei (turbina cu lagărele şi sistemele ei de ungere) se numeşte „turbo”. 2 această întârziere în reacţie (necontrolabilă) a constituit motivaţia renunţării la motorul turbo în competiţiile sportive.

Iex21

û C1

C2

I

u x1 DEC1

DI

DEC2

I I

Can

al d

e tra

nsm

isie

Iex12

x0

x2

y1

y0

y2

LLR1


I.6

Aceste trei secvenţe constituie intrarea turbodecodorului. Prin corespondenţă y0 şi y1 constituie intrarea decodorului pereche lui C1, notat DEC1, iar y0 întreţesută alături de y2, intrarea decodorului pereche lui C2, notat DEC2. Pe lângă aceste intrări fiecare decodor mai prezintă o a treia intrare, prin care celălalt decodor îi furnizează o aşa numită informaţie extrinsecă. Pe baza acestor trei intrări fiecare decodor calculează logaritmul raportului de plauzibilitate (Log Likelihood Ratio –LLR) pentru fiecare bit din u:

LLR(ui) = ln)y 0p(u)y 1p(u

i

i=

= (1.1)

(în figură este prezentat doar logaritmul raportului de plauzibilitate al primului decodor, notat LLR1) şi de asemenea informaţia extrinsecă destinată celuilalt decodor. Turbodecodorul funcţionază iterativ, după cum urmează:

1. se citesc secvenţele y0, y1 şi y2; 2. pe baza secvenţelor y0 şi y1, DEC1 generează informaţia extrinsecă care, întreţesută,

constituie Iex12 –a treia intrare pentru DEC2; 3. pe baza secvenţelor y0 întreţesută, y2 şi Iex12, DEC2 generează informaţia extrinsecă,

care de-întreţesută constituie Iex21 –a treia intrare pentru DEC1; 4. din acest punct fiecare decodor primeşte informaţie extrinsecă şi, pe baza ei şi pe baza

secvenţelor venite din canal (y0 şi y1 respectiv y0 întreţesută şi y2) furnizează la rându-i informaţie extrinsecă. Acest proces se repetă iterativ de un anume număr de ori (impus sau calculat, funcţie de tipul turbocodului);

5. după efectuarea tuturor iteraţiilor impuse, se face o decizie hard asupra logaritmului raportului de plauzibilitate generat după ultima iteraţie de unul din cele două decodoare (în Figura 1.3 s-a ales LLR1). Secvenţa rezultată prin operaţia de decizie hard constituie ieşirea turbo-decodorului.

Observaţii: 1) Cele două decodoare conlucrează asemeni pistoanelor unui motor turbo: fiecare decodor furnizează celuilalt informaţie extrinsecă precum pistoanele, prin turbină, furnizează energie mecanică; 2) Dacă în cazul motorului turbo mărimea fizică vehiculată este energie mecanică (cinetică), în cazul turbodecodorului, decodoarele componente vehiculează între ele informaţie. Iex12 şi Iex21, fiind definite ca şi logaritmul unui raport de probabilităţi (după cum se va arăta în paragraful 2.1), respectă definiţia informaţiei; 3) Asemeni motorului turbo şi decodorul turbo are nevoie de un anume timp pentru a executa o decodare asupra secvenţei recepţionate. Acest fapt se datorează, în principal întârzierii produse de dispozitivele de întreţesere, dar şi de algoritmul de decodare. Deşi denumirea de turbocod se referă strict la structura „paralel” propusă de inventatori, [BGT], datorită asemănărilor conceptuale şi a performanţelor, în literatură unii autori au inclus sub denumirea de turbocod şi structurile „seriale” şi cele „hibride”, cu toate că aceste structuri nu prezintă aceeaşi asemănare cu motorul turbo. În paragraful următor se prezintă câteva structuri de turbocoduri analizându-se diferenţele conceptuale şi din punct de vedere al performanţei, notând că, pentru uşurinţa expunerii, se va păstra denumirea de turbocod şi pentru structurile seriale şi hibride de concatenare a codurilor.


I.7

1.4 Configuraţii de turbocoduri Schema turbocodului din Figura 1.3 poate fi generalizată [WAD] la un număr arbitrar de coduri concatenate în paralel. În Figura 1.4 se prezintă schema unui turbocod cu trei coduri componente concatenate paralel. Secvenţa de informaţie u este codată direct de către codorul C1 şi, după o întreţesere prin I2, de către C2, respectiv după o întreţesere prin I3, de către C3. Secvenţele rezultate prin codare cât şi secvenţa u, după multiplexare şi modulare, sunt emise în canal. La recepţie, după operaţiile inverse de demodulare şi demultiplexare, secvenţele recepţionate sunt distribuite decodoarelor corespunzătoare. Fiecare decodor va beneficia de două seturi de secvenţe de informaţii extrinseci, provenite de la celelalte două decodoare şi va furniza la rându-i informaţie extrinsecă. De remarcat că în acest caz rata de codare este R=1/4. Întârzierea produsă prin decodare este aceeaşi cu a turbodecodorului din Figura 1.3, deoarece decodoarele lucrează în paralel. Dacă se doreşte o rată de codare mai mare se poate apela la puncturare, cu preţul unei degradări în performanţa ratei erorii.

O astfel de structură de turbocod poartă denumirea de Cod Concatenat Paralel Multiplu.

Figura 1.4 Turbocod triplu în structură paralelă

û C1

C2

I3

u x1 DEC1

DEC2

mix

I3

C a

n a

l u

l d

e

t r a

n s

m i

s i e

x0

x2

y1

y0

y2

LLR1

I2 I2

C2 x2 DEC3 y3

I3

mix

mix

DI2

I2 I3

DI3

I2


I.8

O alternativă la structura paralelă a turbocodurilor este cea serială. În Figura 1.5 se prezintă un cod concatenat serial. La acesta, spre deosebire de cel paralel, secvenţa de informaţie u împreună cu cea rezultată prin codarea ei de către codorul C1, după o prealabilă multiplexare şi întreţesere, se recodează cu ajutorul codorului C2. Cele două secvenţe, de la intrarea lui C2 şi de la ieşirea sa, sunt secvenţele de ieşire a turbocodorului. De remarcat că în acest caz rata de codare este R=1/4, iar lungimea necesară de întreţesere este dublă faţă de cazul paralel. În plus codorul C2 execută o codare dublă ca şi volum faţă de codorul C1. La recepţie, ambele secvenţe rezultate din canal sunt preluate de DEC2. Acesta generează o informaţie extrinsecă asupra biţilor săi sistematici, care prin de-întreţesere constituie atât biţii sistematici ai lui DEC1 cât şi cei de paritate. Atât secvenţa notată „y1, y2” cât şi informaţia extrinsecă generată de DEC2, după demultiplexare sunt livrate decodorului DEC1. Acesta la rândul său generează informaţie extrinsecă care se referă atât la biţii săi sistematici cât şi la cei de paritate. Prin multiplexare şi întreţesere cele două secvenţe „informaţie extrinsecă” generate de DEC1 formează informaţia furnizată prin bucla de reacţie decodorului DEC2. Spre deosebire de configuraţia paralelă, unde era indiferent care decodor component genera ieşirea turbodecodorului, la configuraţia serială este mult mai comod să se aleagă DEC1. Altfel ar fi necesare adăugarea a încă altor blocuri de demultiplxare şi deîntreţesere, care în plus ar introduce şi o întârziere suplimentară. Este uşor de remarcat că şi o astfel de structură poate fi generalizată. Generalizarea ar consta în multiplexarea şi întreţeserea secvenţelor de la ieşirea turbocodului din Figura 1.5 în scopul unei a treia codări. Dezavantajul unei astfel de configuraţii multiple îl constituie întărzierea cumulată datorită necesităţii succesiunii serie a operaţiilor atât pentru codare cât şi pentru decodare.

Figura 1.5 Turbocod în configuraţie serială Cele două modalităţi de concatenare prezentate pot fi combinate într-o aşa numită configuraţie hibridă. În figura 1.6 se prezintă două variante de configuraţii hibride. Ambele configuraţii prezintă o structură serială la codare iar la decodare una paralelă. Cele două diferă doar prin faptul că cea de-a doua ieşire a turbocodorului, x2, la prima schemă este întreţesută iar la cea de-a doua schemă este luată direct de la ieşirea codorului C1. Structura serială de la codare se reflectă în turbo-decodor prin faptul că decodorul DEC2 îi furnizează decodorului DEC1 o informaţie extrinsecă despre biţii de paritate şi nu despre cei sistematici, ca şi în cazul

u

C1

C2

I

x3

DEC2

DI DEC1

DI

I

û

mux x1, x2

Can

alul

de

trans

mis

ie

mux

y1, y2

y3

dmux

dmux

LLR1


I.9

configuraţiei paralele. Din această cauză configuraţia hibridă este inferioară din punct de vedere al performanţelor configuraţiei paralele [WAD]. În schemele prezentate anterior s-a subînţeles că secvenţa de intrare conţine un singur bit per tact. Generalizând la un număr arbitrar k de biţi per tact se pot obţine turbocoduri cu o rată de codare şi implicit o eficienţă mai mare. Formal structurile turbocodurilor sunt aceleaşi cu cele prezentate, diferenţa constând în faptul că legăturile dintre blocurile componente devin magistrale de k biţi. În plus creşte complexitatea şi volumul calculelor. O astfel de categorie o reprezintă turbocodurile având k=2, numite „duo-binare” [JEZ]. a) b)

Figura 1.6 Două scheme de coduri concatenate hibrid 1.5 Limite teoretice Teorema codării canalelor cu zgomot, fundamentată de către Shannon, afirmă că se poate face o transmisie cu o rată a erorii oricât de mică, dacă debitul (viteza) de transmisie este mai mică decât capacitatea canalului: vb ≤ C, unde vb este viteza de transmisie binară iar C este capacitatea canalului, dată prin formula: C = B⋅log2 (1+S/Z) (1.2)

C1

C2

I C

anal

de

trans

mis

ie x0

x1

x2

y0

y1

y2 DEC2

DI

DEC1

DI

I

ûLLR1

u

C1

C2

I

Can

al d

e tra

nsm

isie

x0

x1

x2

y0

y1

y2 DEC2

I

DEC1

DI

I

ûLLR1

u


I.10

unde B este banda canalului. Considerând zgomotul AWGN cu densitatea spectrală de putere N0/2, rezultă pentru puterea zgomotului valoarea: Z = σ2 = 2⋅B⋅N0/2 = B⋅N0 (1.3) Puterea semnalului, S se poate calcula astfel: S = Eb/Tb = vb⋅Eb (1.4) unde Eb şi Tb sunt energia necesară per bit şi durata sa. Considerând acum [VUY] că transmisia s-ar face la capacitatea canalului, vb = C, rezultă, ţinând cont de relaţiile (1.3) şi (1.4):

)NE

BC1(log

BC

0

b2 ⋅+= (1.5)

Din ultima relaţie rezultă pentru raportul Eb/N0 expresia:

0

bNE

= C/B

12C/B − (1.6)

Dacă B→∞, din ecuaţia (1.6) rezultă pentru raportul semnal per zgomot, Eb/N0, valoarea minimă necesară:

min0

bNE

= ln 2 = –1,59 dB (1.7)

Observaţii:

1) Marimea η=vb/B se numeşte eficienţă spectrală [VUY] şi este o măsură a eficienţei transmisiei. Dacă se utilizează o modulaţie cu 2q nivele, iar rata de codare este R=k/n, atunci viteza de semnalizare este:

vs = q⋅R⋅ vb (1.8)

şi, la limită (pentru respectarea teoremei lui Shannon: vs =B): ηmax = q⋅R (1.9)

2) Trebuie remarcat că, în cazul introducerii redundanţei (codării FEC), există o diferenţă între puterea semnalului necodat şi cel codat, [WAD]. Astfel:

k⋅Eb = n⋅S⋅Tb (1.10)

Atunci, pentru o densitate spectrală de putere a zgomotului N0/2 şi o modulaţie BPSK (±1):

2200 21

2 σσ ⋅⋅=

⋅⋅=

⋅⋅

=RR

SNRTS

NE bb (1.11)


II.1

2. Turbocoduri convoluţionale În Capitolul 1 s-a făcut o prezentare a principiului de funcţionare al unui turbocod precum şi a diferitor configuraţii de turbocoduri, fără a se detalia blocurile componente. În acest capitol se vor prezenta blocurile componente ale unui turbocod ce utilizează un cod convoluţional, prezentându-se factorii care influenţează performanţele turbocodurilor, din punct de vedere al ratei erorilor (configuraţia turbocodului, felul recursiv sau nerecursiv al codului convoluţional utilizat precum şi lungimea sa de constrângere, rata de codare şi ajustarea ei prin puncturare, felul întreţeserii şi lungimea de întreţesere, algoritmul de decodare utilizat şi parametrii acestuia). Codoarele utilizate în turbocoduri sunt în special cele recursive şi sistematice. În Figura 2.1 este prezentat un codor convoluţional recursiv, sistematic, având matricea generatoare:

G=[1, (1+D2)/(1+D+D2)]. (2.1) 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 [FOR], totuşi în componenţa turbo-codurilor se dovedesc a avea performanţe superioare codurile recursive şi sistematice [WAD]. Acest fapt se datorează unei ponderi mai mari pentru RSC, [JEZ]. În contrast cu codorul convoluţional, care are o implementare hard simplă, după cum se vede în Figura 2.1, un decodor, pentru a putea fi component al unui turbocod, trebuie să accepte intrare soft şi, de asemenea, să ofere ieşire soft, [HOP]. În continuare vor fi prezentaţi principalii algoritmi SISO (soft-input soft-output): MAP şi SOVA, în câteva dintre variantele lor [HLY].

Figura 2.1 Codor convoluţional recursiv, sistematic, cu G=[1, (1+D2)/(1+D+D2)]

DD

Biţii de intrare

Biţii sistematici

Biţii de paritate


II.2

2.1 Algoritmi utilizaţi în decodoarele componente 2.1.1 Logaritmul raportului de plauzibilitate (LLR) Aşa cum s-a arătat în paragraful 1.3, ieşirea turbodecodorului o reprezintă logaritmul raportului de plauzibilitate (LLR). LLR-ul bitului de date uk, notat L(uk), este definit de logaritmul raportului probabilităţilor ca bitul să ia două valori posibile1, adică:

L(uk) = ln

−=+=

)1P(u)1P(u

k

k . (2.2)

Figura 2.2 arată cum variază L(uk) în funcţie de probabilitatea ca uk = +1. Se poate vedea din această figură că semnul LLR-ului pentru bitului uk va indica, prin decizie hard, valoarea bitului uk, iar mărimea LLR-ului dă o indicaţie asupra plauzibilităţii deciziei făcute. Dat fiind LLR-ul L(uk), este posibil calculul probabilităţii ca uk = +1 sau uk = –1 după cum urmează:

+=+=

=)1P(u-1

)1P(ue

k

k)L(uk , (2.3)

şi astfel:

P(uk = +1) = =+ )L(u

)L(u

k

k

e1

e)L(u- ke1

1+

(2.4a)

P(uk = −1) = =+ )L(uke1

1)L(u-

)-L(u

k

k

e1

e

+ (2.4b)

şi de aceea putem scrie:

P(uk = ±1) = 2/)L(u)L(u-

2/)L(u-k

k

ke

e1

e ±⋅

+. (2.5)

Termenul din paranteză al acestei ecuaţii nu depinde de condiţia ca uk = +1 sau uk = –1, şi ca atare poate fi tratat ca o constantă în aplicaţiile concrete. La fel ca pentru LLR-ul L(uk) bazat pe probabilităţile necondiţionate P(uk = ±1), se poate calcula LLR-ul bazat pe probabilităţile condiţionate de recepţionarea unei anume secvenţe y:

L(uk|y) = ln

−=

+=

)y 1P(u

)y 1P(u

k

k . (2.6)

Probabilităţile condiţionate P(uk = ±1/y) sunt probabilităţile a-posteriori pe care decodoarele soft-in soft-out încearcă să le afle. 1 matematic este mai comod de utilizat valorile +1 şi –1 decât 1 şi 0.


II.3

Figura 5.4 LLR-ul L(uk) în funcţie de probabilitatea uk = +1

Figura 2.2 LLR-ul L(uk) în funcţie de probabilitatea ca uk = +1 LLR-ul condiţionat de probabilitatea ca ieşirea filtrului adaptat al receptorului să fie yk dat fiind bitul transmis corespunzător xk = +1 sau –1, notat L(yk/xk), se defineşte ca:

L(yk|xk) = ln

−=

+=

)1 x P(y)1 x P(y

kk

kk . (2.7)

Dacă presupunem că bitul transmis xk = ±1 a fost transmis printr-un canal gaussian sau cu fading utilizând modulaţie BPSK, atunci putem scrie pentru probabilitatea ieşirii filtrului adaptat că:

P(yk | xk=+1) = ( )

− 2

k2b ay

2

E-exp

21

σπσ, (2.8)

unde Eb este energia transmisă per bit, σ2 este dispersia zgomotului iar a este amplitudinea cu fading (avem a=1 pentru canale AWGN fără fading). Similar, avem:

P(yk | xk= –1) = ( )

+ 2

k2b ay

2

E-exp

21

σπσ. (2.9)

Aşadar, atunci când se utilizează o modulaţie BPSK peste un canal Gaussian (posibil cu fading), ecuaţia 2.7 se poate rescrie ca:


II.4

L(yk | xk) = ln( )( )

−=

+=

1 xyP1 xyP

kk

kk = ln ( )

( )

+

−

2k2

b

2k2

b

ay2

E-exp

ay2

E-exp

σ

σ

= ( )

−− 2

k2b ay

2

E

σ− ( )

+− 2

k2b ay

2

E

σ=

= k2b ya4

2

E⋅

σ= Lc⋅yk (2.10)

unde:

Lc = 4a2

b

2

E

σ (2.11)

se defineşte ca valoarea de încredere a canalului, şi depinde doar de raportul semnal per zgomot (SNR), şi de amplitudinea fadingului canalului. Astfel, pentru BPSK peste un canal Gaussian (posibil cu fading), LLR-ul condiţionat L(yk/xk) –ieşirea soft a canalului, este ieşirea filtrului adaptat yk multiplicată prin valoarea de încredere a canalului. 2.1.2 Algoritmul Maximum A-Posteriori Algoritmul Maximum A-Posteriori (MAP) a fost propus de Bahl, Cocke, Jelinek şi Raviv în 1974, pentru estimarea probabilităţilor a-posteriori a stărilor şi tranziţiilor pentru o sursă Markov supusă zgomotului fără memorie. Algoritmul MAP examinează orice drum posibil prin trellisul convoluţional al decodorului şi de aceea iniţial se părea a fi nerealizabil de complex pentru aplicaţiile din majoritatea sistemelor. Ca atare nu a fost prea des utilizat înainte de descoperirea turbocodurilor.

Figura 2.3 Tranziţiile posibile în codorul component K=3 RSC, din Figura 2.1

+1

+1+1

-1

-1

-1

Sk-1 Sk-1

+1


II.5

Algoritmul MAP dă, pentru fiecare bit decodat uk, probabilitatea ca acest bit să fi fost +1 sau −1, dată fiind secvenţa de simboluri y. Aceasta este echivalentă cu aflarea LLR-ului a-posteriori L(uk|y) dat de (2.6). Regula lui Bayes ne permite să rescriem această ecuaţie ca:

L(uk|y) = ln( )( )

∧−=

∧+=

y 1uPy 1uP

k

k . (2.12)

Figura 2.3 arată tranziţiile posibile pentru codorul K=3 RSC prezentat în Figura 2.1.

Pentru acest cod există patru stări ale codorului, şi deoarece se consideră un cod binar, din fiecare stare a codorului sunt posibile două tranziţii, depinzând de valoarea bitului. Una din aceste tranziţii este asociată cu bitul de intrare −1 prezentată printr-o linie continuă, în vreme ce cealaltă tranziţie corespunde bitului de intrare +1 prezentată ca o linie întreruptă. În Figura 2.3 se poate vedea că dacă starea anterioară sk-1, cât şi starea prezentă sk, sunt cunoscute, atunci şi valoarea bitului de intrare uk, ce cauzează tranziţia dintre aceste două stări, va fi cunoscută. Aşadar probabilitatea ca uk = +1 este egală cu probabilitatea ca tranziţia de la starea precedentă sk-1 către starea prezentă sk este una din setul celor patru tranziţii posibile existente când uk = +1 (tranziţii prezentate cu linie întreruptă). Acest set de tranziţii este mutual exclusiv (adică doar una dintre ele ar fi putut exista la codor). Aşadar ecuaţia 2.12 se poate rescrie ca:

L(uk|y) = ln

( )

( )

∧=∧=

∧=∧=

∑

∑

−=⇒

+=⇒

y sSsSP

ysS s SP

k1-k

1us),s(

k1-k

1us),s(

k

k , (2.13)

unde (ŝ,s) ⇒ uk = +1 este setul tranziţiilor de la starea anterioară sk-1 = ŝ la prezenta stare sk = s ce poate exista dacă bitul de intrare uk = +1, şi similar pentru (ŝ,s) ⇒ uk = –1. Pentru simplitate se poate scrie P(sk-1=ŝ∧sk=s∧y) ca P(ŝ∧s∧y). Secvenţa recepţionată y poate fi împărţită în trei secţiuni: cuvântul de cod asociat prezentei tranziţii yk, secvenţa recepţionată precedentă tranziţiei yj<k şi secvenţa recepţionată de după tranziţia prezentă yj>k. Această împărţire se prezintă în Figura 2.4, de asemenea pentru exemplul codului component K=3 RSC prezentat în Figura 2.1. Probabilităţile individuale P(ŝ∧s∧y) se pot scrie:

P(ŝ∧s∧y) = P(ŝ∧s∧yj<k∧ yk∧yj>k). (2.14) Utilizând regula lui Bayes P(a∧b) = P(a| b)⋅P(b) şi faptul că s-a presupus canalul fără memorie, atunci secvenţa recepţionată viitoare yj>k va depinde doar de starea s, nu şi de starea anterioară ŝ sau de secvenţa recepţionată din canal prezentă sau anterioară yk şi yj<k şi se poate scrie:

P(ŝ∧s∧y) = P(yj>k| {ŝ∧s∧yj<k ∧y})⋅P(ŝ∧s∧yj<k ∧ yk) = P(yj>k| s)⋅P(ŝ∧s∧yj<k ∧ yk). (2.15)


II.6

Figura 2.4 Trellis-ul decodorului MAP pentru codul K=3 RSC Utilizând din nou regula lui Bayes cât şi presupunerea canalului fără memorie, ecuaţia 2.15 se poate dezvolta după cum urmează:

P(ŝ∧s∧y) = P(yj>k| s)⋅P(ŝ∧s∧yj<k ∧ yk) = P(yj>k| s)⋅P({yk ∧s}|{ŝ∧yj<k})⋅P(ŝ∧yj<k) = P(yj>k| s)⋅P({yk ∧s}| ŝ)⋅P(ŝ∧yj<k) = βk(s)⋅γk(ŝ,s)⋅αk-1(ŝ), (2.16)

unde: αk-1(ŝ) = P(Sk-1 = ŝ ∧ yj<k) (2.17) este probabilitatea ca trellisul să fie în starea ŝ la momentul k-1 iar secvenţa recepţionată din canal până în acest moment să fie yj<k, aşa cum se prezintă în Figura 2.4, iar: βk(s) = P(yj>k| Sk = s) (2.18) este probabilitatea ca, dată fiind starea trellisului s la momentul k, secvenţa recepţionată din canal să fie yj>k, iar în fine: γk(ŝ,s) = P({yk ∧ Sk = s}| Sk-1 = ŝ) (2.19) este probabilitatea ca, dat fiind trellisul în starea ŝ la momentul k-1, să treacă în starea s iar secvenţa recepţionată din canal pentru această tranziţie este yk. Ecuaţia 2.16 arată că probabilitatea P(ŝ∧s∧y) ca trellisul codorului să fi avut tranziţia de la starea sk-1 = ŝ către starea sk = s iar secvenţa recepţionată să fie y, se poate desface într-un produs de trei termeni: αk-1(ŝ), γk(ŝ,s) şi βk(s). Înţelesul acestor trei termeni de probabilitate

Sk-3 Sk-2 Sk-1 Sk Sk+1

yj<k yk yj>k

αk-1(ŝ) γk-1(ŝ,s) βk(s)


II.7

este prezentat în Figura 2.4, pentru tranziţia de la sk-1 = ŝ la sk = s. Algoritmul MAP găseşte αk(s) şi βk(s) pentru toate stările s de-a lungul trellisului, adică pentru k = 0, 1, ..., N-1, şi γk(ŝ,s) pentru toate tranziţiile posibile de la starea sk-1 = ŝ către starea sk = s, de asemenea pentru k = 0, 1, ..., N-1. Aceste valori sunt mai apoi utilizate pentru aflarea probabilităţilor P(sk-1=ŝ∧sk=s∧y) din ecuaţia 2.16, care sunt utilizate în ecuaţia 2.13 pentru a da LLR-ul L(uk/y) pentru fiecare bit uk. Aceste operaţii sunt rezumate în organigrama din Figura 2.6.

Figura 2.5 Calculul recursiv pentru αk(0) şi βk(0)

Calculul recursiv înainte al valorilor αk(s) Din definiţia pentru αk-1(ŝ) din ecuaţia 2.17 se poate scrie:

αk(s) = P(Sk = s ∧ yj<k+1) = P(s ∧ yj<k ∧yk) = ∑

s totiP (s∧ŝ∧yj<k∧yk), (2.20)

unde în ultima linie s-a descompus probabilitatea P(s∧yj<k+1) într-o sumă de probabilităţi de intersecţie P(s∧ŝ∧yj<k+1) peste toate stările anterioare posibile ŝ. Utilizând din nou regula lui Bayes şi presupunerea canalui fără memorie:

αk(s) = ∑s totiP (s∧ŝ∧yj<k∧yk)

= ∑s totiP ({s∧yk}| {ŝ∧yj<k})⋅P(ŝ∧yj<k)

γk(1,0)

γk+1(0,2)

βk(0)

Sk-1 Sk Sk+1Starea

βk+1(0) αk-1(0)

αk-1(1)

γk+1(0,0)

αk(0)

βk+1(2)

γk(0,0)0

1

2

3

yk+1yk

αk(0) = αk-1(0)⋅γk(0,0) + αk-1(1)⋅γk(1,0) βk(0) = βk+1(0)⋅γk+1(0,0) + βk+1(2)⋅γk+1(0,2)


II.8

= ∑s totiP ({s∧yk}| ŝ)⋅P(ŝ∧yj<k)

= ( )∑s toti

k s,sγ ⋅αk-1(ŝ) (2.21)

Aşadar, o dată ce sunt cunoscute valorile γk(ŝ,s), valorile αk(s) pot fi calculate recursiv. Presupunând că trellisul are starea iniţială s0 = 0, condiţiile iniţiale pentru această recurenţă sunt:

α0(S0 = 0) = 1 α0(S0 = s) = 0 pentru ∀s≠0 (2.22)

Figura 2.5 prezintă, într-un exemplu, cum este calculată recursiv o valoare αk(s), pentru s = 0, utilizând valorile pentru αk-1(ŝ) şi γk(ŝ,s) pentru codul K=3 RSC. De notat că, deoarece s-a considerat un trellis binar, doar două stări anterioare, sk-1 = 0 şi sk-1 = 1, au tranziţie către starea sk = 0. Aşadar γk(ŝ,s) va fi diferită de zero doar pentru ŝ = 0 sau ŝ = 1 şi astfel sumarea din ecuaţia 2.21 presupune doar doi termeni. Calculul recursiv înapoi al valorilor βk(s) Valorile pentru βk(s) pot fi calculate recursiv în mod similar după cum urmează. Pornind de la definiţia pentru βk(s) din ecuaţia 2.18 se poate scrie βk-1(ŝ) ca şi:

βk-1(ŝ) = P(yj>k-1| Sk-1 = ŝ) (2.23) şi, din nou, desfăcând probabilitatea într-o sumă de probabilităţi de intersecţie şi făcând presupunerea că există canal fără memorie:

βk-1(ŝ) = P(yj>k-1| ŝ) = ∑

s totiP ({yj>k-1∧s}| ŝ)

= ∑s totiP ({yk∧yj>k∧s}| ŝ)

= ∑

s totiP (yj>k| {ŝ∧s∧yk})⋅P({yk∧s}| ŝ)

= ∑

s totiP (yj>k| s)⋅P({yk∧s}| ŝ)

= ( )∑

s totik s,sγ ⋅βk(s) (2.24)

Astfel, o dată ce valorile γk(ŝ,s) sunt cunoscute, se poate utiliza o recurenţă înapoi pentru a calcula valorile βk-1(ŝ) din valorile pentru βk(s) utilizând ecuaţia 2.24. Figura 2.5 prezintă de asemenea un exemplu de calcul recursiv al valorii βk(0) utilizând valorile pentru βk+1(s) şi γk(0,s), în exemplul codului K=3 RSC din Figura 2.1. Condiţiile iniţiale ce pot fi utilizate pentru βN(s) nu sunt aşa de clare ca şi pentru α0(s). Dacă trelisul este terminat, aşa cum sugerează Berrou ş.a. [BGT], se pot utiliza valorile


II.9

βN(0)=1 şi βN(s)=0 pentru s≠0, iar pentru un trellis neterminat se pot utiliza relaţiile βN(s) = αN(s) pentru toţi s, sugerate de Robertson în [RVH]. Calculul valorilor pentru γk(ŝ,s) Utilizând definiţia pentru γk(ŝ,s) din ecuaţia 2.19 şi rezultanta regulii lui Bayes:

γk(ŝ,s) = P({yk ∧s}| ŝ) = P(yk|{ŝ∧s})⋅P(s|ŝ) = P(yk|{ŝ∧s})⋅P(uk), (2.25)

unde uk este bitul de intrare necesar a cauza tranziţia de la starea sk-1=ŝ la starea sk=s, iar P(uk) este probabilitatea a-priori a acestui bit. Din ecuaţia 2.5 aceasta poate fi scrisă ca:

P(uk) = )2/)L(u()L(u-

2/)L(u-k

k

ke

e1

e ku⋅

+

= ( )( )1

uL kC )2/)L(u( ke ku⋅ , (2.26)

unde, cum s-a stabilit anterior:

( )( )1

uL kC =

+ )L(u-

2/)L(u-

k

k

e1

e (2.27)

depinde doar de LLR-ul L(uk) nu şi de valoarea lui uk. Primul termen din a doua linie a ecuaţiei 2.25, P(yk| {ŝ∧s}), este echivalent cu P(yk|xk), unde x este cuvântul de cod transmis asociat tranziţiei dintre stările sk-1=ŝ şi sk=s. Presupunând din nou canalul fără memorie putem scrie:

P(yk| {ŝ∧s}) ≡ P(yk| xk) = ∏=

n

1iP (yki | xki), (2.28)

unde xki şi yki sunt biţii individuali din cuvintele de cod emis şi recepţionat xk şi yk, iar n este numărul acestor biţi din fiecare cuvânt de cod yk şi xk. Presupunând că biţii xki au fost transmişi printr-un canal Gaussian utilizând BPSK, astfel încât valorile simbolurile transmise sunt +1 sau −1, avem pentru P(yki|xki):

P(yki | xki) = ( )

⋅− 2

kiki2b xay

2

E-exp

21

σσπ, (2.29)

unde Eb este energia transmisă per bit, σ2 este dispersia zgomotului iar a este amplitudinea de fading (a=1 pentru canale AWGN fără fading). Prin substituirea ecuaţiei 2.29 în 2.28 avem:

P(yk| {ŝ∧s}) = ( )

⋅−∏

=

2kiki2

bn

1ixay

2

E-exp

21

σσπ


II.10

= ( )

⋅−∑

=

n

1i

2kiki2

bn xay

2

E-exp

)2(1

σσπ

= ( )

⋅⋅⋅−⋅+∑

=

n

1i

2kiki

2ki

22ki2

bn yxa2xay

2

E-exp

)2(1

σσπ

= ( )2yC

k⋅ ( )3

xCk⋅

⋅⋅ ∑

=

n

1ikiki2

b xya22

Eexp

σ, (2.30)

unde:

( )2yC

k =

∑=

n

1i

2ki2

bn y

2

E-exp

)2(1

σσπ (2.31)

depinde doar de SNR-ul canalului şi de mărimea secvenţei recepţionate yk, pe când:

( )3xC

k =

∑=

n

1i

2ki

22

b xa2

E-expσ

=

na

2

E-exp 2

2b

σ (2.32)

depinde doar de SNR-ul canalului şi de amplitudinea de fading. De aceea putem scrie pentru γk(ŝ,s):

Figura 2.6 Organigrama algoritmului MAP

Calcululvalorilor

Lcykl

Informaţiaa-priori L(uk)

Evaluează γk(ŝ,s)ecuaţia 2.33

Evaluează αk-1(ŝ) ecuaţia 2.21

Evaluează βk(s) ecuaţia 2.24

Calculează LLR-ulL(uk|y)

ecuaţia 2.35


II.11

γk(ŝ,s) = P(uk)⋅P(yk| {ŝ∧s})

= C )2/)L(uu( kke⋅ ⋅

⋅⋅ ∑

=

n

1ikiki2

b xya22

Eexp

σ

= C )2/)L(uu( kke⋅ ⋅

⋅∑

=

n

1ikiki

c xy2

Lexp , (2.33)

unde: C = ( )

( )1uL k

C ⋅ ( )2yC

k⋅ ( )3

xCk

(2.34)

Termenul C nu depinde de semnul bitului uk sau de cuvântul de cod emis xk şi astfel este o constantă pentru semnalele de la numitor şi numărător din ecuaţia 2.13 şi poate fi şters. Din ecuaţiile 2.13 şi 2.16 se poate scrie pentru LLR-ul condiţionat pentru uk, dată fiind secvenţa recepţionată yk:

L(uk|y) = ln

( )

( )

∧=∧=

∧=∧=

∑

∑

−=⇒

+=⇒

y sSsSP

ysS s SP

k1-k

1us),s(

k1-k

1us),s(

k

k

= ln

( ) ( ) ( )

( ) ( ) ( )

⋅⋅

⋅⋅

∑

∑

−=⇒

+=⇒

1us),s(

1-k

1us),s(

1-k

k

k

ss,ss

ss,ss

kk

kk

βγα

βγα

(2.35)

Acesta este LLR-ul condiţionat L(uk| y) pe care îl furnizează decodorul MAP. Rezumatul algoritmului MAP Se calculează γk(ŝ,s) cu ecuaţia 2.33, utilizând valorile canalului yki şi LLR-ul a-priori L(uk) (ce este furnizat într-un decodor iterativ turbo printr-un alt decodor component –vezi paragraful 1.3). Constanta C poate fi omisă din calculul lui γk(ŝ,s) deoarece se va simplifica în raportul din ecuaţia 2.35. Pentru calculul valorilor αk(ŝ,s) se utilizează recurenţa înainte dată de ecuaţia 2.21, iar pentru calculul valorilor βk(ŝ,s) recurenţa înapoi din ecuaţia 2.24. În final, toate valorile calculate pentru αk(ŝ,s), βk(ŝ,s) şi γk(ŝ,s) sunt utilizate în ecuaţia 2.35 pentru calculul valorilor pentru L(uk/y). Aceste operaţii sunt rezumate în organigrama din Figura 2.6. Pentru a evita probleme de calcul numeric în calculul recursiv pentru αk(ŝ,s) şi βk(ŝ,s), se poate proceda la o normalizare a acestor valori. Această normalizare se şterge în raportul din ecuaţia 2.35 şi de aceea nu cauzează schimbări în LLR-ul produs de algoritm. Algoritmul MAP este, în forma descrisă în această secţiune, extrem de complex datorită multiplicărilor, a operatorilor exponenţiali şi a operatorilor logaritmi naturali utilizaţi. În paragrafele următoare se prezintă două versiuni ale algoritmului MAP care, cu preţul unei oarecare degradări a performanţei, sunt mai puţin complexe.


II.12

2.1.3 Algoritmul MaxLogMAP Tehnica Max-Log-MAP simplifică algoritmul MAP prin transferarea recurenţelor în

domeniul logaritmic şi prin invocarea unei aproximări spre a reduce dramatic complexitatea de implementare asociată. Datorită acestei aproximări performanţa algoritmilor Max-Log-MAP este sub-optimală.

Aproximaţia utilizată de algoritmul Max-Log-MAP este:

ln ( )iii

x xmaxe i ≈

∑ , (2.36)

unde maxi (xi) înseamnă maximul valorilor pentru xi. Atunci, cu Ak(s), Bk(s) şi Γk(ŝ,s) definite astfel: Ak(s) = ln(αk(s)), (2.37) Bk(s) = ln(βk(s)), (2.38) şi: Γk(ŝ,s) = ln(γk(ŝ,s)), (2.39) se poate rescrie ecuaţia 2.21 ca: Ak(s) = ln(αk(s))

= ln ( ) ( )

⋅∑

s totik1-k s,ss γα

= ln ( ) ( )

Γ+∑

s totik1-k ]s,ssexp[A

≈ s

max (Ak-1(ŝ) + Γk(ŝ,s)). (2.40)

Ecuaţia arată că pentru fiecare ramură în Figura 2.4 de la stadiul anterior din trellis către Sk = s la stadiul prezent, algoritmul adună termenul metrică a ramurii Γk(ŝ,s) la valoarea anterioară Ak-1(ŝ) pentru a obţine noua valoare Ãk(s) a ramurii. Noua valoare pentru Ak(s) în acord cu ecuaţia 2.40 este maximul valorilor Ãk(s) peste diferitele ramuri ce sosesc la starea Sk = s. Aceasta poate fi înţeles ca şi selectând o ramură ca „supravieţuitoare” şi ignorând orice altă ramură ce soseşte în acea stare. Valoarea pentru Ak(s) va da logaritmul natural al probabilităţii ca trellisul să fie în starea Sk = s la stadiul k, ştiind că secvenţa canalului recepţionată până la acest punct a fost yj<k. Însă, datorită aproximaţiei din ecuaţia 2.36 utilizată pentru a obţine ecuaţia 2.40, când se calculează această probabilitate se consideră doar ramura maxim plauzibilă pentru starea Sk = s. Astfel valoarea pentru Ak în algoritmul Max-Log-MAP dă acum probabilitatea celei mai plauzibile ramuri din trellis pentru starea Sk = s, ignorând probabilitatea pentru oricare altă ramură prin trellis către starea Sk = s. Această aproximaţie este unul din motivele performanţei sub-optimale ale algoritmului Max-Log-MAP comparativ cu algoritmul MAP. Din ecuaţia 2.40 se observă că în algoritmul Max-Log-MAP recurenţa înainte utilizată pentru a calcula Ak(s) este exact aceeaşi ca recurenţa înainte din algoritmul Viterbi –pentru fiecare pereche de ramuri convergente– supravieţuitorul se află utilizând două adunări şi o comparaţie. Pentru trellisurile binare sumarea şi maximizarea, peste toate stările anterioare


II.13

Sk-1 = ŝ în ecuaţia 2.40 vor fi de fapt peste doar două stări, deoarece vor fi doar două stări anterioare Sk-1 = ŝ cu ramuri către starea prezentă Sk = s. Pentru toate celelalte valori pentru ŝ vom avea γk(ŝ,s) = 0. Similar cu ecuaţia 2.40 pentru recurenţa înainte utilizată pentru a calcula Ak(s), putem rescrie ecuaţia 2.24 ca: Bk-1(ŝ) = ln(βk-1(ŝ))

= ln ( ) ( )

⋅∑

s totikk s,ss γβ

= ln ( ) ( )

Γ+∑

s totikk ]s,ssexp[B

≈ (Bk(s) + Γk(ŝ,s)), (2.41) şi obţinem recurenţa înapoi utilizată pentru a calcula valorile Bk-1(ŝ). De asemenea, aceasta este echivalentă cu recurenţa utilizată în algoritmul Viterbi –valoarea pentru Bk-1(ŝ) se află prin adunarea, pentru orice stare Sk = s ce are ramură dinspre Sk-1 = ŝ (două în trellisul binar), a metricii ramurii Γk(ŝ,s) la valoarea Bk(s) şi selectând acea ramură care dă cea mai mare valoare Bk-1(ŝ). Utilizând ecuaţia 2.33, metricile ramurilor Γk(ŝ,s) în formula recursivă a ecuaţiilor 2.40 şi 2.41 rezultate pentru Ak(s) şi respectiv Bk-1(ŝ) pot fi scrise ca: Γk(ŝ,s) = ln(γk(ŝ,s))

= ln ( )( )

⋅⋅⋅⋅⋅ ∑

=

n

1ikiki2

b2/uLu xya22

EexpeC kk

σ

= ln ( )( )

⋅⋅⋅⋅ ∑

=

n

1ikiki

c2/uLu xy2

LexpeC kk

= Ĉ + 21⋅uk⋅L(uk) + ∑

=⋅

n

1ikiki

c xy2

L (2.42)

unde Ĉ = ln C nu depinde de uk sau de cuvântul de cod transmis xk şi astfel poate fi considerat constant şi omis. Aşadar metrica ramurii este echivalentă cu cea utilizată în algoritmul Viterbi, cu adunarea termenului LLR a-priori ukL(uk). În plus termenul corelaţie

∑ =n

1i kikixy este ponderat prin valoarea de încredere a canalului Lc din ecuaţia 2.11.

L(uk|y) = ln

( ) ( ) ( )

( ) ( ) ( )

⋅⋅

⋅⋅

∑

∑

−=⇒

+=⇒

1us),s(

1-k

1us),s(

1-k

k

k

ss,ss

ss,ss

kk

kk

βγα

βγα


II.14

= ln

( ) ( ) ( )

( ) ( ) ( )

+Γ+

+Γ+

∑

∑

−=⇒

+=⇒

1us),s(

1-k

1us),s(

1-k

k

k

)sB s,s sexp(A

)sB s,s sexp(A

kk

kk

≈ ( )

1us,s

k

max

+=⇒

(Ak-1(ŝ) + Γk(ŝ,s) + Bk(s))

– ( )

1us,s

k

max

−=⇒

(Ak-1(ŝ) + Γk(ŝ,s) + Bk(s)). (2.43)

Aceasta înseamnă că în algoritmul Max-Log-MAP, pentru fiecare bit uk, LLR-ul a-posteriori L(uk/y) se calculează considerând toate tranziţiile de la stadiul trellisului Sk-1 către stadiul Sk. Aceste tranziţii sunt grupate între acelea ce s-ar fi putut produce doar dacă uk = +1, şi acelea ce s-ar fi putut produce doar dacă uk = –1. Pentru ambele grupuri se află tranziţia ce dă valoarea maximă pentru Ak-1(ŝ) + Γk(ŝ,s) + Bk(s), iar LLR-ul a-posteriori este calculat doar pentru „cele mai bune tranziţii”. Pentru un trellis binar vor fi 2⋅2K-1 tranziţii la fiecare stadiu al trellisului, unde K este lungimea de constrângere a codului convoluţional. Aşadar trebuiesc considerate 2K-1 tranziţii la fiecare maximizare în ecuaţia 2.43. Algoritmul Max-Log-MAP se poate rezuma după cum urmează. Metrica ramurii Γk(ŝ,s) utilizată, este dată prin ecuaţia 2.42, unde termenul constant Ĉ poate fi omis. Pentru a calcula Ak(s) şi Bk(s) se utilizează recurenţele înainte şi înapoi, ecuaţia 2.40 şi respectiv ecuaţia 2.41, ambele similare recurenţei înainte utilizate în algoritmul Viterbi. O dată ce ambele recurenţe înainte şi înapoi au fost făcute, se poate calcula LLR-ul a-posteriori utilizând ecuaţia 2.43. Astfel complexitatea algoritmului Max-Log-MAP nu este cu mult mai mare decât cea a algoritmului Viterbi –în loc de o recurenţă există două, metrica ramurii din ecuaţia 2.42 are adunat termenul adiţional a-priori ukL(uk), iar pentru fiecare bit trebuie utilizată ecuaţia 2.43 pentru a da LLR-urile a-posteriori. 2.1.4 Algoritmul Log-MAP

Algoritmul Max-Log-MAP dă o uşoară degradare în performanţă comparativ cu algoritmul MAP datorită aproximării din ecuaţia 2.36. Însă, această aproximare poate fi făcută exactă prin utilizarea logaritmului Jacobian:

ln( 1xe + 2xe ) = max(x1,x2) + ln(1+ 21 xxe −− ) = max(x1,x2) + ƒc( |x1-x2| ) = g(x1,x2), (2.44) unde ƒc(x) poate fi gândită ca un termen de corecţie. Acesta este baza algoritmului Log-MAP propus de Robertson ş.a. [RVH]. Similar cu algoritmul Max-Log-MAP, valorile pentru Ak(s) = ln (αk(s)) şi Bk(s) = ln (βk(s)) sunt calculate utilizând recurenţa înainte şi înapoi. Însă, maximizările din ecuaţiile 2.40 şi 2.41 sunt complementate prin termenul de corecţie din ecuaţia 2.44. Aceasta înseamnă că sunt calculate mai exact decât valorile aproximative Ak(s) şi Bk(s). Similar, aproximaţia din ecuaţia 2.43 ce dă LLR-ul a-posteriori poate fi eliminat utilizând logaritmul Jaobian. Însă vor fi 2K-1 tranziţii de considerat în fiecare maximizare pentru ecuaţia 2.43. Atunci ecuaţia 2.44 trebuie generalizată cu scopul de a face faţă la mai mult de doi termeni. Aceasta se face prin gruparea operaţiilor g(x1, x2) după cum urmează:


II.15

ln

∑=

I

1i

x ie = g(xI, g(xI-1, ⋅⋅⋅, g(x3, g(x2, x1))) ⋅⋅⋅). (2.45)

Termenul de corecţie ƒc(δ) nu necesită să fie calculat pentru fiecare valoare a lui δ, ci poate fi stocat într-un tabel. Robertson ş.a. RVH] au găsit că un astfel de tabel trebuie să conţină doar opt valori pentru δ, cuprinse între 0 şi 5. Rezultă că algoritmul Log-MAP este cu puţin mai complex decât algoritmul Max-Log-MAP, dar el dă exact aceleaşi performanţe ca şi algoritmul MAP. 2.1.5 Algoritmul SOVA cu secvenţă memorată („up-date”)

Algoritmul Soft-Output Viterbi Algoritm (SOVA) prezintă două modificări faţă de algoritmul Viterbi clasic care-i permite să fie utilizat ca şi un decodor component pentru turbo-coduri. În primul rând metrica căii utilizate este modificată pentru a ţine cont de informaţia a-priori atunci când se selectează calea maxim plauzibilă prin trellis. În al doilea rând algoritmul este modificat, astfel încât furnizează o ieşire soft în forma LLR-ului a-posteriori L(uk/y) pentru fiecare bit decodat.

Pentru realizarea primei modificări se consideră secvenţa de stare sks care dă stările

de-a lungul căii supravieţuitoare până la starea Sk = s la stadiul k din trellis. Probabilitatea ca aceasta să fie calea corectă prin trellis este dată de:

≤kjy sp sk =

∧

≤

≤

kj

kjsk

yp

y sp (2.46)

Deoarece probabilitatea secvenţei recepţionate yj≤k pentru tranziţiile de după şi incluzând tranziţia k este constantă pentru toate căile sk prin trellis la stadiul k, probabilitatea ca să fie

aleasă sks cea corectă este proporţională cu

≤kjy sp sk . Dacă calea s

ks la stadiul k include

subcalea s1-ks pentru primele sale k-1 tranziţii, atunci, presupunând canalul fără memorie,

rezultă:

∧

≤kjsk y sp =

∧

≤− 1-kjs

1k y sp ⋅ p(Sk = s ∧yk | Sk-1 = ŝ). (2.47)

O metrică corespunzătoare pentru calea s

ks este atunci M( sks ), unde:

M( sks ) = ln

∧

≤kjsk y sp

= M( s1-ks ) + ln (p(Sk = s ∧yk | Sk-1 = ŝ)). (2.48)

Utilizând ecuaţia 2.19 avem: M( s

ks ) = M( s1-ks )+ ln (γk(ŝ,s)), (2.49)


II.16

unde γk(ŝ,s) este probabilitatea tranziţiei ramurii pentru calea de la Sk-1 = ŝ la Sk = s. Din ecuaţia 2.42 se poate scrie:

ln (γk(ŝ,s) = Γk(ŝ,s) =Ĉ + 21⋅uk⋅L(uk) + ∑

=⋅

n

1lklkl

c xy2

L, (2.50)

şi deoarece termenul Ĉ este constant, poate fi omis şi ca atare se poate rescrie ecuaţia 2.49 ca:

M( sks ) = M( s

1-ks ) + 21⋅uk⋅L(uk) + ∑

=⋅

n

1lklkl

c xy2

L, (2.51)

Metrica rezultată în SOVA este asemeni cu a algoritmului Viterbi cu un termen adiţional ukL(uk) inclus astfel încât se ţine seama de informaţia a-priori disponibilă. Aceasta este echivalentă cu recurenţa înainte din ecuaţia 2.40 utilizată pentru a calcula Ak(s) în algoritmul Max-Log-MAP.

Figura 2.7 Secţiune simplificată a trellisului pentru codul K=3 RSC cu decodare SOVA În continuare se prezintă a doua modificare necesară a algoritmului, adică de a da ieşire soft. În trellisul binar vor fi două căi ce sosesc în starea Sk = s la stadiul k din trellis. Algoritmul Viterbi modificat, ce ţine seama de informaţia a-priori ukL(uk), calculează metrica cu ecuaţia 2.51 pentru ambele căi concurente, şi ignoră calea cu metrica mai mică. Dacă cele două căi s

ks şi sks~ ce sosesc în starea Sk = s au metricile M( s

ks ) şi M( sks~ ), iar calea s

ks este selectată ca supravieţuitoare deoarece metrica sa este mai mare, atunci se defineşte diferenţa metricilor s

k∆ ca: s

k∆ = M( sks ) – M( s

ks ) ≥ 0, (2.52)

14k+∆

04k+∆0

3k+∆0

2k+∆0

1k+∆

Sk Sk+1 Sk+2 Sk+3 Sk+4

0k∆

34k+∆


II.17

Probabilitatea de a lua decizia corectă când s-a selectat calea sks ca supravieţuitoare şi s-a

ignorat sks~ este:

P(decizie corectă la Sk=s) = ( )

( ) ( )sk

sk

sk

sPsP

sP

+. (2.53)

Ţinând cont de definiţia metricii din ecuaţia 2.48 avem:

P(decizie corectă la Sk=s) = ( )

( ) ( )sk

sk

sk

sMsM

sM

ee

e

+

= sk

sk

e1

e∆

∆

+, (2.54)

iar LLR-ul că acesta este o decizie corectă este:

L(decizie corectă la Sk=s) = ln

==

s)S la acorect P(decizie-1s)S la acorect P(decizie

k

k(

(

= sk∆ . (2.55)

Figura 2.7 arată o secţiune simplificată a trellisului pentru codul K=3 RSC, cu diferenţele metricilor s

k∆ marcate la diferite puncte din trellis. Când se ajunge la sfârşitul trellisului şi s-a identificat calea Maxim Plauzibilă (ML) prin trellis, trebuie găsit LLR-ul ce dă încrederea deciziilor în lungul căii ML. Observaţiile algoritmului Viterbi au arătat că toate căile supravieţuitoare la stadiul j din trellis normal vin din aceeaşi cale de la acelaşi punct dinaintea lui j din trellis. Acest punct trebuie să fie la mai mult de δ tranziţii înainte de j, unde uzual δ este setat a fi de cinci ori lungimea de contrângere a codului convoluţional. Astfel valoarea bitului uk asociat cu tranziţia de la starea Sk-1= ŝ la starea Sk = s din calea ML poate fi diferit dacă, în loc de calea ML, algoritmul Viterbi a selectat o cale ce converge cu calea ML după δ tranziţii, adică după stadiul trellisului k+δ. Prin argumentările în discuţie, dacă algoritmul a selectat orice cale ce converge cu calea ML după acest punct, valoarea pentru uk nu va fi afectată deoarece astfel de căi vor diverge de la calea ML după tranziţia de la Sk-1= ŝ către Sk = s. Atunci, când se calculează LLR-ul pentru bitul uk, SOVA trebuie să ţină cont de probabilitatea de a fi fost incorect ignorate căile ce converg cu calea ML de la stadiul k+δ din trellis. Aceasta se face prin considerarea valorilor diferenţei metricii is

i∆ pentru toate stările si în lungul căii ML pentru stadiile trellisului de la i=k la i=k+δ. Hagenauer a văzut în [HAG] că acest LLR poate fi calculat prin: L(uk/y) ≈ uk i

ikk

si

uukki

min ∆

≠+⋅⋅⋅= δ

, (2.56)


II.18

unde uk este valoarea bitului dată prin calea ML, iar iku sunt valorile acestui bit pentru căile

ce converg cu calea ML şi au fost ignorate la stadiul trellisului i. Atunci această minimizare din ecuaţia 2.56 este făcută doar pentru acele căi ce converg cu calea ML ce ar fi dat o valoare diferită pentru bitul uk dacă ar fi fost selectate ca supravieţuitoare. Căile ce converg cu calea ML, dar ar fi dat aceeaşi valoare pentru uk ca şi calea ML, evident că nu afectează încrederea deciziei pentru uk. Pentru clarificarea acestor operaţii în Figura 2.7 se prezintă o secţiune simplificată a trellisului codului K=3 RSC. În această figură, liniile continue reprezintă tranziţii pentru bit de intrare de valoare –1, iar liniile întrerupte reprezintă tranziţii pentru bit de intrare de valoare +1. Presupunând că se identifică calea nulă cu calea ML, această cale se prezintă cu linie îngroşată. De asemenea se prezintă căile ce converg cu această cale ML. Se poate vedea din figură că această cale ML dă o valoare –1 pentru uk, iar căile ce coverg la calea ML în stadiile trellisului Sk, Sk+1, Sk+3 şi Sk+4 toate dau valoarea +1 pentru bitul uk. De aceea, dacă se presupune pentru simplitate că σ = 4, din ecuaţia 2.56 LLR-ul L(uk/y) va fi dat prin –1 multiplicat cu minimul diferenţelor metricilor 0

k∆ , 01k+∆ , 0

3k+∆ şi 04k+∆ .

Figura 2.8 Ieşirile soft comparative pentru algoritmii MAP şi SOVA pentru secvenţa emisă nulă

Implementarea SOVA „up-date” SOVA poate fi implementat după cum urmează. Pentru fiecare stare la fiecare stadiu din trellis se calculează metrica M( s

ks ) pentru ambele căi ce converg în respectiva stare utilizând ecuaţia 2.51. Calea cu metrica cea mai mare este selectată ca şi supravieţuitoare, iar pentru această stare, la acest stadiu din trellis, este memorat un indicator al stării anterioare de-a lungul căii supravieţuitoare, la fel ca şi în algoritmul Viterbi clasic. Însă, cu scopul de a permite calculul încrederii pentru biţii decodaţi, se memorează informaţia utilizată în ecuaţia 2.56 pentru a da L(uk/y). Astfel se memorează diferenţa s

k∆ dintre metricile căilor supravieţuitoare şi ignorate, împreună cu un vector ce conţine δ+1 biţi, ce indică dacă sau nu calea ignorată ar fi dat aceeaşi serie de biţi uj pentru j = k până înapoi la j = k–δ ca şi calea supravieţuitoare. Această serie de biţi se numeşte „up-date sequence” în [HAG], şi este dată


II.19

prin sumarea modulo 2 între cei δ+1 biţi decodaţi anteriori de-a lungul căilor supravieţuitoare şi ignorate. Când SOVA a identificat calea ML, secvenţa memorată şi diferenţele metricilor de-a lungul căii sunt utilizate în ecuaţia 2.56 pentru a calcula valorile L(uk/y). SOVA descris în această secţiune este cel mai puţin complex dintre toate decodoarele prezentate. Însă SOVA este de asemenea cel mai puţin precis dintre algoritmii descrişi, când este utilizat în turbo-decodor lucrează cu aproximativ 0,6 dB mai slab [RVH] decât decodarea ce utilizează algoritmul MAP. Figura 2.8 compară LLR-urile de ieşire de la decodoarele componente într-un decodor iterativ utilizând ambii algoritmi, MAP şi SOVA. Sunt utilizate acelaşi codor, secvenţă de intrare nulă (cu toţi pe –1), iar raportul semnal per zgomot al canalului a fost de 1 dB. Se poate vedea că ieşirile SOVA sunt semnificativ mai zgomotoase decât cele ale algoritmului MAP. Pentru al doilea decodor la a opta iteraţie algoritmul MAP dă LLR-uri ce sunt toate negative, şi de aceea nu există biţi eronaţi. Însă, se poate vedea din Figura 2.8 că, chiar după opt iteraţii, SOVA încă dă LLR-uri pozitive, şi de aceea va face câţiva biţi eronaţi. 2.1.6 Algoritmul SOVA bidirecţional Algoritmii de tip SOVA diferă în esenţă faţă de cei de tip MAP prin faptul că, în procesul de decodare, la SOVA se baleiază secvenţa recepţionată într-un singur sens şi în plus, operaţiile necesare decodării se fac asupra unei „ferestre de decodare” cu lungimea δ, de aproximativ cinci ori lungimea de constrângere a codului convoluţional utilizat. Pornind de la această observaţie şi de la aceea că recurenţele utilizate în algoritmul MaxLogMAP sunt identice cu cele ale algoritmului Viterbi, se poate concepe [VUJ] un algoritm de tip SOVA, numit aici bidirecţional, care să opereze asemeni algoritmului MaxLogMAP, însă doar pe o porţiune a secvenţei recepţionate limitată la două sub-blocuri, aşa cum se ilustrează în Figura 2.9. Avantajele unei astfel de proceduri sunt reducerea drastică a necesarului de memorie şi baleierea într-un singur sens (per ansamblu, binenţeles) a secvenţei recepţionate. Un dezavantaj faţă de algoritmul MaxLogMAP îl constituie şansa ca SOVA, într-o anume fereastră de decodare, să selecteze o cale ce nu coincide cu cea maxim plauzibilă de la MaxLogMAP. Ca atare este de aşteptat ca acest algoritm să prezinte performanţe mai slabe decât algoritmul MaxLogMAP. 2.1.7 Informaţia extrinsecă

În această secţiune se explică conceptele de informaţie intrinsecă şi extrinsecă aşa cum au fost utilizate de Berrou ş.a. [BGT].

Deoarece se lucrează cu coduri sistematice, unul din n biţi transmişi va fi bitul sistematic uk. Dacă se presupune că acest bit sistematic este primul din cei n biţi transmişi, atunci xk1= uk, iar ecuaţia 2.33 se poate rescrie ca:

γk(ŝ,s) = C )2/)L(u( ke ku⋅ ⋅

kks

c uy2

Lexp ⋅

⋅∑

=

n

2ikiki

c xy2

Lexp

= C )2/)L(u( ke ku⋅ ⋅

kks

c uy2

Lexp ⋅χk(ŝ,s), (2.57)

unde yks este versiunea recepţionată a bitului sistematic transmis xk1= uk şi:

χk(ŝ,s) =

⋅∑

=

n

2ikiki

c xy2

Lexp . (2.58)


II.20

Figura 2.9 Desfăşurarea algoritmului SOVA bidirecţional Utilizând ecuaţia 2.57 şi reamintind că la numărător avem uk = +1 pentru toţi termenii din sumă, în vreme ce la numitor avem uk = −1, ecuaţia 2.35 se poate scrie ca:

L(uk|y) = ln

( ) ( ) ( )

( ) ( ) ( )

⋅⋅

⋅⋅

∑

∑

−=⇒

+=⇒

1us),s(

1-k

1us),s(

1-k

k

k

ss,ss

ss,ss

kk

kk

βγα

βγα

Sub-bloc 1

0 D 2D 3D 4D

Sub-bloc 1 Sub-bloc 2 Sub-bloc 3 Sub-bloc 4

0 D 2D

0 D 2D

0 D

Sub-bloc 2

D 2D 3D

D 2D 3D

D 2D

Sub-bloc 3

2D 3D 4D

2D 3D 4D

2D 3D

Recurenţa înainte

Recurenţa înapoi

Ieşirea decodorului

Recurenţaînainte

Recurenţaînapoi


Recurenţa înainte

Recurenţa înapoi



II.21

= ln

( ) ( ) ( ) ( )

( ) ( ) ( ) ( )

⋅⋅⋅⋅

⋅⋅⋅

∑

∑

−=⇒

+=⇒

++

1us),s(

2/yL-2/uL-1-k

1us),s(

2/yL2/uL1-k

k

ksck

k

ksck

ss,sees

ss,sees

kk

kk

βχα

βχα

= L(uk) + Lcyks + ln

( ) ( ) ( )

( ) ( ) ( )

⋅⋅

⋅⋅

∑

∑

−=⇒

+=⇒

1us),s(

1-k

1us),s(

1-k

k

k

ss,ss

ss,ss

kk

kk

βχα

βχα

= L(uk) + Lcyks + Lc(uk), (2.59) unde:

Lc(uk) = ln

( ) ( ) ( )

( ) ( ) ( )

⋅⋅

⋅⋅

∑

∑

−=⇒

+=⇒

1us),s(

1-k

1us),s(

1-k

k

k

ss,ss

ss,ss

kk

kk

βχα

βχα

. (2.60)

Astfel se poate vedea că LLR-ul a-posteriori L(uk/y) calculat cu ajutorul algoritmului MAP poate fi privit ca o sumă de trei termeni „soft-metric”: – L(uk), Lcyks şi Lc(uk). Primul termen metrică-soft este LLR-ul a-priori L(uk), care provine din P(uk) din expresia pentru probabilitatea tranziţiei ramurii γk(ŝ,s) în ecuaţia 2.25. Această probabilitate poate fi generată printr-o sursă independentă şi este numită probabilitate a-priori pentru al k-ulea bit de informaţie, sau sistematic, reprezentat ca +1 sau –1, aşa cum se ilustrează în Figura 2.10. În cazul când nu există o informaţie independentă sau a-priori asupra valorii plauzibile a bitului uk la decodor, LLR-ul a-priori L(uk) va fi zero în domeniul logaritmic, corespunzător unei probabilităţi a-priori pentru P(uk) = 0,5. Însă, în cazul unui decodor turbo iterativ, fiecare decodor component este capabil să furnizeze celuilalt un estimat al LLR-ului a-priori L(uk), aşa cum se prezintă în continuare. Termenul secund Lcyks din ecuaţia 2.59 este ieşirea soft a canalului reprezentând bitul sistematic uk, care a fost transmis direct prin canal şi recepţionat ca şi yks. Cu alte cuvinte, acest termen corespunde biţilor sistematici transportaţi de canal şi valorilor LLR extrinseci arătate în Figura 2.10. Atunci când SNR-ul canalului este mare, valoarea de încredere Lc a canalului, din ecuaţia 2.11 va fi mare iar acest bit sistematic va avea o influenţă mare asupra LLR-ului a-posteriori L(uk/y). În schimb, când SNR-ul canalului este mic şi deci Lc este scăzut, ieşirea soft a canalului pentru bitul sistematic yks va avea un impact mic asupra LLR-ului a-posteriori generat prin algoritmul MAP. Ultimul termen din ecuaţia 2.59, Le(uk), derivă prin constrângerile impuse de codul utilizat, din secvenţa de informaţie a-priori L(uk) şi din secvenţa de informaţie recepţionată din canal y, excluzând bitul sistematic recepţionat yks, şi informaţia a-priori L(uk) pentru bitul uk. De aceea se numeşte LLR extrinsec pentru bitul uk. Figura 2.10 şi ecuaţia 2.59 demonstrează că informaţia-soft extrinsecă despre un anume bit şi generată prin decodorul MAP poate fi obţinută prin scăderea valorii informaţiei-soft a-priori L(uk) şi a ieşirii-soft sistematice recepţionate a canalului reprezentând bitul sistematic uk –numită Lcyks–


II.22

Figura 2.10 Schema decodorului component al turbodecodorului din ieşirea-soft L(uk/y) a decodorului. În Figura 2.11 se prezintă schema completată a unui turbodecodor cu liniile de scădere necesare obţinerii informaţiei extrinseci. Concluzionând, înţelesurile termenilor de informaţie a-priori, extrinsecă şi a-posteriori sunt: a-priori Informaţia a-priori despre un bit este informaţia cunoscută înainte de a începe

decodarea, dintr-o sursă alta decât secvenţa recepţionată sau constrângerile codului. extrinsecă Informaţia extrinsecă despre bitul uk este informaţia furnizată de decodor bazată

pe secvenţa recepţionată şi pe informaţia a-priori, dar excluzând bitul sistematic recepţionat yks şi informaţia a-priori L(uk) despre bitul uk. Decodorul component furnizează tipic această informaţie utilizând constrângerile impuse secvenţei transmise prin codul utilizat. Biţii recepţionaţi şi informaţia a-priori se procesează ocolind bitul sistematic uk. Această informaţie cât şi constrângerile de cod se utilizează pentru a furniza informaţia despre valoarea bitului uk.

a-posteriori Informaţia a-posteriori despre un bit de informaţie este cea generată de decodor ţinând cont de toate sursele de informaţie disponibile cu privire la uk. Este acel LLR a-posteriori, L(uk/y), pe care-l generează algoritmul la ieşirea sa.

Figura 2.11 Schema completă a turbo-decodorului

Informaţia extrinsecă

Decodor

sistematic Informaţia extrinsecă combinată cu a canalului

informaţia a-priori

informaţia a-posteriori

Decodor component

1

Ieşirea soft a

canalului

Decodor component

2

sistematic

Dispozitiv de

întreţesere

Dispozitiv de

întreţesere

Dispozitiv de

de-întreţesere

paritate 1

paritate 2

Lcyks

Lcykl

Lcyks

Lcykl

Le(uk)

Le(uk)

L(uk)

L(uk/y)

L(uk)

L(uk/y)


II.23

2.2 Întreţeserea 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.61) 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∈I. (2.62) 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 = )x()(x min i1i

iππ −+ . (2.63)

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 [JEZ]. 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. Dispozitivele de întreţesere de tip „regulat” au dmin de valori foarte mari, în schimb cele de tip „aleator” oferă o bună împrăştiere. În continuare se prezintă câteva dintre cele mai frecvente dispozitive de întreţesere utilizate în schemele de turbo-coduri. 2.2.1 Dispozitiv de întreţesere aleator

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ă. În Figura 2.12 este ilustrată operaţia de întreţesere (permutarea) de tip aleator pentru un bloc de date de lungime N=10. Procedeul de construcţie al unui dispozitiv de întreţesere aleator, implementat prin programul MATLAB ilvA.m din Anexa B, este următorul. Cunoscând lungimea secvenţei originale, N, (care este implicit şi lungimea de întreţesere) se construieşte mulţimea A = {1,2 ...N}. Se alege în mod aleator un număr, n1∈A. Se atribuie π(1) = n1 şi se elimină această valoare din A. Procedeul se repetă până la epuizarea mulţimii A. Alegerea „aleatoare”, în MATLAB se face cu ajutorul funcţiei rand. Această funcţie generează numere aleatoare cu distribuţie uniformă în intervalul [0, 1]. Teoretic se pot genera 14922 valori fără a se repeta nici una dintre ele [GHF].


II.24

1 2 3 4 5 6 7 8 9 10

)8(π )1(π

8 7 2 10 4 3 6 9 5 1 Date de ieşire (permutate)

Date de intrare )2(π )9(π Figura 2.12 Întreţeserea aleatoare

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ă.

Figura 2.13 Întreţesere bloc (rectangulară)

Citire pe coloane, în ordinea: 1 2 3 . . . . . 10

Înscriere pe linii

în ordinea:1

2

3

.

.

.

.

.

10


II.25

4.1.2 Dispozitiv de întreţesere bloc Denumit şi rectangular, dispozitivul de întreţesere bloc este primul tip utilizat în

schemele de turbocoduri, prezentând cea mai simplă structură. În Figura 2.13 este prezentat un dispozitiv de întreţesere bloc (rectangular) având lungimea N=10x10. 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.

Programul de generare a unui dispozitiv de întreţesere rectangular, prezentat în Anexa B, este „ilvR.m”. 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. 2.2.3 Dispozitiv de întreţesere 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 [BAK]. În Figura 2.14 este ilustrat procesul de întreţesere diagonală pentru o matrice pătratică de dimensiuni 10 x 10.

Programul MATLAB ce implementează o întreţesere de tip diagonal, prezentat în Anexa B, este „ilvD.m”.

La fel ca şi pentru dispozitivul de întreţesere rectangular şi în cazul celui diagonal se poate utiliza un procedeu de amestecare a diagonalelor. Figura 2.14 Întreţesere diagonală

11 . . . . . 18 19 20

Citire pe diagonală, în ordinea: 10 9 . . . . . 4 3 2 1

Înscriere pe linii

în ordinea:1

2

3

.

.

.

.

.

10


II.26

2.2.4 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 2.15.

Figura 2.15 Î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]:

• 2mod)1( −= sm

•

−=

221

ksi

• 221 iksj −

−

=

• )119( += it mod21k

• tq = mod 18 + • )21( mjpc q +⋅= mod 2k

0110101000…010000011001001110100 1110110101…001001100010001101001 1010001100…100010011101100101110 1100101000…110011000010101001011 0111101000…010000111001111010101 0100010101…001001100010101101001 1010001100…100010001101100111110 1100101000…110011000000101001001 ………………………………………….. 0100101011…110011010011001001010 1110101010…010110011001011010110 0100010101…001001100010101101001


II.27

• )(sπ mNct −++

+= )12

1(2

în care [ ] – parte întreagă mod – operaţie modulo (clase de resturi) q = 1÷8 şi 1p =31, 2p =37, 433 =p , 474 =p , 535 =p , 596 =p , 617 =p ,

678 =p . Pe baza acestui algoritm s-a construit programul de generare a funcţiei de întreţesere

pseudo-aleatore, prezentat în Anexa B, „ilvP.m”. 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]. 2.2.5 Dispozitiv de întreţesere de tip “S” (S-interleaver)

Dispozitivul de întreţesere de tip “S” este de tip aleator, însă, spre deosebire de cel pur aleator, prin construcţie se forţează o distanţă minimă de întreţesere egală cu S. Algoritmul de construcţie al funcţiei de întreţesere este următorul: se selectează o posibilă poziţie viitoare pentru bitul curent. Această poziţie este comparat cu a celor S biţi selectaţi anterior în aceeaşi manieră aleatoare. Dacă se îndeplineşte condiţia ca: )()( jn ππ − > S pentru n şi j cu proprietatea jn − < S (2.64) adică poziţia după interschimbare a bitului curent diferă cu S poziţii faţă de a celor S alese anterior, atunci se trece mai departe. Dacă condiţia nu va fi îndeplinită, se alege o altă poziţie a bitului curent, care va fi la rândul său testată. Procesul se va repeta până când s-au găsit

poziţiile tuturor celor N biţi. Simulările pe computer au demonstrat că, dacă 2NS ≤ , atunci

procesul va converge [SSS]. Proiectarea acestor echipamente este dificilă pentru că, după ce o mare parte a

algoritmului a fost parcursă, este din ce în ce mai greu din punct de vedere probabilistic să se genereze numere aleatoare din cele rămase în secvenţă care să îndeplinească cerinţa (2.64). Pentru a elimina pericolul apariţiei unei bucle infinite atunci când algoritmul eşuează, soluţia este reducerea lui S în mod progresiv [PHA].

Dispozitivul de întreţesere de tip “S” oferă foarte bune performanţe.

2.3 Puncturarea 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. La recepţie, în locul biţilor şterşi se inserează zerouri, iar în algoritmul de decodare nu se ţine seama de de valoarea acestor biţi (în calculul coeficienţilor γ pentru algoritmi de tip MAP, sau în calculul metricilor de cale pentru algoritmii de tip SOVA). Practic termenii corespunzători lipsesc din relaţiile respective. De obicei puncturarea se face asupra biţilor de paritate, astfel încât la decodare nu mai este necesar să se restabilească valorile acestora, decât în cazul în care o cere configuraţia turbocodului.


II.28

Cu toate că se pot construi coduri pentru orice rată de codare impusă, puncturarea este procedeul prin care orice cod, având o anumită rată de codare R se poate utiliza la o rată R’>R.

2.4 Decodarea optimală a turbocodurilor. Super-trellisul Algoritmii iterativi de tip SISO prezentaţi în paragraful anterior nu sunt optimali, în sensul că nu caută „cuvântul” de turbocod emisibil cu probabilitate maximă, cunoscută fiind secvenţa recepţionată. În acest paragraf este prezentată pe scurt o metodă neiterativă şi optimală de decodare a turbocodurilor. Din nefericire, însă, complexitatea acestei metode depinde esenţial de tipul dispozitivului de întreţesere, încât ea poate fi aplicată doar pentru dispozitive de întreţesere foarte simple, şi, ca atare, neeficiente [HLY]. Metoda de decodare optimală anunţată are la bază construcţia unui super-trellis pentru turbocod şi căutarea prin acest super-trellis a super-căii maxim plauzibile, asemeni algoritmului Viterbi clasic prin trellisul definit pentru un cod convoluţional în sensul său clasic.

O diferenţă importantă între codurile convoluţionale convenţionale şi turbocoduri este că procesul de decodare pentru ultimul nu este secvenţial. Efectul schimbării unui simbol într-o parte a cuvântului de cod turbocodat va afecta căile posibile nu doar în această parte, ci şi în părţile depărtate ale cuvântului de cod. Acest fapt se datorează întreţeserii existente între codoarele componente ale turbocodorului. În Figura 2.16 sunt prezentate stilizat trellisurile celor două coduri componente ale unui turbocod paralel al cărui dispozitiv de întreţesere este rectangular, cu doar două linii (face separaţie par-impar). Astfel se observă că biţii de date sunt furnizaţi primului codor în ordinea lor iniţială, iar celui de-al doilea îi sunt furnizaţi prima dată biţii impari şi ulterior cei cu număr de ordine par. Este uşor de văzut că, pe vreme ce sunt furnizaţi biţi de intrare, aceştia determină creşterea (evoluţia) trellisurilor spre dreapta, în mod constant la cel de sus şi alternativ la cele două secţiuni a trellisului de jos.

Figura 2.16 Trellisurile codurilor componente turbocodului paralel cu dispozitiv de întreţesere rectangular par-impar

Tranziţia nr.: 1 2 3 4 n1 n1+1 n1 +2 n1 +3

Intrarea pentru C2: u1 u3 u5 u7 u2 u4 u6

Tranziţia nr.: 1 2 3 4 5 6 7

Intrarea pentru C1: u1 u2 u3 u4 u5 u6 u7

Trellisul pentru C1

Trellisul pentru C2


II.29

I-ul trellis component (1)

0S (1)1S (1)

2S (1)3S (1)

4S (1)5S

Al II-lea trellis component (2)

0S (2)1S (2)

2S (2)3S (2)

K/2S (2)1K/2+S

(2)2K/2+S

Figura 2.17 Tranziţiile trellisurilor celor două coduri componente până la momentul t = 5

Cu alte cuvinte, dacă în cazul unui cod convoluţional clasic, un bit de intrare în codor determină o singură tranziţie în trellis între două stări ale codorului, în cazul turbocododului un bit de intrare determină mai multe tranziţii în trellisurile codurilor componente.

Pornind de la această observaţie se poate gândi drept „super-stare” mulţimea tuturor terminaţiilor secţiunilor deschise ale trellisurilor componente, iar în acest context, „super-trellisul” turbocodului va fi şirul evoluţiilor în timp ale super-stărilor. În Figura 2.17 se prezintă evoluţia trelisurilor codurilor componente până la momentul t = 5. Conform definiţiei de mai sus, super-starea din acest moment a super-trellisului este:

Intrarea:

Starea:

U1 U2 U3 U4 U5

...

Intrarea:

Starea:

U1 U3 U5

... ... ...

U2 U4


II.30

S5 = ( )1(5S ; )2(

3S ; )2(2/KS ; )2(

22/ +KS ), (2.65) unde K reprezintă numărul de biţi ai secvenţei de date. Această metodă de decodare a tubocodurilor, cu toate că este optimală, ea nu poate fi aplicată practic în conjuncţie cu orice tip de dispozitiv de întreţesere datorită complexităţii excesive. Complexitatea în discuţie este dată de numărul de super-stări. În [WLY] se dă o limită superioară a numărului de super-stări atât pentru cazul unui turbocod cu dispozitiv de întreţesere rectangular cât şi pentru cazul unui turbocod cu dispozitiv de întreţesere aleator.

2.5 Performanţe. Concluzii Turbocodurile convoluţionale formează una dintre cele mai puternice categorii de coduri corectoare de erori. Performanţele acestora depind de mai mulţi factori. Aceştia sunt: – tipul, sistematic sau nesistematic, recursiv sau nerecursiv al codului convoluţional component. Cele mai bune performanţe se dovedesc a avea cele recursive şi sistematice (RSC). – configuraţia turbocodului. Configuraţiile de bază sunt paralelă, serială şi hibridă (vezi paragrafele 1.3 şi 1.4). La rapoarte semnal per zgomot mici cele mai bune performaţe sunt date de turbocoduri în configuraţii seriale iar la rapoarte semnal per zgomot medii şi mari configuraţia paralelă furnizează cele mai bune rezultate. – rata de codare intrinsecă şi gradul de puncturare. Prin rată de codare intrinsecă se înţelege rata de codare a turbocodorului, excluzând eventualele operaţii de puncturare. Firesc, cu cât rata de codare globală (eficienţa codării) este mai mică, cu atât redundanţa şi implicit puterea de corecţie a turbocodului cresc. Un fapt remarcabil este că la eceeaşi rată de codare globală, un turbocod puncturat este mai slab în performanţă decât un cod concatenat multiplu (de exemplu turbocodurile duo-binare). Însă o comparaţie veridică trebuie să includă în discuţie şi polinoamele generatoare ale codurilor convoluţionale comparate, deoarece acestea nu pot fi aceleaşi pentru coduri de rate intrinseci diferite. – polinomul (polinoamele) generator al codului convoluţional component. Dintre polinoamele generatoare de acelaşi grad posibile, ce constituie reacţia codorului, cele mai bune performanţe sunt obţinute cu polinoame primitive (este şi cazul codorului din Figura 2.1). Evident, performanţa creşte odată cu creşterea gradului polinomului generatoar (egal cu lungimea de constrângere minus unu), însă creşte de asemenea şi complexitatea, încât practic sunt acceptate lungimi de constrânge de până la 6. – tipul dispozitivului de întreţesere. Un bun interleaver trebuie să aibă distanţă minimă de întreţesere cât mai mare şi, de asemenea, să ofere o „împrăştiere” cât mai bună. În Figura 2.18 se prezintă spectrele distanţelor pentru dispozitivele de întreţesere rectangular (cu dimensiunea 32 × 32) şi pseudo-aleator (cu dimensiunea 1000). Se observă superioritatea ultimului din punct de vedere al împrăştierii.


II.31

a) dispozitiv de întreţesere rectangular de dimensiune 32 × 32 b) dispozitiv de întreţesere pseudo-aleator de dimensiune 1000

Figura 2.18 Spectrele distanţelor (dinainte + de după întreţesere) între perechi de biţi

– lungimea blocului de date dă implicit şi lungimea interleaverului, care este de dorit a fi (pentru o bună performanţă BER) cât mai mare. Însă lungimi de întreţesere mari implică întârzieri mari, ce nu pot fi acceptate în multe aplicaţii practice. Lungimile practicate în aplicaţiile uzuale sunt cuprinse între 100 şi 3000.


II.32

– algoritmul de decodare utilizat. Algoritmii de decodare utilizabili practic sunt cei iterativi, prezentaţi în paragraful 2.1. Între aceştia cel mai performant, din punct de vedere strict al ratei erorii, este algoritmul MAP (Maximum A-Posteriori), însă totodată este şi cel mai dificil de implementat practic. O alternativă la algoritmul MAP, atractivă pentru aplicaţiile practice, având aproape aceleaşi performanţe, este algoritmul LogMAP. Algoritmul MaxLogMAP este o variantă şi mai simplu de implementat, însă sesizabil mai puţin performant. La algoritmii de tip SOVA există avantajul independenţei volumului de memorie necesar faţă de lungimea blocului de date. În plus şi volumul calculelor implicate este cel mai mic. Preţul este binenţeles o degradare a performanţei. – numărul de iteraţii şi criteriul de stop al iteraţiilor. Relativ la numărul de iteraţii se poate remarca un efect („turbo”) puternic pentru primele. Pe vreme însă ce procesul turbo evoluează, îmbunătăţirea adusă este tot mai scăzută, încât după practic opt iteraţii efectul turbo este neglijabil. Astfel, pentru a eficientiza procesul decodării turbo-iterative, se poate recurge la oprirea şirului iteraţiilor înainte de numărul fixat, utilizând un criteriu de stop. Un astfel de criteriu ar putea fi identitatea semnului LLR-ului după două iteraţii consecutive. O altă procedură de stopare a iteraţiilor (şi implicit al procesului turbodecodării) ar fi utilizarea unui cod ciclic detector de erori. Atunci când acest cod afirmă absenţa erorilor din blocul în curs de decodare se poate opri decodarea. În Figura 2.19 sunt prezentate câteva curbe BER obţinute prin simulări cu ajutorul programelor prezentate în anexe. În toate cazurile a fost utilizat un cod convoluţional având G=[1, (1+D2)/(1+D+D2)], cu o structură paralelă a turbocodului (Figura 1.2). Rata de codare a fost R=1/3 (fără puncturare) iar numărul de blocuri transmise a fost nb=5000. Secvenţa de date a fost aleatoare iar zgomotul AWGN. Modulaţia utilizată: BPSK. Ceilalţi parametri ai simulărilor sunt indicaţi în figură.


II.33

Performanţa BER: a) sistem necodat; b) MAP, d.î. pseudo-aleator(1000); c) MAP, d.î. rectangular(32,32); 5000 blocuri, 8 iteraţii

Comparaţie între algoritmii de decodare descrişi în paragraful 2.1. 5000 blocuri, d.î. pseudo-aleator (1000), 8 iteraţii

Figura 2.19

Raport semnal per zgomot (dB)

Rar

a er

orii

(BER

)

necodat

MAP LogMAP

MaxLogMAPSOVA “up-date”

SOVA bidirecţional

Rar

a er

orii

(BER

)

Raport semnal

per zgomot(dB)

a)

b)

c)


III.1

3. Turbocoduri bloc 3.1 Trellisul codurilor bloc O alternativă a utilizării codurilor convoluţionale în turbocoduri, ca şi coduri componente, o reprezintă codurile bloc şi în special codurile BCH [HLY]. Codurile BCH sunt cele mai reprezentative coduri bloc binare. În [BAH] s-a făcut o descriere detaliată a generării şi decodării codurilor BCH. a) schema; b) semnalele de comandă;

Figura 3.1 Codor BCH(7,4,1) cu g(x)=1+x+x3

D D D

P2

P1

i v

t/T

0 1 2 3 4 5 6 7 8 t/T

P1

P2


III.2

Figura 3.2 Trellisul codului BCH(7,4,1) cu g=138, din Figura 3.1 Pentru a putea fi utilizate în schemele de turbocoduri este necesar ca şi pentru codurile bloc (BCH) să se implementeze algoritmi de decodare de tip SISO. Funcţionarea acestor algoritmi, în cazul codurilor convoluţionale, are la bază o căutare prin trellis. Rezultă, ca atare, necesitatea construirii trellisului şi pentru codurile BCH, fapt uşor de realizat datorită asemănării între codoarele convoluţionale şi codoarele BCH. În Figura 3.1 se prezintă schema unui codor BCH(7,4,1) iar în Figura 3.2 trellisul său corespunzător. Deoarece memoria codorului este m=3, trellisul conţine un număr maxim de stări M=2m=8 şi un număr maxim de tranziţii între aceste stări 2M=16. Însă, aşa cum se vede în Figura 3.2, doar la pasul 3 sunt permise toate aceste stări şi tranziţii. Aceste 16 tranziţii de la pasul 3 sunt corespondente celor 16 cuvinte de cod posibile ale codului dat (ramurile cu linie continuă corespund unui bit de valoare 1 iar cele cu linie întreruptă corespund unui bit de valoare 0). De remarcat identitatea dintre codorul acestui cod şi codorul codului convoluţional recursiv având matricea generatoare G=1/(1+D+D3). Mai mult, dacă codorul convoluţional codează doar secvenţe de lungime N=k=4 şi în plus face terminaţie (adaugă m=n-k=3 biţi pentru a reseta codorul), atunci cele două coduri devin identice. Identitatea celor două coduri este un fapt deosebit de important deoarece justifică decodarea turbo a codurilor BCH în exact aceeaşi formă ca şi pentru cele convoluţionale. 3.2 Turbocoduri bloc Concatenarea codurilor bloc s-a practicat şi înainte de apariţia turbocodurilor, sub formă de coduri produs (Figura 3.3a). Scopul unei astfel de concatenări este de a construi un cod corector mai puternic utilizând două coduri mai puţin performante. Astfel dacă cele două

0 1 2 3 4 5 6 7000 001 010 011 100 101 110 111


III.3

a) cod produs; b) cod concatenat paralel

Figura 3.3 Construcţia codurilor produs şi a codurilor concatenate paralel coduri componente au distanţele de cod corespunzătoare d1 şi d2, codul produs rezultat va avea o distanţă minimă d=d1xd2 (putând corecta ec=(d-1)/2 erori). Codul rezultat printr-o turbocodare (Figura 3.4) ce utilizează două coduri bloc ca şi coduri componente, numit cod concatenat paralel sau turbocod bloc, se deosebeşte de un cod produs prin două aspecte. În primul rând, aşa cum se vede din Figura 3.3, cele două (codul produs şi turbocodul bloc) diferă prin structura secvenţei codate. Codul concatenat paralel (turbocodul) nu generează biţi de control pentru biţii de control rezultaţi prin codarea biţilor de informaţie, aşa cum procedează codul produs. În acest fel distanţa minimă a turbocodului este d1+d2–11, iar rata de codare este (k1⋅k2)/[n1⋅n2 –(n1 –k1)⋅(n2 –k2)] faţă de (k1⋅k2)/(n1⋅n2) pentru codul produs. Cea de-a doua diferenţă dintre codul produs şi turbocodul bloc este întreţeserea. Aşa cum se vede din Figura 3.4, secvenţa de informaţie, înainte de a fi codată prin C2, este întreţesută. Această întreţesere permite ca şi cel de-al doilea cod să codeze tot pe linie (sau tot pe coloană) asemeni lui C1. Blocul de puncturare din componenţa codorului are rolul de a elimina (şterge) biţii sistematici (de informaţie) generaţi de codorul C2, în scopul de a obţine rata de codare mai sus definită. În acest fel, în canal se trimit biţii sistematici generaţi prin C1 urmaţi de biţii de control (paritate) generaţi de ambele codoare, multiplexaţi.

Figura 3.4 Schema turbocodorului bloc 1 pentru calculul distanţei minime se consideră că blocul de informaţie, având dimensiunile k1⋅k2 este de pondere unu. Acest unu va genera pe linie, prin biţii de control generaţi de codul C1, o pondere minimă d1–1, iar pe coloană, prin biţii de paritate generaţi de C2, o pondere minimă d1–1,. Cumulând, avem că d=1+d1–1+d1–1.

k1 n1–k1

k2 n1–k2

k1 n1–k1

k2 n1–k2

Codor BCHC1

Codor BCHC1

Dispozitiv de întreţesere

Puncturare şi

multiplexare

Intrare

Ieşire


III.4

3.3 Turbodecodorul În Figura 3.5 este prezentată structura unui turbodecodor bloc. Funcţionarea acestuia este descrisă în continuare. Din secvenţa de intrare (generată la ieşirea canalului) se reconstituie secvenţele: cea sistematică (de informaţie), provenită din C1, cât şi cele de control (de paritate) –generate de ambele codoare. Din secvenţa sistematică provenită din canal, prin întreţesere, se obţine secvenţa sistematică corespunzătoare lui C2 (ştearsă la emisie). În acest fel s-au recompus secvenţele –cuvinte de cod BCH– recepţionate, în forma „soft” necesară decodării SISO (secvenţele notate yk1 şi yk2 în Figura 3.5). În vederea calculului coeficienţilor gama, în cazul algoritmilor de tip MAP, ori a calcului metricilor ramurilor de la algoritmul SOVA, intrările yk1 şi yk2 trebuiesc multiplicate cu coeficientul de încredere al canalului, Lc. Implementând unul dintre algoritmii definiţi în capitolul precedent, fiecare dintre decodoarele din componenţa turbodecodorului, utilizând secvenţele Lc⋅yk1 sau Lc⋅yk2 cât şi informaţia extrinsecă generată de celălalt decodor, calculează la rândul lor, informaţie extrinsecă şi logaritmul raportului de plauzibilitate (LLR), într-un proces iterativ descris de asemenea în capitolul precedent. După efectuarea tuturor iteraţiilor necesare se face o decizie hard asupra LLR-lui generat de unul dintre decodoare (decodorul BCH1, în Figura 3.5). Secvenţa binară rezultată prin această decizie reprezintă ieşirea turbodecodorului.

Figura 3.5 Turbo-decodor BCH

Decodor BCH

1

Decodor BCH

2

Dispozitiv de

întreţesere

Dispozitiv de

de-întreţesere

intrare

ieşire

Lc

yk2

Le(uk)

Le(uk)

L(uk)

L(uk/y)

L(uk)

L(uk/y)

Decizie hard

Demultiplexare şi

întreţesere

Lc

yk1


IV.1

4. Interfaţă grafică în MATLAB pentru simularea funcţionării turbocodurilor convoluţionale

4.1 Prezentare generală Simularea funcţionării turbocodurilor convoluţionale prezentate în capitolul 2 s-a realizat printr-un set de programe MATLAB ce sunt listate în anexele aferente acestui referat. Apelarea acestor programe se poate face printr-o interfaţă grafică ce va fi prezentată în continuare, iar în paragraful 4.4 se va indica modul în care pot fi utilizate programele menţionate şi pentru opţiuni ce nu sunt cuprinse în cadrul interfeţei. Programul ce crează interfaţa este „tccGUI.m”. Pentru a putea utiliza interfaţa este necesar a dispune toate programele aferente într-o cale de căutare a MATLAB-ului. Versiunea de MATLAB sub care au fost create aceste programe este 6.1.

Figura 4.1 Interfaţă grafică pentru simularea funcţionării turbocodurilor –imaginea de start


IV.2

Interfaţa grafică propriuzisă este o imagine (fereastră) ce apare pe ecranul monitorului la apelarea (în fereastra MATLAB-ului) a funcţiei „tccGUI.m”. Această imagine este prezentată în Figura 4.1 şi în Planşele 1 şi 2. Interfaţa grafică permite:

a) selecţia opţiunilor pentru definirea turbocodului ce urmează a fi simulat. Aceste opţiuni sunt prezentate în paragraful următor;

b) prezentarea graficelor schemei codorului component, a trellisului codului şi a configuraţiei turbocodului pentru turbocodul definit prin opţiunile alese, cât şi a densităţii de probabilitate a eşantioanelor semnalului recepţionat condiţionate de emisia unui unu, respectiv zero;

c) simularea funcţionării turbocodului definit prin opţiunile alese anterior; d) prezentarea rezultatelor simulării. Acestea sunt: –date numerice (numărul total de

erori, numărul de erori rămase necorectate după decodare, rata erorii rezultate –BER, câştigul de codare); –două imagini ce simbolizează secvenţele recepţionată şi decodată; –graficul densităţii de probabilitate al logaritmului raportului de plauzibilitate;

e) afişarea unor succinte comentarii care indică detalii şi parametrii neprecizaţi prin opţiuni despre turbocod şi simularea funcţionării sale.

Simularea transmisiei presupune parcurgerea următoarelor etape, gestionate de către interfaţă:

1. generarea unei secvenţe binare de date. Secvenţa generată este o secvenţă binară pseudo-aleatoare având o lungime totală N⋅nb, unde N este lungimea unui bloc de date iar nb numărul de blocuri;

2. turbo-codarea secvenţei generate. Prin codare, turbocodorul paralel (Figura 1.3) cât şi cel hibrid (Figura 1.6b) generează trei secvenţe de aceeaşi lungime N⋅nb. Prima dintre aceste trei secvenţe este identică cu cea de date. A doua secvenţă este constituită din biţii de control obţinuţi prin codarea efectuată de primul codor C1. Cea de-a treia este secvenţa de biţi de control generaţi de C2 prin codarea secvenţei de date întreţesută, pentru cazul paralel, şi respectiv prin codarea secvenţei generate de C1 întreţesută, în cazul hibrid.

Observaţii: Întreţeserea se efectuează asupra biţilor dintr-un bloc, altfel spus simularea se repetă identic de nb ori şi este independentă de la un bloc la altul. Fiecare bloc apare ca şi o secvenţă de biţi de informaţie din care, prin codare, se obţine un cuvânt de turbo-cod. Indiferent de configuraţia turbo-codului, primul codor, C1, face terminaţie. În acest scop se elimină ultimii m (lungimea de constrângere –1) biţi din secvenţa de date a blocului ce se va coda, ei fiind aleşi prin procesul de codare încât starea finală a codorului să fie nulă. Acest procedeu nu este posibil, şi, ca atare, nu-l execută şi C2, datorită întreţeserii.

În cazul turbocodului serial (Figura 1.5), secvenţa de date împreună cu cea rezultată prin codarea efectuată de C1 sunt multiplexate astfel încât rezultă o secvenţă de lungime totală 2⋅N⋅nb, adică nb blocuri, fiecare de lungime 2⋅N. Fiecare bloc este întreţesut (separat de celelalte) iar secvenţa rezultată este codată prin C2, astfel că turbocodul serial generează două secvenţe de lungime 2⋅N⋅nb fiecare (secvenţele de la intrarea şi ieşirea lui C2).

Concluzionând: rata de codare este R=1/3 în cazurile paralel şi hibrid şi R=1/4 în cazul serial.

3. modularea secvenţei codate. Modulaţia utilizată este BPSK, astfel încât aceasta poate fi sintetizată prin relaţia:

secvenţa modulată = 2⋅ secvenţa codată –1. (4.1)


IV.3

Cu alte cuvinte, această modulaţie face trecerea de la reprezentarea prin 0 şi 1 la reprezentarea prin –1 şi +1 a secvenţelor constituite.

4. transmiterea secvenţei modulate printr-un canal AWGN. Impunând un raport semnal per zgomot:

ξ(dB) = 10⋅lg (Eb/N0) (4.2)

rezultă pentru puterea zgomotului expresia (vezi paragraful 1.5):

/10

2

10R21

ξσ

⋅⋅= (4.3)

Observaţie: Deoarece operaţiile de multiplexare la emisie şi demultiplexare la recepţie asupra secvenţelor emisă, respectiv recepţionată, nu schimbă statistica secvenţei recepţionate, fapt datorat naturii zgomotului, aceste operaţii au fost omise din lanţul de transmisiune.

Astfel impactul canalului asupra secvenţei transmise s-a simulat printr-o relaţie de forma: y = x + z, (4.4) unde x, y şi z sunt matrici de dimensiune 3×(N⋅nb) în cazurile paralel şi hibrid şi 2×(2⋅N⋅nb) în cazul serial; x reprezintă secvenţa emisă, y cea recepţionată iar z eşantioanele corespunzătoare din zgomotul AWGN suprapus. Dispunând de secvenţa recepţionată, în acest stadiu al simulării se execută două lucruri: –se afişează o imagine (vezi Planşa 2) ce simbolizează secvenţa recepţionată, corespunzătoare biţilor de informaţie. Fiecare bit este simbolizat printr-un pixel de culoare galbenă sau roşie. Culoarea galbenă indică valoare corectă iar roşu pe cea eronată, considerând că s-ar face o decizie hard asupra secvenţei recepţionate; –se calculează şi se afişează numărul de erori din secvenţa recepţionată corespunzătoare informaţiei.

5. turbodecodarea secvenţei recepţionate. Aceasta se face conform configuraţiei turbocodului şi algoritmului de decodare alese prin opţiuni. Principiul funcţionării turbocodului paralel implementat este cel descris în paragraful 1.3 iar cazurile serial şi hibrid au fost implementate conform descrierii din paragraful 1.4. De asemenea, algoritmii de decodare implementaţi sunt descrişi în paragraful 2.2.

Există totuşi o facilitate în plus, pe care o aduce această implementare faţă de cele descrise în paragraful 2.2. Aceasta se referă la o cuantizare a operanzilor pe un număr de nivele Nc=2q. Această cuantizare se doreşte a simula funcţionarea algoritmilor MaxLogMAP, SOVA „up-date” şi SOVA „bidirecţional” sub restricţia ca operaţiile să se efectueze în binar pe un număr q de biţi (q=1, 2, 3). Acest lucru este posibil deoarece în cazul acestor trei algoritmi se efectuează doar operaţii de adunare şi scădere, spre deosebire de cazul algoritmului MAP unde trebuiesc calculate exponenţiale şi logaritmi. Nu s-a prevăzut nici pentru cazul algoritmului LogMAP această cuantizare din cauza complicaţiilor excesive pe care le-ar produce calculul factorului de corecţie.


IV.4

Decodarea se finalizează printr-o decizie hard asupra LLR-ului generat de DEC1, indiferent de configuraţia turbocodului sau algoritmul de decodare alese.

6. prezentarea rezultatelor. Aşa cum s-a specificat la punctul 4. deja au fost prezentate două prime rezultate ale simulării. Este vorba despre imaginea secvenţei recepţionate şi numărul ei de erori. Alte două rezultate similare (o imagine şi un număr) sunt prezentate pe parcursul decodării: imaginea secvenţei decodate şi numărul ei de erori, reactualizate după fiecare iteraţie a fiecărui bloc transmis. Numărul de erori afişat se referă doar la blocurile deja decodate plus cel în curs de decodare şi exclude blocurile ce urmează a fi decodate.

După ce s-a efectuat şi ultima iteraţie asupra ultimului bloc transmis, se afişează rata erorii (BER) şi câştigul de codare. Rata erorii se calculează după formula:

BER = . (4.5)

Dacă nu există erori atunci se specifică:

BER < . (4.6)

Câştigul de codare se calculează cu formula:

Câştig (dB) = ξ0 (dB) – ξ (dB), (4.7) unde ξ0 (dB) este raportul semnal per zgomot fără codare necesar pentru a se obţine aceeaşi rată a erorii ca şi în cazul sistemului codat având un raport semnal per zgomot ξ (dB) dat de relaţia (4.2) şi este cel ales prin opţiuni. Dacă nu există erori, pentru BER indicându-se doar o limită superioară, atunci se va indica şi pentru câştig de asemenea o limită superioară: Câştig (dB) < ξ0 (dB) – ξ (dB). (4.8) Un ultim rezultat afişat este graficul densităţii de probabilitate a logaritmului raportului de plauzibilitate asupra căruia s-a făcut decizia finală. Acest grafic este prezentat suprapus peste densităţile de probabilitate condiţionate ale semnalului recepţionat scalate acum la dimensiuni care să le cuprindă pe toate într-un acelaşi grafic (vezi Planşa 2).

4.2 Posibilităţile interfeţei Parametrii turbocodului ce pot fi setate cu ajutorul interfeţei sunt: 1. Polinoamele generatoare ale codurilor componente. Cele două coduri componente ale turbocodului sunt identice, convoluţionale şi sistematice. Un codor component funcţionează după relaţia:

cj = ∑=

⋅q

1kk-jk cb + ∑

=⋅

p

0kk-jk ia (4.9)

Număr de erori rămase necorectateNumăr de biţi de informaţie transmişi

1Număr de biţi de informaţie transmişi


IV.5

unde ik reprezintă secvenţa de informaţia, cj secvenţa de control iar ak şi bk coeficienţii binari ce definesc codul convoluţional. Utilizând transformata „D”, relaţia (4.9) se poate scrie sub forma:

C(D) = B(D)A(D)

⋅I(D) = G(D)⋅I(D) (4.10)

unde A(D) şi B(D) sunt polinoamele generatoare ale codului convoluţional. Spre exemplu, codul convoluţional al cărui schemă a fost desenată în Figura 2.1 are A(D) =1+D2 şi B(D) = 1+D+D2, sau într-o reprezentare simplificată (în octal) G = 5/78. Dacă B(D)=1 atunci codul convoluţional este nerecursiv (nu există reacţie în codor). Polinoamele generatoare definite mai sus pot fi alese din mulţimea {1, 3, 5, 7, 11, 13, 15, 17}, însă nu este permisă egalitatea celor două (A≠B). Limitarea polinoamelor generatoare la această mulţime a fost impusă doar pentru a putea fi prezentat trellisul corespunzător codului ales cât şi schema codorului. Altfel spus atât programul ce simulează codorul cât şi cele ce simulează decodoarele acceptă orice valori (binare) pentru polinoamele generatoare. Valorile implicite ale polinoamelor generatoare sunt 5 şi 7. Dacă se selectează o altă valoare pentru A sau B, atunci automat se afişează trellisul şi schema codorului corespunzătoare. 2. Configuraţia turbocodului. Configuraţia turbocodului poate fi aleasă între cele trei tipuri deja anunţate: paralelă, serială sau hibridă. Configuraţia implicită este cea paralelă şi este prezentată în dreapta imaginii interfeţei (vezi Figura 4.1 sau Planşa 1). În cazul selectării unei alte configuraţii, aceasta va fi desenată în locul celei vechi. 3. Tipul dispozitivului de întreţesere. Dispozitivele de întreţesere au fost prezentate în Capitolul 2. Pentru dispozitivele de tip regulat şi în cazurile paralel şi hibrid, în vederea întreţeserii, biţii unui bloc de date se ordonează într-o matrice pătrată, fapt facilitat prin alegerea lungimii blocului egală cu un număr pătrat perfect. În cazul configuraţiei seriale matricea nu mai este pătrată ci are un număr de coloane egal cu dublul numărului liniilor. 4. Lungimea unui bloc de date şi numărul de blocuri transmise la o simulare. Lungimea unui bloc poate fi aleasă dintre valorile: 100, 400, 900, 1600, 2500. Aceste sunt pătrate perfecte pentru a putea construi dispozitive de întreţesere cu distanţa minimă de valoare maxim posibilă. Pentru un N dat aceasta are valoarea N . De asemenea cele cinci valori disponibile acoperă plaja de valori utilizată practic pentru lungimea unui bloc de date. În plus pentru a nu avea timpi de simulare excesiv de lungi, numărul de blocuri se setează simultan cu lungimea unui bloc între valorile 4, 4, 1, 1 şi respectiv 1. Dacă totuşi se doresc simulări cu lungimi ale secvenţei de date mai mari, atunci trebuiesc modificate liniile de program din programele „tccGUI.m” respectiv „textcc.m”, pentru a impune valorile dorite pentru lungimea blocului de date sau numărul de blocuri, însă cu restricţiile ce vor fi anunţate în paragraful 4.4. 5. Algoritmul de decodare. Algoritmii de decodare ce pot fi aleşi sunt descrişi în paragraful 2.2. De remarcat că simularea durează sensibil mai mult pentru algoritmul SOVA „up-date” decât pentru ceilalţi algoritmi. De asemenea, aşa cum s-a anunţat deja în paragraful precedent, pentru algoritmii de tip SOVA, cât şi pentru algoritmul MaxLogMAP există posibilitatea de a opera sub restricţia cuantizării operanzilor, astfel încât să se simuleze „decodarea soft pe 2q nivele”. Algoritmul selectat implicit este MAP. Relativ la algoritmul SOVA „up-date”, a cărui prezentare s-a făcut în paragraful 2.2.4, trebuie făcută următoarea observaţie: algoritmul implementat calculează întâi calea maxim plauzibilă şi ulterior revine şi calculează secvenţele „up-date”, spre deosebire de un algoritm Viterbi autentic, care ar calcula secvenţele „up-date”


IV.6

pe vreme ce calculează şi calea maxim plauzibilă. În acest fel rezultă o oarecare simplificare a implementării dar şi un câştig în performanţă pentru algoritmul implementat. 6. Felul decodării. Alegerea „felului decodării” se referă la a alege între variantele de decodare: cuantizat pe 2, 4 sau 8 nivele sau necuantizat (analogic). Această alegere este valabilă doar pentru algoritmii de tip SOVA sau pentru algoritmul MaxLogMAP. Pentru algoritmii MAP şi LogMAP se va executa o decodare necuantizată, indiferent de felul decodării selectate. 7. Raportul semnal per zgomot poate fi ales între limitele 0,1 dB şi 10 dB cu o rezoluţie de 0,1 dB. De remarcat că, impus fiind raportul semnal per zgomot (dat prin relaţia 4.2), puterea zgomotului devine o funcţie de rata de codare, care la rândul ei diferă funcţie de configuraţia turbo-codului. Valoarea implicită a raportului semnal per zgomot este 2 dB. Imediat ce se modifică, cu ajutorul cursorului interfeţei, valoarea pentru raportul semnal per zgomot, se modifică şi graficele densităţilor de probabilitate condiţionate (de emisia unui unu sau a unui zero) ale semnalului recepţionat (desenate în colţul din dreapta-jos a imaginii interfeţei –vezi Planşa 1). Aceste densităţi sunt densităţi gaussiene, fapt datorat zgomotului de tip AWGN. 8. Numărul de iteraţii ce se execută de către fiecare decodor component asupra fiecărui bloc de date poate fi setat între 1 şi 16. 4.3 Instrucţiuni de utilizarea a interfeţei grafice Utilizarea interfeţei grafice pentru simularea funcţionării turbocodurilor convoluţionale presupune efectuarea următoarelor operaţii: – încărcarea programelor din lista următoare într-o cale de căutare a MATLAB-ului: „afcodor.m” „afdpLLR.m” „afdpsr.m” „afschPSH.m” „CodorConv.m” „coment.m” „cuant.m” „dbSOVA.m” „decLogMAP.m” „decMAP.m” „decMLMAP.m” „duSOVA.m” „ilvA.m” „ilvD.m” „ilvP.m” „ilvR.m” „ilvS.m” „LogSumExp.m” „matnatMN.m” „octbin.m” „polgen.m” „schimbrb.m” „sum2.m” „tccGUI.m” „textcc.m” „trastrls.m” „trellis.m” „zecbin.m” – tastarea în linia de comandă a ferestrei principale a MATLAB-ului numelui funcţiei interfeţei, adică: tccGUI; – după apariţia ferestrei cu imaginea interfeţei se pot selecta parametrii turbocodului conform opţiunilor vizibile în stânga imaginii; – după ce s-au ales toţi parametrii doriţi se apasă (clic stânga cu mouse-ul) butonul „START SIMULARE”. Această tastarea are ca efect anularea posibilităţii de a mai face opţiuni prin dispariţia butoanelor active şi pornirea simulării propriuzise. De asemenea, dispar imaginile schemei codorului component şi a configuraţiei turbocodului, iar în locul lor apar două ferestre unde vor fi afişate (imediat ce sunt disponibile) secvenţa recepţionată şi cea rezultată prin decodare. Simultan cu apariţia imaginilor secvenţelor se afişează mai jos şi numărul de erori pe care acestea îl conţin. Imaginea secvenţei decodate cât şi numărul ei de erori se reactualizează imediat ce s-a finalizat o nouă iteraţie. După finalizarea ultimei iteraţii impuse asupra ultimului bloc, se afişează rata erorii (BER), câştigul de codare (calculate după relaţiile 4.3 sau 4.4 respectiv 4.5 sau 4.6) şi graficul densităţii de probabilitate al logaritmului raportului de plauzibilitate (cu verde) suprapus peste graficele densităţilor de probabilitate condiţionate ale semnalului recepţionat (cu albastru –pentru condiţionarea de emiterea unui zero, respectiv cu roşu -pentru condiţionarea de emiterea unui unu). De asemenea apare un buton denumit „REVENIRE”.


IV.7

– tastarea butonului „REVENIRE” are ca efect revenirea la situaţia alegerii unor noi opţiuni. Altfel spus se reactivează butoanele ce servesc la setarea parametrilor turbocodului în vederea unei noi simulări. – închiderea figurii se realizează tastând butonul „STOP” disponibil în stânga-jos a imaginii interfeţei înainte sau după efectuarea simulării. 4.4 Indicaţii-propuneri pentru dezvoltatea altor programe utilizând funcţiile-subrutină aferente interfeţei Acest paragraf se adresează celor ce cunosc limbajul MATLAB şi doresc să dezvolte programe de simulare a turbocodurilor utilizând o parte din funcţiile definite în anexele prezentului referat. În acest scop este prezentat un exemplu de astfel de program. Programul se numeşte „exemplu.m” şi se găseşte listat în anexa D. Se pot schimba după dorinţă: – polinomul generator. Spre exemplu dacă se doreşte G(D)=[1, (1+D)/(1+D+D4)] atunci trebuie setat g=[1 0 0 0; 1 0 0 1]; – tipul interleaverului şi/sau lungimea blocului de date. Lungimea blocului de date N trebuie corelată cu tipul interleaverului. Astfel pentru interleaverele de tip rectangular (ilvR.m) şi diagonal (ilvD.m) trebuie ca N=α×β iar apelarea funcţiei interleaver se va face astfel: rnum=ilvR(α,β). (4.11) Pentru interleaverul pseudo-aleator trebuie ca N să fie multiplu de 10. Apelarea funcţiei interleaver în cazurile interleaverului aleator, pseudo-aleator şi al S-interleaverului se face: rnum=ilvA(N). (4.12) De reţinut că doar în cazul interleaverelor de tip rectangular, diagonal şi pseudo-aleator funcţia interleaver este reproductibilă. În cazul aleator şi S-interleaver ea trebuie memorată pentru a putea fi disponibilă ulterior; – numărul de blocuri şi numărul de iteraţii se pot alege orice numere întregi. Trebuie însă avută o oarecare precauţie deoarece volumul calculelor şi timpul de simulare depind de aceşti doi parametri; – codarea cu sau fără terminaţie. Trebuie avut grijă în a apela corect funcţia „CodorConv.m”, deoarece ea acceptă o informaţie cu dimensiunea 1×(N-M) şi generează o matrice cu dimensiunile 2×N în cazul când face terminaţie iar când nu face terminaţie acceptă o informaţie cu dimensiunea 1×N şi generează o vector cu dimensiunile 1×N. În primul caz se generează o matrice cu două linii, aceste două linii corespunzând secvenţei de informaţie completată în vederea terminaţiei şi secvenţei de control. În cazul când nu se face terminaţie nu mai este necesar a se genera şi secvenţa de informaţie ci doar cea de control. În exemplul de program dat, primul codor face terminaţie, iar al doilea nu. Dacă se doresc schimbări în acest sens trebuiesc luate în calcul probleme ce pot apărea datorită întreţeserii. În plus trebuie făcute schimbările corespunzătoare şi la decodoare, prin alegerea adecvată a parametrului t. – raportul semnal per zgomot se poate seta orice valoare pozitivă, însă valori de interes sunt cuprinse între 0,1 dB şi 5 dB; – configuraţia turbocodului. Pentru a putea simula un alt fel de turbocod trebuie ţinut cont de următoarele. La codare trebuiesc selectate, corespunzător noii scheme, secvenţele ce se vor coda de către fiecare decodor component. Trebuie să corespundă de asemenea lungimea


IV.8

secvenţelor ce vor fi întreţesute cu lungimea interleaverului. În fine, la decodare trebuiesc modificate liniile ce calculează secvenţele de intrare dinspre canal şi în plus liniile ce indică care informaţie extrinsecă va fi considerată de fiecare decodor (este vorba de informaţia extrinsecă despre biţii sistemetici sau despre cei de control, sau ambele); – algoritmul de decodare se poate schimba simplu schimbând in liniile de program corespunzătoare doar numele noului algoritm. Astfel în loc de „decMAP” se poate alege: „decLogMAP”, „decMLMAP”, „duSOVA” sau „dbSOVA”; – afişarea altor parametri. În acest scop se pot crea linii suplimentare.

Coduri utilizate în sistemele de transmisiuni cu spectru împrăştiat Referat nr.3 Horia Balta

Bibliografie [ACR] O.F.Acikel, W.E.Ryan, „Punctured Turbo-Codes for BPSK/QPSK Channels”, IEEE

Transactions on Communications, sept.1999, www.ece.arizona.edu/~ryan/New%20Folder/punctured.pdf [AGK] N.Abdulaziz,A.Glass, K.Khee Pang, „Embedding Data in Images Using Turbo Coding”,

www.elec.uow.edu.au/people/staff/ wysocki/dspcs/papers/017.pdf [APR] P.Adde, R.Pyndiah, O.Raoul, J.R.Inisan, “Block Turbo Decoder Design”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 166-169 [BAK] M.H.Baligh, A.K.Khandani, „Asymptotic Effect of Interleaver Structure on the performance

of Turbo-Codes”, 2000, www.cst.uwaterloo.ca/c/MHBCISS02.pdf [BAP] S.A.Bărbulescu, S.S.Pietrobon, „TURBO CODES: a tutorial on a new class of powerful error

correcting coding schemes, Part I: Code Structures and Interleaver Desing” [BAP] S.A.Bărbulescu, S.S.Pietrobon, „TURBO CODES: a tutorial on a new class of powerful error

correcting coding schemes, Part II: Decoder Desing and Performance” [BBB] M. Benchrifa, M. Belkasmi, A. Benouna, „Amélioration des Performances des Codes

Convolutifs Concaténés en Parallèle avec un Turbo Décodage Utilisant APRI-SOVA”,ICSIP’2001, Agadir, Morocco, 2001

[BCF] P.Bouvier, A.Charnoz, M.Fernandez, P.A.Georges, T. Gros, „Turbo-codes” proiect,

www.i3nice.fr/~charnoz/site/projects/ turbocodes/rapport.pdf [BEM] Sergio Benedetto, Guido Montorsi, “Generalized Concatenated Codes Whith Interleavers”,

International Symposiom on Turbo Codes – Brest – France, 1997, pag. 32-39 [BER] Claude Berrou, “Some clinical aspects of Turbo Codes”, International Symposiom on Turbo

Codes – Brest – France, 1997, pag. 26-31 [BDT] M.Bickerstaff, L.Davis, C.Thomas, D.Garrett, C Nicol, „A 24 Mb/s Radix-4 LogMAP Turbo

Decoder for 3GPP-HSDPA Mobile Wireless”, IEEE International Solid-State Circuits Conference”, februarie 2003, www.bell-labs.com/issccpaper

[BGT] 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 [BAH] H.Balta, “Coduri utilizate în sistemele de transmisiuni cu spectru împrăştiat”, Referat Nr.1,

martie 2003


[BAT] Gérard Battail, “A conceptual framework for understanding turbo-codes”, International Symposiom on Turbo Codes – Brest – France, 1997, pag. 55-62

[BRW] Spencer Brown, „The Turbocharging guide” www.turbomustangs.com/turbotech/main.htm [CAB] G.Caire, E.Biglieri, “Linear Block Codes Over Cyclic Groups”, IEEE Transactions on

Information Theory, vol. 41, pp. 1246-1256, September 1995 [DAM] 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

[DIP] D.Divsalar, F.Pollara, “Serial and Hybrid Concatenated Codes with Applications”,

International Symposiom on Turbo Codes – Brest – France, 1997, pag. 80-87 [FEV] W.Feng, B.Vucetic, “A List Bidirectional Soft Output Decoder of Turbo Codes”,

International Symposiom on Turbo Codes – Brest – France, 1997, pag. 288-292 [FOJ] G.David Forney Jr., “On iterative decoding and the two-way algorithm”, pp.12-25,

International Symposium on Turbo Codes – Brest – France, 1997 [FOR] G.D. Forney Jr, “Convolutional Codes I: Algebraic Structure”, IEEE Transaction on

Information Theory”, nov.1970, pp.720-738 [GAD] H.El Gamal, M.O.Damen, “ Universal Space-Time Coding”, IEEE Transactions on

Information Theory, vol.49 pp.1097-1119, May 2003 [GBN] D.Garrett, Bing Xu, C.Nicol, „Energy Efficient Turbo Decoding for 3G Mobile”,

www.acm.org/.../Archives/ProceedingArchives/Compendiums/ [GHF] M.Ghinea, V.Fireţeanu, „MATLAB Calcul numeric – Grafică – Aplicaţii”, Ed. Teora, 1995 [GOP] A.Goalic, R.Pyndiah, “Real-Time Turbo-Decoding of Product Codes on a Digital Signal

Processor”, International Symposiom on Turbo Codes – Brest – France, 1997, pag. 267-270 [HAG] J.Hagenauer, „The Torbo Principle: Tutorial Introduction and State of the Art”, International

Symposiom on Turbo Codes – Brest – France, 1997 [HLY] L.Hanzo, T.H.Liew, B.L.Yeap, “Turbo Coding, Turbo Equalisation and Space-Time Coding

for Transmission over Fading Channels”, John Wiley & Sons Ltd, England, 2002 [HOE] Peter Hoeher, “New Iterative (“Turbo”) Decoding Algorithms”, International Symposiom on

Turbo Codes – Brest – France, 1997, pag. 63-70 [HOM] J.Hokfelt, T.Maseng, “Methodical Interleaver Design for Turbo Codes”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 212-215


[HOP] J.Hagenauer, E. Offer, L. Papke, “Iterative Decoding of Binary Block and Convolutional Codes”, IEEE Transactions on Information Theory, Vol 42 No 2, March 1996 pp 429-445

[JZG] R. Johannesson, K. Sh. Zigangirov, „Fundamentals of Convolutional Coding”, IEEE Press,

1999 [JEZ] M.Jézéquel, „Turbo codes (convolutifs)”, seminar Timişoara, 18-20 martie 2003 R1, Documentaţie 4/7 SS [KAL] G.Kalai, N.Linial, “On the Distance Distribution of Codes”, IEEE Transactions on

Information Theory, vol. 41, pp. 1467-1471, September 1995 [KOF] K.Koora, A. Finger, “A New Scheme to Terminate all Trellis of Turbo-Decoder for Variable

Block Length”, International Symposiom on Turbo Codes – Brest – France, 1997, pag. 174-179

[KOV] R.Koetter, A.Vardy, “Algebraic Soft-Decision Decoding of Reed-Solomon Codes”, IEEE

Transactions on Information Theory, vol.49 pp.2809-2825, November 2003 [KRL] I.Krasikov, S.Litsyn, “On Spectra of BCH Codes”, IEEE Transactions on Information

Theory, vol. 41, pp. 786-787, May 1995 [KSS] F.R.Kschischang, V.Sorokine, “On the Trellis Structure of Block Codes”, IEEE Transactions

on Information Theory, vol. 41, pp. 1924-1937, November 1995 [LAZ] A.Lapidoth, J.Ziv, “On the Decoding of Convolutional Codes on an Unknown Channel”,

IEEE Transactions on Information Theory, vol.45 pp.2321-2331, November 1999 [OBS] M.Öberg, P.H.Siegel, “The Effect of Puncturing in Turbo Encoders”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 184-187 [PHA] P. Ha, “A Fast Algorithm for Generating Random Interleavers”, www.sarim.changwon.ac.kr [PKY] Li Ping, Kwan L. Yeung, „Symbol-by-Symbol APP Decoding of Golay Code and Iterative

Decoding of Concatenated Golay Codes”, IEEE Transactions on Information Theory”, Vol 45 No 7 November 1999

[PLV] L.Ping, WQ.K.Leung, K.Y.Wu, “Low-Rate Turbo-Hadamard Codes”, IEEE Transactions on

Information Theory, vol.49 pp.3213-3224, December 2003 [PSE] M.Peleg, I.Sason, S.Shamai (Shitz), A.Elia, “On Interleaved, Differentially Encoded

Convolutional Codes”, IEEE Transactions on Information Theory, vol.45 pp.2572-2581, November 1999

[PYN] R. Pyndiah, “Iterative Decoding of Product Codes: Block Turbo Codes”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 71-79


[RIC] T.Richardson, “The Geometry of Turbo-Decoding Dynamics”, IEEE Transactions on

Information Theory, vol.46 pp.9-23, January 2000 [ROB] P. Robertson, “An Overview of Bandwidth Efficient Turbo Schemes”, International

Symposiom on Turbo Codes – Brest – France, 1997, pag. 103-110 [ROY] J.Rosenthal, E.V.York, “BCH Convolutional Codes”, IEEE Transactions on Information

Theory, vol.45 pp.1833-1844, September 1999 [RVH] 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, Seattle, USA, pag. 1009-1013, iunie 1995

[SCB] G.Schnabl, M.Bossert, “Soft-Decision Decoding of Reed-Muller Codes as Generalized

Multiple Concatenated Codes”, IEEE Transactions on Information Theory, vol. 41, pp. 304-307, January 1995

[SCG] C.Schlegel, A.Grant, “Differential Space-Time Turbo Codes”, IEEE Transactions on

Information Theory, vol.49 pp.2298-2306, September 2003 [SHA] C.E. Shannon, „A Mathematical Theory of Communications”, The Bell System Technical

Journal, Vol.27, pp. 379-423, 623-656. October, 1948 [SSS] H. R. Sadjadpour, M. Salehi, N. J. A. Sloane, G. Nebe, “Interleaver Design for Short Block

Length Turbo Codes”,1998, www.ee.cityu.edu.hk [TAC] O.Y.Takeshita, D.J.Costello, „New Deterministic Interleaver Design for Turbo Codes”, IEEE

Transactions on Information Theory, vol.46, September 2000 .[TAJ] Tarokh, H.Jafarkhani, “Space-Time Block Codes from Orthogonal Designs”, IEEE

Transactions on Information Theory, vol.45 pp.1456-1467, July 1999 [TAS] D.J.Taipale, M.J.Seo, “An Efficient Soft-Decision Reed-Solomon Decoding Algorithm”,

IEEE Transactions on Information Theory, vol. 40, pp. 1130-1139, July 1994 [TRK] A.N.Trofimov, B.D.Kudryashov, “Distance Spectra and Upper Bounds on Error Probability

for Trellis Codes”, IEEE Transactions on Information Theory, vol. 41, pp. 561-571, March 1995

[VHS] N.R.Veselinovic, P.Henttu, S.A.Siltala, D.Tujkovic, M.Juntti, “Wideband Interference

Suppression in Turbo-Coded DS/FH System”, www.cwc.oulu.fi/home/projects/AWICS/awics_pub/ 2001/nenad_veselinovic_icc01.pdf

[VVN] A.J. Viterbi, A.M.Viterbi, J.Nicolas, N.T.Sindhushayana Perspectives on Interleaved

Concatenated Codes with Iterative Soft-Output Decoding , International Symposiom on Turbo Codes – Brest – France, 1997, pag.47-54


[VUY] B.Vucetic, J.Yuan, “Turbo Codes Principles and Applications”, Kluwer Academic

Publishers, USA, 2000 [WAD] G.Wade, “Coding Techniques, An Introduction to Compression and Error Control”, Creative

Print and Design, Ebbw Vale, Great Britain, 2000 [WHO] J.P.Woodard, L.Hanzo, “Comparative Study of Turbo Decoding Techniques: An Overview”,

IEEE Transactions on Vehicular Technology, nov.2000 [ZMY] S.Zhou, S.Mei, Y.YAO, “Turbo-Code without Chanel Estimator”, International Symposiom

on Turbo Codes – Brest – France, 1997, pag. 147-150

turbocoduri - uptshannon.etc.upt.ro/docs/cercetare//teze_doctorat/tcoduri.pdfÎn celebra sa lucrare...

Documents