Processamento Digital de Sinais
Renato da Rocha Lopes e Amauri Lopes
DECOM - Departamento de Comunicacoes - DECOMFaculdade de Engenharia Eletrica e de Computacao - FEEC
Universidade Estadual de Campinas - UNICAMP
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 1 / 55
Conteudo da Aula
1 IntroducaoDFTExemploExtensao PeriodicaRecuperando a DTFT
2 Propriedades
3 Vazamento em FrequenciaIntroducaoExplicacaoJanelamentoZero Padding
4 Convolucao e DFT
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 2 / 55
Introducao
Transformada de Fourier
X (ω) =∞∑
n=−∞
x [n]e−jωn
x [n] = 12π
2π∫
0
X (ω)ejωn dω
Formula fechada so para funcoes especıficas, como seno.I Como calcular para um sinal de audio?I Numericamente impossıvel, teria que calcular para todo ω
Alternativa: Transformada Discreta de Fourier
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 4 / 55
Introducao DFT
DFT: Definicao
Computadores e processadores trabalham com sequencias finitas dedados
I x [n], n = 0, 1, . . . ,N − 1I Exemplo: arquivo MP3
DTFT: X (ω) =N−1∑
n=0x [n]e−jωn
I Exagero: representa N valores de x [n] com infinitos valores de X (ω)I Como representar com N valores?
DFT: X [k] =∑N−1
n=0 x [n]e−j2πkn/N , para k = 0, 1, . . . ,N − 1I X [k ] = X (2πk/N), para k = 0, 1, . . . ,N − 1I Amostragem em frequencia
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 6 / 55
Introducao DFT
Interpretacao: Mudanca de Base
Exemplo: N = 4
X [0] = x [0] + x [1] + x [2] + x [3]
X [1] = x [0] − jx [1]− x [2] + jx [3]
X [2] = x [0] − x [1] + x [2]− x [3]
X [0] = x [0] + jx [1]− x [2] − jx [3]
X [0]X [1]X [2]X [3]
︸ ︷︷ ︸
X
=
1 1 1 11 −j −1 j
1 −1 1 −11 j −1 −j
︸ ︷︷ ︸
F
x [0]x [1]x [2]x [3]
︸ ︷︷ ︸
x
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 7 / 55
Introducao DFT
DFT Inversa
x = F−1X
Fato:N−1∑
k=0
e j2πk(n−r)/N =
N, n − r = lN (l ∈ N)0, c.c.
X [k] =N−1∑
n=0x [n]e−j2πkn/N
x [n] = 1N
N−1∑
k=0
X [k]ej2πkn/N
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 8 / 55
Introducao DFT
Interpretacao: Amostragem em Frequencia
0 π/2 π 3π/2 2π0
1
2
3
4
5
6
7
8
9
10
|X(ω
)|
ω
k = 0
k = 1
k = 2 k = 3 k = 4k = 5
k = 6
X [k] = X
(2πk
N
)
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 9 / 55
Introducao Exemplo
Exemplo: N = 7
x [n] =
1, 0 ≤ n ≤ 90, c.c.
X (ω) = e−jω9/2 sin(10ω/2)
sin(ω/2)
0 π/2 π 3π/2 2π0
1
2
3
4
5
6
7
8
9
10
|X(ω
)|
ω
k = 0
k = 1
k = 2 k = 3 k = 4k = 5
k = 6
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 11 / 55
Introducao Exemplo
Exemplo: N = 7
k = 0:6;
X = exp(-j*2*pi*k*9/14).*sin(10*pi*k/7)./sin(pi*k/7)
X(1) = 10;x = ifft(X);
(a)
(b)
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 12 / 55
Introducao Exemplo
Exemplo: N = 10
0 π/2 π 3π/2 2π0
1
2
3
4
5
6
7
8
9
10
|X(ω
)|
ω
k = 0
k = 1 k = 2
k = 3
k = 9
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 13 / 55
Introducao Exemplo
Exemplo: N = 13
0 p/2 p 3p/2 2p0
1
2
3
4
5
6
7
8
9
10
|X(ω
)|
ω
k = 0
k = 1
k = 2
k = 3
k = 12
x [n]
x[n-13]1
13 22-13 - 4
13
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 14 / 55
Introducao Extensao Periodica
Extensao Periodica
DTFT: X (ω) ↔ x [n]
DFT: X [k] = X (k2π/N) ↔ xs [n]
x [n] nao necessariamente de duracao finita
A qual sinal corresponde a DFT?
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 16 / 55
Introducao Extensao Periodica
Extensao Periodica: Prova
xs [n] =1
N
N−1∑
k=0
X [k]e−j2πkn/N
=1
N
N−1∑
k=0
X (2πk/N)e−j2πkn/N
=1
N
N−1∑
k=0
(∞∑
l=−∞
x [l ]e−j2πkl/N
)
ej2πkn/N
MasN−1∑
n=0
e−j2πk(l−n)/N =
N, n − l e multiplo de N
0, c.c.
xs [n] =
∞∑
l=−∞
x [n − lN]
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 17 / 55
Introducao Extensao Periodica
Extensao Periodica: Exemplo
x [n] = 0,9nu[n]
−20 −10 0 10 20 30 400
0.2
0.4
0.6
0.8
1
1.2
1.4
x[n+20]
x[n+40]
x[n−20]x[n]
ExtensãoPeriódica
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 18 / 55
Introducao Recuperando a DTFT
A formula
Dado X [k], como calcular X (ejω) para um ω qualquer?
X (ejω) =
N−1∑
n=0
x [n]ejωn
=
N−1∑
n=0
(
1
N
N−1∑
k=0
X [k]ej2πkn/N
)
ejωn
=1
N
N−1∑
k=0
X [k]
N−1∑
n=0
ej2πkn/Nejωn
X (ejω) =1
N
N−1∑
k=0
X [k]1− e−jN(ω−2πk/N)
1− e−j(ω−2πk/N)
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 20 / 55
Introducao Recuperando a DTFT
A Figura
−2pi −pi 0 pi 2pi 3pi
−2
0
2
4
6
8
X[1]
X[3]
X[0]
X[2]
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 21 / 55
Propriedades
Periodicidade no Tempo
X [k] =
N−1∑
n=0
x [n]e−j2πkn/N
x [n] =1
N
N−1∑
k=0
X [k]ej2πkn/N
x [n + N] =1
N
N−1∑
k=0
X [k]ej2πk(n+N)/N
=1
N
N−1∑
k=0
X [k]ej2πkn/N ej2πk
= x [n]
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 23 / 55
Propriedades
Simetrias
x [n] real ⇒ X (ω) = X ∗(−ω)I Magnitude e par:
|X (ω)| = |X (−ω)|I Fase e ımpar:
∠X (ω) = ∠X (−ω)
x [n] real ⇒ X [k] = X ∗[−k]I Magnitude e par:
|X [k ]| = |X [−k ]|I Fase e ımpar:
∠X [k ] = ∠X [−k ]
Como X [N − k] = X [−k], |X [k]| = |X [N − k]|
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 24 / 55
Propriedades
Periodicidade em Frequencia
X [k] =
N−1∑
n=0
x [n]e−j2πkn/N
x [n] =1
N
N−1∑
k=0
X [k]ej2πkn/N
X [k + N] =1
N
N−1∑
k=0
X [k]ej2π(k+N)n/N
=1
N
N−1∑
k=0
X [k]ej2πkn/Nej2πn
= X [k]
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 25 / 55
Propriedades
Relacao entre Frequencias
xc(t)DFT
x [n] X [k]A/D
X (ω) = Xc
(ωfs2π
)
X [k] = X
(2πk
N
)
X [k] = Xc
(kfs
N
)
......
k
ΩΩm
N−N
X [k]
Xc(Ω)X [−1] = X [n − 1]
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 26 / 55
Vazamento em Frequencia Introducao
Entrada Senoidal
DFT calcula espectro em 2kπ/NI Sinais de duracao N so contem essas frequenciasI Frequencia “desejada” pode ter outra forma.
x [n] = ejωn, n = 0, 1, . . . ,N − 1 ↔ |X [k]| =
∣∣∣∣
sin((ω − 2kπ/N)N/2)
sin((ω − 2kπ)/2)
∣∣∣∣
Se ω − 2kπ/N = l2π/N, entaoI X [k ] = N se l e multiplo de N ,I X [k ] = 0 caso contrario.
Caso contrario, X [k] 6= 0.
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 29 / 55
Vazamento em Frequencia Introducao
Exemplo sem Vazamento
N = 20
ω = π = 2 ∗ π ∗ 10/N
−15 −10 −5 0 5 10 150
2
4
6
8
10
12
14
16
18
20
k
|X[k
]|
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 30 / 55
Vazamento em Frequencia Introducao
Exemplo com Vazamento
N = 20
ω = π − 2π ∗ 9,75/N
−15 −10 −5 0 5 10 150
2
4
6
8
10
12
14
16
18
20
k
|X[k
]|
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 31 / 55
Vazamento em Frequencia Explicacao
Vazamento Explicado
−10 0 10 20 30−1
−0.5
0
0.5
1
n
Seqüência de Interesse
−10 0 10 20 30−1
−0.5
0
0.5
1Entrada da DFT
n
−10 0 10 20 300
0.2
0.4
0.6
0.8
1
n
Janelamento
−10 0 10 20 30−1
−0.5
0
0.5
1
n
Extensão Periódica
Sinal deinteresse: x∞[n]
Janela: w [n]
DFT: espectro dex [n] = x∞[n]w [n]
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 33 / 55
Vazamento em Frequencia Explicacao
Vazamento Explicado
Resumo:
DFT calcula amostras do espectro de sinal janelado:
X [k] = X (ej2πk/N )
X (ejω) = Fx [n] = x∞w [n]
Consequencia
Convolucao em frequencia:
X (ejω) =1
2π
∫ π
−πX∞(ejθ)W (ej(ω−θ))dθ
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 34 / 55
Vazamento em Frequencia Explicacao
Prova da Convolucao em Frequencia
Seja z [n] = x [n]y [n]. Entao
Z (ejω) =∞∑
n=−∞
z [n]e−jωn
=
∞∑
n=−∞
x [n]y [n]e−jωn
=
∞∑
n=−∞
x [n]
(1
2π
∫ π
−πY (ejθ)dθ
)
e−jωn
=1
2π
∫ π
−πY (ejθ)
∞∑
n=−∞
x [n]e−j(ω−θ)n dθ
=1
2π
∫ π
−πY (ejθ)X (e−j(ω−θ))dθ
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 35 / 55
Vazamento em Frequencia Explicacao
Vazamento em Frequencia
ωπ−π 0
X (ejω)Janela
Frequencia de Interesse
DFT calcula componente em frequencia como area sob a curva
Comportamento desejado da janela em frequencia:I Valores nulos em frequencias diferentes da de interesseI Extrai apenas frequencia de interesse ⇒ resposta em frequencia
concentrada em torno da origem.
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 36 / 55
Vazamento em Frequencia Janelamento
Melhorando Janela
Aumenta tamanho da janela, diminui vazamento
−pi −pi/2 0 pi/2 pi0
1
2
3
4
5N = 5
−pi −pi/2 0 pi/2 pi0
5
10
15
20N = 20
−pi −pi/2 0 pi/2 pi0
2
4
6
8
10
ω
N = 10
−pi −pi/2 0 pi/2 pi0
10
20
30
40
50
ω
N = 50
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 38 / 55
Vazamento em Frequencia Janelamento
Melhorando Janela
Usa outras formas de onda, com frequencia mais concentrada na origem
Retangular:w [n] = 1, 0 ≤ n ≤ N − 1
Triangular:
w [n] =|n|
N/2, |n| ≤ N/2
Hanning:
w [n] = 0,5− 0,5 cos
(2πn
N − 1
)
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 39 / 55
Vazamento em Frequencia Janelamento
Janelas em Frequencia
0 pi/2 pi0
2
4
6
8
10
12
14
16
18
20Resposta em Frequencia de Algumas Janelas
RetangularTriangularHanning
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 40 / 55
Vazamento em Frequencia Janelamento
Janelas em Frequencia
0 pi/2 pi−100
−80
−60
−40
−20
0
20
ω
Resposta em Frequencia (dB) de Algumas Janelas
RetangularTriangularHanning
Melhora vazamento de frequencias distantes.Piora influencia de frequencias vizinhas (perda de resolucao).
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 41 / 55
Vazamento em Frequencia Janelamento
Exemplo do Efeito das Janelas
N = 64 pontos, x [n] = sin(2π3,4n/64) + 0,1 sin(2π7n/64)
0 5 10 15 20 25 300
5
10
15
20
25
30
RetangularHanning
Freq. k = 7
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 42 / 55
Vazamento em Frequencia Zero Padding
Melhorando Aproximacao da DFT
DFT calcula espectro nas frequencias 2πk/N
Aumentando N, calculamos espectro em mais pontos.I melhor aproximacao do espectro contınuo do sinal.
Exemplo: senoide amostrada 16 vezes em 3 perıodos
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 44 / 55
Vazamento em Frequencia Zero Padding
Sinal Contınuo
−1 −0.5 0 0.5 1 1.5 2 2.5 3 3.5 4−1
−0.5
0
0.5
1
t
Sinal no Tempo
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 20
50
100
150
200
250
300
f
Sinal em Frequencia
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 45 / 55
Vazamento em Frequencia Zero Padding
Sem preencher com zeros
0 5 10 15−1
−0.5
0
0.5
1
n
Sinais no Tempo
0 2 4 6 8 10 12 14 160
2
4
6
8
10
k
Sinais em Frequencia
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 46 / 55
Vazamento em Frequencia Zero Padding
16 zeros
0 5 10 15 20 25 30−1
−0.5
0
0.5
1
n
Sinais no Tempo
0 5 10 15 20 25 30 350
2
4
6
8
10
k
Sinais em Frequencia
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 47 / 55
Vazamento em Frequencia Zero Padding
112 zeros
0 20 40 60 80 100 120−1
−0.5
0
0.5
1
n
Sinais no Tempo
0 20 40 60 80 100 1200
2
4
6
8
10
k
Sinais em Frequencia
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 48 / 55
Vazamento em Frequencia Zero Padding
Notas
Resolucao nao melhora com zero-padding
I Largura do lobulo central nao se alteraI Resolucao depende do numero de amostras original
Eixo x da DFT: 2πk/N ↔ frequencia analogica kfs/NI Pico sempre ocorre em f = 3fs/16I Como fs = 16, senoide de frequencia 3.
Contradicao:I Amostragem exige x(t) limitado em frequenciaI DFT exige x(t) limitado no tempoI Teoria proıbe que ambos sejam verdade.I Pratica: sinais sao quase limitados no tempo e na frequencia
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 49 / 55
Convolucao e DFT
Motivacao
x [n] y [n]h[n]
Duracao de x [n]: Nx amostras
Duracao de h[n]: Nh amostras
⇒ Calculo da saıda envolve ≈ NxNh somas e ≈ NxNh produtos
FFT
Calcula DFT em N log(N) operacoes!
E possıvel calcular saıda com DFT?
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 51 / 55
Convolucao e DFT
Convolucao Circular
x [n] y [n]h[n]
y [n] = x [n] ∗ h[n] Y (ejω) = X (ejω)H(ejω)
O que da X [k]H[k] = Z [k]? Exemplo com N = 4:
z [0] = x [0]h[0] + x [1]h[3] + x [2]h[2] + x [3]h[1]
z [1] = x [0]h[1] + x [1]h[0] + x [2]h[3] + x [3]h[2]
z [2] = x [0]h[2] + x [1]h[1] + x [2]h[0] + x [3]h[3]
z [3] = x [0]h[3] + x [1]h[2] + x [2]h[1] + x [3]h[0]
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 52 / 55
Convolucao e DFT
Convolucao Circular Versus Linear
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 n
n−4 −3 −2 −1
Intervalo de Soma
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n
Intervalo de Soma
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
x [n] x [n]
Convolucao Circular Convolucao Linear
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 53 / 55
Convolucao e DFT
Convolucao Circular e Zero-Padding
Duracao de x [n]: Nx amostras
Duracao de h[n]: Nh amostras
⇒ Duracao de y [n]: Ny = Nx + Nh − 1 amostras
DFTs envolvidas devem ter comprimento Ny ⇒ Zero-Padding
Nesse caso, convolucao circular = convolucao linear.
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 54 / 55
Convolucao e DFT
Convolucao Circular com Zero-Padding
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
x [n]
n
n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6
x [n]
n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
0 1 2 3 4 5 6 7 n−4 −3 −2 −1
n
Intervalo de Soma
Intervalo de Soma Efetivo
Renato R. Lopes e Amauri Lopes (DECOM) Processamento Digital de Sinais 55 / 55