ejω xne jωn −∞ Processamento Digital de Sinais ω€¦ · S´erie e Transformada Discreta de Fourier 15 Amostragem da DTFT Logo, ao se tomar N amostrasda DTFT de um sinal x[n],

Serie e 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.


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


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.


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 < +∞

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.


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.


Exemplo - DFS (cont.)

Outra forma de verificar o resultado e reescrevendo a sequencia x[n] emtermos 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


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 < +∞

Comparando as equacoes, tem-se que a DFS e a DTFT, nessas condicoes,

estao relacionadas por:

X[k] = X(ejω)|ω= 2π

Nk, −∞ < k < +∞

ou seja, a DFS e composta por amostras da DTFT em N pontosequiespacados de 2π/N , entre ω = 0 e 2π.


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)

-6 -4 -2 0 2 4 6 8 10 12 140

0.5

1

-2 -1 0 1 2 3 40

2

4

6

x[n], x[n]

n

|X(ejω)|, |X [k]|

ω/π, ωk/π = 2k/7


Exemplo

x[n] = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, N = 10, L = 5

X(ejω) =4∑


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)

-10 -5 0 5 10 15 20

n

0

0.5

1

-2 -1 0 1 2 3 40

2

4

6

x[n], x[n]

|X(ejω)|, |X [k]|

ω/π, ωk/π = 2k/10


Exemplo

x[n] = {1, 1, 1, 1, 1}, N = 5, L = 5

X(ejω) =4∑


sin(5ω/2)

sin(ω/2)

X[k] =4∑

n=0

e−j(2π/5)n = e−j(4π/5)ksin(πk)

sin(πk/5)

-5 0 5 10

n

0

0.5

1

-2 -1 0 1 2 3 40

2

4

6

x[n], x[n]

|X(ejω)|, |X [k]|

ω/π, ωk/π = 2k/5


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/20

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/40


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.


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

Ou seja, a DFS pode ser escrita em funcao de x[n] como:

X[k] =+∞∑

m=−∞x[m]e−j

2π

Nkm

Calculando-se a DFS inversa pode-se chegar a uma relacao entre asequencia periodica x[n] e a sequencia x[n].


Amostragem da DTFT

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 impulsos

periodico:

1

N

N−1∑

k=0

ej2π

Nk(n−m) =

+∞∑


Portanto:

x[n] =+∞∑

m=−∞x[m]

+∞∑


= x[n] ∗+∞∑

r=−∞δ[n+ rN ]

=+∞∑

r=−∞x[n+ rN ]


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).


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]


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]


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]


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]}


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.



Deseja-se fazer a convolucao periodica entre as sequencias:

......

0 1 2 3 4

0 1 2 3 4

...

...

n

n

N

N

−N

−N

x[n]

h[n]

y[n] =N−1∑

m=0

x[m]h[n−m]

Para n = 0: y[0] =N−1∑

m=0x[m]h[0−m]

0 1 2 3 4

...

...

... ...

0 1 2 3 4 m

m

N

N

−N

−N

x[m]

h[−m]



Para n = 1: y[1] =N−1∑

m=0

x[m]h[1−m]

0 1 2 3 4

...

...

... ...

0 1 2 3 4 m

m

N

N

−N

−N

x[m]

h[1−m]

Para n = 2: y[2] =N−1∑

m=0

x[m]h[2−m]

0 1 2 3 4

...

...

... ...

0 1 2 3 4 m

m

N

N

−N

−N

x[m]

h[2−m]



Para n = 3: y[3] =N−1∑

m=0

x[m]h[3−m]

0 1 2 3 4

...

...

... ...

0 1 2 3 4 m

m

N

N

−N

−N

x[m]

h[3−m]

Para n = 4: y[4] =N−1∑

m=0

x[m]h[4−m]

0 1 2 3 4

...

...

... ...

0 1 2 3 4 m

m

N

N

−N

−N

x[m]

h[4−m]


Transformada Discreta de Fourier - DFT

Seja um sinal x[n] de duracao finita N (ou de comprimento L ≤ 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 .

X[k] =N−1∑

n=0

x[n]e−j2π

Nkn.

Para manter a dualidade entre os domınios do tempo e frequencia, toma-

se um perıodo dessa sequencia periodica e da-se o nome de 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 ]

Exemplo para L = 6 e N = 8:

...

...

......

x[n]

x[n]

X [k]

X [k]

DFS

DFT

n

n k

k

L− 1 N − 1

NN −N−N

0

00

0


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]

OBSERVACOES:

• 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).


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]


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]


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 ]}


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] ?



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]



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].



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


Convolucao Circular

x[n]

h[n]

x[n](4)h[n]

n

x[n]

h[n]

x[n](5)h[n]


Convolucao Circular

n

x[n]

h[n]

x[n](6)h[n]

n

x[n]

h[n]

x[n](7)h[n]



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)


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;


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.


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] + ...


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]


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;


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

+∞∑


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]

Documents

ejω xne jωn −∞ Processamento Digital de Sinais ω€¦ · S´erie e Transformada Discreta de Fourier 15 Amostragem da DTFT Logo, ao se tomar N amostrasda DTFT de um sinal x[n],