Transformada Discreta de Fourier - .Transformada Discreta de Fourier ENGC33: Sinais e Sistemas II

  • View
    212

  • Download
    0

Embed Size (px)

Text of Transformada Discreta de Fourier - .Transformada Discreta de Fourier ENGC33: Sinais e Sistemas II

  • 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 Lus 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 Lus 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 Lus Maia Santos 3/ 25

  • Introducao

    Objetivos da aula de hoje:

    Apresentar a transformada de Fourier rapida (FFT).

    Discutir exemplos praticos de aplicacao.

    Prof. Tito Lus 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 Lus 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]ejk(2/N)n.

    Transformada de Fourier em tempo discreto (TFTD):

    x [n] =1

    2

    2

    X(ej)ejnd

    X(ej) =

    n=

    x [n]ejn.

    E realmente necessario considerar N para um sinal de tempofinito?

    Prof. Tito Lus 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]ejk(2/N)n.

    Transformada de Fourier em tempo discreto (TFTD):

    x [n] =1

    2

    2

    X(ej)ejnd

    X(ej) =

    n=

    x [n]ejn.

    E realmente necessario considerar N para um sinal de tempofinito?

    Prof. Tito Lus 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 Lus Maia Santos 7/ 25

  • RevisaoFormulacao via sinal periodico

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

    0N1

    0N1

    x[n]

    x [n]

    Prof. Tito Lus 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]ejk(2/N)n.

    Por conveniencia escolheremos n = N de maneira que

    ak =1

    N

    N1

    n=0

    x [n]ejk(2/N)n.

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

    ak =1

    N

    N1

    n=0

    x [n]ejk(2/N)n = X [k ].

    Prof. Tito Lus 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]ejk(2/N)n.

    Transformada de Fourier em tempo discreto (TFTD):

    x [n] =1

    2

    2

    X(ej)ejnd X(ej) =

    n=

    x [n]ejn.

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

    x [n] =N1

    k=0

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

    N

    N1

    n=0

    x [n]ejk(2/N)n.

    Prof. Tito Lus 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]ejk(2/N)n.

    Transformada de Fourier em tempo discreto (TFTD):

    x [n] =1

    2

    2

    X(ej)ejnd X(ej) =

    n=

    x [n]ejn.

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

    Nx [n] =N1

    k=0

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

    N

    N1

    n=0

    x [n]ejk(2/N)n.

    Prof. Tito Lus 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]ejk(2/N)n.

    Transformada de Fourier em tempo discreto (TFTD):

    x [n] =1

    2

    2

    X(ej)ejnd X(ej) =

    n=

    x [n]ejn.

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

    x [n] =1

    N

    N1

    k=0

    X [k ]ejk(2/N)n X [k ] =N1

    n=0

    x [n]ejk(2/N)n.

    Prof. Tito Lus 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 Lus Maia Santos 13/ 25

  • Transformada rapida de Fourier (FFT)Ideia principal

    Considerem uma sequencia finita no tempo determinada pelo par

    x [n] =1

    N

    N1

    k=0

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

    N1

    n=0

    x [n]ejk(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 ] =

    N1

    n=0

    x [n]ejk(2/N)n =

    N1

    n=0

    x [n]W nkN

    com WN = ej(2/N) WN/2 = e

    j[2/(N/2)] = ej(4/N) = W 2N .

    Prof. Tito Lus Maia Santos 14/ 25

  • Transformada rapida de Fourier (FFT)Ideia principal

    Considerem uma sequencia finita no tempo determinada pelo par

    x [n] =1

    N

    N1

    k=0

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

    N1

    n=0

    x [n]ejk(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 ] =

    N1

    n=0

    x [n]ejk(2/N)n =

    N1

    n=0

    x [n]W nkN

    com WN = ej(2/N) WN/2 = e

    j[2/(N/2)] = ej(4/N) = W 2N .

    Prof. Tito Lus 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]} eg[n] = x [2n + 1] {x [1], x [3], ...x [N 1]}.

    Assim, pode-se dividir o problema como segue

    X [k ] =N1

    n=0

    x [n]ejk(2/N)n

    =

    N/21

    n=0

    x [2n]ejk(2/N)2n +

    N/21

    n=0

    x [2n + 1]ejk(2/N)(2n+1)

    =

    N/21

    n=0

    f [n]W nkN/2 + WkN

    N/21

    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 Lus Maia Santos 15/ 25

  • Transformada rapida de Fourier (FFT)Ideia principal

    Dado o problema

    X [k ] =

    N/21

    n=0

    f [n]W nkN/2 + WkN

    N/21

    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 ej = W kN .

    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 Lus Maia Santos 16/ 25

  • Transformada rapida de Fourier (FFT)Ideia principal

    Dado o problema

    X [k ] =

    N/21

    n=0

    f [n]W nkN/2 + WkN

    N/21

    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 ej = W kN .

    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 Lus 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 Lus Maia Santos 17/ 25

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

    0N1

    N1 NN

    0N1

    N1

    x[n]

    x[n]

    Podemos considerar

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

    sendo

    rectN1[n] ,

    {

    1, |n| N10, |n| > N1

    Prof. Tito Lus 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

    F{rectN1[n]} =sen[(N1 + 0.5)]

    sen(/2).

    3

    F{x [n]} = 2

    k=

    ak( 2k/N).

    4

    F{x1[n]x2[n]} =1

    2

    2

    X1(ej)X2(e

    j())d.

    Prof. Tito Lus 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

    F{rectN1[n]} =sen[(N1 + 0.5)]

    sen(/2).

    3

    F{x [n]} = 2

    k=

    ak( 2k/N).

    4

    F{x1[n]x2[n]} =1

    2

    2

    X1(ej)X2(e

    j())d.

    Prof. Tito Lus Maia Santos 19/ 25

  • Transformada de Fourier de tempo discreto (N < )Informacoes