Transformada rápida de Fourier

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.