Transformada Discreta de Fourier

ENGC33: Sinais e Sistemas II

Departamento de Engenharia Eletrica - DEEUniversidade Federal da Bahia - UFBA

05 de abril de 2017

Prof. Tito Luís Maia Santos 1/ 25

Sumario

1 Introducao

2 Revisao

3 Representacao de sinais limitados no tempo

4 Transformada rapida de Fourier

5 Transformada de Fourier de tempo discreto (limitado no tempo)

6 Comentarios Finais

Prof. Tito Luís Maia Santos 2/ 25

Sumario

1 Introducao

2 Revisao

3 Representacao de sinais limitados no tempo

4 Transformada rapida de Fourier

5 Transformada de Fourier de tempo discreto (limitado no tempo)

6 Comentarios Finais

Prof. Tito Luís Maia Santos 3/ 25

Introducao

Objetivos da aula de hoje:

Apresentar a transformada de Fourier rapida (FFT).

Discutir exemplos praticos de aplicacao.

Prof. Tito Luís Maia Santos 4/ 25

Sumario

1 Introducao

2 Revisao

3 Representacao de sinais limitados no tempo

4 Transformada rapida de Fourier

5 Transformada de Fourier de tempo discreto (limitado no tempo)

6 Comentarios Finais

Prof. Tito Luís Maia Santos 5/ 25

RevisaoTransformada e Serie de Fourier em tempo discreto

Serie de Fourier em tempo discreto (SFTD):

x [n] =∑

k=〈N〉

ak ejk(2π/N)n,

ak =1

N

∑

n=〈N〉

x [n]e−jk(2π/N)n.

Transformada de Fourier em tempo discreto (TFTD):

x [n] =1

2π

∫

2π

X(ejΩ)ejΩndΩ

X(ejΩ) =

∞∑

n=−∞

x [n]e−jΩn.

E realmente necessario considerar N → ∞ para um sinal de tempofinito?

Prof. Tito Luís Maia Santos 6/ 25

RevisaoTransformada e Serie de Fourier em tempo discreto

Serie de Fourier em tempo discreto (SFTD):

x [n] =∑

k=〈N〉

ak ejk(2π/N)n,

ak =1

N

∑

n=〈N〉

x [n]e−jk(2π/N)n.

Transformada de Fourier em tempo discreto (TFTD):

x [n] =1

2π

∫

2π

X(ejΩ)ejΩndΩ

X(ejΩ) =

∞∑

n=−∞

x [n]e−jΩn.

E realmente necessario considerar N → ∞ para um sinal de tempofinito?

Prof. Tito Luís Maia Santos 6/ 25

Sumario

1 Introducao

2 Revisao

3 Representacao de sinais limitados no tempo

4 Transformada rapida de Fourier

5 Transformada de Fourier de tempo discreto (limitado no tempo)

6 Comentarios Finais

Prof. Tito Luís Maia Santos 7/ 25

RevisaoFormulacao via sinal periodico

Seja x [n] um sinal periodico e x [n] limitado no tempo.

0N−1

0N−1

x[n]

x [n]

Prof. Tito Luís Maia Santos 8/ 25

Representacao de sinais limitados no tempoObtencao da Transformada discreta de Fourier (sinais limitados no tempo)

Como x [n] e periodico, temos:

x [n] =∑

k=〈N〉

ak ejk(2π/N)n,

ak =1

N

∑

n=〈N〉

x [n]e−jk(2π/N)n.

Por conveniencia escolheremos n = 〈N〉 de maneira que

ak =1

N

N−1∑

n=0

x [n]e−jk(2π/N)n.

Para o intervalo em questao, x [n] = x [n], entao

ak =1

N

N−1∑

n=0

x [n]e−jk(2π/N)n = X [k ].

Prof. Tito Luís Maia Santos 9/ 25

Pares de transformadaTransformada e Serie de Fourier

Serie de Fourier em tempo discreto (SFTD):

x [n] =∑

k=〈N〉

ak ejk(2π/N)n ⇐⇒ ak =1

N

