TE-810 Processamento Digital de Sinais - UFPR 1 8. Transformada Discreta de Fourier - DFT 8.1 Representação de seqüências periódicas: Série Discreta de

TE-810 Processamento Digital de Sinais - UFPR

1

8. Transformada Discreta de Fourier - DFT

8.1 Representação de seqüências periódicas:Série Discreta de Fourier - DFS

Vamos relembrar o desenvolvimento daTDFT – Transformada de Fourier p/ Sinais Discretos


2

2.7. A Transformada de Fourier para Sinais Discretos

Seja o sinal x[n] não-periódico

e x[n] seu sinal periódico associado com período N~

-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12

0

1

2

3

4

x[n]

-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12

0

1

2

3

4

xp[n]

-N1 N1

N-N


3

Podemos representar x[n] através da Série de Fourier:~

Nk

nN

jk

k eanx2

.][~

Nn

nN

jk

k enxN

a2

].[~1

Como:

1

11

||/0][

/][~][

Nnpnx

NnNpnxnx

Podemos escrever:

1

1

2

].[1 N

Nn

nN

jk

k enxN

a

ou então:

n

nN

jk

k enxaN2

].[.


4

Encontrando a envoltória de N.ak :

0.2

kN

k Discreto Contínuo

Obtemos:

n

njenxX ].[)(

Transformada de Fourier do Sinal Discreto x[n]

Logo:N

kXN

ak

2)(.

100

Os coeficientes da Série de Fourier do sinal x[n]podem ser vistos como amostragem da Transformadade Fourier em k.0 do sinal x[n].

~


5

Voltando à nossa análise:

Chamando os termos: ][~

. kXaN k

Definimos a Equação de Análise da DFS de N pontos como:

NenxkX

N

n

njk 2].[~][

~0

1

0

0

e a Equação de Síntese da DFS de N pontos:

NekX

Nnx

N

k

njk 2].[

~1][~

0

1

0

0


6

Denotando a quantidade complexa:

Nj

N eW2

Podemos reescrever as equações de análise eSíntese como:

1

0

1

0

[ ] [ ].

1[ ] [ ].

Nkn

Nn

Nkn

Nk

X k x n W

x n X k WN


7

8.2. Propriedades da DFS

8.2.1. Linearidade: ][~

][~11 kXnx DFS

][~

][~22 kXnx DFS

][~

.][~

.][~.][~. 2121 kXbkXanxbnxa DFS

8.2.2. Deslocamento: ][~

][~ kXnx DFS km

NmjkDFS WkXekXmnx N ].[

~].[

~][~ 2

8.2.3. Dualidade: ][~

][~ kXnx DFS

][~][~

kxNnX DFS


8

8.2.5. Convolução Periódica

][~

][~11 kXnx DFS

][~

][~22 kXnx DFS

][~

].[~

][~][~2121 kXkXnxnx DFS *

1

02121 ][~].[~][~][~

N

m

mnxmxnxnx *


9

8.2.6. Resumo das propriedades da DFS


10

8.5. A Transformada Discreta de Fourier - DFT

r

rNnxnx ][][~

outros

Nnnxnx

,0

10],[~][

ou ]))[((][~Nnxnx

Pela propriedade da Dualidade da DFS

Considere sequência finita e a periódica associada ][~ nx][nx

Se comprimento [ ]x n N


11

Temos que:

outros

NkkXkX

,0

10],[~

][

ou ]))[((][~

NkXkX

Podemos definir a DFT de N pontos:

1

0

2

].[][N

n

njk NenxkX

1

0

2

].[1

][N

k

njk NekXN

nx

Eq. de análise:

Eq. de síntese:


12

1

0

2

].[][N

n

njk NenxkX

1

0

2

].[1

][N

k

njk NekXN

nx

][][ )( kXnx NDFT

Interpretações:- , DFS de x[n], é uma amostragem do espectro X()

-X[k] uma amostragem de 1 período de X() espectro do sinal não periódico. -X[k] é um período do espectro do sinal periódico associado

][~

kX][~ nx

][~

kX


13

DFT de um sinal contínuonão limitado no tempo:


14

Exemplo:

0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

N=5

N=6

N=8

aliasing


15

0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

0 1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

N=10 N=25

N=50


16

0 10 20 30 400

0.5

1

0 10 20 30 400

20

40

0 10 20 30 40-1

0

1

0 10 20 30 400

10

20

0 10 20 30 40-1

0

1

0 10 20 30 400

10

20

0 10 20 30 40-1

0

1

0 10 20 30 400

20

40

DFT de sinais sinusoidais


17

0 5 10 15 20 25 30 35-1

-0.5

0

0.5

1

0 5 10 15 20 25 30 350

5

10

15

Porém:


18

DFT Sinal limitado em freq.com truncamento igual aoperíodo.


19

DFT Sinal limitado em freq.com truncamento não igual aoperíodo.


20

8.6. Propriedades da DFT

8.6.1. Linearidade: ][][ 1)(

13 kXnx NDFT

][][ 2)(

23 kXnx NDFT

3( )1 2 1 2. [ ] . [ ] . [ ] . [ ]DFT Na x n b x n a X k b X k

8.6.2. Deslocamento Circular: ][][ )( kXnx NDFT

mjkNDFTN

NekXmnx2

].[]))[(( )(

8.6.3. Dualidade: ][][ )( kXnx NDFT

]))[((.][ )(N

NDFT kxNnX

},max{ 213 NNN

10 Nn

10 Nk


21

8.6.5. Convolução Circular:

][][ 1)(

1 kXnx NDFT

][][ 2)(

2 kXnx NDFT

1

02122 ][~].[~][~][~

N

M

mnxmxnxnx *

Nada mais é do que a convolução periódica considerandosinais de duração finitos x1[n] e x2[n]

Linear:Sinais ilimitados

m

mnxmxnxnx ][].[][*][ 2121

Periódica:Sinais periódicos

1

02121 ]))[((].))[((][][

N

mNN mnxmxnxnx NCircular:

Sinais limitados

][].[][][ 21)(

21 kXkXnxnx NDFT N


22

8.6.6. Resumo das Propriedades da DFT


23

8.7. Convolução Linear usando DFT

-Existem algoritmos muito eficientes p/ cálculo da DFT

algoritmos de FFT (Fast Fourier Transform)

Logo é eficiente implementar a convolução de 2 sinaisatravés dos seguintes passos:

a) Calcular as DFTs de x1[n] e x2[n], X1[k] e X2[k]b) Calcular X3[k]=X1[k].X2[k]c) Calcular IDFT de X3[k], x3[n], obtendo:][][][ 213 nxnxnx N

Porém muitas vezes desejamos: ][][][ 213 nxnxnx


24

Sendo:Pocomprimentdenx

Locomprimentdenx

][

][

2

1

O resultado da convolução circular de N amostras seráigual à convolução linear se:

1 PLN

Porém: se um dos sinais tiver comprimento indeterminado(processamento em tempo real).

Dois métodos implementam uma forma eficientede cálculo da convolução linear através da DFT.

Overlap-add e Overlap-save

Implementação de Sistemas LTI


25

8.8 Transformada Discreta do Cosseno (DCT)

DFT é o exemplo mais comum da classe deTransformadas Discretas de tamanho finito

1*

0

[ ] [ ] [ ]N

kn

A k x n n

1

0

1[ ] [ ] [ ]

N

kk

x n A k nN

Onde as sequências baseSão ortogonais:

[ ]k n1

*

0

1,1[ ] [ ]

0,

N

k mn

m kn n

m kN


26

No caso da DFT:2

[ ] Njk nk n e

A[k] nesse caso é geralmente uma sequência complexa.

São exemplos de Transformadas que fazem :

-Haar-Hadamard-Hartley (DHT)-DCT-DST- ...


27

A DCT considera o sinal x[n] periódico e com simetria par:

Logo: temos 4 tipos de DCT: DCT-1, DCT-2, DCT-3 e DCT-4E existem outras 4 formas de se criar um sinal periódico e com simetria par.

2N-2 2N

4N 4N

Período: Período:


28

A DST (Discrete Sine Transform) considera sinal periódicoE com simetria ímpar. 8 formas de se fazer.Sendo as funções de base baseadas no seno.

Logo temos uma família de 16 transformadas ortogonais

A DCT-2 é a mais utilizada em aplicações de compressãode sinais (JPEG e MPEG-1,2,4):

12

0

2 12[ ] [ ] [ ]cos

2

NC

n

k nX k k x n

N N

12

0

2 12[ ] [ ] [ ]cos

2

NC

k

k nx n k X k

N N

Onde:12

, 0[ ]

1, 1,2,..., 1

kk

k N


29

Exemplo: Compactação de Energia na DCT-2


30


31

Transformada ótima para compactaçãode energia : Karhunen-Loève (Hotelling, PCA)Base formada pelos auto-vetores da matriz de covariância do sinal a ser compactado

A DCT é assintoticamente ótima.


32

9. Computação da DFT

Complexidade Computacional: Medida através do número de , + , é proporcional ao tempo gasto p/ executar um algoritmo.Porém: outros fatores: quantidade de memória requerida operações transcendentais, raiz, log, etc.

Em VLSI: consumo, área de chip são fatores importantesP/ escolha de um algoritmo.

Algoritmos de FFT: revolucionaram a área de processamento de sinais


33

9.1. Computação eficiente da DFT

1,...,2,1].[][1

0

NkWnxkXN

n

knN

1,...,2,1].[1

][1

0

NnWkXN

nxN

k

knN

NjN eW

2

Como as equações diferem apenas do fator de escala Ne do sinal do expoente de WN, a teoria vista p/ cálculoda DFT aplica-se também à IDFT

Cálculo direto:-como x[n] pode ser sinal complexo,Para computar N amostras do sinal X[k] requerN2 multiplicações complexas e N(N-1) adições complexasou4N2 multiplicações reais e N(4N-2) somas reaisE mais memórias p/ armazenamento de N amostras complexasde x[n] e coeficientes WN

Proporcional O(N2)


34

A maioria dos algoritmos de FFT exploram as seguintes características:

knN

knN

nNkN WWW ][1) Simetria complexa conjugada:

