Grupo4 - FFT

De Física Computacional
Revisão de 21h21min de 23 de outubro de 2017 por Csdionatan (discussão | contribs)
Ir para navegação Ir para pesquisar

A Transformada rápida de Fourier (em inglês Fast Fourier Transform, ou FFT) é um algoritmo que torna o cálculo da Transformada Discreta de Fourier (DFT) viável para a maior parte das aplicações.


Transformada Discreta de Fourier

Em muitas aplicações se tem informação sobre um conjunto de dados, ao invés de uma função contínua. A Transformada Discreta de Fourier transforma esse conjunto de dados em um conjunto de tamanho igual com informação sobre as frequências da função que satisfaz o conjunto de dados.

Para um conjunto de dados igualmente espaçados, pode-se, ao considerar os dados como um período de uma função periódica, cujo período normalmente é considerado entre para facilitar o cálculo (e que pode sempre ser transformada em uma função nesse interválo), mostrar que a transformada discreta de Fourier pode ser dada pela equação:

A sua inversa é, em paralelo ao caso da transformada contínua,

A transformada também pode ser expressa em forma vetorial, como

onde é definido como

O cálculo dessa expressão leva em torno de passos para o resultado. Uma amostra com 3,000 pontos precisa de 9,000,000 operações para a transformada ser obtida, tornando a DFT inviável para aplicações rápidas.


Transformada Rápida de Fourier

É possível calcular a transformada com passos. Para isso se dispõe de um algoritmo chamado Transformada Rápida de Fourier. Considera-se um conjunto de pontos (com inteiro, então, da definição da DFT

podemos dividir o somatório em 2:

onde a soma em vermelho é a parte par e a soma em azul é a parte ímpar da transformada. As duas somas tem o mesmo expoente, que agora é dividido por . Desse expoente, é evidente a relação entre o ponto e o ponto

Com essa relação, podemos ver que e tem o mesmo expoente e podem ser calculadas ao mesmo tempo. Mais que isso, a nova forma da transformada pode ser sucessivamente dividida, cada vez produzindo somas com limites menores.


Exemplo

Suponha que temos a função sinusoidal e fazemos quatro medidas no intervalo de 1 segundo, resultando em

Com essas 4 medidas, podemos dividir a soma 2 vezes:

e como temos podemos calcular

FFT para N diferente de uma potência de 2

Mesmo com a FFT sendo um algoritmo extremamente eficiente para , esse dificilmente é o caso que encotramos. Ainda assim, para altamente composto () o algoritmo ainda resulta em uma boa queda no tempo de cálculo.

Para o caso mais simples a transformada pode ser escrita como

onde , e

, e

assim a transformada que antes necessitava de N calculos, agora pode ser vista como calculos