Transformada rápida de Fourier

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

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]

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 $O\left(N^{2}\right)$ , 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 $O(N\log N)$ , onde $N$ é 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]

História

O desenvolvimento de algoritmos rápidos para Transformada discreta de Fourier pode ser rastreado até o trabalho não publicado de Gauss em 1805, quando ele precisou interpolar a órbita dos asteroides Pallas e Juno de observações de amostras.^[6]^[7] Seu método foi muito semelhante ao publicado em 1965 por James William Cooley e John Wilder Tukey, que são geralmente creditados pela invenção do moderno algoritmo de Transformada rápida de Fourier genérico. Enquanto o trabalho de Gauss antecedeu os resultados de Fourier em 1822, ele não analisou o tempo de computação e eventualmente, usou outros métodos para atingir seu objetivo.

Entre 1805 e 1965, algumas versões da Transformada rápida de Fourier foram publicadas por outros autores. Frank Yates, em 1932, publicou sua versão chamada algoritmo de interação, que forneceu uma computação eficiente das transformadas de Hadamard e Walsh.^[6] O algoritmo de Yates ainda é usado no campo do projeto estatístico e análise de experimentos. Em 1942, G. C. Danielson e Cornelius Lanczos publicaram sua versão para computar a Transformada discreta de Fourier para cristalografia de raios X, um campo onde o cálculo das transformadas de Fourier apresentava um formidável obstáculo.^[8]^[9] Embora muitos métodos no passado tenham se concentrado em reduzir o fator constante para computação de $O\left(N^{2}\right)$ aproveitando as "simetrias", Danielson e Lanczos perceberam que usando a "periodicidade" e aplicando um "truque de duplicação" poderiam obter o tempo de execução $O(N\log N)$ .^[10]

James Cooley e John Tukey publicaram uma versão mais geral da Transformada rápida de Fourier em 1965 que é aplicável quando N é composto e não necessariamente uma potência de 2.^[11] Tukey teve a ideia durante uma reunião do Comitê Consultivo Científico do presidente Kennedy, onde um tópico de discussão envolveu a detecção de testes nucleares pela União Soviética, através da instalação de sensores para cercar o país de fora. Para analisar a saída desses sensores, seria necessário um algoritmo de transformação rápida de Fourier. Em discussão com Tukey, Richard Garwin reconheceu a aplicabilidade geral do algoritmo não apenas a problemas de segurança nacional, mas também a uma ampla gama de problemas, incluindo um de interesse imediato para ele, determinar as periodicidades das orientações de spin em um cristal 3-D de hélio-3.^[12] Garwin deu a ideia de Tukey para Cooley (ambos trabalharam nos laboratórios Watson da IBM) para implementação.^[13] Cooley e Tukey publicaram o artigo em um período relativamente curto de seis meses.^[14] Como Tukey não trabalhava na IBM, a patenteabilidade da ideia foi posta em dúvida e o algoritmo entrou no domínio público, o que, através da revolução da computação na próxima década, fez da FFT um dos algoritmos indispensáveis no processamento digital de sinais.

Visão Geral

A Transformada discreta de Fourier é obtida pela decomposição de uma sequência de valores em componentes de diferentes frequências.^[15] Esta operação é útil em muitos campos, entretanto calculá-la diretamente da definição é frequentemente lenta demais para ser prática. Uma Transformada rápida de Fourier é uma maneira de calcular o mesmo resultado mais rapidamente: calcular a Transformada discreta de Fourier de n pontos da maneira ingênua, usando a definição, leva operações aritméticas de $O\left(N^{2}\right)$ , enquanto uma Transformada rápida de Fourier pode computar a mesma Transformada discreta de Fourier em apenas $O(N\log N)$ operações. A diferença de velocidade pode ser enorme, especialmente para conjuntos de dados longos em que N pode estar na casa dos milhares ou milhões. Na prática, o tempo de computação pode ser reduzido em várias ordens de magnitude em tais casos, e a melhoria é aproximadamente proporcional a N/log N. Essa grande melhoria tornou o cálculo da Transformada discreta de Fourier prático; As Transformadas rápidas de Fourier são de grande importância para uma ampla variedade de aplicações, desde processamento digital de sinais e resolução de equações diferenciais parciais até algoritmos para rápida multiplicação de inteiros grandes.

Algoritmo

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 u\cdot x/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.

Aplicações

A importância da FFT deriva do fato de que, no processamento de sinais e no processamento de imagens, o trabalho no domínio da freqüência é igualmente viável computacionalmente como o trabalho no domínio temporal ou espacial. Algumas das aplicações importantes da FFT incluem^[16]^[14]:

Multiplicação rápida de números inteiros e polinomiais

Multiplicação eficiente de vetores matriciais para Toeplitz, circulantes e outras matrizes estruturadas

Algoritmos de filtragem

Algoritmos rápidos para transformações discretas de cosseno ou seno (por exemplo, Fast DCT usado para codificação JPEG, MP3 / MPEG)

Aproximação rápida de Chebyshev

