TE-810 Processamento Digital de Sinais
-
UFPR
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 da
TDFT – Transformada de Fourier p/ Sinais Discretos
1
TE-810 Processamento Digital de Sinais
-
UFPR
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
4
x[n]
3
2
1
0
-8
-7
-6
-5
-4
-3
-2
-1
0
-N1
1
2
3
4
2
3
4
5
6
7
8
9
10
11
12
5
6
7
8
9
10
11
12
N1
4
xp[n]
3
2
1
0
-8
-7
-6
-5
-N
-4
-3
-2
-1
0
1
N
2
TE-810 Processamento Digital de Sinais
-
UFPR
Podemos representar ~x[n] através da Série de Fourier:
~
x [n] 
 a .e
k N
k
2
jk n
N
1
ak 
N
~
 x[n].e
 jk
n N
~
x
[
n
]

x [n] p /  N1  n  N1
Como:
x[n]  0
p / | n | N1
Podemos escrever:
ou então:
1
ak 
N
N .ak 
2
n
N
N1
 x[n].e
 jk
2
n
N
n   N1

 x[n].e
 jk
2
n
N
n  
3
TE-810 Processamento Digital de Sinais
-
UFPR
Encontrando a envoltória de N.ak :
2
k
 k . 0  
N
Obtemos:
Discreto  Contínuo

X () 
 x[n].e
 jn
n  
Transformada de Fourier do Sinal Discreto x[n]
1
Logo: ak  . X ( k 0 )
N
2
0 
N
Os coeficientes da Série de Fourier do sinal ~x[n]
podem ser vistos como amostragem da Transformada
de Fourier em k.0 do sinal x[n].
4
TE-810 Processamento Digital de Sinais
-
UFPR
Voltando à nossa análise:
Chamando os termos:
~
N.ak  X [k ]
Definimos a Equação de Análise da DFS de N pontos como:
N 1
~
X [k ]   ~
x [n].e  jk0n
n 0
2
0 
N
e a Equação de Síntese da DFS de N pontos:
N 1
1
~
~
x [n]   X [k ].e jk0n
N k 0
2
0 
N
5
TE-810 Processamento Digital de Sinais
-
UFPR
Denotando a quantidade complexa:
WN  e
j
2
N
Podemos reescrever as equações de análise e
Síntese como:
N 1
X [k ]   x[n].W
n 0
1
x[n] 
N
N 1
kn
N
 X [k ].W
k 0
 kn
N
6
TE-810 Processamento Digital de Sinais
-
UFPR
8.2. Propriedades da DFS
~
DFS
~
x1[n] 
 X1[k ]
8.2.1. Linearidade:
~
DFS
~
x2[n] 
 X 2[k ]
~
~
DFS
~
~
a.x1[n]  b.x2[n] 
 a.X1[k ]  b.X 2[k ]
~
DFS
~
x[n] 
 X [k ]
~
~
 jk 2N m
DFS
~
x [n  m] 
 X [k ].e
 X [k ].WNkm
8.2.2. Deslocamento:
8.2.3. Dualidade:
~
DFS
~
x[n] 
 X [k ]
~
DFS
X [n] 
 N~
x[k ]
7
TE-810 Processamento Digital de Sinais
-
UFPR
8.2.5. Convolução Periódica
~
DFS
~
x1[n] 
 X1[k ]
~
DFS
~
x [n] 
 X [k ]
2
2
~
~
DFS
~
~
x1[n] * x2[n] 
 X1[k ].X 2[k ]
N 1
~x [n] ~x [n]  ~x [m].~x [n  m]
* 2
1 2
1
m 0
8
TE-810 Processamento Digital de Sinais
-
UFPR
8.2.6. Resumo das propriedades da DFS
9
TE-810 Processamento Digital de Sinais
-
UFPR
8.5. A Transformada Discreta de Fourier - DFT
x [ n]
Considere sequência finita x[n] e a periódica associada ~
~
x [ n] 

 x[n  rN ]
