Transformada Rápida de Fourier

  • View
    225

  • Download
    10

Embed Size (px)

Text of Transformada Rápida de Fourier

  • Transformada Rapida de Fourier

    L. S. Sousa, M. B. Rodrigues

    Instituto Federal do Ceara

    lucasssousa10@gmail.com, murillobarata1@gmail.com

    December 9, 2013

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 1 / 48

  • Indice

    1 Conceitos BasicosSeries de FourierTransformada de FourierRepresentacao de Sinais

    2 Razes Complexas da Unidade3 Transformada Discreta de Fourier

    Definicao4 Transformada Rapida de Fourier

    IntroducaoAlgoritmo de Cooley-TukeyPasso-a-PassoAnalise da Complexidade ParcialContinuando com a melhoriaAnalise da ComplexidadeBorboletaAlgoritmo de Cooley-TukeyReferencias e Agradecimentos

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 2 / 48

  • Series de Fourier

    Figure: Jean Baptiste Joseph Fourier

    Series de Fourier

    Qualquer funcao periodica, por mais complicada que seja, pode serdecomposta a partir de uma soma de senos e cossenos

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 3 / 48

  • Series de Fourier

    Series de Fourier

    Uma serie de fourier decompoe funcoes periodicas ou sinais periodicos paraa soma de um conjunto, possivelmente finito, de funcoes simples deoscilacao(Senos e Cossenos). (Wikipedia)

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 4 / 48

  • Series de Fourier

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 5 / 48

  • Transformada de Fourier

    A Transformada de Fourier e deduzida atraves das Series deFourier.

    E utilizada para mudar o domnio de uma Representacao de Sinal.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 6 / 48

  • Representacao de Sinais

    Um sinal, naturalmente, e representado no domnio do tempo.

    Exibe um grupo de caractersticas do sinal.

    Figure: Sinal no domnio do tempo

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 7 / 48

  • Representacao de Sinais

    Para que algumas caractersticas do sinal sejam exibidas, e necessarioque ele esteja no Domnio da Frequencia.

    Exibe outro grupo de caractersticas do sinal.

    Figure: Sinal no domnio da frequencia.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 8 / 48

  • Razes Complexas da Unidade

    Uma n-esima raiz complexa da unidade e um numero W tal que:

    W n = 1

    Existem exatamente n razes n-esimas complexas da unidade, que sao:

    e2piikn , para k = 0, 1, ..., n-1

    e iu = cos(u) + isen(u)

    O valor Wn = e2piin e a principal raz complexa da unidade, assim:

    W 0n , W1n , W

    2n , ..., W

    n1n . Sao as n razes da unidade.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 9 / 48

  • Razes Complexas da Unidade

    Formam o grupo aditivo (Zn, +) modulo n.W nn = W

    0n = 1

    W jnW kn = Wj+kn = W

    (j+k)mod(n)n

    W1n = W n1n

    Figure: Raizes Complexas n = 8

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 10 / 48

  • Transformada Discreta de Fourier

    Considere a sequencia x[n] que e periodica em tempo T, ou seja.

    x [n] = x [n + rT ], rZ (1)

    Tal sequencia pode ser representada por uma serie de Fourier,correspondendo a` soma de sequencias exponenciais relacionadasharmonicamente.

    x [n] =1

    N

    m

    X [m]ei2pimn

    N (2)

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 11 / 48

  • Transformada Discreta de Fourier

    A representacao em serie de Fourier de um sinal periodico contnuono tempo, geralmente, precisa de infinitas exponenciais complexas.

    No entanto, a Serie de Fourier para qualquer sinal discreto no tempocom perodo N requer apenas N exponenciais complexas ja que elassao periodicas.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 12 / 48

  • Transformada Discreta de Fourier

    Assim, a representacao torna-se:

    x [n] =1

    N

    N1m=0

    X [m]ei2pimn

    N (3)

    E os coeficientes da serie de Fourier X[m] sao obtidos a partir de x[n]pela relacao.

    X [m] =N1n=0

    x [n]ei2pimn

    N (4)

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 13 / 48

  • Transformada Discreta de Fourier

    Se fizermos Wn = ei( 2pi

    N) Temos que:

    Equacao de Analise:

    X [k] =N1n=0

    x [n]W knN(DFT )

    (5)

    Equacao de Sntese:

    X [k] =1

    N

    N1k=0

    X [k]WknN(IDFT )

    (6)

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 14 / 48

  • Transformada Discreta de Fourier

    Alta complexidade computacional com custo assintotico de O(n2)

    Para diminuir essa complexidade, e proposto o uso da TransformadaRapida de Fourier.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 15 / 48

  • Introducao

    Algoritmo criado em 1965

    Autores: J.W. Cooley(IBM) e J.W. Tukey(Bell Labs)

    Dividir a subsequencia x[n] em duas sequencias.

    Decimacao em Tempo

    Algoritmos no qual a sequencia e decomposta sucessivamente emsequencias menores.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 16 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 17 / 48

  • Algoritmo de Cooley-Tukey

    X (k) =nPar

    x [n]W nkN +

    nImpar

    x [n]W nkN (7)

    Fazendo n = 2r e n = 2r + 1, temos que:

    X (k) =

    N/21r=0

    x [2r ]W 2rkN +

    N/21r=0

    x [2r + 1]W(2r+1)kN (8)

    X (k) =

    N/21r=0

    x [2r ](W 2N)rk

    + W kN

    N/21r=0

    x [2r + 1](W 2N)rk

    (9)

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 18 / 48

  • Algoritmo de Cooley-Tukey

    Mas W 2N = WN/2 ja que:

    W 2N = e2i( 2pi

    N) = e

    2i( pi(N/2)

    )= WN/2

    Logo (9) pode ser reescrito como:

    X (k) =

    N/21r=0

    x [2r ]W rkN/2 + WkN

    N/21r=0

    x [2r + 1]W rkN/2 (10)

    X (k) = G [k] + W kNH[k] (11)

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 19 / 48

  • Algoritmo de Cooley-Tukey

    Cada parcela da equacao (11) e uma DFT de N/2 pontos:

    G[k] e H[k]

    No caso de uma DFT de 8 pontos, o resultado da decimacao notempo gera o seguinte diagrama de fluxo.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 20 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 21 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 22 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 23 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 24 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 25 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 26 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 27 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 28 / 48

  • Algoritmo de Cooley-Tukey

    Figure: Algoritmo de Cooley-Tukey

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 29 / 48

  • Complexidade

    Analise de Complexidade:

    DFT Classica

    N2 Multiplicacoes complexas e adicoes.

    Cooley-Tukey

    X (k) = G [k] + W kNH[k]

    G [k] e H[k] sao duas DFTs de N/2 pontos, portanto, ambas realizam(N/2)2 operacoes.

    A multiplicacao W kNH[k] e realizada N vezes.

    Assim, o custo do algoritmo de Cooley-Tukey e 2(N/2)2 + N.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 30 / 48

  • Complexidade

    Assim, usando o algoritmo de Cooley-Tukey, para N > 2, temos umacomplexidade menor do que usando o algoritmo de DFT classico.

    Ainda podemos melhorar a complexidade se aplicarmos novamente aideia de divisao de Cooley-Tukey.

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 31 / 48

  • Complexidade

    Figure: DivisaoL. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 32 / 48

  • Algoritmo de Cooley-Tukey

    Se N e potencia de 2, podemos dividir novamente o conjunto dedados:

    G [k] =

    N/41l=0

    g [2l ]W lkN/4 + WkN/2

    N/41l=0

    g [2l + 1]W lkN/4 (12)

    H[k] =

    N/41l=0

    h[2l ]W lkN/4 + WkN/2

    N/41l=0

    h[2l + 1]W lkN/4 (13)

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 33 / 48

  • Algoritmo de Cooley-Tukey

    G[k] = [ x[0], x[2], x[4], x[6] ], tal quex[0] = 0, x[2] = 1, x[4] = 2, x[6] = 3

    Figure: Divisao

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 34 / 48

  • Algoritmo de Cooley-Tukey

    G[k] = [ x[0], x[2], x[4], x[6] ], tal quex[0] = 0, x[2] = 1, x[4] = 2, x[6] = 3

    Figure: Divisao

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 35 / 48

  • Algoritmo de Cooley-Tukey

    G[k] = [ x[0], x[2], x[4], x[6] ], tal quex[0] = 0, x[2] = 1, x[4] = 2, x[6] = 3

    Figure: Divisao

    L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 36 / 48

  • Algoritmo de Cooley-Tukey

    G[k] = [ x[0], x[2], x[4], x[6] ], tal quex[0] = 0, x[2] = 1, x[4] = 2, x[6] = 3

    Figure: Divisao

    L. S. Sousa, M. B. Rodr