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.

A transformada 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}$