r  
ou
~
x[n]  x[((n))N ]
Se comprimento x[n]  N
x[n], 0  n  N  1
~
x[n]  
0, outros
Pela propriedade da Dualidade da DFS
10
TE-810 Processamento Digital de Sinais
-
UFPR
Temos que:
~
 X [k ], 0  k  N  1
X [k ]  
0, outros
ou
~
X [k ]  X [((k ))N ]
Podemos definir a
DFT de N pontos:
N 1
Eq. de análise:
X [k ]   x[n].e
Eq. de síntese:
1 N 1
jk 2N n
x[n]   X [k ].e
N k 0
 jk 2N n
n 0
11
TE-810 Processamento Digital de Sinais
1 N 1
jk 2N n
x[n]   X [k ].e
N k 0
N 1
X [k ]   x[n].e
-
UFPR
 jk 2N n
n 0
x[n] 
 X [k ]
DFT ( N )
Interpretações:
-X~[k ], 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 X [k ] do sinal
periódico associado ~x [n]
12
TE-810 Processamento Digital de Sinais
-
UFPR
DFT de um sinal contínuo
não limitado no tempo:
13
Exemplo:
aliasing
TE-810 Processamento Digital de Sinais
-
5
UFPR
4.5
4
3.5
3
N=5
2.5
2
1.5
1
0.5
0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
5
4.5
4
3.5
N=6
3
2.5
2
1.5
1
0.5
0
5
4.5
4
3.5
3
N=8
2.5
2
1.5
1
0.5
0
14
TE-810 Processamento Digital de Sinais
5
5
4.5
4.5
4
4
3.5
3.5
3
3
2.5
2.5
2
2
1.5
1.5
1
1
0.5
0.5
0
0
1
2
3
4
5
6
0
7
0
1
2
3
N=10
4
5
6
-
UFPR
7
N=25
N=50
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
1
2
3
4
5
6
7
15
TE-810 Processamento Digital de Sinais
-
UFPR
DFT de sinais sinusoidais
1
40
0.5
20
0
0
10
20
30
40
0
1
20
0
10
-1
0
10
20
30
40
0
1
20
0
10
-1
0
10
20
30
40
0
1
40
0
20
-1
0
10
20
30
40
0
0
10
20
30
40
0
10
20
30
40
0
10
20
30
40
0
10
20
30
40
16
TE-810 Processamento Digital de Sinais
-
UFPR
Porém:
1
0.5
0
-0.5
-1
0
5
10
15
20
25
30
35
0
5
10
15
20
25
30
35
15
10
5
0
17
TE-810 Processamento Digital de Sinais
-
UFPR
DFT Sinal limitado em freq.
com truncamento igual ao
período.
18
TE-810 Processamento Digital de Sinais
-
UFPR
DFT Sinal limitado em freq.
com truncamento não igual ao
período.
19
TE-810 Processamento Digital de Sinais
-
UFPR
8.6. Propriedades da DFT
8.6.1. Linearidade:
DFT ( N3 )
x1[n] 
 X1[k ]
DFT ( N3 )
x2[n] 
 X 2[k ]
DFT ( N3 )
a.x1[n]  b.x2[n] 
 a.X1[k ]  b.X 2[k ]
N3  max{N1, N2}
DFT ( N )
8.6.2. Deslocamento Circular: x[n] 

 X [k ]
x[((n  m))N ] 
 X [k ].e
DFT ( N )
 jk 2N m
0  n  N 1
DFT ( N )
8.6.3. Dualidade: x[n] 

 X [k ]
DFT ( N )
X [n] 

 N.x[((k ))N ]
0  k  N 1
20
TE-810 Processamento Digital de Sinais
-
UFPR
8.6.5. Convolução Circular:
Nada mais é do que a convolução periódica considerando
sinais de duração finitos x1[n] e x2[n]
x1[n] * x2 [n] 
Linear:
Sinais ilimitados

 x [m].x [n  m]
m  
Periódica: ~x2 [n] * ~x2 [n] 
Sinais periódicos
1
2
N 1
 ~x [m].~x [n  m]
M 0
1
2
N 1
Circular:
x1[n]
Sinais limitados
N
x2 [n]   x1[((m))N ].x2 [((n  m))N ]
m 0
DFT ( N )
x1[n] 

 X1[k ]