2) Periodicidade em k e n : nNkN

NnkN

knN WWW )()(

Exploram ainda a decomposição de uma DFTde N pontos em DFTs de comprimentos menores

Algoritmos:-Goertzel(1958): O(N2)-Cooley-Tukey(1965): Deu origem à decimação no tempo-Sande-Tukey(1966): Deu origem à decimação em frequência


35

9.3. Algoritmos de Decimação no Tempo

-decomposição sucessiva de x[n] em parcelas menores

Diversos tipos: mais clássico: p/ N potência de 2

x[n] de N pontos é dividido em 2 sequências de N/2 pontosCompostas dos n ímpares e n pares

parn ímparn

nkN

nkN

N

n

knN

WnxWnxkX

WnxkX

].[].[][

].[][1

0


36

parn ímparn

nkN

nkN WnxWnxkX ].[].[][

Mudando as variáveis: n=2r para n par n=2r+1 para n ímpar

)12/(

0

2)12/(

0

2

)12/(

0

)12()12/(

0

2

].12[].2[][

].12[].2[][

N

r

rk

Nk

N

N

r

rk

N

N

r

krN

N

r

rkN

WrxWWrxkX

WrxWrxkX

Como:2/

2NN WW


37

Podemos reescrever:

)12/(

0

2)12/(

0

2 ].12[].2[][N

r

rk

Nk

N

N

r

rk

N WrxWWrxkX

Como: 2/2

NN WW

rkN

N

r

kN

N

r

rkN WrxWWrxkX 2/

)12/(

0

)12/(

02/ ].12[].2[][

1,...,2,1,0][][][ NkkHWkGkX kN


38

Aplicando o mesmo princípio para o cálculo de G[k] e H[k]DFT(N/2)

lkN

N

l

kN

N

l

lkN WlgWWlgkG 4/

)14/(

02/

)14/(

04/ ].12[].2[][

lkN

N

l

kN

N

l

lkN WlhWWlhkH 4/

)14/(

02/

)14/(

04/ ].12[].2[][


39

Temos:

E assim sucessivamente até chegar ao cálculo da DFT(2)


40

DFT de 2 pontos:

]1[]0[].1[].0[]1[

]1[]0[].1[].0[]0[

].[][

1.12

0.12

1.02

0.02

1

0

xxWxWxX

xxWxWxX

WnxkXn

knN


41

Diagrama completo p/ DFT 8-pontos decimação no tempo:

Notar que a complexidade computacional é: N.log(N)


42

Reduzindo ainda mais a complexidade computacional:

Célula básica de computação: butterfly

Como: )1.(. 2/)2/( rN

NN

rN

NrN WWWW


43

Assim: Algoritmo completo

Obs:-Complexidade computacional O(N.log(N))-Computação In-Place, uso da mesma memória p/ entrada e saída-Ordem do sinal de entrada x[n]


44

Ordenação Bit-Reversa

X[0] = x[0]X[1] = x[4]X[2] = x[2]X[3] = x[6]X[4] = x[1]X[5] = x[5]X[6] = x[3]X[7] = x[7]

X[000] = x[000]X[001] = x[100]X[010] = x[010]X[011] = x[110]X[100] = x[001]X[101] = x[101]X[110] = x[011]X[111] = x[111]


45

9.4. Algoritmos de Decimação na Frequência

-decomposição sucessiva de X[k] em parcelas menores

Diversos tipos: mais clássico: p/ N potência de 2

X[k] de N pontos é dividido em 2 seqüências de N/2 pontosCompostas dos k ímpares e k pares

1

0

].[][N

n

nkNWnxkX

1

0

)2(].[]2[N

n

rnNWnxrX P/ X[pares]

Que podemos escrever como:


46

1

0

)2(].[]2[N

n

rnNWnxrX P/ X[pares]


1

2/

212/

0

2 ].[].[]2[N

Nn

nrN

N

n

nrN WnxWnxrX

Substituindo variáveis no 2° somatório

12/

0

)(22

12/

0

2 2].[].[]2[N

n

rnN

NN

n

nrN

N

WnxWnxrX

Notando que: 1.. 22)2/(2 rnN

rNN

rnN

NnrN WWWW

Logo:

12/

0

22

12/

0

2 ].[].[]2[N

n

rnN

NN

n

rnN WnxWnxrX


47

rnN

rnN WW 2/2

Temos que:

12/

0

22

12/

0

2 ].[].[]2[N

n

rnN

NN

n

rnN WnxWnxrX

Lembrando que:

Pode ser escrito como:

12/

02/2 .][][]2[

N

n

rnN

N WnxnxrX

De modo análogo p/ k ímpares podemos escrever:

1

0

)12(].[]12[N

n

rnNWnxrX P/ X[ímpares]



48

1

0

)12(].[]12[N

n

rnNWnxrX P/ X[ímpares]


1

2/

)12(12/

0

)12( ].[].[]12[N

Nn

rnN

N

n

rnN WnxWnxrX

Substituindo variáveis no 2° somatório

12/

0

)12)((2

12/

0

)12( 2].[].[]12[N

n

rnN

NN

n

rnN

N

WnxWnxrX

Notando que: )1.(. )12()12()12()12)(2/( 2 rnN

rN

rnN

rNnN WWWW

N

Logo:

12/

0

)12(2

12/

0

)12( ].[].[]12[N

n

rnN

NN

n

rnN WnxWnxrX


49

Logo:

12/

0

)12(2

12/

0

)12( ].[].[]12[N

n

rnN

NN

n

rnN WnxWnxrX

12/

0

)12(2 .][][]12[

N

n

rnN

N WnxnxrX

12/

0

22 ..][][]12[

N

n

nN

nrN

N WWnxnxrX

12/

02/2 ..][][]12[

N

n

nrN

nN

N WWnxnxrX

12/

02/2 .][][]2[

N

n

rnN

N WnxnxrX

P/ k pares:

P/ k ímpares:


50

Aplicando o mesmo procedimento p/ cálculoda DFT N/2 pontos


51

E assim sucessivamente até a DFT de 2 pontos,Calculada por:

Algoritmo completo p/ DFT(8) decimação em Frequência:

Obs:-O(N.log(N))-Computação In-Place-Saída bit-reverso


52

Algoritmos vistos são Radix-2

Outros algoritmos:-Radix-4, Radix-8, etc...-Split-Radix-Produto de inteiros-...


53

Convolução:

1

0

][].[][N

k

knhkxny

Complexidade: O(2N2)

Método Direto:

Por FFT: ][][ )2( kXnx NFFT ][][ )2( kHnh NFFT ][].[][ kHkXkY

][][ )2( nykY NIFFT

Complexidade: O(3.2N.log(2N)+2N)

12121 NNNN

Documents

TE-810 Processamento Digital de Sinais - UFPR 1 8. Transformada Discreta de Fourier - DFT 8.1 Representação de seqüências periódicas: Série Discreta de