8/6/2019 Decodarea Codurilor Convolution Ale Prin Algoritmul Viterbi
1/6
1
DECODAREA CODURILOR CONVOLUTIONALE PRIN ALGORITMUL
VITERBI
1. Introducere
Cele mai cunoscute metode de decodare a codurilor convoluionale sunt:
decodarea cu prag, decodarea secveniali decodarea cu algoritmul Viterbi. n aceastlucrare prezentm algoritmul de decodare Viterbi, deoarece este un algoritm optimal,complexitatea sa este redusi este foarte utilizat n practic.
Secvenele codate se transmit pe canalul de comunicaie dup folosirea uneitehnici de modulaie digital. n prezenta lucrare presupunem c modulaia folosit estemodulaia binarde faz (BPSK Binary Phase Shift Keying). Cu acest tip de modulaie
biii 0, sunt translai n valorile -1, iar biii 1 n valorile +1, prin relaia 2 1k kx c= , unde
keste momentul de timp al translaiei. Dacpe canal existun zgomot aditiv alb gaussian
(AWGN), atunci la fiecare valoare kx , se adun un eantion de zgomot kn , rezultndvaloarea recepionat:
k k kr x n= + . (1)
2. Algoritmul de decodare Viterbi
Prin algoritmul de decodare Viterbi se alege calea ( )ix din trellis de maxim
plauzibilitate, astfel nct se maximizeazprobabilitatea ( )( )iP r x , unde r este secvena
recepionat, iar ( )ix secvena de bii corespunztoare cii din trellis care se consider
secvena decodat. Dac secvena r se transleaz n domeniul valorilor 0, 1, princompararea cu pragul 0, adic unei valori negative i corespunde 0, iar unei valoripozitive i corespunde 1, atunci rezult o decodare hard. Cnd valorile din secvena rsunt lsate nemodificate sau cuantizate pe un numr de nivele mai mare ca 2 avem odecodare cu decizie soft necuantizat, respectiv cuantizat.
n cazul unui zgomot aditiv alb gaussian i folosind o decodare cu decizie soft,
valorile recepionate pentru setul de ieiri ale demodulatorului la momentul l sunt, ncazul canalului AWGN:
( )( ) 02 1 , 1,r
jl jl jr c n j n= + = , (2)
unde ( )rjlc este un simbol binar codat (0 sau 1), iar jn este un eantion din zgomotul
gaussian de medie zero i varian 20N . Zgomotul fiind alb, rezult c eantioanele de
zgomot sunt independente i atunci, probabilitatea de a recepiona secvena lr, dac s-a
transmis secvena codat ( )rlc este:
8/6/2019 Decodarea Codurilor Convolution Ale Prin Algoritmul Viterbi
2/6
2
( )( ) ( )( )
( )( )2
0 0
0
2 1
1 1 0
1r
jl jlr cn n
r r N
l l jl jl
j j
P r c P r c eN
= =
= = . (3)
Logaritmnd relaia (3) se obine:
( )( )
( )
( ) ( )( )2
0 0
0
22 1
01 1 00
2 11ln ln ln
r jl jlr c rn n
jl jlr N
l l
j j
r cP r c e N
NN
= =
= = =
( )( )( )0
2
01 0 0 0
2 2 11ln
rn
jl jljl
j
r crN
N N N
=
= +
. (4)
Atunci, eliminnd constantele i innd cont ( )2jlr este aceeai pentru toate
ramurile din trellis, metrica corespunztoare ramurii, la momentul l , este:
( ) ( ) ( )( )0
11
, 2 1n
i i
l l jl jll
j
V r c +=
= , (5)
metric numitde corelaie.Calea aleaseste calea r, corespunztoare la:
( ) ( ) ( )1
1 10
max ,L
i
L l llr
l
U V
+
=
=
. (6)
unde L este lungimea secvenei (primul moment este 0), l este starea n trellis la
momentul l , iar ( ) ( )1,i
l llV + este metrica ramurii dintre strile l i 1l + .
n relaia (5) indicile j semnificpoziia din secvena de valori recepionate saudin secvena codat corespunztoare ramurii din trellis, din cele 0n valori cte sunt n
total la momentul l .
Prin algoritmul Viterbi se rein doar SN ci la fiecare moment de timp, cte una
corespunztoare fiecrei stri.n general algoritmul Viterbi trebuie sconinurmtorii pai:
Pas 1: Se iniializeazcodorul cu starea nul. Se iniializeazstarea nula decodorului la
momentul 0l = cu metrica ( )0 0 0U S = . Celelalte stri nu intereseazdeoarece codorul s-
a iniializat cu starea nul.Pas 2: Se incrementeazvariabila moment de timp 1l l= + .
Pas 3: Se calculeaz metrica fiecrei ci ce intr n nodurile de pe nivelul l cu ajutorulrelaiei (5).
8/6/2019 Decodarea Codurilor Convolution Ale Prin Algoritmul Viterbi
3/6
3
Pas 4: Se calculeazmetricile cilor corespunztoare fiecrei stri la momentul de timp l ,
cu relaia ( ) ( ) ( )1 1 1 1,l l l l l l lU U V = + , presupunnd c avem o tranziie ntre
strile 1l i l .
Pas 5: Se reine numai calea de intrare n fiecare stare care are metrica maxim numit
cale supravieuitoare.Pas 6: Dac 1l L< , se revine la pasul 2.Pas 7: Se decide c s-a recepionat secvena corespunztoare cii ce intr n starea cumetricmaxim.
Complexitatea algoritmului Viterbi este una liniarn raport cu numrul de ramuridintr-o seciune de trellis. Peformana codurilor convoluinale este mai bun cndmemoria acestora crete, dar cu preul unei complexiti de decodare crescute.
Exemplu:n continuare se dun exemplu de folosire a algoritmului Viterbi pentru codul din
exemplul cu generatorii n octal 1 6g = , 2 3g = . Pentru a calcula mai uor metricile sepresupune c secvena recepionat este format din numere ntregi. Acest caz poate ficonsiderat un caz special de decodare cu decizie soft cuantizat. n tabelul 1 sunt date
secvena de bii codat (considerat aceeai din calea ngroat n trellis-ul din figura 4,lucrarea anterioar), secvena recepionat, metricile ramurilor pentru fiecare moment detimp i combinaie de bii codai.
Tabel nr. 1
Moment de timp 1 2 3 4 5
Secvena codat 10 11 11 01 10Secvena recepionat 2,-1 2,3 1,2 -3,0 2,-2
Metricileramurilor
00011011
-1-331
-51-15
-31-13
33-3-3
0-440
n cazul codului menionat anterior avem 0 2n = . La momentul 1l = , secvena de
bii codat transmiseste 11 1c = , 21 0c = , iar secvena recepionat se presupune 11 2r = ,
21 1r = . Atunci metricile corespunztoare fiecrei din cele 4 ramuri posibile, pentru
secventele codate 00, 01, 10 i 11, sunt calculate cu ajutorul relaiei (5), dup cumurmeaz:
- pentru ramura cu secvena codat 00: ( )( ) ( )( )11 11 21 212 1 2 1r rr c r c + =
( ) ( ) ( )2 2 0 1 1 2 0 1 1= + =
8/6/2019 Decodarea Codurilor Convolution Ale Prin Algoritmul Viterbi
4/6
4
- pentru ramura cu secvena codat01: ( ) ( ) ( )2 2 0 1 1 2 1 1 3 + =
- pentru ramura cu secvena codat10: ( ) ( ) ( )2 2 1 1 1 2 0 1 3 + =
- pentru ramura cu secvena codat11: ( ) ( ) ( )2 2 1 1 1 2 1 1 1 + =
Metricile ramurilor la momentele 2,5l = sunt calculate n mod similar.n figura 1 este dat trellis-ul corespunztor codorului din exemplu, cu secvenele
de ieire din codor corespunztoare fiecrei ramuri.
n continuare dm aplicare algoritmului Viterbi pas cu pas pentru secvenarecepionatdatn tabelul 1.
Pas 1: Se iniializeaz starea nul a decodorului la momentul 0l = cu metrica
( )0 0 0U S = . Celelalte stri nu intereseazdeoarece codorul s-a iniializat cu starea nul.
Pas 2: Se trece momentul de timp urmtor 0 1 1l = + = .Pas 3: Metricile corespunztoare ramurilor cu secvenele de ieire 00 i 10 sunt
( )0 0 0, 1V S S = , respectiv ( )0 0 2, 3V S S = , conform tabelului 1.
Pas 4: Avem metricile la momentul de timp 1l = :
( ) ( ) ( )1 0 0 0 0 0 0, 0 1 1U S U S V S S= + = = i ( ) ( ) ( )1 2 0 0 0 0 2, 0 3 3U S U S V S S= + = + = .
Acestea sunt trecute ncadrate n trellis-ul din figura 2. ncadrate cu linie continu suntmetricele cele mai mari la fiecare moment de timp, iar cu linie ntrerupt metricilecelorlalte ci supravieuitoare.
Pas 5: La acest moment de timp se rein cele douci care pleacdin starea 0S i ajung
n strile 0S , respectiv 2S .
Pas 6: 1l L< (1 5< ), deci se trece la pasul 2.
Pas 2: Se trece momentul de timp urmtor: 1 1 2l = + = .
Fig. 1. Trellis-ul pentru codorul din exemplu
0S
2S
1S
3S
0l = 1l= 2l = 3l =
00 00 00
10 10 10 01
11 11
11
01 01
00
10
4l =
00
1001
1111
01
00
10
5l =
00
1001
1111
01
00
10
8/6/2019 Decodarea Codurilor Convolution Ale Prin Algoritmul Viterbi
5/6
5
Pas 3: Metricile corespunztoare ramurilor sunt, conform tabelului 1, ( )1 0 0, 5V S S = ,
( )1 0 2, 1V S S = , ( )1 2 1, 5V S S = i ( )1 2 3, 1V S S = .
Pas 4: Metricile la momentul de timp 2l = sunt urmtoarele:
( ) ( ) ( )1 0 1 0 1 0 0, 1 5 6U S U S V S S= + = = , ( ) ( ) ( )2 2 1 0 1 0 2, 1 1 2U S U S V S S= + = = ,
( ) ( ) ( )2 1 1 2 1 2 1, 3 5 8U S U S V S S= + = + = , ( ) ( ) ( )2 3 1 2 1 2 3, 3 1 4U S U S V S S= + = + = .
Pas 5: La momentul de timp 2l = se rein cele patru ci care pleacdin starea 0S i ajung
n strile 0S , 2S , 1S , respectiv 3S .
Pas 6: 1l L< ( 2 5< ), se trece la pasul 2.
Pas 2: Se trece momentul de timp urmtor: 2 1 3l = + = .
Pas 3: Pentru tranziia ntre momentele de timp 2l = i 3l = (i la fel mai departe) avemcte dou ramuri care pleacdin fiecare stare. Astfel metricile corespunztoare ramurilor
sunt, conform tabelului 1, ( )2 0 0
, 3V S S = , ( )2 1 0
, 1V S S = , ( )2 0 2
, 1V S S = , ( )2 1 2
, 3V S S = ,
( )2 2 1, 3V S S = , ( )2 3 1, 1V S S = i ( )2 2 3, 1V S S = , ( )2 3 3, 3V S S = .
Pas 4: Avem cte dou metrici pentru fiecare stare la momentul de timp 3l = :
( ) ( ) ( )3 0 2 0 2 0 0, 6 3 9U S U S V S S= + = = sau ( ) ( ) ( )3 0 2 2 2 2 0, 8 1 9U S U S V S S= + = + = ,
( ) ( ) ( )3 2 2 0 2 0 2, 6 1 7U S U S V S S= + = = sau ( ) ( ) ( )3 2 2 1 2 1 2, 8 3 11U S U S V S S= + = + = ,
( ) ( ) ( )3 1 2 2 2 2 1, 2 3 1U S U S V S S= + = + = sau ( ) ( ) ( )3 1 2 3 2 3 1, 4 1 3U S U S V S S= + = = ,
( ) ( ) ( )3 3 2 2 2 2 3, 2 1 1U S U S V S S= + = + = sau ( ) ( ) ( )3 3 2 3 2 3 3, 4 3 1U S U S V S S= + = = .
Pas 5: La acest pas se rein numai cile care conduc la metric maxim pentru fiecare
stare, adic cele trecnd prin succesiunile de stri: 0 2 1 0S S S S , 0 2 1 2S S S S , 0 2 3 1S S S S ,
0 2 3 3S S S S , fiind eliminate ramurile desenate cu linie-punct.
Algoritmul continu n mod similar pn la momentul de timp 5l = . Trellis-ul
corespunztor codorului din exemplu cu metricile cilor supravieuitoare la fiecaremoment de timp, respectiv ale cilor eliminate este dat n figura 2. ngroateste calea cumetrica maxim la fiecare moment de timp. Calea rezultat n decodare este cea
corespunztoare succesiunii de stri 0 2 1 2 3 1S S S S S S , adic secvenei de bii de informaie
10110.
Algoritmul Viterbi descris mai sus realizeaz estimarea de maximplauzibilitate(ML maximum likelihood) a secvenei recepionate (minimiznd probabilitatea deeroare a acesteia) i are astfel nevoie de ntreaga secven pentru decodare optim,ducnd la ntrziere de decodare pentru L mare. Cnd aceast ntrziere este prea mare
se folosete algoritmul Viterbi trunchiat, n care la momentul k se alege calea pn la
momentul Dk (D fiind adncimea de trunchiere), reinndu-se metricile, respectivcile, numai pentru ultimele D momente de timp. Experimental s-a gsit co adncime
8/6/2019 Decodarea Codurilor Convolution Ale Prin Algoritmul Viterbi
6/6
6
de trunchiere ND 5 (N fiind lungimea de constrngere a codului) conduce la odegradare neglijabila performanei algoritmului.
5. Desfurarea lucrrii
1. Se consider secvena recepionat r={2,1,3,-2,-2,-3,-1,2,-2,1}. Pentru codul
(2,1,2) cu polinoamele generatoare n octal 1 2g = , 2 3g = i pentru codul (2,1,3) cu
polinoamele generatoare n octal 1 5g = , 2 7g = , s se decid ce secven decodat
rezultaplicnd algoritmul Viterbi cu decizie soft.2. Pentru aplicaia Matlab se deschide modelul lucrrii de laborator. Se urmretefuncionarea sistemului de transmisie folosind coduri convoluionale astfel:
- Se identific i se studiaz blocurile de pe schem (generatorul de secvenebinare, codorul convoluional, modulatorul BPSK, canalul de transmisie, decodorulViterbi i blocul de calcul a probabilitii de eroare de bit)
- Prin acionarea butonului Start se pornete simularea, la terminarea eiobinndu-se probabilitatea de eroare de bit n blocul Display n urma decodrii Viterbi
- Se schimbvaloarea raportului semnal-zgomot (SNR) din blocul corespunztorcanalului AWGN i se noteazdiferenele n probabilitatea de eroare de bit rezultat
- Se schimb polinoamele generatoare n blocul corespunztor codorului idecodorului Viterbi. Se modific corespunztor adncimea de trunchiere i se observrezultatele n urma simulrii.
Fig. 2. Decodarea Viterbi cu metricile asociate
0S
2S
1S
3S
0l =
1l = 2l = 3l =
1 5 3
3 1 1 1
5 3
3
1 1
3
1
4l =
3
3 3
3 3
3
3
3
5l =
0
4 4
00
4
0
4
1
3
6
2
8
4
11
9
3
1 14
8
12
6
12
18
16
14
Top Related