DFT ( N )
x2 [n] 

 X 2 [k ]
x1[n]
N
DFT ( N )
x2[n] 

 X1[k ].X 2[k ]
21
TE-810 Processamento Digital de Sinais
-
UFPR
8.6.6. Resumo das Propriedades da DFT
22
TE-810 Processamento Digital de Sinais
-
UFPR
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 sinais
atravé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:
x3[n]  x1[n] N x2[n]
Porém muitas vezes desejamos: x3[n]  x1[n] x2 [n]
23
TE-810 Processamento Digital de Sinais
Sendo:
-
UFPR
x1[n] de compriment
oL
x2 [n] de compriment
o P
O resultado da convolução circular de N amostras será
igual à convolução linear se:
N  L  P 1
Porém: se um dos sinais tiver comprimento indeterminado
(processamento em tempo real).
Dois métodos implementam uma forma eficiente
de cálculo da convolução linear através da DFT.
Overlap-add e Overlap-save
Implementação de Sistemas LTI
24
TE-810 Processamento Digital de Sinais
-
UFPR
8.8 Transformada Discreta do Cosseno (DCT)
DFT é o exemplo mais comum da classe de
Transformadas Discretas de tamanho finito
N 1
A[k ]   x[n]  k*[n]
n 0
1
x[n] 
N
N 1
 A[k ]  [n]
k 0
k
Onde as sequências base k [n]
São ortogonais:
N 1
1, m  k
1
*
k [n]  m [n]  

N n 0
0, m  k
25
TE-810 Processamento Digital de Sinais
No caso da DFT:
k [n]  e
-
UFPR
jk 2N n
A[k] nesse caso é geralmente uma sequência complexa.
São exemplos de Transformadas que fazem :

-Haar
-Hadamard
-Hartley (DHT)
-DCT
-DST
- ...
26
TE-810 Processamento Digital de Sinais
-
UFPR
A DCT considera o sinal x[n] periódico e com simetria par:
Período:
2N-2
4N
Período:
2N
4N
Logo: temos 4 tipos de DCT: DCT-1, DCT-2, DCT-3 e DCT-4
E existem outras 4 formas de se criar um sinal periódico e com simetria par.
27
TE-810 Processamento Digital de Sinais
-
UFPR
A DST (Discrete Sine Transform) considera sinal periódico
E 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ão
de sinais (JPEG e MPEG-1,2,4):
X C 2 [k ] 
x[n] 
Onde:
N 1
  k  2n  1 
2
 [k ] x[n]cos 

N
2N
n 0


  k  2n  1 
2 N 1
C2
 [k ] X [k ]cos 


N k 0
2
N


1

 2, k 0
 [k ]  

1, k  1, 2,..., N  1
28
TE-810 Processamento Digital de Sinais
-
UFPR
Exemplo: Compactação de Energia na DCT-2
29
TE-810 Processamento Digital de Sinais
-
UFPR
30
TE-810 Processamento Digital de Sinais
-
UFPR
Transformada ótima para compactação
de 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.
31
TE-810 Processamento Digital de Sinais
-
UFPR
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 importantes
P/ escolha de um algoritmo.
Algoritmos de FFT: revolucionaram a área de
processamento de sinais
32
TE-810 Processamento Digital de Sinais
-
UFPR
9.1. Computação eficiente da DFT
N 1
X [k ]   x[n].WNkn
k  1,2,..., N  1
n 0
N 1
1
x[n]   X [k ].WNkn
N k 0
n  1,2,..., N  1
WN  e
 j 2N
Como as equações diferem apenas do fator de escala N
e do sinal do expoente de WN, a teoria vista p/ cálculo
da DFT aplica-se também à IDFT
Cálculo direto:
-como x[n] pode ser sinal complexo,
Para computar N amostras do sinal X[k] requer
N2 multiplicações complexas e N(N-1) adições complexas
ou
4N2 multiplicações reais e N(4N-2) somas reais
E mais memórias p/ armazenamento de N amostras complexas
de x[n] e coeficientes WN
Proporcional O(N2)
33
TE-810 Processamento Digital de Sinais
-
UFPR
A maioria dos algoritmos de FFT exploram as
seguintes características:
1) Simetria complexa conjugada: W
k [ N n]
N
W
 kn