∑

n=〈N〉

x [n]e−jk(2π/N)n.

Transformada de Fourier em tempo discreto (TFTD):

x [n] =1

2π

∫

2π

X(ejΩ)ejΩndΩ ⇐⇒ X(ejΩ) =

∞∑

n=−∞

x [n]e−jΩn.

Transformada Discreta de Fourier (TDF) para 0 ≤ n ≤ N − 1:

x [n] =N−1∑

k=0

X [k ]ejk(2π/N)n ⇐⇒ X [k ] =1

N

N−1∑

n=0

x [n]e−jk(2π/N)n.

Prof. Tito Luís Maia Santos 10/ 25

Pares de transformadaTransformada e Serie de Fourier em tempo discreto

Serie de Fourier em tempo discreto (SFTD):

x [n] =∑

k=〈N〉

ak ejk(2π/N)n ⇐⇒ ak =1

N

∑

n=〈N〉

x [n]e−jk(2π/N)n.

Transformada de Fourier em tempo discreto (TFTD):

x [n] =1

2π

∫

2π

X(ejΩ)ejΩndΩ ⇐⇒ X(ejΩ) =

∞∑

n=−∞

x [n]e−jΩn.

Transformada Discreta de Fourier (TDF) para 0 ≤ n ≤ N − 1:

Nx [n] =N−1∑

k=0

NX [k ]ejk(2π/N)n ⇐⇒ NX [k ] =N

N

N−1∑

n=0

x [n]e−jk(2π/N)n.

Prof. Tito Luís Maia Santos 11/ 25

Pares de transformadaTransformada e Serie de Fourier em tempo discreto

Serie de Fourier em tempo discreto (SFTD):

x [n] =∑

k=〈N〉

ak ejk(2π/N)n ⇐⇒ ak =1

N

∑

n=〈N〉

x [n]e−jk(2π/N)n.

Transformada de Fourier em tempo discreto (TFTD):

x [n] =1

2π

∫

2π

X(ejΩ)ejΩndΩ ⇐⇒ X(ejΩ) =

∞∑

n=−∞

x [n]e−jΩn.

Transformada Discreta de Fourier (TDF) para 0 ≤ n ≤ N − 1:

x [n] =1

N

N−1∑

k=0

X [k ]ejk(2π/N)n ⇐⇒ X [k ] =N−1∑

n=0

x [n]e−jk(2π/N)n.

Prof. Tito Luís Maia Santos 12/ 25

Sumario

1 Introducao

2 Revisao

3 Representacao de sinais limitados no tempo

4 Transformada rapida de Fourier

5 Transformada de Fourier de tempo discreto (limitado no tempo)

6 Comentarios Finais

Prof. Tito Luís Maia Santos 13/ 25

Transformada rapida de Fourier (FFT)Ideia principal

Considerem uma sequencia finita no tempo determinada pelo par

x [n] =1

N

N−1∑

k=0

X [k ]ejk(2π/N)n ⇐⇒ X [k ] =

N−1∑

n=0

x [n]e−jk(2π/N)n.

Para o calculo direto de X [k ] com k fixo:

N multiplicacoes complexas e N − 1 somas.

Para o calculo direto de X [k ], k = 0, 1, ...,N − 1:

N2 multiplicacoes complexas e (N − 1)N somas.

O problema pode ser reescrito como segue:

X [k ] =

N−1∑

n=0

x [n]e−jk(2π/N)n =

N−1∑

n=0

x [n]W nkN

com WN = e−j(2π/N) ⇒ WN/2 = e−j[2π/(N/2)] = e−j(4π/N) = W 2N .

Prof. Tito Luís Maia Santos 14/ 25

Transformada rapida de Fourier (FFT)Ideia principal

Considerem uma sequencia finita no tempo determinada pelo par

x [n] =1

N

N−1∑

k=0

X [k ]ejk(2π/N)n ⇐⇒ X [k ] =

N−1∑

n=0

x [n]e−jk(2π/N)n.

Para o calculo direto de X [k ] com k fixo:

