UNIVERSITATEA POLITEHNICA TIMIOARA FACULTATEA DE ELECTRONIC I
TELECOMUNICAII B-dul V. Prvan Nr. 2, 300223 TIMIOARA, ROMNIA
tel/fax: +40-256-403291 e-mail: [email protected] http:// www.etc.upt.ro
CONTRIBUII LA ANALIZA I MBUNTIREA PERFORMANELOR TURBO CODURILOR N CANALE
CU FADING PLAT
Tez de doctorat Conductor tiinific: Doctorand: Prof. Dr. Ing. Miranda NAFORNI As. Ing. Maria KOVACI
_________________________2009 _____________________
U1920
Cuprins
List abrevieri ................................................................................................. 3
Cap.1. Introducere ......................................................................................... 5
Cap.2. Coduri convoluionale .................................................................... 9
2.1 Principiul codrii convoluionale ........................................................... 9
2.2 Tipuri de coduri convoluionale ............................................................. 11
2.3 Reprezentarea grafic a codurilor convoluionale ............................... 15
2.4 Distana liber ...................................................................................... 18
2.5 Funcia de transfer asociat unui cod convoluional ................. 19
2.6 Simularea spectrului ponderilor ................................................ 24
Cap.3 Turbo coduri .. 27
3.1 Turbo codorul ......................................................................................... 29
3.2 Turbo decodorul .............................................................................. 30
3.3 Concatenarea paralel a codurilor convoluionale ............................... 32
3.4 Dispozitive de ntreesere ........................................................................ 33
3.4.1 Interleaver aleator ......................................................................... 35
3.4.2 Interleaver de tip S ..................................................................... 35
3.4.3 Interleaver bloc .......................................................................... 36
3.4.4 Interleaver pseudo-aleator ........................................................ 37
3.4.5 Interleaver Takeshita-Costello ..................................................... 38
3.4.6 Interleaver bloc-aleator ............................................................. 38
3.4.6.1 Interleaver bloc aleator n linie, BRL .............................. 39
3.4.6.2 Interleaver bloc cu linii aleatoare, BLR ........................... 40
3.4.7 Performanele interleaver-elor utilizate n turbo coduri ........... 41
3.5 Algoritmi de decodare ......................................................................... 48
3.5.1 Algoritmul Viterbi ......................................................................... 49
3.5.1.1 Algoritmul Viterbi cu decizie hard ................................... 49
3.5.1.2 Algoritmul Viterbi cu decizie soft ..................................... 50
Cuprins 2
3.5.2 Algoritmul MAP ............................................................................ 53
3.5.3 Algoritmul Max-Log-MAP ........................................................... 61
3.5.4 Algoritmul Log-MAP .................................................................... 65
3.5.5 Performane ale algoritmilor de decodare ................................... 67
3.6 Concluzii ............................................................................................... 68
Cap.4 Performanele turbo codurilor n canalele cu fading plat . 69 4.1 Propagarea radio n comunicaiile mobile ........................................ 69
4.2 Modelul sistemului de transmisie ...................................................... 78
4.3 Fading plat de tip Rayleigh ................................................................ 80
4.4 Fading plat de tip Rice ........................................................................ 88
4.5 Fading plat de tip Nakagami .................................................................. 96
4.6 Concluzii .................................................................................................. 104
Cap.5 Turbo coduri multi-binare ........................................................... 105 5.1 Interleaver-e pentru turbo coduri multi-binare .................................. 113
5.2 Performanele turbo codurilor i a turbo codurilor multi-binare puncturate ......................................................................................................
118
5.3 Performanele turbo codurilor multi-binare n canalele cu fading plat ....................................................................................................................
125
5.3.1 Fading plat de tip Nakagami .......................................................... 125
5.3.2 Fading plat de tip Raylegh ............................................................. 132
5.4 Concluzii ................................................................................................... 138
Cap.6 Contribuii i concluzii ................................................................... 139
Anexa A ............................................................................................................ 142
Anexa B ............................................................................................................. 145
Anexa C ............................................................................................................ 146
Anexa D ............................................................................................................ 156
Bibliografie ...................................................................................................... 158
List abrevieri
APP A Posteriori Probability
AWGN Aditive White Gaussian Noise
BER Bit Error Rate
BLR Bloc with Random Lines
BPSK Binary Phase Shift Keying
BRL Block Random in Line
CC Convolutional Code
CCSDS Consultative Comittee for Space Data Systems
DVB-T Digital Video Broadcasting-Terrestrial
FER Frame Error Rate
ISI Inter Symbol Interference
LDPC Low-Density Parity-Check
LFSR Linear Feedback Shift Register
LLR Log Likelihoods Ratio
Log-MAP Logarithm-MAP
LOS Line-Of-Sight
MAP Maximum A-Posteriori
Max-Log-MAP Maximum-Logarithm-MAP
MBTC Multi-Binary Turbo Code
NRNSC Non-Recursive Non-Systematic Code
NRSC Non-Recursive Systematic Code
psd Power Spectral Densiy
QPSK Quarternary Phase Shift Keying
RF Radio Frequency
RNSC Recursive Non-Systematic Code
RSC Recursive Systematic Convolutional Code
SISO Soft Input Soft Output
SNR Signal to Noise Ratio
SOVA Soft Output Viterbi Algorithm
TC Turbo Code
List abrevieri 4
UMTS Universal Mobile Telecommunications System
WCDMA Wideband Code Division Multiple Access
WiMAX Worldwide Interoperability for Microwave Access
CAPITOLUL 1
Introducere
Noi servicii de comunicaii i tehnologia informaiei apar aproape zilnic i cererile
de a avea o capacitate de comunicaie i rate de transmisie din ce n ce mai mari
continu s creasc. Acest progres spectaculos al comunicaiilor se datoreaz, n mare
msur, creterii performanelor codurilor i reducerii costului tehnologiei.
Calitatea unui sistem numeric de comunicaii este n general evaluat prin
probabilitatea de eroare a simbolurilor recepionate, sau rata erorii pe bit, BER
(Bit Error Rate).
Aceast probabilitate depinde de raportul semnal pe zgomot al mesajului,
SNR (Signal to Noise Ratio), din canalul de comunicaii. Cu ct SNR este mai
mare, BER este mai mic. Pentru a ameliora calitatea unui sistem de comunicaii
numerice este necesar creterea acestui raport.
O soluie de a scdea BER, fr creterea SNR este codarea mesajulului de
transmis. Operaia de codare const n a aduga la mesajul de transmis simboluri,
numite de redundan, dup o lege dat. Necesitatea de a se introduce redundan n
mesaj, pentru a se proteja contra erorilor de transmisie, este demonstrat n cadrul
teoriei informaiei, [BOR99].
Pentru un mesaj lipsit de redundan, fiecare simbol este esenial i astfel
orice eroare de transmisie conduce la o pierdere ireversibil de informaie. n
schimb, introducerea de simboluri de redundan va corela simbolurile mesajului
codificat. Astfel, n anumite condiii, simbolurile eronate n cursul transmisiei
vor modifica legea de codare utilizat la emisie, ceea ce va permite detectarea,
apoi eventual, corectarea erorilor.
n celebra sa lucrare din 1948, [SHA48], Shannon a demonstrat c o comunicaie
sigur este posibil printr-un canal orict de zgomotos dac este ndeplinit condiia ca
rata de transmisie s fie mai mic dect capacitatea canalului. Totui, Shannon nu a
propus soluii explicite de codare a canalului pentru implementri practice. Astfel,
vreme de aproape 60 de ani, cercettorii au creat coduri, limitate ca performan de
complexitatea decodrii i de complexitatea canalului. n urma cercetrilor efectuate
s-au impus n principal dou mari familii de coduri, codurile bloc i codurile
convoluionale [PRO00].
Introducere - 1
6
n structura oricrui receptor digital exist un detector. n prezent se
utilizeaz dou tipuri de detectoare, hard i soft. Acestea din urm utilizeaz
valori ale unui raport de plauzibilitate. Prima soluie, care conduce la o pierdere
ireversibil de informaie pentru decodor, a dat natere la algoritmi de decodare
de tip algebric, bine adaptai la structura codurilor bloc [THI93]. A doua soluie,
permite decodorului s exploateze cel mai bine informaia disponibil, conduce
la algoritmi de decodare de tip probabilist, utilizai n special pentru codurile
convoluionale [FAN63, VIT67].
Pentru a atinge cel mai bun rezultat din punct de vedere al BER-ului i al
complexitii de implementare, n tehnicile de codare a informaiei au fost
imaginate diferite asocieri de coduri elementare. Una dintre aceste asocieri
const n concatenarea a dou coduri elementare astfel nct simbolurile de la
ieirea primului codor, numit exterior, s fie aplicate la intrarea celui de al
doilea, numit interior. n general concatenarea codurilor este realizat prin
asocierea unui cod convoluional, interior, cu un cod bloc, exterior. n cazul
concatenrii a dou coduri convoluionale, [HAH89], pentru a atinge cel mai bun
rezultat n urma concatenrii, este necesar ca decodorul interior s poat furniza
decizii ponderate decodorului exterior.
Decodarea codurilor convoluionale este n general realizat pornind de la
algoritmul Viterbi care furnizeaz decizii hard [OMU69, VIT71]. Acest algoritm
nu poate fi utilizat dect pentru decodarea codului interior. Au fost propuse mai
multe soluii pentru a rezolva problema decodrii codurilor convoluionale cu
decizii soft la ieire. Bahl .a. [BCJR74] au propus s se decodeze codurile
convoluionale determinnd simbolul cel mai plauzibil. Algoritmul propus se
numete MAP (Maximum A-Posteriori). Acest algoritm este mai complex
comparativ cu algoritmul Viterbi. Au fost propuse mai multe versiuni ale
algoritmului Viterbi, ce permit furnizarea deciziilor ponderate la ieirea
decodorului, de diferii autori printre care i Berrou .a. [BAAF93]. Totui
performanele unei astfel de soluii sunt nc destul de deprtate de cele
previzionate de Shannon.
O cretere semnificativ a performanelor poate fi obinut folosind
decodarea turbo, prin optimizarea subsistemului din structura receptorului,
format din decodoare i detector. Aceast optimizare presupune aducerea unei
pri din informaia de la ieirea detectorului la intrarea primului decodor.
1 - Introducere
7
Aceasta este aa numita informaie extrinsec. Sistemul obinut se numete turbo
decodor, [BGT93]. Funcionarea acestuia este iterativ, aportul informaiei
extrinseci la scderea BER-ului diminundu-se odat cu creterea numrului de
iteraii.
Din momentul apariiei, turbo codarea a evoluat ntr-un ritm fr precedent, datorit
eforturilor intense depuse de cercettorii din domeniu. Ca urmare, turbo codurile au fost
introduse i n standarde, ca de exemplu standardul pentru comunicaii mobile de
generaia a treia (3G) [HOT04]. n sistemele video de difuzare, unde ntrzierea asociat
sistemului este mai puin critic dect n sistemele interactive, ctigurile n performan
care pot fi atinse sunt i mai impresionante.
Conceptul de turbo codare a fost introdus n 1993, de ctre Berrou, Glavieux i
Thitimajashima, care au raportat rezultate excelente de ctig de codare [BGT93],
apropiate de limita lui Shannon. Secvena de informaie este codat de dou ori, avnd
un interleaver (dispozitiv de ntreesere) ntre cele dou codoare (concatenate paralel)
care servete la realizarea a dou secvene de date aproximativ independente statistic
una fa de cealalt. Cel mai des sunt utilizate codoarele convoluionale recursive
sistematice, RSC (Recursive Systematic Convolutional Code). Fiecare codor RSC, din
structura unui turbo codor, produce o ieire sistematic, care conine secvena de
informaie original, precum i o secven de informaie de paritate. Cele dou secvene
de paritate pot fi apoi puncturate [VUY01, KBDN07], nainte de a fi transmise
mpreun cu secvena de informaie original. Aceast puncturare a informaiei de
paritate permite o gam larg a ratelor de codare i deseori este transmis jumtate din
informaia de paritate de la fiecare codor. Puncturarea coduce la creterea ratei de
codare, obinndu-se de exemplu o rat de codare a TC-ului egal cu 1/2, comparativ cu
cazul nepuncturat, unde rata de codare este 1/3.
n prezent turbo codurile se utilizeaz n cele mai moderne sisteme de
comunicaii. Un exemplu potrivit este cel al sistemelor fr fir (wireless). n
cazul acestor sisteme canalele sunt variante n timp, deoarece propagarea se face
pe mai multe ci. Acestea sunt numite canale cu fading. Majoritatea lucrrilor
despre turbo coduri din literatura de specialitate trateaz cazul canalului AWGN
(Aditive White Gaussian Noise). Scopul acestei teze este studiul sistematic al
comportrii turbo codurilor pe canale cu fading plat. Diferena fa de abordrile
anterioare este dat tocmai de acest caracter sistematic al studiului.
Introducere - 1
8
Capitolele 2 i 3 reprezint o introducere n teoria turbo codurilor, pe care
am considerat-o necesar pentru ca teza s aib un caracter unitar. Capitolul 4
reprezint partea central a tezei. Capitolul 5 se refer la modul n care
acioneaz ultima generaie de turbo coduri, cele multi-binare, n cazul canalelor
cu fading plat.
Teza n continuare este structurat dup cum urmeaz.
n capitolul 2 am fcut o prezentare a codurile convoluionale, a codrii,
respectiv decodrii acestora. Deasemenea, am simulat i am analizat spectrul
ponderilor pentru diferite coduri convoluionale, de memorie 2.
n prima parte a capitolului 3 am descris, pe scurt, turbo codul. n continuare,
am prezentat cteva tipuri de interleaver-e. Apoi, am propus, simulat i analizat
dou noi tipuri de interleaver-e, i anume: interleaver-ul bloc aleator n linie i
interleaver-ul bloc cu linii aleatoare. Tot n cadrul acestui capitol am fcut o
prezentare a algoritmilor de decodare: Viterbi, MAP, Max-Log-MAP (Maximum-
Logarithm-MAP) i Log-MAP (Logarithm-MAP). La sfritul capitolului am artat
performanele algoritmilor de decodare MAP, Max-Log-MAP i Log-MAP, prin
intermediul rezultatelor pe care le-am obinut cu ajutorul simulrilor.
La nceputul capitolului 4 am prezentat cteva noiuni legate de propagarea
radio n comunicaiile mobile i am prezentat pe scurt o clasificare a
manifestrilor fading-ului n canale. Apoi, am analizat i simulat comportarea
turbo codurilor n diferite canale cu fading plat de tip: Rayleigh, Rice i
Nakagami. Deasemenea, am fcut o estimare a canalului, necesar pentru
construcia coeficientului Lc, utilizat n algoritmul de decodare MAP.
n capitolul 5 am reprezentat, structurile unui turbo cod multi-binar ct i
codoarelor sale componente multi-intrare RSC. Apoi, am fcut o analiz a celor
dou metode de decodare, decodare pe bit i decodare pe simbol, ce pot fi
realizate n cadrul turbo codurilor multi-binare. Deasemenea, am analizat
performanele BER i FER (Frame Error Rate) ale turbo codurilor puncturate i
a turbo codurilor multi-binare puncturate ct i cele ale turbo codurilor multi-
binare n canalele AWGN i cu fading plat (Rayleigh i Nakagami).
n capitolul 6 am prezentat principalele contribuii i concluzii pe care le-am
avut, respectiv, obinut n cadrul acestei lucrri.
CAPITOLUL 2
Coduri convoluionale
Codurile convoluionale (CC) se utilizeaz frecvent n aplicaii cum sunt:
comunicaiile spaiale i prin satelit, telefonia celular, televiziunea digital, Digital
Video Broadcasting Terrestrial (DVB-T), etc., [VUY01]. Rspndirea lor este datorat
structurii simple i implementrii facile a metodelor de decodare.
2.1. Principiul codrii convoluionale
Codurile convoluionale introduse n 1954 de P. Elias [ELI54] reprezint o
clas de coduri corectoare de erori avnd o mare aplicabilitate practic. Datorit
simplitii lor i posibilitii de a utiliza algoritmi de decodare de tip Soft Input
Soft Output (SISO), CC-urile sunt cele mai utilizate coduri componente n turbo
coduri.
n cazul CC-urilor, fiecare bloc de n simboluri binare de la ieirea codorului
depinde att de blocul de k simboluri binare prezent la intrarea sa, la momentul
considerat, ct i de m blocuri precedente [THI93]. n consecin CC-urile
introduc un efect de memorie de ordinul m.
Lungimea de constrngere a codului convoluional, exprimat n bii ai
mesajului, este definit ca numrul de deplasri dup care un bit al mesajului
poate influena ieirea decodorului. ntr-un codor avnd un registru de deplasare
cu m celule, i memoria codorului egal cu m, sunt necesare K=m+1 deplasri
pentru ca un bit al mesajului s intre n registrul de deplasare i s ias n final.
Astfel lungimea de constrngere a codorului este K [HAY00].
Principiul codorului convoluional este prezentat n Fig. 2.1. Codorul este
constituit:
- dintr-un sistem de m registre de ntrziere, fiecare avnd o capacitate de k bii, care
memoreaz cele m blocuri de k simboluri de informaie,
- dintr-o mulime de funcii liniare, ce genereaz blocurile de n simboluri de la ieire,
- dintr-un convertor paralel-serie.
Raportul R=k/n se numete rat de codare.
Coduri convoluionale - 2
10
Un cod convoluional de rat R este o aplicaie de la mulimea matricilor (binare) cu
un numr de k linii i numr infinit de coloane ctre mulimea matricilor (binare) cu un
numr de n linii i numr infinit de coloane, unde n > k [THI93]:
Fig. 2.1 Principiul de realizare a unui codor convoluional.
nk MMC : (2.1)
Astfel, prin transformarea C, fiecrei matrici kMI , de forma :
=
LLLLLLLLLLLL
jkkkk
j
j
iiii
iiiiiiii
210
22212
1
02
211101
I { } ksji js 1, ,0, 1,0 ==
(2.2)
i se ataeaz o matrice nMV , de forma :
=
LLLLLLLLLLLLLLLLLLLL
jnnnn
jkkkk
j
j
aaaa
aaaa
aaaaaaaa
210
210
2221202
1211101
V { } nsja js 1, ,0, 1,0 ==
(2.3)
. . .
. . .
. . .
Funcii liniare
Conversie paralel/serie
1 2 K=m+1
bloc de k simboluri de informaie
cuvnt de cod bloc de n simboluri
m registre de ntrziere
.
.
.
2.1 - Principiul codrii convoluionale
11
Matricea I conine biii de informaie, n ordinea KK 1100201 iiii k , iar matricea V
secvena codat : KK 1100201 aaaa n . Dac js jsa i pentru orice j pozitiv i pentru
orice ks = 1 , atunci codul se numete sistematic. Fcnd apel la o reprezentare
polinomial, matricile I i V se pot scrie ca, [BAK04a]:
( )
=
=
=
=
0
02
01
s
ssk
s
ss
s
ss
Di
Di
Di
DM
I , ( )
=
=
=
=
=
0
0
02
01
s
ssn
s
ssk
s
ss
s
ss
Da
Da
Da
Da
D
M
MV
(2.4)
Cu aceste notaii, relaia de codare, poate fi scris astfel :
( ) ( ) ( )DDD IGV = (2.5) unde G(D) se numete matricea generatoare a codului i are forma:
( )( ) ( ) ( )
( ) ( ) ( )
=
DgDgDg
DgDgDgD
nknn
k
LLLLL
L
21
11211G
(2.6)
2.2 Tipuri de coduri convoluionale
n funcie de forma polinoamelor gjs(D) i a criteriului adoptat, codurile
convoluionale pot fi clasificate ca i, [FOR90, HLY02]:
1. Coduri sistematice, respectiv nesistematice.
1.a) Dac primele k linii din G(D) formeaz matricea unitate de ordinul k, Ik, atunci
codurile sunt sistematice. La codurile sistematice, simbolurile de informaie sunt plasate
toate, fie la nceputul fie la sfritul cuvntului de cod. Astfel, dac cele k simboluri de
informaie, prezente la intrarea codorului din Fig. 2.1, sunt efectiv emise, adic se
gsesc n mod explicit n blocul de n simboluri de la ieirea codorului pe primele k
poziii, codul se numete cod sistematic [FOR70]. Altfel spus, n cazul codurilor
Coduri convoluionale - 2
12
sistematice biii sau simbolurile de informaie originale constituie parte din cuvntul de
cod codat i astfel, ei pot fi recunoscui n mod explicit la ieirea codorului [HLY02].
1.b) Pentru codurile nesistematice, biii din V sunt combinaii liniare ale biilor din
I, neexistnd bii de informaie i de control ca i n cazul precedent.
2. Coduri recursive, respectiv nerecursive.
2.a) Dac toate polinoamele generatoare care compun G(D) sunt finite, atunci codul
rezultat este nerecursiv.
2.b) Dac polinoamele generatoare gjs(D) pot fi scrise sub forma:
)()(
)(DbDa
Dgjs
jsjs =
(2.7)
unde polinoamele ajs i bjs sunt finite, i dac exist cel puin un polinom bjs(D)1,
atunci codul este recursiv.
Lungimea de constrngere este unul dintre parametri importani ai codurilor
convoluionale. O alt definiie a sa este dat n relaia de mai jos, [BAK04a]:
( ) ( ){ }DbDagradK sjsjsj ,,, ,max1+=
(2.8)
Pentru a ilustra codurile convoluionale nerecursive i nesistematice, n Fig.
2.2 se prezint un exemplu de codor convoluional de rat R = 1/2 i de lungime
de constrngere K=m+1=3. Intrarea sa este constituit din blocurile de k=1 simbol de informaie i ieirea sa de blocurile de n=2 simboluri codate.
Fig. 2.2 : Exemplu de codor convoluional nerecursiv, nesistematic (R = 1/2, K = 3).
ik ik-1 ik-2 D D 2ka
1ka V
2.2 - Tipuri de coduri convoluionale
13
Caracterul convoluional al codurilor provine din faptul c fiecare ieire a
codorului este egal cu produsul de convoluie dintre irul de simboluri prezente
la intrarea codorului i rspunsul codorului, definit prin polinoamele sale
generatoare. n codorul din Fig. 2.2 ieirile aik ; i = 1, 2 sunt multiplexate de
ctre un comutator, obinndu-se o singur secven de cod, V. Relaiile de calcul
ale acestor secvene de ieire sunt:
=
=
2
0
11
jjjkk gia
(2.9)
=
=
2
0
22
jjjkk gia
(2.10)
Cele dou secvene generatoare sunt:
[ ] [ ][ ] [ ]1,1,1,,
1,0,1,,22
21
20
2
12
11
10
1
==
==
gggg
gggg
(2.11)
Ieirile codorului fiind egale cu o combinaie liniar a simbolurilor de
informaie, codul este liniar. Codurile convoluionale sunt de asemenea definite
pornind de la polinoamele lor generatoare exprimate n funcie de variabila D
(delay-ntrziere) echivalent cu variabila Z-1 a transformatei Z [FOR70].
Considernd tot exemplul din Fig. 2.2, polinoamele generatoare ale acestui cod
au expresiile:
222
21
20
22
212
11
10
11
)(
)(
DgDggDGgDgDggDGg
++=
++=
(2.12)
i:
( )( ) 22
21
1
1
DDDG
DDG
++=
+=
(2.13)
rezultnd matricea generatoare G=[1+D2, 1+D+D2].
Coduri convoluionale - 2
14
i
+ D DD
+
a0 a1 a2 aM-1 aM
b1 b2 bM-1 bM
i
c
n general polinoamele generatoare ale codorului se exprim n octal i
astfel, pentru cazul din Fig. 2.2, avem:
octal)7(n 1] 1 [1
octal)5(n 1] 0 [1 2
1
==
==
G
G
(2.14)
CC-urile nesistematice pot fi catastrofice. Codurile catastrofice sunt codurile
pentru care un numr finit de erori n canalul de transmisie poate da natere unui
numr infinit de erori la ieirea din decodor. O condiie necesar i suficient,
[BOR99], pentru apariia erorilor catastrofice n cazul codurilor cu R=1/n este
ca polinoamele generatoare s aib factor comun.
Astfel, dac un cod de rat R=1/2 are polinoamele generatoare de forma
G1(D)=1+D i G2(D)=1+D2, el este un cod catastrofic, deoarece polinoamele
generatoare l au ca i factor comun pe 1+D. Deoarece se face o sumare modulo
doi, putem scrie: (1+D)(1+D)=1+D+D+D2=1+D2. Dup cum se observ din
matricea generatoare, G, codorul din Fig. 2.2 nu genereaz un cod catastrofic.
Pentru codurile sistematice, exist cel puin o secven binar de informaie de
pondere infinit, care d natere unei secvene binare de pondere finit la ieirea codorului. n consecin, codurile sistematice nu pot fi catastrofice.
n Fig. 2.3 a) se prezint schema general a unui codor RSC, iar n Fig. 2.3 b) un caz
particular al acesteia.
a) b)
Fig. 2.3 CC recursiv sistematic: a) schema general, b) exemplu (R=1/2, K=3). n exemplul considerat matricea generatoare este de forma:
i
i
c
+ D D
+
2.2 - Tipuri de coduri convoluionale
15
++
+= 2
2
11,1
DDDG
(2.15)
n figura urmtoare este prezentat un exemplu de codor sistematic i nerecursiv, NRSC
(Non-Recursive Systematic Code), considerndu-se rata R=1/2 i lungimea de
constrngere K=3, [BOR99]:
Fig. 2.4 CC sistematic i nerecursiv, R=1/2, K=3, G=1+D+D2.
2.3 Reprezentarea grafic a codurilor convoluionale
Proiectarea algoritmilor de decodare poate fi simplificat dac se utilizeaz
reprezentri grafice ale CC-urilor. Reprezentarea cea mai uzual i mai bine
adaptat este, n mod incontestabil, reprezentarea grafic sub forma unui trellis
sau sub forma unei diagrame de stri. n continuare se prezint diagrama trellis
i diagrama de stri pentru codorul convoluional nesistematic din Fig. 2.2,
[THI93].
Diagrama trellis
Fiecare bloc de n = 2 simboluri de la ieirea acestui codor depinde de blocul
de k = 1 simbol prezent la intrarea sa dar i de m = 2 blocuri de k simboluri
coninute n memoria sa. Aceste mk = 2 simboluri definesc starea codorului. Se
noteaz cu S0 = (00), S1 = (01), S2 = (10) i S3 = (11), cele patru stri posibile
ale codorului din Fig. 2.2. Oricare ar fi starea iniial a codorului, dup m+1=3
ntrzieri la intrarea codorului, toate strile au fost atinse.
Funcionarea codorului poate fi explicat innd seama doar de strile sale i
de tranziiile dintre acestea, numite ramuri (ramificaii, brae). Diagrama trellis
iDDi
C
Coduri convoluionale - 2
16
astfel obinut este reprezentat n Fig. 2.5, pentru codorul convoluional din
Fig. 2.2, presupunnd ipoteza c starea sa iniial era S0=(00).
Fig. 2.5: Trellis-ul codorului convoluional din Fig. 2.2.
Ramurile reprezentate prin linii punctate corespund prezenei unui simbol de
informaie egal cu 1, la intrarea codorului, i ramurile reprezentate prin linii
pline, unui simbol de informaie egal cu 0. Fiecrei ramuri i s-a asociat valoarea
cuplului binar disponibil la ieirea codorului.
Dup m+1 ntrzieri, oricare ar fi starea iniial a codorului, trellis-ul se
repet. Din fiecare nod pleac 2k ramuri (n cazul de fa sunt dou ramuri) i n
fiecare nod converg 2k ramuri.
Pornind de la starea S0 = (00) n momentul t = 0, de exemplu, vedem c
exist patru ci care permit atingerea strii S0 = (00) n momentul t = 4.
00 00 00 00 calea 1
00 11 01 11 calea 2
11 10 10 11 calea 3
11 01 11 00 calea 4
Diagrama de stri
Diagrama de stri este o alt reprezentare a funcionrii unui codor
convoluional, n care timpul nu apare n mod explicit. Aceast diagram, care
00 00 00 00
00 0011 11 11 11
11 11
01 01 01
01 01
10 10 10
10 10
t=0 t=1 t=2 t=3 t=4
00
01
10
11
21 , kk aaik=1
21 , kk aaik=0
2.3 - Reprezentarea grafic a codurilor convoluionale
17
se poate deduce din trellis, nu reine dect diferitele stri ale codorului i felul n
care acestea comunic.
n Fig. 2.6 s-a reprezentat diagrama de stri asociat codorului convoluional
din Fig. 2.2. Diagrama de stri permite evaluarea funciei de transfer a
codorului, care va fi utilizat pentru calculul performanelor codului.
Fig. 2.6: Diagrama de stri a codorului din Fig. 2.2.
Diagramele de stri corespunztoare codurilor convoluionale din Fig. 2.3 b) i
Fig. 2.4 sunt prezentate n Fig. 2.7.
Fig. 2.7 Diagramele de stri pentru codoarele convoluionale: a) RSC; b) NRSC.
00
10
11 01
11
01
10 00
00
10 01
11
21 , kk aaik=1
21 , kk aaik=0
00
10 01
11
00
00
01 01
11 11
10
10
a)
00
10 01
11
00
00
01
01
11
11
10
10
b)
Coduri convoluionale - 2
18
2.4 Distana liber
La fel ca pentru codurile bloc, distana minim a CC este un parametru
fundamental, deoarece determin capacitatea de control a erorii cnd numrul mediu de
erori raportat la numrul de cuvinte de cod este mic. Oricum, procesul de estimare a
distanei este mai complex n cazul codului convoluional dect n cazul unui cod bloc
deoarece aceast operaie depinde de tipul de decodor folosit. Mai precis depinde de
numrul de cadre, m, folosit de decodor [WAD00] (Fig. 2.8).
Fig. 2.8 Cadrele folosite de un decodor convoluional binar.
Distana minim dm, de ordin m, a unui CC este minimul distanelor Hamming
dintre toate perechile posibile ale secvenelor codate sau ale cuvintelor de cod de
lungime de m cadre (sau ramuri) ce difer n cadrul lor iniial :
dm=min dH(um,vm), u1v1 (2.16)
unde, primele m cadre ale celor dou cuvinte de cod sunt notate um i vm.
Fr a pierde din generalitate, relaia (2.16) se poate reduce la gsirea distanei
Hamming minime de la cuvntul specific la oricare din celelalte cuvinte de cod. n
consecin, distana minim a unui CC reprezint numrul minim de 1 din toate
cuvintele de cod care nu au toi biii de informaie egali cu zero.
Conform teoremei care afirm c distana minim, d, a unui cod liniar este egal cu
ponderea Hamming minim a vectorilor nenuli, rezult c pentru determinarea distanei
minime trebuie identificat pe trellis-ul asociat codului studiat, calea cu ponderea cea
mai mic. Prin ponderea unei ci se nelege numrul de simboluri de 1 care apar pe
acea cale. De exemplu, folosind Fig. 2.2, se identific calea de pondere minim (este
cea marcat cu rou).
me cadre k bii n bii
m cadre
intrarea codorului
ieirea codorului
ieirea decodorului
2.4 - Distana liber
19
Odat ce dm a fost determinat putem folosi acelai mecanism de control al erorii ca
i pentru codurile bloc. CC poate corecta orice structur de t erori sau mai puin de t
erori din oricare m cadre adiacente, dac este satisfcut condiia:
12 + tdm (2.17)
Un decodor convoluional poate corecta orice structur (izolat) de t sau mai puine
erori care apar ntr-o secven continu de mn simboluri. Dup cum am menionat mai
sus distana minim, dm, depinde de tipul de decodare utilizat.
De exemplu, tehnicile simple de decodare cu logic de prag au o memorie de
decodare egal cu doar o lungime de constrngere. Cea mai important distan
msurat pentru codurile convoluionale corespunde lui m i este denumit dfree, distan liber. Aceast distan este potrivit pentru metodele de decodare
probabilistice, cum ar fi decodarea Viterbi i decodarea secvenial, din moment ce aici
memoria de decodare este n principiu nelimitat. Pentru a gsi distana liber n
diagrama trellis din Fig. 2.5, se examineaz toate cile care pleac din starea zero
i se ntorc la aceast stare. Calea cu ponderea Hamming minim ne d dfree, care
n cazul codului din Fig. 2.2 rezult a fi dfree=5, corespunztor cuvntului de cod:
110111.
2.5 Funcia de transfer asociat unui cod convoluional
Funcia de transfer a codului este utilizat pentru a determina distribuia ponderilor
Hamming ale diferitelor ci care diverg de la calea nul i apoi converg din nou spre ea.
Ea se poate calcula pornind de la diagrama de stri, scindnd starea S0=(00) n dou
stri (starea Si i starea Sf), apoi aducnd pe fiecare ramur un cuplu DjBi unde
exponenii acestor argumente indic: pentru D - ponderea secvenei emise, pentru B -
ponderea secvenei de intrare corespunztoare (0 sau 1). Graful ataat diagramei de
stri din Fig. 2.6 este prezentat n Fig. 2.9.
Coduri convoluionale - 2
20
Fig. 2.9 Graful corespunztor diagramei de stri din Fig. 2.6.
Prezena lui B semnific faptul c la intrarea codorului bitul de informaie, i,
a fost 1. Gradul lui D ne d ponderea secvenei emise, adic numrul de unu-ri
din aceast secven.
Funcia de transfer T(D, B) a codului este definit de urmtoarea relaie:
( )i
f
SS
BDT =,
(2.18)
Utiliznd graful din Fig. 2.9, putem s scriem urmtoarele ecuaii:
233
12
2
321
12
DBSDBSSBSBSDS
DSDSSSDS
i
f
+=
+=
+=
=
(2.19 a)
rezult:
if BSDBDS5)21( ==
(2.19 b)
Dup rezolvarea acestui sistem de patru ecuaii, se obine funcia de transfer a
codului:
BDBD
SS
BDTi
f
21),(
5
==
(2.20)
Dezvoltnd funcia de transfer T (D, B) n serie de puteri, putem s scriem [GLJ96]:
Si
S3
S2 SfS1D2
DB
DB
D2B
D
B
D
2.5 - Funcia de transfer asociat unui cod convoluional
21
=
++=
0
152),(k
kkk BDBDT
(2.21)
Aceast dezvoltare n serie arat c exist 2k ci de pondere Hamming (k+5)
i c acestea corespund respectiv secvenelor de ponderi (k+1) de la intrarea
codorului. Exponentul variabilei D, n primul termen al dezvoltrii n serie de
puteri a funciei de transfer, pentru k=0, este egal cu distana liber dfree a
codului (pentru exemplul nostru dfree = 5).
Pentru un cod de rat R=k/n, probabilitatea de eroare Peb poate fi mrginit
superior de urmtoarea relaie:
( )1,
,1
==
BDeb B
BDTk
P
(2.22)
unde T(D,B) este funcia de transfer a codorului i este o mrime ce depinde de tipul
canalului utilizat.
n continuare se prezint valorile lui pentru dou canale clasice.
1. Canal cu ieire binar:
=
=1
010
jjj pp
(2.23)
unde pi,j, i=0,1 este probabilitatea ca un eantion binar de la intrarea decodorului s fie
egal cu j, condiionat de emisia, de la codor, a unui element binar avnd valoarea i.
2. Canal cu ieire continuu:
( ) ( )+
= dyypyp 10
(2.24)
unde pi(y), i=0,1 reprezint densitatea de probabilitate a eantioanelor analogice de la
intrarea decodorului, condiionat de emisia de la codor a unui element binar avnd
valoarea i.
Coduri convoluionale - 2
22
Pentru a ilustra calculul probabilitii de eroare voi considera dou exemple:
1. Canal binar simetric
Se cunoate c intrarea i ieirea unui canal binar simetric sunt alctuite din
elemente binare, din alfabetul {0,1}. Cantitatea pi,j, i=0,1, ce apare n relaia (2.23),
reprezint aadar probabilitatea de tranziie a canalului. Notnd cu p probabilitatea de
eroare din canal, se obine:
pi,j = p, dac i j
pi,j = 1-p, dac i = j
(2.25)
Rezult c va fi egal cu:
( )pp = 12 (2.26)
Considernd codorul convoluional din Fig. 2.2 (k=1 i n=2) i innd cont de faptul c:
( )[ ]2
5
21,
DBD
BBDT
=
(2.27)
probabilitatea de eroare Peb, conform relaiei (2.22), este mrginit superior de:
( )[ ]( )[ ]2
5
141
132
pp
ppPeb
(2.28)
Dac se consider o modulaie binar (modulaie de faz cu dou sau 4 stri),
probabilitatea de eroare p pe canalul binar simetric este egal cu:
021
NRE
erfcp b=
(2.29)
2.5 - Funcia de transfer asociat unui cod convoluional
23
unde Eb reprezint energia pe element binar de informaie transmis, erfc este funcia
eroare, R=1/2 reprezint rata codului, iar N0 este densitatea spectral de putere
unilateral a zgomotului.
2. Canal AWGN
Ieirea unui canal AWGN (zgomot aditiv alb gaussian) fiind format din eantioane
analogice, mrimile pi(y), i=0,1 reprezint densitile de probabilitate condiionate ale
acestor eantioane. Mrimea definit de relaia (2.24) este egal cu:
( ) ( )
== +
010 exp N
REdyypyp b
(2.30)
i probabilitatea de eroare pe element binar de informaie, pentru codul convoluional
din Fig. 2.2, poate fi mrginit superior conform relaiei (2.22) i utiliznd relaia (2.27)
rezult:
( )22/2/5
0
0
21 NE
NE
ebb
b
e
eP
(2.31)
Calculul marginii superioare a probabilitii de eroare Peb plecnd de la relaia (2.22)
necesit determinarea funciei de transfer a codorului. Din pcate numrul de stri ale
codorului crete exponenial n funcie de lungimea sa de constrngere, iar calculul
funciei de transfer devine dificil de efectuat pe msur ce lungimea de constrngere
depete cteva uniti. Aceast problem poate fi rezolvat prin nlocuirea funciei de
transfer cu dezvoltarea sa n serie, n expresia (2.22) a marginii superioare a
probabilitii de eroare.
Pentru codorul din Fig. 2.2 lund B=1 n relaiile (2.21) i (2.27), i dezvoltnd n
serii de puteri rezult:
Coduri convoluionale - 2
24
( ) ddd
d
dd
dd
d
ddB
DdnDDDD
DBDTff
f =
=
=
=
===
= 2221
),(0
55
1
( )[ ] ( ) ( ) ( )
d
ddd
d
dd
ddddB DdwDdDdDD
DB
BDT
ff
f =
=
=
===+=
=
0
52
5
1 421221
,
(2.32)
Probabilitatea de eroare va fi marginit superior de:
( ) ( ) dd
d
BDeb dB
BDTP =
=
== 5
5
1,
42,
(2.33)
Notnd:
( ) ( )42 5 = ddw d (2.34)
i remarcnd c d=5 este distana liber a codului, expresia (2.33) se poate scrie mai
general, pentru un cod de rat k/n, sub forma:
( ) ddd
ebf
dwk
P =
1
(2.35)
Ansamblul de coeficieni n(d) i w(d) este numit spectrul de distan al codului.
2.6 Simularea spectrului ponderilor
n literatur, [THI93], am gsit spectrul ponderilor doar pentru un numr redus de
coduri convoluionale de rat R=1/2 i lungime de constrngere K=3. n tabelul urmtor
am reprezentat, cu ajutorul propriilor simulri, [BAK04a], spectrul ponderilor (coloana
n(d)) pentru toate codurile convoluionale, exceptnd codurile convoluionale recursive
i nesistematice, RNSC (Recursive Non-Systematic Code).
2.6 - Simularea spectrului ponderilor
25
Tabel 2.1 Spectrul ponderilor pentru codurile convoluionale de rat 1/2 i K=3. Cod
d NRSC[1,5] (1) n(d) w(d)
NRSC[1,7] (2) n(d) w(d)
RSC[1,7/3] (3) n(d) w(d)
RSC [1,1/5] (4) n(d) w(d)
RSC[1,7/5] (5) n(d) w(d)
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16
0 0 0 0 1 1 1 2 1 3 2 6 4 14 7 30 11 57 17 102 27 181 44 324 72 580 117 1028 189 1801 305 3130
0 0 0 0 0 0 2 3 0 0 5 15 0 0 13 58 0 0 34 201 0 0 89 655 0 0 233 2052 0 0 610 6255
0 0 0 0 0 0 1 2 2 4 2 6 5 18 8 32 13 62 24 128 40 236 69 452 120 856 205 1586 354 2956 610 5458
0 0 0 0 1 2 3 6 5 10 8 18 12 29 19 49 31 84 51 145 81 239 130 401 210 678 341 1151 553 1944 885 3218
0 0 0 0 0 0 0 0 1 2 2 6 4 14 8 32 16 72 32 160 64 352 128 768 256 1664 512 3584 1024 7680 2048 16384
Cod d
RSC[1,1/7] (6) n(d) w(d)
RSC[1,3/7] (7) n(d) w(d)
RSC[1,5/7] (8) n(d) w(d)
NRNSC[3,7] (9) n(d) w(d)
NRNSC[5,7] (10) n(d) w(d)
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16
0 0 0 0 0 0 2 5 0 0 5 15 0 0 13 46 0 0 34 139 0 0 89 413 0 0 233 1210 0 0 610 3505
0 0 0 0 0 0 1 2 2 6 2 6 5 17 8 32 13 55 24 112 40 204 69 376 120 704 205 1284 354 2354 610 4302
0 0 0 0 0 0 0 0 1 3 2 6 4 14 8 32 16 72 32 160 64 352 128 768 256 1664 512 3584 1024 7680 2048 16384
0 0 0 0 0 0 1 2 2 4 2 8 5 21 10 48 15 87 28 188 54 394 85 698 146 1350 269 2664 460 4906 770 9008
0 0 0 0 0 0 0 0 1 1 2 4 4 12 8 32 16 80 32 192 64 448 128 1024 256 2304 512 5120 1024 11264 2048 24576
unde: d reprezint ponderea cii; n(d) este numrul de ci de pondere d, w(d) este
suma ponderilor din secvenele de informaie corespunztoare celor n(d) ci.
n continuare, pe baza rezultatelor pe care le-am obinut, am fcut o analiz a acestor
coduri.
O prim comparaie ce se poate face pe baza tabelului 2.1 este din punct de vedere
al distanei minime a codului. Astfel, exist :
- dou coduri cu distana minim dmin=3, codul nerecursiv i sistematic, NRSC[1,5]
i codul recursiv i sistematic, RSC[1,1/5],
- cinci coduri: NRSC [1,7], RSC[1,7/3], RSC[1,1/7], RSC[1,3/7] i NRNSC (Non-
Recursive Non-Systematic Code) [3,7] au dmin=4,
- iar codurile: RSC[1,7/5], RSC[1,5/7] i NRNSC[5,7] au dmin=5.
Coduri convoluionale - 2
26
Am notat n paranteze matricea generatoare n octal. De exemplu, lui
G(D)=[1,1/1+D2] i corespunde G=[1,1/5]. Distana minim superioar a ultimelor 3
coduri, specificate mai sus, indic o superioritate din punctul de vedere al capacitii de
corecie, fapt ce se va manifesta, n special la raporturi semnal/zgomot mari, unde sunt
importante cuvintele (cile) de ponderi mici. n Fig. 2.10 se prezint spectrul ponderilor
codului recursiv i sistematic, RSC[1,5/7]:
Fig. 2.10 Distana spectral a codului RSC[1,5/7]: a) log(n(d)+1) /d; b) log(w(d)+1) / d.
Pe baza observaiilor anterioare i datorit faptului c funcia w(d) ia valoarea 1
pentru codul NRNSC[5,7] i 2 pentru codul RSC[1,7/5] pentru dmin=5, se poate
concluziona c cel mai performant cod la SNR-uri mari va fi NRNSC[5,7], [BAK04a].
La SNR-uri mici, vor conta cile cu ponderi mari. Cu alte cuvinte, aici se recomand
codurile NRSC[1,7] i RSC[1,1/7] sau chiar NRSC[1,5] i RSC[1,3/7].
5 4.5 4
3.5 3
2.5 2
1.5 1 0.5 0
54.54
3.53
2.52
1.51
0.500 02 4 6 8 10 12 14 16 2 4 6 8 10 12 14 16
a) b) d d
log(
n(d)
+1)
log(
w(d
)+1)
CAPITOLUL 3
Turbo coduri
Dintre toate metodele de corecie a erorilor cunoscute pn astzi, turbo codurile
(TC) alturi de codurile LDPC (Low-Density Parity-Check), [CFRU01, BCVSV02] se
apropie cel mai mult de limita lui Shannon [SHA48], limita teoretic a ratei maxime de
transfer a informaiei printr-un canal cu zgomot. Datorit performanelor lor apropiate
de capacitatea lui Shannon, TC-urile, nc de la introducerea lor [BGT93], au beneficiat
de o atenie deosebit. Astfel, din momentul apariiei lor, TC-urile au fost studiate pe
larg i adoptate n mai multe sisteme de comunicaii.
Turbo codurile sunt atractive, n special, pentru sistemele de comunicaii mobile,
fiind incluse n standardele celulare de generaia a treia (3G), cum ar fi: Sistemul de
Telecomunicaii Mobile Universal (UMTS-Universal Mobile Telecommunications
System), cunoscut i sub denumirea de Acces Multiplu prin Divizare n Cod de Band
Larg (WCDMA-Wideband Code Division Multiple Access), [TSG99] i CDMA2000,
[TIA02]. Deasemenea, sunt incluse i n standardele video de difuzare digital (DVB-
Digital Video Broadcasting) de la canal spre satelit (DVB-RCS), [[ETSI03]] n
sistemul de distribuie terestr (DVB-RCT), [ETSI02] ct i n standardele 802.16-2004
(deseori numit 802.16d), [STAND04] i 802.16e-2005 (care este o mbuntire a
standardului 802.16-2004 i care este deseori numit 802.16e) [STAND05], primul
standard fcnd referire la WiMAX (Worldwide Interoperability for Microwave
Access) fix deoarece acest standard nu are suport pentru mobilitate, iar al doilea la
WiMAX mobil, deoarece a introdus, printre alte lucruri, i suportul pentru mobilitate.
Secvena de informaie este codat de dou ori, avnd un interleaver ntre cele dou
codoare. Rolul interleaver-ului este acela de a se asigura c cele dou secvene de bii
codate sunt independente una fa de cealalt, datorit amestecrii biilor de informaie
de ctre acesta. Cel mai des sunt utilizate codoarele RSC cu ieire sistematic care este
echivalent cu sevena de informaie original, precum i o secven de informaie de
paritate. Cele dou secvene de paritate pot fi apoi puncturate nainte de a fi transmise
mpreun cu secvena de informaie original a decodorului. Aceast puncturare a
informaiei de paritate permite o gam larg a ratelor de codare i deseori este transmis
Turbo coduri - 3
28
jumtate din informaia de paritate de la fiecare codor. mpreun cu secvena de date
original acesta conduce la o rat de codare 1/2.
Dou decodoare RSC sunt utilizate la decodare. Trebuie utilizai algoritmi speciali
de decodare, care s accepte intrri soft i care genereaz ieiri soft pentru secvena
decodat. Aceste intrri i ieiri soft furnizeaz o indicaie asupra faptului c un bit
oarecare a fost 0 sau 1, precum i raportul de plauzibilitate care d probabilitatea ca
bitul respectiv s fi fost corect decodat. Turbo decodorul opereaz n mod iterativ. n
prima iteraie primul decodor RSC furnizeaz ieiri soft dnd o estimare a secvenei de
date originale bazate doar pe intrrile soft furnizate de canal. De asemenea el furnizeaz
o ieire extrinsec. Ieirea extrinsec pentru un bit dat nu se bazeaz numai pe intrarea
canalului corespunztoare acestui bit ci i pe informaia biilor vecini i pe
constrngerile impuse de ctre codul ce a fost utilizat. Aceast ieire extrinsec de la
primul decodor, este utilizat de ctre cel de-al doilea decodor RSC, ca informaie a-
priori, i aceast informaie mpreun cu intrrile canalului sunt utilizate de ctre cel de-
al doilea decodor RSC pentru a genera ieirea sa soft i informaia sa extrinsec. n
ceea de a doua iteraie informaia extrinsec a celui de-al doilea decodor, de la prima
iteraie, este utilizat ca informaie a-priori de primul decodor, i, utiliznd aceast
informaie a-priori, decodorul poate decoda corect mai muli bii fa de prima iteraie.
Acest ciclu poate continua, la fiecare iteraie, ambele decodoare RSC producnd o ieire
soft i informaie extrinsec bazate pe intrrile canalului i pe informaia a-priori,
obinut din informaia extrinsec provenit de la cellalt decodor. Dup fiecare iteraie,
BER scade, dar mbuntirile obinute cu fiecare iteraie se micoreaz pe msur ce
numrul de iteraii crete, astfel c din motive de complexitate sunt utilizate de obicei
ntre 4 i 15 iteraii.
n lucrarea lor de nceput, Berrou .a., au invocat o versiune modificat a
algoritmului de decodare MAP, datorit lui Bahl .a., [BCJR74], n structura iterativ de
mai sus pentru decodarea codurilor componente. Acest algoritm, clasic, conduce la o
probabilitate minim a erorii pe bit. De la apariia turbo codurilor s-a depus un efort
mare pentru a reduce complexitatea decodorului, de ctre diveri cercettori, ca
Robertson, Villebrun i Hoher [RVH95], Berrou .a. [BAAF93], Goff, Glavieux i
Berrou [GGB94]. Robertson i Worz [ROW98] sugereaz utilizarea codurilor mpreun
cu scheme de modulaie care folosesc eficient banda de frecvene. Lucrrile lui
Benedetto i Montorsi [BEM96a, BEM96b] respectiv Perez .a. [PSC96] au facilitat
nelegerea cauzelor performanelor excelente ale turbo codurilor. Un numr de
3.1 - Turbo codorul
29
contribuii similare au fost aduse de ctre Hagenauer, Offer i Papke [HOP96] i de
Pyndiah [PYN97], care extind conceptul de turbo i la codurile bloc concatenate n
paralel. Brbulescu i Peitrobon [BAP94], ca i un numr de ali autori, aloc o mare
importan realizrii interleaver-ului.
Din punctul de vedere al concatenrii codurilor convoluionale componente de la
codor, respectiv, decodor, rezult urmtoarele scheme: coduri convoluionate
concatenate paralel (turbo codurile), coduri convoluionale concatenate serie i coduri
convoluionale concatenate hibrid. n paragraful 3.3 se prezint codurile convoluionale
concatenate paralel.
3.1. Turbo codorul
Structura general utilizat n turbo codor este prezentat n Fig. 3.1, [BGT93].
Sunt utilizate dou coduri componente pentru a coda biii de intrare i un interleaver
plasat ntre cele dou codoare.
Fig. 3.1 Schema unui turbo codor.
n general sunt utilizate codurile RSC, ca i coduri componente, dar este
posibil de a se obine performane bune, utiliznd o structur ca cea din Fig. 3.1,
cu ajutorul altor coduri componente, cum ar fi codurile bloc, propuse de
Hagenauer, Offer i Papke [HOP96]. De asemenea, este posibil s se utilizeze
mai mult de dou coduri componente.
Ieirile celor dou codoare componente sunt mai apoi puncturate [THI93] i
multiplexate. De obicei ambele coduri componente RSC sunt de rat 1/2, dnd
un bit de paritate i un bit sistematic pentru fiecare bit de intrare.
bii de intrare
Codor 1
Codor 2 Interleaver
Puncturare i
Multiplexare bii de ieire
Turbo coduri - 3
30
Pentru a obine un turbo codor cu o rat de codare R=1/2, trebuiesc
puncturai jumtate din biii de ieire ai fiecruia dintre codoare. Astfel, se
transmit toi biii sistematici ai primului codor RSC i jumtate din biii de
paritate ai fiecrui codor. De precizat c biii sistematici sunt foarte rar
puncturai, deoarece aceasta degradeaz dramatic performana codului.
n Fig. 2.3b) s-a prezentat un cod RSC de rat 1/2 i lungime de constrngere
K=3, ce poate fi folosit ca i cod component n Fig. 3.1. Codurile concatenate n
paralel au fost propuse i analizate de Claude Berrou .a. n articolul din 1993,
[BGT93].
mbuntiri considerabile n performan ale turbo codurilor se datoreaz
interleaver-ului utilizat ntre cele codoare i a utilizrii codurilor recursive ca i
coduri componente. Articolele publicate de Benedeto i Montorsi [BEM96a,
BEM96b] ncearc s explice remarcabilele performane ale turbo codurilor,
ajungnd la concluzia c turbo codurile pot avea un ctig al performanei
proporional cu lungimea interleaver-ului utilizat. Complexitatea decodrii per
bit nu depinde de lungimea interleaver-ului. Aadar pot fi obinute perfomane
foarte bune cu o complexitate rezonabil prin utilizarea interleaver-elor foarte
lungi. ns, n multe aplicaii importante, precum transmisiile vocale, lungimile
blocurilor de date extrem de mari nu sunt practice, datorit ntrzierii rezultate.
3.2 Turbo decodorul
Structura general a unui decodor iterativ este reprezentat n Fig. 3.2. Dou
componente decodoare sunt conectate prin interleaver-e, ntr-o structur similar
cu cea de la codor. Aa cum se observ din figur, fiecare decodor are trei
intrri: biii de ieire din canal codai sistematic, biii de paritate transmii de
ctre codul component asociat i informaia de la cellalt decodor numit
informaie a-priori. Decodoarele componente au de explorat ambele intrri
provenite din canal i aceast informaie a-priori.
3.2 - Turbo decodorul
31
Fig. 3.2 Schema turbo decodorului.
Ele trebuie de asemenea s furnizeze i (cele ce sunt cunoscute ca i) ieiri soft pentru
biii decodai. Aceasta nseamn c, la fel cum furnizeaz secvena de bii de la ieire
decodat, decodoarele componente trebuie s genereze probabilitile de decodare
corect, asociate pentru fiecare bit. Ieirile soft sunt tipic reprezentate n termenii aa
numiilor logaritmi de rapoarte de plauzibilitate, (Log Likelihoods Ratios), LLRs.
Polaritatea LLR-ului determin semnul bitului, n vreme ce amplitudinea sa cuantific
probabilitatea deciziei corecte.
Turbo decodorul din Fig. 3.2 lucreaz iterativ, n prima iteraie primul decodor
component preia doar valorile ieirilor canalului i produce o ieire soft ca o estimare a
biilor de date. Ieirea soft a primului decodor este apoi utilizat ca informaie
adiional de cel de al doilea decodor mpreun cu ieirile canalului pentru a calcula
estimaii si pentru biii de date. Acum cea de a doua iteraie poate s nceap, primul
decodor decodeaz din nou ieirile din canal, dar de data aceasta cu o informaie
adiional despre valorile biilor de intrare furnizat de ieirea celui de-al doilea decodor
n prima iteraie. Aceast informaie adiional permite primului decodor s obin un
set de ieiri soft de acuratee mai mare, care este apoi utilizat de cel de-al doilea decodor
ca informaie a-priori. Acest ciclu este repetat i cu fiecare iteraie rata de eroare per bit
a biilor decodai, tinde s scad. ns, mbuntirea performanei cu creterea
numrului de iteraii descrete. Astfel, din motive de complexitate, sunt utilizate uzual
doar un numr de 8 iteraii.
Datorit ntreeserii utilizat la codor, trebuie ntreesut i de-ntreesut LLR-ul care
este utilizat pentru a reprezenta valorile soft ale biilor, aa cum se vede n Fig. 3.2. n
plus, datorit naturii iterative a decodorului, trebuie avut grij s nu se reutilizeze
aceeai informaie mai mult de o dat la fiecare pas de decodare. Din acest motiv a fost
Decodor 1
Decodor 2
Interleaver
Interleaver
De-Interleaver
+
+
Intrri
soft
din
canal
Sistematic
Paritate 1
Paritate 2
-
-
-
-
Ieire soft
Turbo coduri - 3
32
Iex21
C1
C2
I
u x1 DEC1
DI
DEC2
I I
Can
al d
e tr
ansm
isie
Iex12
x0
x2
y1
y0
y2
LLR1
utilizat conceptul aa numitei informaii extrinseci i intrinseci n articolul scris de
Berrou .a. [BGT93]. Alte decodoare, neiterative, care dau o decodare optimal a turbo
codurilor au fost propuse, [BRH00, BRH97]. ns mbuntirea n performan,
comparativ cu decodoarele iterative, s-a gsit a fi de doar 0,35 dB [HLY02], i sunt
foarte complexe. Aadar schema prezentat n Fig. 3.2 este utilizat cel mai des.
3.3 Concatenarea paralel a codurilor convoluionale
n cadrul acestei teze, n primele simulri realizate, am utilizat codurile
convoluionale concatenate n paralel (turbo codurile), nepuncturate. Schema general a
unui turbo cod, TC, este prezentat n Fig.3.3:
Fig. 3.3 Coduri convoluionale concatenate paralel.
Secvena de informaie, notat u, este codat de ctre codorul C1 rezultnd secvena
de paritate x1. Aceeai secven de bii, u, este furnizat, ns n alt ordine obinut prin
ntreesere cu ajutorul interleaver-ului I, codorului C2, care genereaz la rndul su,
secvena de paritate x2. Secvenele rezultate ux =0 , x1 i x2, prin multiplexare i
modulare (operaii omise n Fig. 3.3) se transform n semnalul ce va fi emis n canal.
La ieirea acestuia, prin demodulare i demultiplexare rezult secvenele (soft)
recepionate, corespunztoare: y0, y1 i y2.
Fiecare decodor calculeaz LLR-ul pentru fiecare bit din u:
( ) ( )( )yupyup
uLLRi
ii 0
1ln
=
=
= . (3.1)
3.3 - Concatenarea paralel a codurilor convoluionale
33
n figur este prezentat doar logaritmul raportului de plauzibilitate al primului
decodor, notat LLR1 i informaia extrinsec destinat celuilalt decodor.
Fiecare decodor primete informaie extrinsec i pe baza ei i a secvenelor venite
din canal (y0 i y1 respectiv y0 ntreesut i y2) furnizeaz la rndu-i informaie
extrinsec. Acest proces se repet iterativ de un anume numr de ori (impus sau
calculat, funcie de tipul turbo codului). Dup efectuarea tuturor iteraiilor se ia o
decizie hard asupra logaritmului raportului de plauzibilitate generat dup ultima iteraie
de unul din cele dou decodoare (n Fig. 3.3 s-a ales LLR1). Secvena rezultat
constituie ieirea turbo decodorului.
3.4 Dispozitive de ntreesere
ntreeserea este o tehnic de cretere a capacitii de corecie a erorii de codare. A
fost deseori utilizat mpreun cu codarea controlat a erorilor pentru canalele cu erori
n rafal [VUY01]. Un exemplu este cel al canalului cu fading multici, la care variaiile
de semnal datorate propagrii multici determin adeseori scderea nivelului semnalului
sub cel al nivelului zgomotului, ducnd la un numr mare de erori.
O metod efectiv de reducere a acestor erori este aceea de a insera un interleaver
ntre codor i intrarea canalului. Datele codate sunt reordonate de interleaver i apoi
transmise n canal. La receptor, de-interleaver-ul realizeaz operaia invers, pentru a
reda datele n ordinea original. Ca rezultat al acestei operaii de ntreesere i de-
ntreesere, erorile n rafal sunt mprtiate, astfel nct erorile dintr-un cuvnt de cod
apar independent. Astfel, canalul cu erori n rafal este transformat ntr-un canal cu erori
aleatoare i un cod realizat pentru un canal cu erori independente poate fi utilizat i n
cazul canalelor cu erori n rafale.
n cazul turbo codrii, ntreeserea este realizat nainte de a fi codat informaia de
date de cel de-al doilea codor component. n general lungimea N a interleaver-ului este
semnificativ mai mare dect memoria codului i elementele interleaver-ului sunt alese n
mod aleator.
Limita capacitii Shannon poate fi atins doar de coduri bloc de lungime mare.
Acestea pot fi implementate n varianta construcional doar folosind memorii mari.
Rolul de baz al interleaver-ului este de a construi un cod bloc lung pentru coduri
convoluionale cu memorie mic.
Turbo coduri - 3
34
Un alt rol al interleaver-ului este acela de a mprtia erorile n rafal. Interleaver-ul
furnizeaz informaia de date amestecat spre cel de-al doilea codor component
[BGT93], i decoreleaz intrrile celor dou decodoare componente de la
recepie, astfel nct poate fi aplicat un algoritm de decodare sub-optimal iterativ
bazat pe schimbul de informaie necorelat dintre cele dou decodoare
componente. De exemplu, dup corecia unor erori n primul decodor
component, cteva din erorile rmase pot fi mprtiate de ctre interleaver astfel
nct s poat fi corectate de cellalt decodor. Crescnd numrul de iteraii, n
procesul de decodare, probabilitatea erorii pe bit se apropie de capacitatea
canalului.
Un dispozitiv de ntreesere realizeaz o permutare a unei secvene de numere
[BAK04b), KBN05], de forma:
II : , cu { }NI K,2,1= , (3.2)
unde N reprezint lungimea secvenei ce trebuie ntreesut. Pentru refacerea ordinii
iniiale se utilizeaz un dispozitiv pereche, de de-ntreesere, ce implementeaz funcia
invers:
II :1 , cu ( )( ) Iiii = ,1 . (3.3)
Un interleaver bun trebuie s ndeplineasc dou condiii: s aib o distan minim
de ntreesere de valoare ct mai mare i s aib un grad de mprtiere ct mai bun.
Fiind dat funcia interleaver, , definim distana de ntreesere dintre poziiile i i j
ca:
( ) ( ) ( ) jiIjijijijid += , , ,, . (3.4)
Atunci distana minim de ntreesere este dat prin, [CRO00, MCK04]:
) ,(min,
jiddji
Ijimin
= .
(3.5)
3.4 - Dispozitive de ntreesere
35
Mulimea valorilor funciei d(.), dat prin relaia (3.5), este mrginit inferior de
valoarea 2 iar superior de 2N-2. 3.4.1 Interleaver aleator
Interleaver-ul aleator, [VUY01] este relativ simplu de realizat, ofer o bun
mprtiere a secvenei originale, ns are n general dmin=2, adic cea mai mic valoare
posibil. n Fig. 3.4 este ilustrat operaia de permutare de tip aleator pentru un bloc de
date de lungime N=10. Procedeul de construcie al unui dispozitiv de ntreesere aleator
este urmtorul. Cunoscnd lungimea de ntreesere, N, se construiete mulimea
A={1,2 ...N}. Se alege n mod aleator un numr, n1A. Se atribuie (1) = n1 i se elimin aceast valoare din A. Procedeul se repet pn la epuizarea mulimii A. Aadar,
se poate scrie funcia de mprtiere aleatore de forma:
r(i) = rand(i), iI={1,2 ...Nr}. (3.6)
Fig. 3.4 Dispozitiv de ntreesere aleator.
Un dezavantaj major al ntreeserii aleatoare este nereproductibilitatea procedeului de
generare al funciei : Odat generat funcia de tip aleator ea trebuie memorat pentru
a putea fi reprodus.
3.4.2 Interleaver de tip S
Interleaver-ul S este de tip aleator [DIP95], ns, spre deosebire de interleaver-ul pur
aleator, prin construcie se foreaz o distan minim de ntreesere egal cu S.
Algoritmul de construcie al funciei de ntreesere este urmtorul: se selecteaz o
posibil poziie viitoare pentru bitul curent. Aceasta este comparat cu poziiile celor S
bii selectai anterior n aceeai manier aleatoare. Dac se ndeplinete condiia ca:
1 2 3 4 5 6 7 8 9 10
4 6 1 5 10 2 8 7 3 9
Intrare
Ieire
Turbo coduri - 3
36
Sjn > )()( pentru n i j cu Sjn
3.4 - Dispozitive de ntreesere
37
Fig. 3.5 ntreesere bloc.
3.4.4 Interleaver pseudo-aleator
Interleaver-ul pseudo-aleator [JBD04], face parte din recomandarea CCSDS
(Consultative Comittee for Space Data Systems) denumit CCSDS Recomandation for
Telemetry Channel Coding, [CCSDS02].
Denumirea dispozitivului provine de la faptul c permutrile nu sunt aleatoare n
adevratul sens al cuvntului (avem de-a face cu o dezordine controlat). Este un
dispozitiv de ntreesere performant, care mbin avantajele furnizate de interleaver-ele
aleator i bloc, adic prezint o bun mprtiere la o distan minim suficient de mare.
Permutarea pentru fiecare secven de lungime N a blocului este dat de o
reordonare particular a biilor 1, 2, ... N, generat de urmtorul algoritm:
N = k1k2 unde k1 este un parametru fix, iar k2 variaz n funcie de lungimea
dispozitivului de ntreesere;
pentru s de la 1 la N (poziia curent nainte de interschimbare) se efectueaz
urmtoarele operaii i se obin permutrile )(s :
2mod)1( = sm
=
221
ksi
221 iksj
= )119( += it mod
21k
tq = mod 18 + )21( mjpc q += mod 2k
mNcts +++= )12
1(2)(
Citire pe coloane, n ordinea: 1 2 3 . . . . . 10
nscriere pe linii,
n ordinea: 1 2 3 . . . . .
10
Turbo coduri - 3
38
n care: [ ] parte ntreag,
mod operaie modulo (clase de resturi),
q = 18 i 1p =31, 2p =37, 433 =p , 474 =p , 535 =p , 596 =p , 617 =p ,
678 =p .
3.4.5 Interleaver Takeshita-Costello
Interleaver-ul Takeshita-Costello, este prezentat n [TAC98] i presupune c
lungimea interleaver-ului, NTC, este o putere ntreag a lui 2. Construcia funciei
interleaver-ului este dat n cele ce urmeaz. Vectorul ci=1N, este construit cu
relaia urmtoare:
c(i)=ki(i+1)/2 (3.10)
unde k, n mod uzual, este egal cu unu. Funcia de ntreesere va fi:
(c( i)) = c(i+1), iI (3.11)
3.4.6 Interleaver bloc-aleator
n cadrul acestui paragraf propun dou variante noi de interleaver-e pe care le-am
realizat i analizat. Acest tip nou de interleaver-e , [KBN05], dorete s mbine calitile
interleaver-elor bloc (dmin de valori mari) i aleator (o bun mprtiere), fiind o
alternativ a celui de tip S, care este greu de realizat. Astfel, am propus dou variante
noi de interleaver-e: interleaver bloc aleator n linie, BRL (Block Random in Line),
notat IXBRLY (X i Y sunt dai n Tabelul 3.1) i interleaver bloc cu linii aleatoare,
BLR (Bloc with Random Lines), notat IXBLRY (X i Y sunt dai n Tabelul 3.1), ai cror algoritmi de generare vor fi descrii n continuare. Am presupus c lungimea
acestor interleaver-e este Nbr=XY, la fel ca pentru un interleaver bloc.
3.4 - Dispozitive de ntreesere
39
3.4.6.1 Interleaver bloc aleator n linie, BRL
Pentru nceput, am construit matricea:
c(i,j)=1+i+jX, iI={0,1X-1}, jJ={0,1Y-1} (3.12)
Apoi, am permutat fiecare linie a acestei matrici, c(i,J) folosind relaia:
r(i) = rand(i), iI={1,2 ...Nr}, (3.13 a)
obinnd, astfel matricea b de forma:
b(i,J)= c(i,r(J)) iI (3.13 b)
n final, pentru a crete distana minim de ntreesere se reordoneaz liniile
astfel nct pe primele X/2 poziii s se regseasc liniile impare. Dup ce
realizez ordonarea liniilor fac o citire pe coloan:
BRL(k+jY+1)=b(i, j), i=(2k)I, jJ BRL(k+jY+Y2+1)=b(i, j), i=(2k1)I, jJ (3.14)
unde: Y2 = floor[(Y 1)/2].
Schema interleaver-ului bloc aleator n linie este dat n Fig. 3.6:
Fig. 3.6 Schema interleaver-ului bloc aleator n linie, BRL.
Y
X
nscrie pe coloan
Citete pe coloan
Permutare n linii Reordoneaz liniile
Turbo coduri - 3
40
3.4.6.2 Interleaver bloc cu linii aleatoare, BLR
Algoritmul de generare este identic cu cel al interleaver-ului BRL, cu excepia
pasului doi unde aleatorizarea nu o fac n linie ci ntre linii:
d(i,J)= c(r(i), J)) iI={0,1X-1} (3.15)
Astfel c:
BLR(j+i Y+1)=d(i, j), iI, jJ (3.16)
Distana minim de ntreesere este dminY n cazul interleaver-ului BRL i dminX
n cazul interleaver-ului BLR. Pentru a obine o bun mprtiere n cazul interleaver-
ului BRL dimensiunea X trebuie aleas ct mai mare, iar pentru BLR Y trebuie s fie ct
mai mare. Un bun compromis se obine dac se alege X Y2 pentru BRL respectiv
Y X2.
n Fig. 3.7 este dat schema interleaver-ului bloc cu linii aleatoare:
Fig. 3.7 Schema interleaver-ului bloc cu linii aleatoare, BLR.
n concluzie, se poate spune c cele dou interleavere propuse se difereniaz
prin urmtoarele caracterisitci:
- n cazul interleaver-ului bloc aleator n linie se realizeaz o ntreesere de tip
aleator pur pentru fiecare linie separat. Aceasta reprezint un avantaj deoarece
metoda pur aleatoare este uor de aplicat i de implementat pentru blocuri mai
mici (cum pot fi considerate liniile de lungime Y). Ulterior, reordonarea liniilor
va conferi i o distan minim egal cu X/2. Aadar, interleaver-ul va dispune
i de o bun amestecare (datorit ntreeserii aleatoare) ct i de o distan
nscrie pe coloan
Citete pe linie Permutare ntre linii Y
X
3.4 - Dispozitive de ntreesere
41
minim suficient de mare. Este de ateptat ca acest interleaver s ofere
performane bune.
- n cazul celui de-al doilea interleaver, interleaver bloc cu linii aleatoare, un
dezavantaj fa de primul este c ntreeserea aleatoare a liniilor nu va reui o
distan minim impus (ntreeserea pur aleatoare are deobicei distana minim
egal cu 2, adic cea mai mic posibil).
3.4.7 Performanele interleaver-elor utilizate n turbo coduri
n scopul analizei performaelor, BER i FER (rata erorii pe cadru), interleaver-elor
(de diferite lungimi) utilizate n turbo coduri, am folosit interleaver-ele prezentate mai
sus. Astfel, n Tabelul 3.1, au fost trecute notaiile corespunztoare acestor interleaver-e.
Tabelul 3.1. Interleavere folosite.
unde: - Interleaver-ul aleator s-a notat cu INrS1,
- Interleaver-ul S s-a notat cu INsSY,
- Interleaver-ul bloc s-a notat cu IXRY,
- Interleaver-ul pseudo-aleator s-a notat cu IXP8,
- Interleaver-ul Takeshita-Costello s-a notat cu IXTC,
- Interleaver-ul bloc aleator n linie s-a notat cu IXBRLY,
- Interleaver-ul bloc cu linii aleatoare s-a notat cu IXBLRY .
Nr, Ns, X i Y, iau valorile din Tabelul 3.1.
n diagramele din Fig. 3.8, am prezentat cteva curbe cu performanele BER pe care
le-am obinut, utiliznd diferite interleaver-e:
- interleaver aleator,
- interleaver S,
N 400 900 1800 3600 IXRY I19R21 I29R31 I41R45 I59R61 INrS1 I392S1 I896S1 I1784S1 I3568S1
INsSY I392S5 I392S10 I392S13
I896S5 I896S10 I896S20
I1784S10 I1784S20 I1784S29
I3568S10 I3568S20 I3568S40
IXP8 I392P8 I896P8 I1784P8 I3568P8 IXTC I512TC I1024TC I2048TC I4096TC IXBRLY I49BRL8 I81BRL11 I121BRL15 I225BRL16IXBLRY I7BLR56 I9BLR99 I11BLR165 I15BLR240
Turbo coduri - 3
42
- interleaver bloc,
- interleaver pseudo-aleator,
- interleaver Takeshita-Costello,
- interleaver-e BLR i BRL.
Aceste interleaver-e au fost introduse ntr-un turbo cod nepuncturat, de rat 1/3, n
care dou coduri componente RSC, avnd matricea generatoare G=[1, 15/13] i
lungimea de constrngere a codului convoluional K=4, sunt conectate n paralel
[BGT93]. Lungimile interleaver-elor sunt n jur de: 400, 900, 1800 i 3600. Valorile
exacte iau n consideraie limitarea impus de construcia fiecrui interleaver. n
simulri am folosit algoritmul de decodare MAP i un numr de 12 iteraii. S-a
considerat canalul AWGN i modulaia BPSK (Binary Phase Shift Keying).
0 0.5 1 1.5
10-4
10-3
10-2
10-1
SNR(dB)
BER
uncodedI19R21I392S1I392S5I392S10I512TC
Fig. 3.8 a) Performanele BER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru 5 interleaver-e cu N400.
3.4 - Dispozitive de ntreesere
43
0 0.5 1 1.5
10-4
10-3
10-2
10-1
SNR (dB)
BER
uncodedI392S13I392P8I49BRL8I7BLR56
Fig. 3.8 b) Performanele BER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru alte 4 interleaver-e cu
N400.
0 0.5 1 1.510
-7
10-6
10-5
10-4
10-3
10-2
10-1
SNR (dB)
BER
uncodedI29R31I896S1I896S5I896S10I896S20I896P8I1024TCI81BRL11I9BLR99
Fig. 3.8 c) Performanele BER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru interleaver-e cu N900.
Turbo coduri - 3
44
0 0.2 0.4 0.6 0.8 110
-8
10-7
10-6
10-5
10-4
10-3
10-2
10-1
SNR (dB)
BER
necodatI41R45I1784S1I1784S10I1784S20I1784S29I1784P8I2048TCI121BRL15I11BLR165
Fig. 3.8d) Performanele BER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru interleaver-e cu N1800.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.710
-8
10-6
10-4
10-2
100
SNR(dB)
BER
necodatI59R61I3568S1I3568S10I3568S20I3568S40I3568P8I4096TCI225BRL16I15BLR240
e)
Fig. 3.8 e) Performanele BER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru interleaver-e cu N3600.
3.4 - Dispozitive de ntreesere
45
n Fig. 3.8 se poate observa c performanele S-interleaver-lor cresc odat
cu S, distana de interleav-are minim. Deci, la un grad de mprtiere dat
(deoarece toate sunt interleaver-e aleatoare ele au acelai grad de mprtiere)
aceast distan reprezint o msur a performanelor.
n diagramele din Fig. 3.9 sunt reprezentate curbele corespunztoare
performanelor FER, utiliznd aceleai interleaver-e: interleaver aleator (S=1),
interleaver S, interleaver rectangular (R), interleaver pseudo-aleator (P),
interleaver Takeshita-Costello (TC) i interleaver-ele BLR i BRL.
0 0.5 1 1.510
-4
10-3
10-2
10-1
100
SNR(dB)
FER
Limita ShannonI19R21I392S1I392S5I392S10I392S13I392P8I512TCI49BRL8I7BLR56
Fig. 3.9 a) Performanele FER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru interleaver-e cu
N400.
Turbo coduri - 3
46
0 0.5 1 1.5
10-4
10-3
10-2
10-1
100
SNR(dB)
FER
Limita ShannonI29R31
I896S1
I896S5
I896S10I896S20
I896P8
I1024TC
I81BRL11I9BRL99
Fig. 3.9 b) Performanele FER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru interleaver-e cu
N900.
0 0.2 0.4 0.6 0.8 1
10-4
10-3
10-2
10-1
100
SNR(dB)
FER
Limita ShannonI41R45I1784S1I1784S10I1784S20I1784S29I1784P8I2048TCI121BRL15I11BLR165
Fig. 3.9 c) Performanele FER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru interleaver-e cu
N1800.
3.4 - Dispozitive de ntreesere
47
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7
10-4
10-3
10-2
10-1
100
SNR(dB)
FER
Limita ShannonI59R61I3568S1I3568S10I3568S20I3568S40I3568P8I4096TCI225BRL16I15BLR240
Fig. 3.9 d) Performanele FER ale turbo-codurilor de rat 1/3, [1, 15/13], pentru interleaver-e cu
N 3600.
Analiznd curbele din Fig. 3.8 i Fig. 3.9, am observat c atunci cnd lungimea de ntreesere crete, gradul de mprtiere devine factorul cel mai
important n analiza performanelor BER i FER, [KBN05, BAK04b]. Aadar,
pentru lungimi mici de ntreesere, interleaver-ele au un caracter bloc. n acest
caz, interleaver-ele R, TC, BLR au performane similare cu celelalte. Cel mai bun
interleaver este interleaver-ul TC. La o lungime de ntreesere egal cu 3600
aceste interleaver-e (R, TC, BLR) au cele mai slabe performane. n Fig. 3.8 se
poate observa c performanele interleaver-lor S cresc odat cu S, distana de
interleav-are minim. Deci, la un grad de mprtiere dat (deoarece toate sunt
interleaver-e aleatoare ele au acelai grad de mprtiere) aceast distan
reprezint o msur a performanelor.
Interleaverul P (recomandat de CCSDS, [CCSDS02]), are performane bune
la toate lungimile de ntreesere. Dar, cu creterea lungimii de ntreesere, au
performane mai sczute n comparaie cu interleaver-ele aleatoare.
Analiznd performanele interleaver-lor bloc-aleatoare BLR i BRL, pot fi
fcute urmtoarele observaii. Interleaver-ul BLR are performane similare cu ale
interleaver-elor bloc. Performanele interleaver-ului BRL sunt similare
Turbo coduri - 3
48
performanelor interleaver-lor S, avnd o distan minim comparabil.
Similaritile pot fi explicate innd cont de procedura de construcie. n
construcia interleaver-ului BLR lungimea permutrilor aleatoare a fost egal cu
jumtate din lungimea permutrilor aleatoare realizate n construcia interleaver-
ului BRL. Mai mult, n cazul interleaver-lui BLR, toate coloanele sunt permuate
n acelai fel. n construcia interleaver-lui BRL permutrile sunt realizate
independent de la linie la linie. n ciuda faptului c, la o lungime mare de
ntreesere (N>1000) interleaver-ul S, cu un S mare, este foarte bun, construcia
sa este dificil. n aceast analiz a fost utilizat doar un cod, [1, 15/13], dar
aceast concluzie este valabil pentru orice cod, [BAK04e]. Acesta este motivul pentru care interelaver-ul BRL propus este atractiv; are performane bune i o
construcie simpl.
Aadar, se pot trage urmtoarele concluzii. Am propus dou tipuri de interleaver-e,
interleaver-ul bloc aleator n linie i interleaver-ul bloc cu linii aleatoare, i am comparat
performaele lor, BER i FER, cu ale altor interleaver-e cunoscute n literatur. Analiza
performanelor recomand interleaver-ul BRL propus ca o alternativ la interleaver-ul S,
care este cel mai bun la lungimi mai mari de 1000 bii. Performanele interleaver-ului
propus, BRL, sunt foarte apropiate de cele ale interleaver-ului S, cu S maxim, dar
construcia noului interleaver este mai simpl. n simulrile realizate, deoarece TC-urile opereaz la mai puin de 1dB distan de limita teoretic, s-a cutat obinerea unei
precizii suficient de mari asupra curbelor BER/SNR (FER/SNR) n vederea unei
comparaii veridice, [BAK04c]
3.5 Algoritmi de decodare
Cuvintele de la ieirea unui codor convoluional sunt corelate i fiecare cuvnt este
funcie de m+1 blocuri de informaie. Pentru a decoda o secven binar alctuit din N
cuvinte, este necesar s se considere secvena recepionat n ansamblul su. La ieirea
codorului sunt posibile doar anumite secvene binare, ele corespunznd diferitelor ci ce
exist n trellis. Ca i pentru codurile bloc, decodarea unui cod convoluional n prezena
unui canal binar simetric va consta n a cuta n trellis, secvena binar (corespunztoare
unei ci particulare) cea mai apropiat de secvena recepionat. Aceast secven este
numit secvena cea mai probabil. Adoptnd acelai criteriu ca i pentru codurile bloc,
secvena emis cea mai probabil este cea care se gsete la distan minim
3.5 - Algoritmi de decodare
49
fa de secvena recepionat. Algoritmul Viterbi permite decodarea codurilor
convoluionale, cutnd secvena cea mai probabil din trellis, i este bine adaptat la
decodarea codurilor ce au lungimea de constrngere puin mai mare (tipic, K=7),
[WAD00]. Algoritmul Viterbi poate fi implementat att cu decizie hard ct i cu
decizie soft.
O variant a algoritmului Viterbi, este SOVA (Soft Output Viterbi Algorithm
algoritm Viterbi cu ieire soft), [HAH89]. Acest algoritm este folosit n special la
schemele cu coduri concatenate i anume n turbo coduri.
n afara utilizrii algoritmului SOVA, n turbo coduri se folosesc, ca i algoritmi de
decodare, algoritmii: MAP, Max-Log-MAP i Log-MAP.
3.5.1 Algoritmul Viterbi
3.5.1.1 Algoritmul Viterbi cu decizie hard
Pentru prezentarea acestui algoritm se consider un canal binar simetric (fr
memorie), intrarea decodorului fiind alctuit dintr-o secven de simboluri binare.
n fiecare moment dou ramuri, aparinnd la dou ci diferite, converg spre fiecare
nod al trellis-lui (Fig. 2.5). Din aceste dou ci una este mai probabil, altfel spus, se
gsete la cea mai mic distan Hamming fa de secvena recepionat, dect cealalt
cale. Distana fiind o funcional aditiv, n fiecare nod se pstreaz calea cea mai
probabil numit cale supravieuitoare. Dac se obin dou ci cu aceeai distan
Hamming, doar o singur cale este pstrat, alegndu-se n mod arbitrar una din cele
dou ci posibile, [GLJ96].
n general este dificil s se atepte ca toat secvena binar emis s fie recepionat
pentru a se ncepe operaia de decodare. De fapt, aceasta va introduce o ntrziere
important la decodare, i va fi necesar o memorie de talie foarte mare pentru a
memora toate cile supravieuitoare.
n practic, un decodor Viterbi are o memorie finit ce poate fi vzut ca o fereastr,
W, numit fereastr de decodare, ce pstreaz o poriune finit a trellis-ului. Observnd
derularea algoritmului Viterbi pn la momentul curent t=n, se poate remarca c, urcnd
suficient n timp, cile supravieuitoare converg aproape ntodeauna spre acelai drum n
t=n-W, Fig. 3.10.
Turbo coduri - 3
50
Fig. 3.10 Convergena supravieuitorilor spre o cale unic n t=n-4 (W=4).
Astfel, pentru a decoda elementul binar de informaie emis la t=n-W, rareori este
necesar s se observe secvena recepionat ncepnd de la t=n. Practic, memorarea
supravieuitorilor poate fi aadar limitat la un interval temporal de durat W, i astfel,
ntrzierea la decodare rmne finit pentru a decoda o secven infinit. n fiecare
moment t=n, decodorul Viterbi furnizeaz o decizie cu privire la elementul binar de
informaie prezent la intrare codorului la momentul t=n-W. W trebuie s fie suficient de
mare pentru a asigura o decizie corect asupra celui mai vechi cadru transmis. Durata
intervalului de timp necesar pentru obinerea unui drum unic este o variabil aleatoare.
Simulri pe calculator au demonstrat c durate de:
( )KW 54 , (3.17)
produc aproximri cu erori neglijabile comparativ cu o memorie infinit (W)
a decodorului, fapt pentru care decodoarele Viterbi practice au ferestre de
decodare dimensionate dup relaia (3.17).
3.5.1.2 Algoritmul Viterbi cu decizie soft
n paragraful anterior, s-a prezentat algoritmul Viterbi considernd c intrarea
decodorului a fost alctuit dintr-un ir de simboluri binare (decizii ferme). Codurile
convoluionale se comport bine n decodarea ponderat utiliznd algoritmul Viterbi.
n cazul decodrii ponderate intarea decodorului este n mod sigur constituit de o
secven de simboluri analogice. Dac se consider cazul unei transmisii pe un canal cu
zgomot aditiv alb i gaussian, aceste simboluri sunt gaussiene i necorelate, codiionnd
t = n-4 t = n-3 t = n-2 t = n-1 t = n
So=00
S1
Top Related