N
 
W
kn 
N
kn
k ( n N )
 WN( k  N ) n
2) Periodicidade em k e n : WN  WN
Exploram ainda a decomposição de uma DFT
de 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
34
TE-810 Processamento Digital de Sinais
-
UFPR
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 pontos
Compostas dos n ímpares e n pares
N 1
X [k ]   x[n].WNkn
n 0
X [k ] 
nk
x
[
n
].
W

N 
n par
nk
x
[
n
].
W

N
n ímpar
35
TE-810 Processamento Digital de Sinais
X [k ] 
nk
x
[
n
].
W

N 
n par
-
UFPR
nk
x
[
n
].
W

N
n ímpar
Mudando as variáveis: n=2r
para n par
n=2r+1 para n ímpar
X [k ] 
X [k ] 
( N / 2 1)
( N / 2 1)
r 0
r 0
2 rk
x
[
2
r
].
W


N
( N / 2 1)

 
2 rk
N
x[2r ]. W
r 0
( 2 r 1) k
x
[
2
r

1
].
W

N
W
k
N
( N / 2 1)

r 0
 
2 rk
N
x[2r  1]. W
Como: WN2  WN / 2
36
TE-810 Processamento Digital de Sinais
Como: W  WN / 2
2
N
-
UFPR
Podemos reescrever:
X [k ] 
( N / 21)

r 0
X [k ] 
 
2 rk
N
x[2r ]. W
W
( N / 21)
k
N

( N / 21)
r 0
r 0
X [k ]  G[k ]  WNk H[k ]
x[2r  1]. W
r 0
( N / 21)
rk
k
x
[
2
r
].
W

W

N /2
N
 
2 rk
N
rk
x
[
2
r

1
].
W

N /2
k  0,1,2,...,N 1
37
TE-810 Processamento Digital de Sinais
-
UFPR
Aplicando o mesmo princípio para o cálculo de G[k] e H[k]
DFT(N/2)
G[k ] 
( N / 41)
( N / 41)
l 0
l 0
H [k ] 
lk
k
g
[
2
l
].
W

W

N /4
N /2
lk
g
[
2
l

1
].
W

N /4
( N / 41)
( N / 41)
l 0
l 0
lk
k
h
[
2
l
].
W

W

N /4
N /2
lk
h
[
2
l

1
].
W

N /4
38
TE-810 Processamento Digital de Sinais
-
UFPR
Temos:
E assim sucessivamente até chegar ao cálculo da DFT(2)
39
TE-810 Processamento Digital de Sinais
-
UFPR
DFT de 2 pontos:
1
X [k ]   x[n].WNkn
n 0
X [0]  x[0].W20.0  x[1].W20.1  x[0]  x[1]
X [1]  x[0].W21.0  x[1].W21.1  x[0]  x[1]
40
TE-810 Processamento Digital de Sinais
-
UFPR
Diagrama completo p/ DFT 8-pontos decimação no tempo:
Notar que a complexidade computacional é: N.log(N)
41
TE-810 Processamento Digital de Sinais
-
UFPR
Reduzindo ainda mais a complexidade computacional:
Célula básica de computação: butterfly
Como:
WN( r  N / 2)  WNr .WNN / 2  WNr .(1)
42
TE-810 Processamento Digital de Sinais
-
UFPR
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]
43
TE-810 Processamento Digital de Sinais
-
UFPR
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]
44
TE-810 Processamento Digital de Sinais
-
UFPR
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 pontos
Compostas dos k ímpares e k pares
N 1
X [k ]   x[n].WNnk
n 0
N 1
X [2r ]   x[n].WNn ( 2 r )
P/ X[pares]
n 0
Que podemos escrever como:
45
TE-810 Processamento Digital de Sinais
-
UFPR
N 1
X [2r ]   x[n].WNn ( 2 r )
P/ X[pares]
n 0
Que podemos escrever como:
X [ 2r ] 
N / 21
2 nr
x
[
n
].
W


