Transformada rápida de Fourier
De Wikipedia, a enciclopédia encyclopedia
Em matemática, engenharia e em áudio profissional, a Transformada rápida de Fourier (do inglês: Fast Fourier Transform, abreviado FFT) é um algoritmo que calcula a Transformada discreta de Fourier (DFT) e a sua inversa (Teorema inverso de Fourier), criado pelo estatístico estadunidense John Tukey. A análise de Fourier converte um sinal do domínio original para uma representação no domínio da frequência e vice-versa. 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. A transformada é amplamente utilizadas na engenharia, ciência e matemática. As ideias básicas foram popularizadas em 1965, mas alguns algoritmos foram obtidos em 1805.[1]
Transformada rápida de Fourier | |
---|---|
Fenômeno | algoritmo, Transformada de Fourier |
Homenageado | Jean-Baptiste Joseph Fourier |
Descobridor | John Tukey |
Portal Ciência - Edite Wikidata - Mídia Commons |
Uma Transformada rápida de Fourier calcula rapidamente essas transformações fatorizando a matriz da Transformada discreta de Fourier em um produto de fatores esparsos (principalmente zero).[2] Como resultado, ele consegue reduzir a complexidade de calcular a Transformada discreta de Fourier de , ou seja na ordem de n elevado ao quadrado, que surge se alguém simplesmente aplica a definição de Transformada discreta de Fourier, a , onde é o tamanho dos dados.
Em 1994, Gilbert Strang descreveu a Transformada rápida de Fourier como "O algoritmo numérico mais importante da nossa vida",[3][4] e foi incluída no Top 10 Algorithms of 20th Century pela revista IEEE Computing in Science & Engineering.[5]