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 105: Linha 105:


=== Algorítmo (usando recursão) ===
=== Algorítmo (usando recursão) ===
<math>\mathbf{function} ~ FFT(N,a)</math>
<math>>>\mathbf{function} ~ FFT(N,a)</math>


<math> ~~~~ \mathbf{if} ~ N = 1 ~ \mathbf{then}</math>
<math> >>> ~~~~ \mathbf{if} ~ N = 1 ~ \mathbf{then}</math>


<math> ~~~~~~~~ return ~ a;</math>
<math> >>> ~~~~~~~~ return ~ a;</math>


<math> ~~~~ \mathbf{else}</math>
<math> >>> ~~~~ \mathbf{else}</math>


<math> ~~~~~~~~ E = FFT(N/2, (a_0, a_2, ..., a_{N-2}));</math>
<math> >>>~~~~~~~~ E = FFT(N/2, (a_0, a_2, ..., a_{N-2}));</math>


<math> ~~~~~~~~ O = FFT(N/2, (a_1, a_3, ..., a_{N-1}));</math>
<math> >>>~~~~~~~~ O = FFT(N/2, (a_1, a_3, ..., a_{N-1}));</math>




<math> ~~~~~~~~ \mathbf{for} k = 0 to k <= N/2 -1 \mathbf{do}</math>
<math> >>>~~~~~~~~ \mathbf{for} ~ k = 0 ~ to ~ k <= N/2 -1 ~ \mathbf{do}</math>


<math> ~~~~~~~~~~~~ A_k=E_k+exp(-i\frac{2\pi}{N} k) * O_k;</math>
<math> >>>~~~~~~~~~~~~ A_k=E_k+exp(-i2\pi k/N) * O_k;</math>


<math> ~~~~~~~~~~~~ A_{k+N/2}=E_k-exp(-i\frac{2\pi}{N} k) * O_k;</math>
<math> >>>~~~~~~~~~~~~ A_{k+N/2}=E_k-exp(-i2\pi k/N) * O_k;</math>

Edição das 22h25min de 23 de outubro de 2017

A Transformada rápida de Fourier (em inglês Fast Fourier Transform, ou FFT) é um algoritmo que torna viável o cálculo da Transformada Discreta de Fourier (DFT), que é a forma discretizada da [Transformada de Fourier]. A FFT permite transformar de forma rápida uma série de sinais discretos em uma amostra contendo as frequências desses sinais, desde que satisfaça algumas propriedades.


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

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

Algorítmo (usando recursão)