convolutia secventelor

PNS Lucrarea 4 Convoluia secvenelor

34

Lucrarea 4

Convoluia Secvenelor n aceast lucrare se vor trata sisteme discrete, liniare, invariante n timp (SDLIT), care sunt complet caracterizate n domeniul timp de rspunsul la impuls. Exist dou metode de baz, folosite n analiza rspunsului sistemelor discrete liniare la un semnal de intrare dat. Una se bazeaz pe obinerea soluiei din ecuaia intrare ieire care caracterizeaz sistemul, care are, n general, forma

Mk

k

N

kk knxbknyany

01

unde ka i kb sunt parametri constani care caracterizeaz sistemul i independeni de nx i ny . Relaia de mai sus se numete ecuaie cu diferene a sistemului discret, liniar, invariant n timp. A doua metod se bazeaz pe folosirea rspunsului la impuls al sistemului. Ca o consecin a proprietilor de liniaritate i invarian n timp, rspunsul sistemului la un semnal de intrare arbitrar poate fi exprimat n funcie de rspunsul su la impuls cu ajutorul sumei de convoluie. Pentru determinarea rspunsului unui sistem liniar la un semnal de intrare dat, acesta se descompune ntr-o sum de semnale elementare componente i, folosind proprietatea de liniaritate a sistemului, rspunsurile sistemului la semnalele elementare se sumeaz pentru a forma rspunsul total

k

y n x h n h x n x k h n k

1. Convoluia liniar a secvenelor

Pentru dou secvene, x i h, reprezentate prin:

, 0, 1x x n n N , 0, 1h h n n L

(4.1)

se definete convoluia lor liniar prin una din formele:

1 10 0

N L

k ky n x h n h x n x k h n k h k x n k

, 0, 2y y n n N L

(4.2)

Dac secvenele sunt reprezentate prin polinoamele:

1

0( ) [ ]

Nk

kX z x k z

, cu grad ( ) -1X z N

1

0( ) [ ]

Lk

iH z h k z

, cu grad ( ) -1H z L

