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