N
n 0
N 1
2 nr
x
[
n
].
W

N
n N / 2
Substituindo variáveis no 2° somatório
X [ 2r ] 
N / 2 1
 x[n].W
n 0
2 nr
N

N / 2 1
 x[n 
N
2
2( n N 2 ) r
N
].W
n 0
Notando que: WN2r ( n N / 2)  WN2rn .WNrN  WN2rn .1
Logo:
X [ 2r ] 
N / 2 1
N / 2 1
n 0
n 0
2 rn
x
[
n
].
W


N
N ].W 2 rn
x
[
n

2

N
46
TE-810 Processamento Digital de Sinais
Lembrando que:
-
UFPR
WN2rn  WNrn/ 2
Temos que: X [2r ] 
N / 2 1
N / 2 1
n 0
n 0
2 rn
x
[
n
].
W


N
N ].W 2 rn
x
[
n

2

N
Pode ser escrito como:
X [ 2r ] 
N / 21
N ].W rn

x
[
n
]

x
[
n

2

N /2
n 0
De modo análogo p/ k ímpares podemos escrever:
N 1
X [2r  1]   x[n].WNn ( 2 r 1)
P/ X[ímpares]
n 0
Que podemos escrever como:
47
TE-810 Processamento Digital de Sinais
N 1
X [2r  1]   x[n].WNn ( 2 r 1)
-
UFPR
P/ X[ímpares]
n 0
Que podemos escrever como:
X [2r  1] 
N / 2 1
n ( 2 r 1)
x
[
n
].
W


N
n 0
N 1
n ( 2 r 1)
x
[
n
].
W

N
n N / 2
Substituindo variáveis no 2° somatório
X [2r  1] 
N / 21
 x[n].W
n 0
n ( 2 r 1)
N

N / 21
 x[n 
N
2
( n  N 2 )( 2 r 1)
N
].W
n 0
Notando que: WN( n N / 2)( 2r 1)  WNn( 2r 1) .WN( 2r 1)
Logo: X [2r  1] 
N / 21
 x[n].W
n 0
n ( 2 r 1)
N

N
2
 WNn(2r 1) .(1)
N / 21
N ].W n ( 2 r 1)
x
[
n

2

N
n 0
48
Logo: X [2r  1] 
N / 21
n ( 2 r 1)
x
[
n
].
W


N
n 0
N / 21
X [2r  1] 
X [2r  1] 
TE-810 Processamento Digital de Sinais
N / 21
n ( 2 r 1)
N
2
N
n 0
 x[n 
-
UFPR
].W
N ].W n ( 2 r 1)

x
[
n
]

x
[
n

2

N
n 0
N / 2 1
N ].W 2 nr .W n

x
[
n
]

x
[
n

2

N
N
n 0
N / 2 1
P/ k ímpares: X [2r  1] 
N ].W n .W nr

x
[
n
]

x
[
n

2

N
N /2
n 0
P/ k pares:
X [ 2r ] 
N / 21
N ].W rn

x
[
n
]

x
[
n

2

N /2
n 0
49
TE-810 Processamento Digital de Sinais
-
UFPR
Aplicando o mesmo procedimento p/ cálculo
da DFT N/2 pontos
50
TE-810 Processamento Digital de Sinais
-
UFPR
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
51
TE-810 Processamento Digital de Sinais
-
UFPR
Algoritmos vistos são Radix-2
Outros algoritmos:
-Radix-4, Radix-8, etc...
-Split-Radix
-Produto de inteiros
-...
52
TE-810 Processamento Digital de Sinais
Convolução:
-
UFPR
N 1
Método Direto: y[n]   x[k ].h[n  k ]
k 0
Complexidade: O(2N2)
N  N1  N 2 1  2 N 1
(2 N )

 X [k ]
Por FFT: x[n] FFT
(2 N )
h[n] FFT

 H [k ]
Y [k ]  X [k ].H [k ]
(2 N )
Y [k ] IFFT

 y[n]
Complexidade: O(3.2N.log(2N)+2N)
53