atunci convoluia lor liniar este reprezentat de polinomul: )()()( zHzXzY (4.3)


35

2. Convoluia ciclic a secvenelor

Pentru dou secvene periodice, de aceeai perioad N:

, 0, 1x x n n N , 0, 1h h n n N

(4.4)

se definete convoluia lor ciclic, prin secvena periodic:

' '{ [ ], 0, 1}y x h h x y n n N (4.5) n care valoarea yn este definit de relaia:

1 1'

( ) ( )0 0

[ ] [ ] [ ] [ ] [ ]N N

N Nk k

y n x k h n k h k x n k

(4.6)

unde s-a notat prin

( ) , pentru [ ] modulo ,pentru Nn k n k

n k n k Nn k N n k

Dac secvenele sunt reprezentate (ntr-o perioad) prin polinoamele:

1

0( ) [ ]

Nk

kX z x k z

, cu grad ( ) -1X z N

1

0( ) [ ]

Nk

iH z h k z

, cu grad ( ) -1H z N

atunci convoluia lor ciclic este reprezentat de polinomul:

)()()( zHzXzY modulo 1Nz (4.7) 3. Corelaia liniar i ciclic a secvenelor

Pentru dou secvene finite d i g, reprezentate prin: , 0, 1d d n n N , 0, 1g g n n L , cu L N se definete corelaia liniar prin una din secvenele: , 1 , 1dg dgr r n n L N sau , 1 , 1gd gdr r n n N L unde

[ ] [ ] [ ] [ ] [ ],

[ ] [ ] [ ] [ ] [ ]

dgk k

gdk k

r n d k g k n d k n g k

r n g k d k n g k n d k

(4.8)


36

n care, n prima relaie dac ( ) k n N sau ( ) 0k n se consider c 0d k n , iar n a doua relaie dac ( ) k n L sau ( ) 0k n se consider c 0g k n . Se observ c n calculul corelaiei liniare conteaz care secven este considerat prima. Este adevrat relaia [ ] [ ]dg gdr n r n . Dac secvenele d i g sunt periodice, de aceeai perioad N, se definete corelaia ciclic prin una din secvenele periodice: , 0, 1dg dgr r n n N sau , 0, 1gd gdr r n n N unde

1

( )0

[ ] [ ] [ ]N

dg Nk

r n d k n g k

, 1 ( )

0[ ] [ ] [ ]

N

gd Nk

r n g k n d k

Este adevrat relaia ( ) ( )[ ] [ ] [ ]dg gd N gd Nr n r n r N n .

(4.9)

4. Metode i algoritmi pentru calculul convoluiilor

4.1. Calculul convoluiei ciclice folosind Transformata Fourier Discret

Se bazeaz pe proprietatea: [ ] [ ] [ ]y n x n h n TFD X k H k Y k , unde 21

1[ ]

k nNdef jN

nX k x n e

i

se definete ca fiind Transformata Fourier Discret (TFD) n N puncte a secvenei [ ]x n . Algoritmul cuprinde trei etape: 1se calculeaz: [ ] [ ] , 0, 1X k TFD x n i H k TFD h n n k N 2se calculeaz: 0, 1Y k X k H k k N 3se calculeaz: [ ]y n TFDI Y k unde TFDI este Transformata Fourier Discret Invers definit astfel 21

1

1 [ ]k nNdef j

N

ky n Y k e

N

.

Dup cum se poate observa din relaiile (4.5) i (4.6), pentru efectuarea direct a convoluiei ciclice ntre dou secvene cu coeficieni reali, sunt necesare 2N nmuliri reale i

( 1)N N adunri reale. Eficiena metodei depinde de eficiena algoritmului rapid pentru calculul TFD i TFDI utilizat n etapele 1 i 3. n cazul calculului convoluiei cu ajutorul TFD vom avea un numr de 28 4N N nmuliri ( 22 2N la pasul 1, 4N la pasul 2 i 22 2N la pasul 3). TFD se poate realiza i utiliznd algoritmi rapizi. Dac N este de forma 2m , pentru calculul TFD n N puncte a unei secvene este nevoie de 22 logN N nmuliri reale i

23 logN N adunri reale. Vor fi deci necesare: 24 logN N nmuliri i 26 logN N adunri reale pentru realizarea transformatelor

directe ale lui [ ]x n i [ ]h n ;


37

N nmuliri complexe, deci 4N nmuliri i 2N adunri reale pentru realizarea produselor X k H k ;

22 logN N nmuliri i 23 logN N adunri reale pentru realizarea transformatei inverse TFDI.

n total, utiliznd TFD rapid, se vor efectua 2(6log 4)N N nmuliri i 2(9log 4)N N adunri reale.

De exemplu pentru 102N avem: - 202 nmuliri i 202 adunri reale prin efectuarea direct a convoluiei; - 20 10 238 2 4 2 2 nmuliri reale prin utilizarea TFD; - 10 162 (6 10 4) 2 nmuliri i 10 16,52 (9 10 2) 2 adunri reale prin utilizarea TFD Rapide. 4.2. Algoritmul Cook-Toom pentru calculul convoluiei liniare Algoritmul cuprinde urmtoarele etape: 1 se alege un set de 1 LN valori reale 2,1,0 i etc (unde N i L sunt lungimile secvenelor [ ]x n , respectiv [ ]h n ). 2se evalueaz polinoamele )(zX i )(zH n iz 3se calculeaz ( ) ( ) ( ), 0, 2i i iY X H i N L 4se determin, prin interpolare Lagrange, polinomul: 22

0 0,( )

N LN Lj

ii j j i i j

zY z Y

4.3. Algoritmul Winograd pentru calculul convoluiei liniare i ciclice

Algoritmul se bazeaz pe reprezentarea polinomial a celor dou secvene [ ]x n i [ ]h n , ( )X z , respectiv ( )H z .

Se calculeaz )( mod)()()( zMzHzXzY unde, n cazul convoluiei liniare gradM(z)gradY(z), iar n cazul convoluiei ciclice 1)( NzzM . Polinomul )(zM poate fi descompus n polinoame simple, ireductibile, astfel nct: )(...)()()()( )1()1()0()( zMzMzMzMzM K

Nd

d . unde produsul se face dup toi divizorii lui N ( /d N reprezint toi divizorii lui N inclusiv 1 i N). Algoritmul Winograd cuprinde, principial, trei etape: 1se calculeaz reziduurile polinoamelor X(z) i H(z): ( ) ( )( )( ) ( ) ( )mod ( ), 0, 1kk kM zX z R X z X z M z k K ( ) ( )( )( ) ( ) ( )mod ( ), 0, 1kk kM zH z R H z H z M z k K 2se calculeaz reziduurile polinomului Y(z): ( ) ( ) ( ) ( )( )( ) ( ) ( )mod ( ) ( ) ( ) , 0, 1kk k k kM zY z X z H z M z R X z H z k K


38

3se calculeaz polinomul convoluiei Y(z) din reziduurile sale Y(k)(z), pe baza teoremei chineze a resturilor:

)( mod)()()( )(1

0

)( zMzSzYzY kK

k

k

unde ( ) ( )kS z pot fi gsite tabelate pentru diveri N (valorile coeficienilor acestor polinoame pot fi stocate ntr-o memorie de date). Numrul minim de multiplicri necesare pentru a realiza o convoluie ciclic de ordinul N, este )(2 NDN , unde )(ND reprezint numrul de divizori ai lui N.

5. Aplicaii rezolvate Exemplul 1. S se calculeze convoluia liniar ntre secvenele: 2[0], [1], [2] ( ) [0] [1] [2]x x x x X z x x z x z ,cu 3N [0], [1] ( ) [0] [1]h h h H z h h z ,cu 2L . Conform definiiei:

1

0[ ] [ ] [ ]

N

ky n x k h n k

, rezult c:

[0], [1], [2], [3] [0] [0], [0] [1] [1] [0], [1] [1] [2] [0], [2] [1]y y y y y x h x h x h x h x h x h Folosind reprezentrile polinomiale )(zX i )(zH ale secvenelor, rezult:

2

2 3

( ) ( ) (z) ( [0] [1] [2] )( [0] [1] )[0] [0] ( [0] [1] [1] [0]) ( [1] [1] [2] [0]) [2] [1]

Y z X z H x x z x z h h zx h x h x h z x h x h z x h z

Funcia MATLAB pentru calculul convoluiilor liniare este conv.m i realizeaz de fapt, produsul polinoamelor X(z) i Y(z). De exemplu, pentru x=1,2,3 i h=1,1 rezult: [0] 1 [1] 3 [2] 5 [3] 3y y y y iar verificarea n Matlab este sub forma urmtorului program: %Program P4_1 x=[1 2 3]; h=[1 1]; disp('rezultatul convolutiei este:'); y=conv(x,h)

Operaia invers convoluiei este deconvoluia, care realizeaz mprirea cu rest a

polinoamelor. Comanda MATLAB deconv de mai jos va avea ca rezultat secvena h=1,1.

disp('rezultatul deconvolutiei este:'); h1=deconv(y,x) Exemplul 2. S se calculeze convoluia ciclic ntre secvenele: [0], [1]x x x ( ) [0] [1]X z x x z , cu N=2 [0], [1]h h h ( ) [0] [1]H z h h z


39

Conform definiiei 1

( )0

[ ] [ ] [ ]N

Nk

y n x k h n k

, rezult c:

[0], [1] [0] [0] [1] [1], [0] [1] [1] [0]y y y x h x h x h x h Folosind reprezentrile polinomiale )()()( zHzXzY mod )1( 2 z , adic: 2( [0] [0] ) ( [0] [1] ) mod( 1)x x z h h z z , rezult ca rest al mpririi polinomului 2[1] [1] ( [0] [1] [1] [0]) [0] [0]h x z h x h x z h x la )1( 2 z , polinomul convoluiei ciclice fiind ( ) ( [0] [1] [1] [0]) [0] [0] [1] [1]Y z h x h x z h x h x .

Un exemplu de program MATLAB, care calculeaz convoluia ciclic, cuprinde comenzile: %Program P4_2 x=[1 2]; h=[1 3]; disp(rezultatul convolutiei circulare:); y=circonv(x,h,2) %(vezi circonv.m) i rezult y={7 ,5} adic 5,7750)( 2 yzzzY Funcia Matlab circonv are sintaxa: y=circonv(x,h,L); returneaz rezultatul convoluiei circulare n L puncte dintre

secvenele x i h. Observaie. n reprezentarea polinomial, programul MATLAB necesit ordonarea coeficienilor n ordine descresctoare a puterilor variabilei. Exemplul 3. Calculul convoluiei ciclice ntre dou secvene x i h , periodice, de aceeai perioad N, utiliznd TFD, este realizat de urmtoarea secven de comenzi MATLAB: %Program P4_3 x=[1 2]; h=[1 1]; X=fft(x); H=fft(h); Y=X.*H; disp(iesirea calculata cu DFT=); y=ifft(Y) adic 5,7y . Observaie. Dac cele dou secvene au lungimi mai mici dect numrul de puncte n care trebuie calculat convoluia circular, L, secvenele vector x i h se completeaz cu zerouri pn la lungimea dorit. Exemplul 4. S se calculeze corelaia liniar pentru secvenele: [0], [1]d d d i [0], [1], [2]g g g g cu 2, 3N L . Pe baza definiiei, corelaia lor liniar este n una din formele:


40

20

[ ] [ ] [ ] [ ] [0] [1 ] [1] [2 ] [2]dg dgk

r r n d k n g k d n g d n g d n g

, pentru 2, 1,0,1n , astfel c [ 2], [ 1], [0], [1]dg dg dg dg dgr r r r r , cu [ 2] [0] [2]dgr d g ,

[ 1] [0] [1] [1] [2]dgr d g d g , [0] [0] [0] [1] [1]dgr d g d g , iar 1 [1] [0]dgr d g . Similar 1

0[ ] [ ] [ ] [ ] [0] [1 ] [1]gd gd

kr r n g k n d k g n d g n d

, pentru 1,0, 1,2n ,

astfel c [ 1], [0], [1], [2]gd gd gd gd gdr r r r r , cu [ 1] [0] [1]gdr g d , [0] [0] [0] [1] [1]gdr g d g d , 1 [1] [0] [2] [1]gdr g d g d , iar [2] [2] [0]gdr g d .

De exemplu, pentru secvenele 1,1d i 1,2,3g rezult: [ 2] 3, [ 1] 5, [0] 3, [1] 1, [2] 0dg dg dg dg dgr r r r r i

[ 2] 0, [ 1] 1, [0] 3, [1] 5, [2] 3gd gd gd gd gdr r r r r . Se observ c se verific relaia [ ] [ ]dg gdr n r n . Funcia MATLAB pentru calculul corelaiilor liniare este xcorr.m. Un exemplu de

program MATLAB, care calculeaz corelaia liniar ntre dou secvene d i g, este urmtorul:

%Program P4_4 d=[1 1]; g=[1 2 3]; disp('Corelatia liniara a secventelor d si g'); rdg=xcorr(d,g) rgd=xcorr(g,d)

Dac secvenele d i g sunt considerate periodice, de perioad 3N , corelaia lor ciclic va fi n una din formele urmtoare: 2 ( ) ( ) ( )

0[ ] [ ] [ ] [ ] [0] [1 ] [1] [2 ] [2]dg dg N N N

kr r n d k n g k d n g d n g d n g

,

pentru 0,1,2n sau 1 ( ) ( ) ( )0

[ ] [ ] [ ] [ ] [0] [1 ] [1] [2 ] [2]gd gd N N Nk

r r n g k n d k g n d g n d g n d

, pentru 0, 1,2n , astfel c

[0], [1], [2]dg dg dg dgr r r r , cu [0] [0] [0] [1] [1] [2] [2]dgr d g d g d g , [1] [1] [0] [2] [1] [0] [2]dgr d g d g d g , iar [2] [2] [0] [0] [1] [1] [2]dgr d g d g d g i

[0], [1], [2]gd gd gd gdr r r r , cu [0] [0] [0] [1] [1] [2] [2]gdr g d g d g d , [1] [1] [0] [2] [1] [0] [2]gdr g d g d g d , iar [2] [2] [0] [1] [1] [0] [2]gdr g d g d g d .

Se observ c se verific relaia ( )[ ] [ ] [ ]dg gd N gdr n r n r N n , adic (3)[0] [3 0] [0]dg gd gdr r r , (3)[1] [3 1] [2]dg gd gdr r r i (3)[2] [3 2] [1]dg gd gdr r r .


41

Exemplul 5. S se calculeze convoluia liniar a secvenelor: [0], [1] ( ) [0] [0]x x x X z x x z ,cu 2N [0], [0] ( ) [0] [1]h h h H z h h z ,cu 2L prin metoda Cook-Toom, folosind interpolarea Lagrange. 1 Fie setul de 31 LN valori reale: 1,0 10 i 2 . 2 S evalueaz polinoamele )(zX i )(zH pentru iz : 00 z (0) [0]X x ; 0)0( hH 11 z (1) [0] [1]X x x ; (1) [0] [1]H h h

12 z ( 1) [0] [1]X x x ; ( 1) [0] [1]H h h 3 Rezult c : (0) (0) (0) [0] [0]Y X H x h (1) (1) (1) [0] [1] [0] [1]Y X H x x h h ( 1) ( 1) ( 1) [0] [1] [0] [1]Y X H x x h h 4 Folosind relaia de interpolare Lagrange, rezult:

2

2

( 1)( 1) ( 1) ( 1)( ) [0] [1] [2] (0) (1) ( 1)1 2 2

[0] [0] ( [0] [1] [1] [0]) [1] [1]

z z z z z zY z y y z y z Y Y Y

x h x h x h z x h z

Prin identificare: [0], [1], [2] [0] [0], [0] [1] [1] [0], [1] [1]y y y y x h x h x h x h Observaie. Algoritmul necesit doar 3 multiplicri: )1()1(),0()0( HXHX i )1()1( HX i 3 adunriscderi: [0] [1], (1) (0) ( 1)x x Y Y Y , considernd c ( [0] [1])h h poate fi precalculat. Calculul direct al convoluiei ar necesita 4 multiplicri i o adunare. Exemplul 6. S se realizeze descompunerea polinomului 1)( NzzM n factori de polinoame ireductibile. Rezult:

Nd

dN zMzzM )(1)( )( , produsul fiind efectuat pentru toi divizorii d ai lui N , inclusiv pe 1 i pe N , iar )()( zM d va reprezenta n acest caz polinomul ciclotomic de ordinul d . Un alt mod de a scrie descompunerea lui )(zM este:

1),(,

)(1)(didi

id

N WzzzM cu 2 j d

dW e

unde di, reprezint Cel Mai Mare Divizor Comun(CMMDC) al numerelor i i d . De exemplu, polinomul 16 z se descompune n 4 polinoame ireductibile, corespunztoare divizorilor 3,2,1d i 6 ai lui 6N , astfel c: 1)()( 1211

)1( zezWzzM j 1)()( 2212

)2( zezWzzM j 1))(()( 223

13

)3( zzWzWzzM


42

1))(()( 2561

6)6( zzWzWzzM .

Observaie. O proprietate a polinoamelor ciclotomice ale lui 1Nz este c pn la ordinul 105N au numai coeficieni egali cu 1 sau 0.

Exemplul 7. Teorema chinez a restului pentru polinoame poate fi formulat astfel: se poate determina un polinom C(z) dac se cunosc resturile mpririi lui n raport cu un set de polinoame )()( zM i , relativ prime ntre ele. Fie deci cunoscute: )()()(

)()(zCzCRzC zM

ii mod KizM i ,0),()(

atunci polinomul )(zC se poate reface din relaia:

K

i

iii zmznzCzC0

)()()( )()()()( mod )(zM

unde

K

i

i zMzM0

)( )()(

)()()( )()( zMzMzm ii iar )()( zn i este polinomul soluie a ecuaiei: 1)()()()( )()()()( zMzNzmzn iiii sau, echivalent, )()( zn i rezult din relaiile: 1)()( )()( zmzn ii mod )()( zM i Exemplul 8. S se calculeze, cu ajutorul algoritmului Winograd, convoluia ciclic a secvenelor: [0], [1], [2], [3] [0], [1], [2], [3] [0], [1], [2], [3]y y y y x x x x h h h h care este reprezentat polinomial prin: 1mod)()()( 4 zzHzXzY unde 2 3( ) [0] [1] [2] [3]X z x x z x z x z 2 3( ) [0] [1] [2] [3]H z h h z h z h z 2 3( ) [0] [1] [2] [3]Y z y y z y z y z Polinomul 14 z se descompune n 3 polinoame ciclotomice: )1)(1)(1()()()(1 2)4()2()1(4 zzzzMzMzMz Se calculeaz polinoamele rest )()( zX i n raport cu )()( zM i : (1) (1)( ) ( )mod ( ) ( )mod 1 [0] [1] [2] [3]X z X z M z X z z x x x x (2) (2)( ) ( )mod ( ) ( )mod 1 [0] [1] [2] [3]X z X z M z X z z x x x x (4) (4) 2( ) ( )mod ( ) ( )mod 1 ( [0] [2]) ( [1] [3])X z X z M z X z z x x x x z Similar, se calculeaz i polinoamele rest )()( zH i : (1) ( ) ( )mod 1 [0] [1] [2] [3]H z H z z h h h h


43

(2) ( ) ( )mod 1 [0] [1] [2] [3]H z H z z h h h h (4) 2( ) ( )mod 1 ( [0] [2]) ( [1] [3])H z H z z h h h h z Rezult c reziduurile polinomului convoluie vor fi:

(1) (1) (1) (1)( ) ( ) (z)mod ( ) ( [0] [1] [2] [3])( [0] [1] [2] [3])Y z X z H M z x x x x h h h h (2) (2) (2) (2)( ) ( ) (z)mod ( ) ( [0] [1] [2] [3])( [0] [1] [2] [3])Y z X z H M z x x x x h h h h

(4) (4) (4) (4)( ) ( ) (z)mod ( ) ( [0] [2])( [0] [2]) ( [1] [3])( [1] [3])

[0] [2] [1] [3] [0] [2] [1] [3]

[0] [2] [0] [2] [1] [3] [1] [3]

Y z X z H M z x x h h x x h h

x x x x h h h h

x x h h x x h h z

n final, se determin polinomul convoluie )(zY , din reziduurile sale )()( zY i , pe baza teoremei chineze a resturilor. Rezult astfel: 1mod)()()()()()()( 4)4()4()2()2()1()1( zzYzSzYzSzYzSzY unde

141)( 23)1( zzzzS

)1(41)( 23)2( zzzzS

)1(21)( 2)4( zzS

6. Aplicaii propuse 1. Se dau secvenele: 1, dac 0,1,2,3,4,5

0, n rest n

x n

1 , dac 0,1,20 , n restn n

h n

Calculai analitic convoluia liniar nhnxny i verificai rezultatul, folosind funcia conv.m. 2. Se dau secvenele: 1, dac 0,1,2

0, n rest n

x n

5 , dac 0,1,2,3,40 , n rest

n nh n

Calculai analitic convoluia lor ciclic pentru 6N i verificai rezultatul n MATLAB , folosind funcia circonv.m.


44

3. Se dau secvenele: 1, dac 0,1,2,3

0, n rest n

x n

4 , dac 0,1,2,30, n rest

n nh n

a) calculai analitic convoluiile lor liniare i ciclice (n 4 puncte) ale celor dou secvene; b) determinai valoarea minim pentru perioada N , pentru care valorile celor dou tipuri de convoluie sunt egale. Verificai rezultatul n Matlab cu ajutorul Transformatei Fourier Discrete. 4. Se dau secvenele: Nnununx nunh n Pentru cazurile ( 50; 0,5N ) i ( 50; 1N ):

a) schiai pe caiet forma celor dou semnale discrete b) generai cu ajutorul programului MATLAB cele dou secvene pe suportul

0,99n i calculai convoluia lor liniar. c) reprezentai grafic secvenele [ ], [ ]x n h n , precum i secvenele rezultate la punctul

b).

convolutia secventelor

Documents

Transcript of convolutia secventelor