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

onde

.

Assumimos que onde é um inteiro positivo.


Portanto, pode ser escrito como onde é um inteiro positivo.


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

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

Considerando que , nomeamos a primeira soma por

para valores de , e

E a segunda soma por

para valores de

Podemos reescrever a transformada de Fourier como sendo


Uma vez que e .

A recombinação da equação com a última nos fornece



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

  • Uma transformada de 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.