N multiplicacoes complexas e N − 1 somas.

Para o calculo direto de X [k ], k = 0, 1, ...,N − 1:

N2 multiplicacoes complexas e (N − 1)N somas.

O problema pode ser reescrito como segue:

X [k ] =

N−1∑

n=0

x [n]e−jk(2π/N)n =

N−1∑

n=0

x [n]W nkN

com WN = e−j(2π/N) ⇒ WN/2 = e−j[2π/(N/2)] = e−j(4π/N) = W 2N .

Prof. Tito Luís Maia Santos 14/ 25

Transformada rapida de Fourier (FFT)Ideia principal

Considerem as seguintes sequencias x [n] =

f [n], n par;g[n], n ımpar.

sendo f [n] = x [2n] → x [0], x [2], ...x [N − 2] e

g[n] = x [2n + 1] → x [1], x [3], ...x [N − 1].

Assim, pode-se dividir o problema como segue

X [k ] =N−1∑

n=0

x [n]e−jk(2π/N)n

=

N/2−1∑

n=0

x [2n]e−jk(2π/N)2n +

N/2−1∑

n=0

x [2n + 1]e−jk(2π/N)(2n+1)

=

N/2−1∑

n=0

f [n]W nkN/2 + W k

N

N/2−1∑

n=0

g[n]W nkN/2

= F [k ] + W kNG[k ]

com F [k + N/2] = F [k ] e G[k ] = G[k + N/2].

Prof. Tito Luís Maia Santos 15/ 25

Transformada rapida de Fourier (FFT)Ideia principal

Dado o problema

X [k ] =

N/2−1∑

n=0

f [n]W nkN/2 + W k

N

N/2−1∑

n=0

g[n]W nkN/2

= F [k ] + W kNG[k ]

com F [k + N/2] = F [k ] e G[k ] = G[k + N/2].

Notar que W(k+N/2)N = e(−j2π/N)(k+N/2) = e(−j2π/N)k e−jπ = −W k

N .

Assim temos para 0 ≤ k ≤ (N/2)− 1

X [k ] = F [k ] + W kNG[k ],

X [k + N/2] = F [k ]− W kNG[k ].

Repetindo o procedimento sucessivas vezes ⇒ N log2(N) adicoescomplexas e N/2 log2(N) multiplicacoes complexas.

Prof. Tito Luís Maia Santos 16/ 25

Transformada rapida de Fourier (FFT)Ideia principal

Dado o problema

X [k ] =

N/2−1∑

n=0

f [n]W nkN/2 + W k

N

N/2−1∑

n=0

g[n]W nkN/2

= F [k ] + W kNG[k ]

com F [k + N/2] = F [k ] e G[k ] = G[k + N/2].

Notar que W(k+N/2)N = e(−j2π/N)(k+N/2) = e(−j2π/N)k e−jπ = −W k

N .

Assim temos para 0 ≤ k ≤ (N/2)− 1

X [k ] = F [k ] + W kNG[k ],

X [k + N/2] = F [k ]− W kNG[k ].

Repetindo o procedimento sucessivas vezes ⇒ N log2(N) adicoescomplexas e N/2 log2(N) multiplicacoes complexas.

Prof. Tito Luís Maia Santos 16/ 25

Sumario

1 Introducao

2 Revisao

3 Representacao de sinais limitados no tempo

4 Transformada rapida de Fourier

5 Transformada de Fourier de tempo discreto (limitado no tempo)

6 Comentarios Finais

Prof. Tito Luís Maia Santos 17/ 25

Transformada de Fourier de tempo discreto (N < ∞)Formulacao via sinal periodico

0−N1

N1 N−N

0−N1

N1

x[n]

x[n]

Podemos considerar

x [n] = x [n]rectN1[n],

sendo

rectN1[n] ,

1, |n| ≤ N1

0, |n| > N1

Prof. Tito Luís Maia Santos 18/ 25

Transformada de Fourier de tempo discreto (N < ∞)Informacoes importantes

1

x[n] = x[n]rectN1[n] = rectN1[n]x[n].

