Transformada rápida de Fourier

A Transformada rápida de Fourier (em inglês fast Fourier transform, ou FFT) é um algoritmo eficiente para se calcular a Transformada discreta de Fourier (DFT) e a sua inversa. As Transformadas rápidas de Fourier são de grande importância em uma vasta gama de aplicações, de Processamento digital de sinais para a resolução de equações diferenciais parciais a algoritmos para multiplicação de grandes inteiros.

Algoritmo FFT

O algoritmo baseia-se no chamado método de dobramentos sucessivos, onde podemos expressar a transformada de Fourier como sendo

$F(u) = \frac{1}{N} \sum_{x=0}^{N-1} f(x) W_N^{ux}\,\!$

onde

$W_N^{ux} = e^{-j2\pi/N}\,\!$.

Assumimos que $N = 2^n\,\!$ onde $n\,\!$ é um inteiro positivo.

Portanto, $N\,\!$ pode ser escrito como $N = 2M\,\!$ onde $M\,\!$ é um inteiro positivo.

Logo, a transformada de Fourier escrita inicialmente, pode ser reescrita como

$F(u) = \frac{1}{2M} \sum_{x=0}^{2M-1} f(x) W_{2M}^{ux}\,\!$

A soma escrita acima pode ser separada em duas, da seguinte maneira

$F(u) = \frac{1}{2}\left[ \frac{1}{M} \sum_{x=0}^{M-1} f(2x) W_M^{u(2x)} + \frac{1}{M} \sum_{x=0}^{M-1} f(2x+1) W_{2M}^{u(2x+1)} \right] \,\!$

Considerando que $W_{2M}^{2ux} = W_M^{ux}$, nomeamos a primeira soma por

$F_{par}(u) = \frac{1}{M} \sum_{x=0}^{M-1} f(2x) W_M^{ux} \,\!$ para valores de $u=0,1,2, ... , M-1\,\!$, e

E a segunda soma por

$F_{impar}(u) = \frac{1}{M} \sum_{x=0}^{M-1} f(2x+1) W_{2M}^{ux} \,\!$ para valores de $u=0,1,2, ... , M-1\,\!$

Podemos reescrever a transformada de Fourier como sendo

$F(u) = F_{par}(u) + F_{impar}(u)W_{2M}^u \,\!$

Uma vez que $W_M^{u+M} = W_M^u\,\!$ e $W_{2M}^{u+M} = - W_{2M}^u\,\!$.

A recombinação da equação $F_{par}(u)\,\!$ com a última nos fornece

$F(u+M) = F_{par}(u) - F_{impar}(u)W_{2M}^u \,\!$

A observação dessas equações nos fornece suas propriedades. Dentre elas vemos:

• Uma transformada de $N\,\!$ pontos pode ser computada pela divisão da expressão original em duas partes.

Ligações externas

• Multiplicando inteiros com Fast Fourier Transform