Transformada rápida de Fourier
Em matemática, engenharia e em áudio profissional, a Transformada rápida de Fourier é um algoritmo que calcula a Transformada discreta de Fourier (DFT) e a sua inversa, 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.
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. 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. 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. Embora muitos métodos no passado tenham se concentrado em reduzir o fator constante para computação de O ( N 2 ) {\displaystyle 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 ) {\displaystyle O(N\log N)} .
A Transformada discreta de Fourier é obtida pela decomposição de uma sequência de valores em componentes de diferentes frequências. 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 ( N 2 ) {\displaystyle 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 ) {\displaystyle O(N\log N)} operações. A diferença de velocidade pode ser enorme, especialmente para conjuntos de dados longos em que N {\displaystyle 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 {\displaystyle 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 de Cooley-Tukey
De longe o algoritmo FFT mais utilizado é o de Cooley–Tukey. Trata-se de um algoritmo de divisão e conquista que decompõe recursivamente uma DFT de qualquer tamanho N = N 1 N 2 {\displaystyle N=N_{1}N_{2}} em N 1 {\displaystyle N_{1}} DFTs menores de tamanho N 2 {\displaystyle N_{2}} , juntamente com O ( N ) {\displaystyle O(N)} multiplicações por raízes complexas da unidade, tradicionalmente chamadas de fatores de rotação (segundo Gentleman e Sande, 1966). Este método (e a ideia geral de uma FFT) foi popularizado por uma publicação de Cooley e Tukey em 1965, mas descobriu-se posteriormente que esses dois autores haviam, de forma independente, reinventado um algoritmo já conhecido por Carl Friedrich Gauss por volta de 1805 (e redescoberto diversas vezes em versões mais restritas).
Algoritmo DIT (dizimação no tempo) raiz-2
O algoritmo baseia-se no chamado método de dobramentos sucessivos, onde podemos expressar a transformada de Fourier como sendo F ( u ) = 1 N ∑ x = 0 N − 1 f ( x ) W N u x {\displaystyle F(u)={\frac {1}{N}}\sum _{x=0}^{N-1}f(x)W_{N}^{ux}\,\!} W N u x = e − j 2 π u ⋅ x / N {\displaystyle W_{N}^{ux}=e^{-j2\pi u\cdot x/N}\,\!} . Assumimos que N = 2 n {\displaystyle N=2^{n}\,\!} onde n {\displaystyle n\,\!} é um inteiro positivo. Portanto, N {\displaystyle N\,\!} pode ser escrito como N = 2 M {\displaystyle N=2M\,\!} onde M {\displaystyle M\,\!} é um inteiro positivo. Logo, a transformada de Fourier escrita inicialmente, pode ser reescrita como F ( u ) = 1 2 M ∑ x = 0 2 M − 1 f ( x ) W 2 M u x {\displaystyle F(u)={\frac {1}{2M}}\sum _{x=0}^{2M-1}f(x)W_{2M}^{ux}\,\!}
Outros Algoritmos FFT
Para N = N 1 N 2 {\displaystyle N=N_{1}N_{2}} com N 1 {\displaystyle N_{1}} e N 2 {\displaystyle N_{2}} primos entre si, é possível utilizar o algoritmo do fator primo (Good–Thomas), baseado no Teorema Chinês do Resto, para fatorar a DFT de forma semelhante a Cooley–Tukey, porém sem os fatores twiddle. O algoritmo de Rader–Brenner (1976) é uma fatoração similar à de Cooley–Tukey, mas com fatores twiddle puramente imaginários, reduzindo multiplicações ao custo de mais adições e menor estabilidade numérica. O algoritmo de Bruun é um algoritmo FFT que usa fatoração recursiva de polinômios com coeficientes reais, proposto por G. Bruun em 1978 para potências de dois e expandido em 1996 para tamanhos compostos pares arbitrários por H. Murakami. Apesar de suas vantagens teóricas, o algoritmo de Bruun não obteve adoção ampla, uma vez que implementações do algoritmo de Cooley-Tukey comum foram adaptadas com sucesso para dados reais atingindo eficiência computacional equivalente.
Uma TFD multidimensional é definida como: Ela transforma um arranjo x n {\displaystyle x_{\mathbf {n} }} , com vetor de índices d-dimensional n = ( n 1 , … , n d ) {\displaystyle \mathbf {n} =(n_{1},\ldots ,n_{d})} , por meio de um conjunto de d somatórios encadeados (sobre n j = 0 … N j − 1 {\textstyle n_{j}=0\ldots N_{j}-1} para cada j {\displaystyle j} ), nos quais a divisão n / N = ( n 1 / N 1 , … , n d / N d ) {\displaystyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots ,n_{d}/N_{d}\right)} é realizada elemento a elemento. De maneira equivalente, ela é a composição de uma sequência de d {\displaystyle d} conjuntos de DFTs unidimensionais, realizadas ao longo de uma dimensão por vez, em qualquer ordem. Essa interpretação composicional fornece imediatamente o algoritmo de DFT multidimensional mais simples e mais comum, conhecido como algoritmo linha-coluna (row-column algorithm), devido ao caso bidimensional apresentado a seguir: primeiro transforma-se ao longo da dimensão n 1 {\displaystyle n_{1}} , depois ao longo da dimensão n 2 {\displaystyle n_{2}} , e assim por diante (na verdade qualquer ordenação funciona).
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:
A FFT pode ser uma escolha inadequada para analisar sinais com conteúdo espectral não estacionário — ou seja, cujas características espectrais variam ao longo do tempo. As DFTs fornecem uma estimativa global no domínio da frequência, assumindo que todas as componentes espectrais estão presentes ao longo de todo o sinal, o que dificulta a detecção de componentes transitórios ou de curta duração nos sinais. Nos casos em que as componentes espectrais aparecem brevemente no sinal ou, de maneira geral, variam ao longo do tempo, alternativas como a transformada de Fourier de tempo curto, a transformada de wavelet discreta e a transformada de Hilbert discreta podem ser mais adequadas. Essas transformadas permitem uma análise localizada no domínio da frequência, levando em consideração simultaneamente o conteúdo espectral e temporal do sinal.