2

FrectN1[n] =sen[Ω(N1 + 0.5)]

sen(Ω/2).

3

Fx [n] = 2π∞∑

k=−∞

akδ(Ω− 2πk/N).

4

Fx1[n]x2[n] =1

2π

∫2π

X1(ejθ)X2(e

j(Ω−θ))dθ.

Prof. Tito Luís Maia Santos 19/ 25

Transformada de Fourier de tempo discreto (N < ∞)Informacoes importantes

1

x[n] = x[n]rectN1[n] = rectN1[n]x[n].

2

FrectN1[n] =sen[Ω(N1 + 0.5)]

sen(Ω/2).

3

Fx [n] = 2π∞∑

k=−∞

akδ(Ω− 2πk/N).

4

Fx1[n]x2[n] =1

2π

∫2π

X1(ejθ)X2(e

j(Ω−θ))dθ.

Prof. Tito Luís Maia Santos 19/ 25

Transformada de Fourier de tempo discreto (N < ∞)Informacoes importantes

1

x[n] = x[n]rectN1[n] = rectN1[n]x[n].

2

FrectN1[n] =sen[Ω(N1 + 0.5)]

sen(Ω/2).

3

Fx [n] = 2π∞∑

k=−∞

akδ(Ω− 2πk/N).

4

Fx1[n]x2[n] =1

2π

∫2π

X1(ejθ)X2(e

j(Ω−θ))dθ.

Prof. Tito Luís Maia Santos 19/ 25

Transformada de Fourier de tempo discreto (N < ∞)Informacoes importantes

1

x[n] = x[n]rectN1[n] = rectN1[n]x[n].

2

FrectN1[n] =sen[Ω(N1 + 0.5)]

sen(Ω/2).

3

Fx [n] = 2π∞∑

k=−∞

akδ(Ω− 2πk/N).

4

Fx1[n]x2[n] =1

2π

∫2π

X1(ejθ)X2(e

j(Ω−θ))dθ.

Prof. Tito Luís Maia Santos 19/ 25

Transformada de Fourier de tempo discreto (N < ∞)Comportamento em frequencia

Para N → ∞, temos

limN1→∞

sen[(Ω)(N1 + 0.5)]

sen[(Ω)/2]= δ(Ω).

−3 −2 −1 0 1 2 3

0

50

100

sen[Ω(N1+0.5)]/sen(Ω n/2)

N1=10

−3 −2 −1 0 1 2 3

0

50

100

N1=25

−3 −2 −1 0 1 2 3

0

50

100

Ω

N1=50

Prof. Tito Luís Maia Santos 20/ 25

ExemplosComportamento em frequencia

Calculando a FFT para um sinal do tipo x [n] = cos[(2π/10)n]truncado:

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

2

4

6

8

10

12

14

16

18

20

Prof. Tito Luís Maia Santos 21/ 25

ExemplosComportamento em frequencia

Aumentado a largura da funcao rectN1[n]:

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

10

20

30

40

50

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

10

20

30

40

50

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

10

20

30

40

50

Prof. Tito Luís Maia Santos 22/ 25

ExemplosSinal de voz

Portadora da voz humana (tipicamente 85 a 255Hz).

0 0.2 0.4 0.6 0.8 1−0.6

−0.5

−0.4

−0.3

−0.2Sinal de audio no tempo

0 500 1000 1500 2000 2500 30000

2

4

6

8x 10

−3 Sinal de audio na frequencia

Prof. Tito Luís Maia Santos 23/ 25

Sumario

1 Introducao

2 Revisao

3 Representacao de sinais limitados no tempo

4 Transformada rapida de Fourier

5 Transformada de Fourier de tempo discreto (limitado no tempo)

6 Comentarios Finais

Prof. Tito Luís Maia Santos 24/ 25

Comentarios Finais

Nesta discutiu-se sobre a transformada rapida de Fourier.

Na proxima aula discutiremos sobre:

Resposta em frequencia.

Prof. Tito Luís Maia Santos 25/ 25