Transformada Discreta de Fourier 1
Processamento Digital de Sinais
Notas de Aula
Serie e Transformada Discreta deFourier
DFS / DFT
Ricardo Tokio Higuti
Departamento de Engenharia Eletrica - FEIS - Unesp
Observacao: Estas notas de aula estao baseadas no livro: “Discrete-Time Signal Processing”,
A.V. Oppenheim and R.W. Schafer, Prentice Hall, 1989/1999.
Transformada Discreta de Fourier 2
Transformadas para sinais de tempo discreto
DTFT: X(ejω) =∞∑
n=−∞x[n]e−jωn
• E uma transformada da variavel contınua ω
• Usada para sinais de duracao finita/infinita
• Nao pode ser implementada de maneira exata num computador
• Uso de outras ferramentas matematicas que a aproximam
DFT:
• Aplicada a sinais de tempo discreto de duracao finita
• O resultado e um sinal de frequencia discreta e de duracao finita
• Pode ser implementada de maneira exata num computador
• E uma aproximacao da DTFT
• Existem algoritmos eficientes para seu calculo (FFT - Fast Fourier
Transform)
• Esta relacionada com sinais periodicos (DFS - Discrete Fourier Series)
Aplicacoes:
• Analise espectral de sinais, resposta em frequencia
• Implementacao de SLITs
Transformada Discreta de Fourier 3
Serie Discreta de Fourier - DFS
Seja um sinal de tempo discreto periodico, com perıodo N , que obedece a:
x[n] = x[n+ rN ], r, N inteiros,
em que define-se a frequencia fundamental do sinal por:
ω0 =2π
N
Analogamente ao caso de tempo contınuo, este sinal tambem pode ser
representado por uma serie, composta por uma soma de exponenciais com-plexas de tempo discreto, cujas frequencias sao multiplas da frequencia
fundamental:
x[n] =∑
k
Xk
Nej
2π
Nkn
Devido a periodicidade das frequencias das exponenciais complexas, ha
apenas N frequencias distintas:
ek[n] = ej2π
Nkn
Para k inteiro, fica-se com as exponenciais e0[n], e1[n], ..., eN−1[n].
Quando k = N , tem-se:
eN [n] = ej2π
NNn = ej2πn = 1 = e0[n]
De forma analoga, eN+1[n] = e1[n] e assim por diante.
Transformada Discreta de Fourier 4
Serie Discreta de Fourier - DFS
Portanto, ha apenas N diferentes frequencias:
ωk =2π
Nk, para k = 0, 1, 2, · · · , N − 1
e portanto a serie fica:
x[n] =1
N
N−1∑
k=0
Xkej 2π
Nkn =
1
N
N−1∑
k=0
X[k]ej2π
Nkn
Os valores X[k] sao os coeficientes da serie discreta de Fourier (DFS),que representam a contribuicao de cada componente de frequencia 2πk/N
na composicao do sinal periodico. Os coeficientes sao obtidos por:
X[k] =N−1∑
n=0
x[n]e−j2π
Nkn, k = 0, 1, · · · , N − 1
Chagando-se ao par transformado:
x[n]DFS←→ X[k]
Observacoes:
• X [k] e de frequencia discreta. Para cada k ha uma frequencia 2πk/N
• X [k] e periodico com N : X[k + N ] = X [k], por isso basta observar
seus valores no intervalo entre 0 e N − 1.
Transformada Discreta de Fourier 5
Exemplo - DFS
Calcule a DFS da sequencia:
x[n] = A cos(πn/2)
Inicialmente verifica-se que a sequencia e periodica, com perıodo N = 4,
e valores {A, 0, −A, 0} em um perıodo (0 ≤ n ≤ 3).Portanto, a os coeficientes da DFS sao:
X [k] =N−1∑
n=0
x[n]e−j2π
Nkn = A(1− e−j
2π
42k)
Com valores:
• X [0] = A(1− e−jπ0) = 0
• X [1] = A(1− e−jπ1) = 2A
• X [2] = A(1− e−jπ2) = 0
• X [3] = A(1− e−jπ3) = 2A
e percebe-se que X[4] = X [0], e assim por diante.Outra forma de verificar o resultado e reescrevendo a sequencia x[n] em
termos de exponenciais complexas:
x[n] = A cos(πn/2) =A
2ej
π
2n +
A
2e−j
π
2n =
A
2ej
2π
4n +
A
2e−j
2π
4n
Deve-se notar que e−j2π
Nkn = ej
2π
N(N−k)n, e portanto x[n] pode ser escrito
como:
x[n] =A
2ej
2π
4n +
A
2ej
2π
43n
Como a expansao de x[n] em termos da DFS e:
x[n] =1
4
N−1∑
k=0
X [k]ej2π
4kn
Nota-se que:
• X [0] = 0
• X [1]/4 = A/2, portanto X[1] = 2A
• X [2] = 0
• X [3]/4 = A/2, portanto X[3] = 2A
Transformada Discreta de Fourier 6
Relacao entre a DFS e a DTFT
Seja um sinal periodico de tempo discreto, x[n], com perıodo N . Tomando-
se um perıodo desse sinal, fica-se com o sinal x[n]:
x[n] =
x[n], n = 0, 1, ..., N − 10, caso contrario
A DTFT de x[n] e:
X(ejω) =N−1∑
n=0x[n]e−jωn =
N−1∑
n=0x[n]e−jωn
E a DFS de x[n]:
X [k] =N−1∑
n=0
x[n]e−j2π
Nkn, k = 0..N − 1
Comparando as equacoes, tem-se que a DFS e a DTFT, nessas condicoes,
estao relacionadas por:
X[k] = X(ejω)|ω= 2π
Nk, k = 0..N − 1
ou seja, a DFS e composta por amostras da DTFT em N pontosequiespacados de 2π/N , entre ω = 0 e 2π.
Transformada Discreta de Fourier 7
Exemplo
x[n] = {1, 1, 1, 1, 1, 0, 0}, N = 7, L = 5
X(ejω) =4∑
n=0e−jωn = e−j2ω
sin(5ω/2)
sin(ω/2)
X[k] =4∑
n=0
e−j(2π/7)n = e−j(4π/7)ksin(5πk/7)
sin(πk/7)
−2 0 2 4 6 8 10 12 140
0.2
0.4
0.6
0.8
1
1.2
n
0 0.5 1 1.5 20
1
2
3
4
5
x[n], x[n]
|X(ejω)|, |X[k]|
ω/π, ωk/π = 2k/N
Transformada Discreta de Fourier 8
Exemplo
x[n] = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, N = 10, L = 5
X(ejω) =4∑
n=0e−jωn = e−j2ω
sin(5ω/2)
sin(ω/2)
X [k] =4∑
n=0
e−j(2π/10)n = e−j(4π/10)ksin(πk/2)
sin(πk/10)
n
x[n], x[n]
|X(ejω)|, |X [k]|
Transformada Discreta de Fourier 9
Exemplo
x[n] = {1, 1, 1, 1, 1}, N = 5, L = 5
X(ejω) =4∑
n=0e−jωn = e−j2ω
sin(5ω/2)
sin(ω/2)
X[k] =4∑
n=0
e−j(2π/5)n = e−j(4π/5)ksin(πk)
sin(πk/5)
−2 0 2 4 6 8 10 12 140
0.2
0.4
0.6
0.8
1
1.2
n
0 0.5 1 1.5 20
1
2
3
4
5
6
x[n], x[n]
|X(ejω)|, |X[k]|
ω/π, ωk/π = 2k/N
Transformada Discreta de Fourier 10
Exemplo
0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
|X(ejω)|, |X[k]|, N = 20
ω/π, ωk/π = 2k/N
0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
|X(ejω)|, |X[k]|, N = 40
ω/π, ωk/π = 2k/N
Transformada Discreta de Fourier 11
Exemplo - DFS
Calcule a DFS de um trem de impulsos periodico:
x[n] =∞∑
r=−∞δ[n−m+ rN ]
Um perıodo do sinal, para 0 ≤ n ≤ N − 1 e dado por δ[n−m], com muma constante inteira. Os coeficientes da DFS sao dados por:
X[k] =N−1∑
n=0
x[n]e−j2π
Nkn =
N−1∑
n=0
δ[n−m]e−j2π
Nkn = e−j
2π
Nkm
Portanto, a representacao do sinal periodico fica:
x[n] =1
N
N−1∑
k=0
X [k]ej2π
Nkn =
1
N
N−1∑
k=0
e−j2π
Nkmej
2π
Nkn =
1
N
N−1∑
k=0
ej2π
Nk(n−m)
E tem-se a identidade:
x[n] =∞∑
r=−∞δ[n−m+ rN ] =
1
N
N−1∑
k=0
ej2π
Nk(n−m)
Esta identidade sera util quando for relacionada a DFS com a DTFT.
Transformada Discreta de Fourier 12
Amostragem da DTFT
Foi visto que, se, a partir de uma sequencia de duracao finita L, x[n], se
produz uma sequencia periodica x[n] com perıodoN ≥ L, os coeficientes daDFS X[k] sao as amostras da DTFT X(ejω), nas frequencias ωk = 2πk/N .
x[n]⇒ x[n] =+∞∑
m=−∞x[n+mN ]
DFS←→ X[k] = X(ejω)|ω= 2π
Nk
Suponha agora que se tenha uma DTFT de um sinal x[n] qualquer, dadapor X(ejω), e se tomam amostras da DTFT, formando coeficientes de uma
DFS:
X [k] = X(ejω)|ω= 2π
Nk
em que a DTFT e dada por:
X(ejω) =+∞∑
m=−∞x[m]e−jωm
A sequencia periodica x[n] resultante pode ser calculada por meio da
DFS inversa:
x[n] =1
N
N−1∑
k=0
X [k]ej2π
Nkn
=1
N
N−1∑
k=0
+∞∑
m=−∞x[m]e−j
2π
Nkm
ej2π
Nkn
=+∞∑
m=−∞x[m]
1
N
N−1∑
k=0
ej2π
Nk(n−m)
O termo entre colchetes representa a DFS de um trem de impulsosperiodico:
1
N
N−1∑
k=0
ej2π
Nk(n−m) =
+∞∑
r=−∞δ[n−m+ rN ]
Portanto:
x[n] =+∞∑
m=−∞x[m]
+∞∑
r=−∞δ[n−m+ rN ]
= x[n] ∗+∞∑
r=−∞δ[n+ rN ]
=+∞∑
r=−∞x[n+ rN ]
Transformada Discreta de Fourier 13
Amostragem da DTFT
Logo, ao se tomar N amostras da DTFT de um sinal x[n], obtendo-se coefi-
cientes de uma DFS, a sequencia periodica correspondente pode ser obtidapor meio da adicao de infinitas copias de x[n], deslocadas de multiplos deN .
DTFT
DFS
x[n] X(ejω)
X[k] = X(ejω)|ω= 2π
Nk
x[n] =+∞∑
r=−∞x[n+ rN ]
N amostras
Logo: se a sequencia x[n] possuir um comprimento L > N , havera so-
breposicao no domınio do tempo, e um perıodo de x[n] nao representaracorretamente a sequencia x[n].
Ha um numero mınimo de amostras de X(ejω) para que a sequencia x[n]
possa ser recuperada a partir de x[n] (ou a partir das amostras da DTFT).
Transformada Discreta de Fourier 14
Amostragem da DTFT: Exemplo
Seja x[n] um pulso de duracao 5 amostras (L = 5).
0 5 10 15 200
1
2
3sequências
0 0.5 1 1.5 20
5
| DTFT | , | DFS |
0 5 10 15 200
1
2
3
0 5 100
5
0 5 10 15 200
1
2
3
0 2 40
5
0 5 10 15 200
1
2
3
amostra n0 1 2 3 4
0
5
amostra k
x[n] |X(ejω)|
N = 10, X1[k] = X(ejω)|ω= 2π
10kx1[n] =
+∞∑
r=−∞
x[n + 10r]
N = 5, X2[k] = X(ejω)|ω= 2π
5k
x2[n] =+∞∑
r=−∞
x[n + 5r]
N = 4, X3[k] = X(ejω)|ω= 2π
4k
x3[n] =+∞∑
r=−∞
x[n + 4r]
Transformada Discreta de Fourier 15
Amostragem da DTFT - Exemplo
x[n] = (7/10)nu[n]⇔ X(ejω) = [1− (7/10)e−jω]−1
Amostrando a DTFT com N = 4 pontos, a sequencia no domınio dotempo fica (em preto: amostras de x[n], em vermelho: amostras de x[n]):
0 1 2 30
0.5
1
1.5
0 1 2 3−0.4
−0.3
−0.2
−0.1
0
amostra n
x[n] =+∞∑
r=−∞
x[n + 4r]
Erro: x[n]− x[n]
Para N = 8 pontos:
0 1 2 3 4 5 6 70
0.5
1
1.5
0 1 2 3 4 5 6 7−0.08
−0.06
−0.04
−0.02
0
amostra n
x[n] =+∞∑
r=−∞
x[n + 8r]
Erro: x[n]− x[n]
Transformada Discreta de Fourier 16
DTFT de Sinais Periodicos
Um sinal periodico x[n] pode ser representado por sua DFS:
x[n] =1
N
N−1∑
k=0
X [k]ej2π
Nkn
Usando as propriedades da DTFT:
x[n]DTFT←→ X(ejω)
x[n] · ejω0n DTFT←→ X(ej(ω−ω0))
1DTFT←→ 2πδ(ω), 0− ≤ ω < 2π (um perıodo)
1 · ejω0n DTFT←→ 2πδ(ω − ω0), 0− ≤ ω < 2π
Logo, a DTFT do sinal periodico, representado por uma soma de expo-nenciais complexas, fica:
x[n] =1
N
N−1∑
k=0
X [k]ej2π
Nkn DTFT
←→2π
N
N−1∑
k=0
X [k]δ
(
ω −2π
Nk
)
, 0− ≤ ω < 2π
Na pratica, a informacao contida no espectro da DTFT e a mesma daDFS de um sinal periodico, a menos de uma constante (2π/N) e a substi-
tuicao das amostras para cada k (X[k]) pelos impulsos nas frequencias2πk/N , com areas (2π/N)X[k].
...
...
...
...
...
...
0 1
0 1
0 2p 2p
2p( -1)
n
k
ω
NN
N
NN
NN
−1
−1
x[n], x[n]
X(ejω)
X [k]
Transformada Discreta de Fourier 17
Propriedades da DFS
Sequencias x[n] e y[n], e suas series, de perıodo N .
Propriedade Sequencia DFS, perıodo N
Linearidade ax[n] + by[n] aX [k] + bY [k]
Atraso no tempo x[n−m] e−j(2π/N)kmX [k]
Deslocamento em frequencia ej(2π/N)k0nx[n] X [k − k0]
Dualidade X [n] Nx[−k]
Convolucao periodica y[n] =N−1∑
m=0
x[m]h[n−m] Y [k] = X [k] · H[k]
Modulacao v[n] = x[n] · w[n] V [k] =1
N
N−1∑
l=0
X [l]W [k − l]
Simetria x∗[n] X∗[−k]
x∗[−n] X∗[k]
ℜ{x[n]} Xe[k] =X [k] + X∗[−k]
2
ℑ{x[n]} Xo[k] =X [k]− X∗[−k]
2
xe[n] =x[n] + x∗[−n]
2ℜ{X [k]}
xo[n] =x[n]− x∗[−n]
2ℑ{X [k]}
x[n] real X [k] = X∗[−k]
|X [k]| = |X[−k]|
6 {X [k]} = −6 {X [−k]}
Transformada Discreta de Fourier 18
Exemplo - Convolucao periodica
Deseja-se fazer a convolucao periodica entre as sequencias:
x3[n] =N−1∑
m=0
x1[m]x2[n−m]
Nota-se que a somatoria e realizada em um perıodo apenas. Para n = 0,deve-se ter o sinal x2[0−m],e multiplica-lo por x1[m]:
Deve-se perceber que, como o sinal e periodico, deslocamentos posteri-
ores do sinal serao da forma:
e amostras que “saem” pelo lado direito “entram” pelo lado esquerdo,
quando se considera um perıodo dos sinais.Para obter os valores da saıda, deve-se multiplicar as duas sequenciase
realizar a soma das amostras em um perıodo.
Transformada Discreta de Fourier 19
Transformada Discreta de Fourier - DFT
Seja um sinal x[n] de duracao finita N :
x[n] = 0 para n < 0 e n ≥ N
Pode-se montar, com essa sequencia, uma outra, periodica, tal que:
x[n] =∞∑
r=−∞x[n+ rN ] = x[n modulo N ] = x[((n))N ]
Dessa sequencia periodica, pode-se calcular a DFS, X [k], que e periodicacom perıodo N . Para manter a dualidade entre os domınios do tempo e
frequencia, toma-se um perıodo dessa sequencia periodica e da-se o nomede X[k]:
X[k] =
X[k], k = 0, 1, ..., N − 1
0, caso contrario
de modo que:
X[k] = X[k modulo N ] = X[((k))N ]
...
...
......
x[n]
x[n]
X [k]
X [k]
DFS
DFT
n
n k
k
L− 1 N − 1
NN −N−N
0
00
0
Transformada Discreta de Fourier 20
DFT
Dessa forma, tem-se:
X[k] =
N−1∑
n=0
x[n]e−j2π
Nkn, k = 0, 1, ..., N − 1
0, caso contrario
x[n] =
1
N
N−1∑
n=0
X[k]ej2π
Nkn, n = 0, 1, ..., N − 1
0, caso contrario
x[n]DFT←→ X[k]
• Os sinais x[n] e X[k] sao ambos discretos e de duracao finita N
• Da mesma forma que antes, a DFT pode ser vista como amostras da
DTFT do sinal x[n], nas frequencias ωk = 2πk/N , k = 0..N − 1.
• Ao se trabalhar com as sequencias x[n] eX[k] e a DFT, deve-se sempre
lembrar que ha sequencias periodicas envolvidas.
• Ao se usar a DFT, deve-se trabalhar com as sequencias considerando
que estas sao periodicas e, ao final toma-se apenas um perıodo (0 ≤n ≤ N − 1, 0 ≤ k ≤ N − 1). Fora desse intervalo, considera-se que as
sequencias tem valor zero (sinais de duracao finita N).
Transformada Discreta de Fourier 21
Operacoes com (( ))N
Ao se trabalhar com a DFT, lembrar que as sequencias (de duracao finitano tempo e na frequencia) sao na verdade um perıodo das sequencias
periodicas correspondentes (x[n] e X [k]).
x[n]
n
x[n] = x[((n))5]
x[n− 2]
x[n− 2]
x[n]
n
x[n] = x[((n))5]
x[n+ 2]
x[n + 2]
Transformada Discreta de Fourier 22
Operacoes com (( ))N
x[n]
n
x[n] = x[((n))5]
x[−n]
x[−n]
x[−n− 2]
n
x[−n − 2]
x[−n + 2]
x[−n + 2]
Transformada Discreta de Fourier 23
Propriedades da DFT
Sequencias x[n], y[n], X[k] e Y [k] (etc.) com comprimento N (iguais a zero
para n < 0 e n ≥ N).
Propriedade Sequencia DFT N pontos
Linearidade ax[n] + by[n] aX [k] + bY [k]
Atraso no tempo x[((n− nd))N ] e−j(2π/N)kndX [k]
Deslocamento em freq. ej(2π/N)k0nx[n] X [((k − k0))N ]
Dualidade X [n] Nx[((−k))N ]
Convolucao circular y[n] = x[n](N)h[n]
=N−1∑
m=0
x[m]h[((n−m))N ] Y [k] = X [k] ·H [k]
Janelamento v[n] = x[n] · w[n] V [k] =1
N
N−1∑
l=0
X [l]W [((k − l))N ]
Simetria x∗[n] X∗[((−k))N ]
x∗[((−n))N ] X∗[k]
ℜ{x[n]} Xep[k] =X [((k))N ] +X∗[((−k))N ]
2
ℑ{x[n]} Xop[k] =X [((k))N ]−X∗[((−k))N ]
2
xep[k] =x[((n))N ] + x∗[((−n))N ]
2ℜ{X [k]}
xop[k] =x[((n))N ]− x∗[((−n))N ]
2ℑ{X [k]}
x[n] real X [k] = X∗[((−k))N ]
|X [k]| = |X [((−k))N ]|
6 {X [k]} = −6 {X [((−k))N ]}
Transformada Discreta de Fourier 24
Convolucao Linear Usando a DFT
• Em SLITs, a saıda e obtida pela convolucao linear entre a entrada e
a resposta impulsiva
• A operacao de convolucao pode ser muito custosa (somas e multi-plicacoes)
• Quando se usa a DFT, tem-se a convolucao circular
• Existem algoritmos eficientes para o calculo da DFT (FFT)
• Como usar a DFT para implementar a convolucao linear?
Para fazer a convolucao linear entre duas sequencias x1[n] e x2[n] (DTFT):
y[n] = x[n] ∗ h[n] =∞∑
k=−∞
x[k]h[n− k]↔ Y (ejω) = X(ejω) ·H(ejω)
Usando-se a DFT, tem-se a convolucao circular:
yp[n] = x[n](N)h[n]↔ Y [k] = X[k] ·H[k]
Questao: Sob que condicoes yp[n] = y[n] ?
Transformada Discreta de Fourier 25
Convolucao Linear Usando a DFT
Sejam duas sequencias:
• x[n] de comprimento L
• h[n] de comprimento M
O resultado da convolucao linear entre x[n] e h[n] tera comprimento
L+M − 1
n
x[n]
h[n]
x[n] ∗ h[n]
Transformada Discreta de Fourier 26
Convolucao Linear Usando a DFT
Vimos que se um sinal de duracao finita x[n] tem DTFTX(ejω), as amostras
de X(ejω) nas frequencia ωk = 2πk/N formam um perıodo de uma DFScuja sequencia e:
x[n] = x[((n))N ] =∞∑
r=−∞x[n+ rN ]
e
X[k] =
X(ej(2πk/N)), k = 0..N − 1
0, caso contrario
e a DFT de um perıodo de x[n]:
x[n] =
x[n], n = 0..N − 1
0, caso contrario
Note que, se o comprimento de x[n] for menor ou igual a N , nao havera
sobreposicao no tempo, e um perıodo de x[n] sera igual a x[n].
Transformada Discreta de Fourier 27
Convolucao Linear Usando a DFT
No caso da convolucao linear, tem-se:
y[n] = x[n] ∗ h[n] =∞∑
k=−∞
x[k]h[n− k]↔ Y (ejω) = X(ejω) ·H(ejω)
Definindo a DFT:
Y [k] = Y (ej(2πk/N)), k = 0..N − 1
Entao,
Y [k] = X(ej(2πk/N)) ·H(ej(2πk/N)) = X[k] ·H[k], k = 0..N − 1
E a DFT inversa de Y [k] corresponde a:
yp[n] =
∞∑
r=−∞y[n+ rN ], n = 0..N − 1
0, caso contrario
em que y[n] e a convolucao linear entre x[n] e h[n], e yp[n] e o resultado daconvolucao circular entre x[n] e h[n]:
yp[n] = x[n](N)h[n]
Ou seja, a convolucao circular entre duas sequencias pode ser vista como
a convolucao linear entre essas sequencias seguida de uma sobreposicaono tempo. Com isso, conclui-se que a convolucao circular sera igual aconvolucao linear, se e se somente se N for maior que o comprimento de
x3[n]:
N ≥ L+M − 1
Transformada Discreta de Fourier 28
Convolucao Circular
x[n]
h[n]
x[n](4)h[n]
n
x[n]
h[n]
x[n](5)h[n]
Transformada Discreta de Fourier 29
Convolucao Circular
n
x[n]
h[n]
x[n](6)h[n]
n
x[n]
h[n]
x[n](7)h[n]
Transformada Discreta de Fourier 30
Convolucao Linear Usando a DFT
Conclusao: sendo
• x[n] de comprimento L;
• h[n] de comprimento M ;
• A convolucao circular entre x[n] e h[n] e igual a convolucao linear se
N ≥ L+M − 1.
Convolucao rapida (Fast Convolution)
1. Calcular a DFT X[k], de comprimento N ≥ L+M − 1;
2. Calcular a DFT H[k], de comprimento N ;
3. Obter Y [k] = X[k] ·H[k];
4. Calcular a DFT inversa de Y [k] para obter y[n]
Nestas operacoes se utilizam algoritmos eficientes para o calculo da
DFT, que sao os algoritmos de FFT (Fast Fourier Transform).
100
101
102
103
104
101
102
103
104
105
106
107
108
flo
ps
Convolução rápidaConvolução linear
L = M (N = 2L)
Transformada Discreta de Fourier 31
Convolucao por Blocos
• Convolucao rapida: para sinais de duracao finita;
• Sistemas praticos: a entrada pode ter duracao muito grande;
• Se a resposta impulsiva tiver duracao finita, pode-se separar a en-trada em blocos de comprimento finito e utilizar a convolucao rapida,
aplicada aos blocos - linearidade da operacao de filtragem;
• O comprimento da convolucao linear entre dois sinais e maior que
a duracao de cada sinal - necessario um ajuste entre resultados deconvolucoes aplicadas a blocos adjacentes;
Transformada Discreta de Fourier 32
Overlap-Add
Neste metodo, considera-se o seguinte:
• O sistema FIR tem resposta impulsiva h[n], com comprimento M ;
• O sinal de entrada x[n] tem comprimento muito maior que M ;
• Separa-se o sinal x[n] em blocos de comprimento L, produzindo sinais
xi[n];
• Calcula-se a convolucao rapida entre xi[n] e h[n], produzindo os sinais
yi[n].
• Como visto anteriormente, a convolucao rapida deve ser realizada com
um numero de pontos N ≥ L+M−1, que e o comprimento resultantedas sequencias yi[n].
No processamento por blocos:
• Na pratica, adicionam-se zeros a xi[n] e h[n] para que atinjam o com-primento N .
• A saıda y0[n] corresponde as amostras entre 0 e N − 1;
• A saıda y1[n] corresponde as amostras entre L e L +N − 1 ;
• Ha uma sobreposicao entre y0[n] e y1[n], para L ≤ n ≤ N − 1. Essasamostras devem ser somadas na resposta total;
• Ha um atraso no processamento.
Transformada Discreta de Fourier 33
Overlap-Add
...
...
(M − 1) zeros
(M − 1) zeros
(M − 1) zeros
LLL
adiciona
adiciona
M − 1
M − 1
pontos
pontos
x[n]
x0[n]
x1[n]
x2[n]
y[n]
y0[n]
y1[n]
y2[n]
xi[n] = x[n+ iL], 0 ≤ n ≤ L− 1; i = 0, 1, ...
yi[n] = DFT−1{H[k] ·Xi[k]}, N = L+M − 1
y[n] = y0[n] + y1[n− L] + y2[n− 2L] + ...
Transformada Discreta de Fourier 34
Overlap-Add - Exemplo
1
1
1
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
1
1
1
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
...
...
M = 4, L = 5, N = 8h[n]
x[n]
n
n
n
n
n
n
n
n
n
x0[n]
x1[n]
x2[n]
y[n]
y0[n]
y1[n]
y2[n]
Transformada Discreta de Fourier 35
Overlap-Save
Neste metodo, se faz a sobreposicao dos blocos de entrada, de modo que
nao seja necessario adicionar saıdas adjacentes.
• Separa-se a entrada x[n] em sequencias de comprimento L = N > M ;
• Calcula-se a DFT com comprimento N ;
• O comprimento de h[n] e igual a M < L, e adicionam-se N −M zerospara que fique com comprimento N ;
• Faz-se uma sobreposicao das entradas, em que as M − 1 ultimasamostras de xi[n] serao as M − 1 primeiras amostras de xi+1[n].
• A sequencia x0[n] e montada com zeros nas primeiras M −1 amostrase depois com as L− (M − 1) primeiras amostras de x[n].
• A convolucao circular entre h[n] e xi[n] (yi[n]) tera valores diferentes
da convolucao linear nas M − 1 primeiras amostras. Essas M − 1primeiras amostras de yi[n] sao descartadas;
Transformada Discreta de Fourier 36
Overlap-Save
...
...
...
(M − 1)
(M − 1)
(M − 1)
zeros
LLL− (M − 1)
descarta
sobreposicao
pontos
pontos
x[n]
x0[n]
x1[n]
x2[n]
y[n]
y0[n]
y1[n]
y2[n]
xi[n] = x[n+ iL− i(M − 1)− (M − 1)], 0 ≤ n ≤ L− 1, i > 0
x0[n] =
0, 0 ≤ n ≤M − 2x[n], M − 1 ≤ n < L− (M − 1)
yi[n] = DFT−1{H[k] ·Xi[k]}, N = L, 0 ≤ n ≤ L− 1
yli[n] = yi[n], M − 1 ≤ n < L− 1
y[n] =+∞∑
i=0
yli[n− iL− i(M − 1)− (M − 1)]
Transformada Discreta de Fourier 37
Overlap-Save - Exemplo
1
1
1
1
1
1
1
1 1
2
2
2
2
2
2 2
3
3
3
3
3
3
4
4
4
4
4 4
3
1
1
1
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
...
...
M = 4, L = N = 8h[n]
x[n]
n
n
n
n
n
n
n
n
n
x0[n]
x1[n]
x2[n]
y[n]
y0[n]
y1[n]
y2[n]