Transformada Hartley discreta rápida

Resolvendo Equações Diferenciais

Computação de distribuições isotópicas.^[16]

Implementações computacionais

ALGLIB – C++ and C# library with real/complex FFT implementation.
FFTW "Fastest Fourier Transform in the West" – C library for the discrete Fourier transform (DFT) in one or more dimensions.
FFTS – The Fastest Fourier Transform in the South.
FFTPACK – another Fortran FFT library (public domain)
Math Kernel Library

Veja também

Referências

↑ Heideman, Michael T.; Johnson, Don H.; Burrus, C. Sidney (1985). «Gauss and the history of the fast Fourier transform». Archive for History of Exact Sciences. 34 (3): 265–277. ISSN 0003-9519. doi:10.1007/bf00348431
↑ Van Loan, Charles (janeiro de 1992). Computational Frameworks for the Fast Fourier Transform. [S.l.]: Society for Industrial and Applied Mathematics. ISBN 9780898712858
↑ D., Kent, Raymond (2002). The acoustic analysis of speech 2nd ed. Australia: Singular/Thomson Learning. ISBN 0769301126. OCLC 48024997
↑ Strang, Gilbert (abril de 1984). «Duality in the Classroom». The American Mathematical Monthly. 91 (4). 250 páginas. ISSN 0002-9890. doi:10.2307/2322961
↑ «Institute of Electrical and Electronics Engineers». Wikipedia (em inglês). 12 de julho de 2018
↑ ^a ^b Heideman, Michael T.; Johnson, Don H.; Burrus, C. Sidney (1985). «Gauss and the history of the fast Fourier transform». Archive for History of Exact Sciences. 34 (3): 265–277. ISSN 0003-9519. doi:10.1007/bf00348431
↑ Gauss, Carl Friedrich (1877). «Auszug aus dreijährigen täglichen Beobachtungen der magnetischen Declination zu Göttingen». Berlin, Heidelberg: Springer Berlin Heidelberg: 556–568. ISBN 9783642493201
↑ Michaelson, S.; Lanczos, Cornelius (fevereiro de 1960). «Applied Analysis». The Mathematical Gazette. 44 (347). 75 páginas. ISSN 0025-5572. doi:10.2307/3608551
↑ Danielson, G.C.; Lanczos, C. (abril de 1942). «Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids». Journal of the Franklin Institute. 233 (4): 365–380. ISSN 0016-0032. doi:10.1016/s0016-0032(42)90767-1
↑ Cooley, J.; Lewis, P.; Welch, P. (junho de 1967). «Historical notes on the fast Fourier transform». IEEE Transactions on Audio and Electroacoustics. 15 (2): 76–79. ISSN 0018-9278. doi:10.1109/tau.1967.1161903
↑ Cooley, James W.; Tukey, John W. (abril de 1965). «An Algorithm for the Machine Calculation of Complex Fourier Series». Mathematics of Computation. 19 (90). 297 páginas. ISSN 0025-5718. doi:10.2307/2003354
↑ Cooley, James W. (janeiro de 1987). «The re-discovery of the fast Fourier transform algorithm». Mikrochimica Acta. 93 (1-6): 33–45. ISSN 0026-3672. doi:10.1007/bf01201681
↑ Cooley, J.; Garwin, R.; Rader, C.; Bogert, B.; Stockham, T. (junho de 1969). «The 1968 Arden house workshop on fast Fourier transform processing». IEEE Transactions on Audio and Electroacoustics. 17 (2): 66–76. ISSN 0018-9278. doi:10.1109/tau.1969.1162047
↑ ^a ^b Rockmore, D.N. (2000). «The FFT: an algorithm the whole family can use». Computing in Science & Engineering. 2 (1): 60–64. ISSN 1521-9615. doi:10.1109/5992.814659
↑ Heideman, M.; Johnson, D.; Burrus, C. (outubro de 1984). «Gauss and the history of the fast fourier transform». IEEE ASSP Magazine (em inglês). 1 (4): 14–21. ISSN 0740-7467. doi:10.1109/massp.1984.1162257
↑ ^a ^b 1950-, Chu, Eleanor Chin-hwa, (2000). Inside the FFT black box : serial and parallel fast Fourier transform algorithms. Boca Raton, Fla.: CRC Press. ISBN 0849302706. OCLC 51949140

