Grupo4 - FFT: mudanças entre as edições

De Física Computacional
Ir para navegação Ir para pesquisar
Sem resumo de edição
Sem resumo de edição
Linha 70: Linha 70:
Com essas 4 medidas, podemos dividir a soma 2 vezes:
Com essas 4 medidas, podemos dividir a soma 2 vezes:


<math>A = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math>
<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math>


<math>A = \sum_{t_1=0}^1 a_{2t_1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1} + C_k^1\sum_{t_1=0}^1 a_{2t_1+1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1}</math>
<math>A_k = \sum_{t_1=0}^1 a_{2t_1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1} + C_k^1\sum_{t_1=0}^1 a_{2t_1+1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1}</math>


<math>A = \sum_{t_2=0}^0 a_{4t_2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^2\sum_{t_2=0}^0 a_{4t_2+2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^1\sum_{t_2=0}^0 a_{4t_2+1} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^3\sum_{t_2=0}^0 a_{4t_2+3} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2}</math>
<math>A_k = \sum_{t_2=0}^0 a_{4t_2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^2\sum_{t_2=0}^0 a_{4t_2+2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^1\sum_{t_2=0}^0 a_{4t_2+1} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^3\sum_{t_2=0}^0 a_{4t_2+3} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2}</math>


e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular
e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular

Edição das 21h02min de 23 de outubro de 2017

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.