Grupo4 - FFT

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 $[-\pi ,\pi ]$ 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:

$F_k=\sum _{n=0}^{N-1}{f}_n{e}^{-i2\pi nk/N}$

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

$f_n=\frac{1}{N}\sum _{n=0}^{N-1}{F}_k{e}^{i2\pi nk/N}$

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

$\overrightarrow{F}=\mathbf{𝐀}\overrightarrow{f}$ onde $\mathbf{𝐀}$ é definido como

$\mathbf{𝐀}=\left[\begin{array}{cccc}{e}^{-2\pi i0\cdot 0/N}& e^{-2\pi i0\cdot 1/N}& \cdots & e^{-2\pi i0\cdot k/N}\\ e^{-2\pi i1\cdot 0/N}& e^{-2\pi i1\cdot 1/N}& \cdots & e^{-2\pi i1\cdot k/N}\\ ⋮& ⋮& \ddots & ⋮\\ e^{-2\pi in\cdot 0/N}& e^{-2\pi in\cdot 1/N}& \cdots & e^{-2\pi in\cdot k/N}\end{array}\right]$

O cálculo dessa expressão leva em torno de $N^2$ 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 $NlogN$ passos. Para isso se dispõe de um algoritmo chamado Transformada Rápida de Fourier. $F_k=\sum _{n=0}^{N-1}{f}_n\cdot e^{-i\frac{2\pi }{N}\cdot k\cdot n}$$$$$$F_k=\sum _{n=0}^{N/2-1}{f}_{2n}\cdot e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}+C(k)\sum _{n=0}^{N/2-1}{f}_{2n+1}\cdot e^{-i\frac{2\pi }{N/2}\cdot k\cdot n}$