Erro de citação: Elemento <ref> com nome "Loan_1992" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Heideman_Johnson_Burrus_1984" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Heideman_Burrus_1986" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Dongarra_Sullivan_2000" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Brenner_Rader_1976" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Kent_2002" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Strang_1994" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Ergün_1995" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Frigo_Johnson_2005" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Frigo_Johnson_2007" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Duhamel_1990" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Duhamel_Vetterli_1990" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Edelman_McCorquodale_Toledo_1999" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Guo_Burrus_1996" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Shentov_Mitra_Heute_Hossen_1995" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Hassanieh_2012" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Haynal_2011" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Lundy_Buskirk_2007" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Papadimitriou_1979" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Sorensen_Jones_Heideman_Burrus_1987_1" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Sorensen_Jones_Heideman_Burrus_1987_2" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Winograd_1978" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Winograd_1979" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Morgenstern_1973" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Mohlenkamp_1999" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Schatzman_1996" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Nussbaumer_1977" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Pan_1986" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Potts_Steidl_Tasche_2001" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Rokhlin_Tygert_2006" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Welch_1969" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Gauss_1866" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Heideman_Johnson_Burrus_1985" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Yates_1937" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Cooley_Lewis_Welch_1967" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Cooley_Tukey_1965" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Danielson_Lanczos_1942" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Lanczos_1956" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Fernandez-de-Cossio_2012" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Chu_George_1999" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Rockmore_2000" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Rockmore_2004" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Gentleman_Sande_1966" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Gauss_1805" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Cooley_1987" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Garwin_1969" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "libftsh" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "Cormen_Nicol_1998" definido em <references> não é utilizado no texto da página.

Erro de citação: Elemento <ref> com nome "Dutt_Rokhlin_1993" definido em <references> não é utilizado no texto da página.

Ligações externas

Multiplicando inteiros com Fast Fourier Transform

[1] Heideman, Michael T.; Johnson, Don H.; Burrus, C. Sidney (1985). «Gauss and the history of the fast Fourier transform». Archive for History of Exact Sciences. 34 (3): 265–277. ISSN 0003-9519. doi:10.1007/bf00348431

[2] Van Loan, Charles (janeiro de 1992). Computational Frameworks for the Fast Fourier Transform. [S.l.]: Society for Industrial and Applied Mathematics. ISBN 9780898712858

[3] D., Kent, Raymond (2002). The acoustic analysis of speech 2nd ed. Australia: Singular/Thomson Learning. ISBN 0769301126. OCLC 48024997

[4] Strang, Gilbert (abril de 1984). «Duality in the Classroom». The American Mathematical Monthly. 91 (4). 250 páginas. ISSN 0002-9890. doi:10.2307/2322961

[5] «Institute of Electrical and Electronics Engineers». Wikipedia (em inglês). 12 de julho de 2018

[Não_nomeado-yJ_8-1-6] Heideman, Michael T.; Johnson, Don H.; Burrus, C. Sidney (1985). «Gauss and the history of the fast Fourier transform». Archive for History of Exact Sciences. 34 (3): 265–277. ISSN 0003-9519. doi:10.1007/bf00348431

[7] Gauss, Carl Friedrich (1877). «Auszug aus dreijährigen täglichen Beobachtungen der magnetischen Declination zu Göttingen». Berlin, Heidelberg: Springer Berlin Heidelberg: 556–568. ISBN 9783642493201

[8] Michaelson, S.; Lanczos, Cornelius (fevereiro de 1960). «Applied Analysis». The Mathematical Gazette. 44 (347). 75 páginas. ISSN 0025-5572. doi:10.2307/3608551

[9] Danielson, G.C.; Lanczos, C. (abril de 1942). «Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids». Journal of the Franklin Institute. 233 (4): 365–380. ISSN 0016-0032. doi:10.1016/s0016-0032(42)90767-1

[10] Cooley, J.; Lewis, P.; Welch, P. (junho de 1967). «Historical notes on the fast Fourier transform». IEEE Transactions on Audio and Electroacoustics. 15 (2): 76–79. ISSN 0018-9278. doi:10.1109/tau.1967.1161903

[11] Cooley, James W.; Tukey, John W. (abril de 1965). «An Algorithm for the Machine Calculation of Complex Fourier Series». Mathematics of Computation. 19 (90). 297 páginas. ISSN 0025-5718. doi:10.2307/2003354

[12] Cooley, James W. (janeiro de 1987). «The re-discovery of the fast Fourier transform algorithm». Mikrochimica Acta. 93 (1-6): 33–45. ISSN 0026-3672. doi:10.1007/bf01201681

[13] Cooley, J.; Garwin, R.; Rader, C.; Bogert, B.; Stockham, T. (junho de 1969). «The 1968 Arden house workshop on fast Fourier transform processing». IEEE Transactions on Audio and Electroacoustics. 17 (2): 66–76. ISSN 0018-9278. doi:10.1109/tau.1969.1162047

[Não_nomeado-yJ_8-2-14] Rockmore, D.N. (2000). «The FFT: an algorithm the whole family can use». Computing in Science & Engineering. 2 (1): 60–64. ISSN 1521-9615. doi:10.1109/5992.814659

[15] Heideman, M.; Johnson, D.; Burrus, C. (outubro de 1984). «Gauss and the history of the fast fourier transform». IEEE ASSP Magazine (em inglês). 1 (4): 14–21. ISSN 0740-7467. doi:10.1109/massp.1984.1162257

[Não_nomeado-yJ_8-3-16] 1950-, Chu, Eleanor Chin-hwa, (2000). Inside the FFT black box : serial and parallel fast Fourier transform algorithms. Boca Raton, Fla.: CRC Press. ISBN 0849302706. OCLC 51949140

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]