Transformação rápida de Fourier

Um exemplo de estrutura de algoritmo FFT, usando uma decomposição em FFTs de meio tamanho

Uma análise discreta de Fourier de uma soma de ondas de cossenos em 10, 20, 30, 40 e 50 Hz

A Transformação rápida de Fourier (FFT) é um algoritmo que computa a discreta transformada de Fourier (DFT) de uma sequência, ou seu inverso (IDFT). A análise de Fourier converte um sinal de seu domínio original (muitas vezes tempo ou espaço) para uma representação no domínio de frequência e vice-versa. O DFT é obtido através da decomposição de uma sequência de valores em componentes de diferentes frequências. Esta operação é útil em muitos campos, mas computá-lo diretamente da definição é muitas vezes muito lento para ser prático. Um FFT rapidamente computa tais transformações, fatorando a matriz DFT em um produto de fatores esparsos (principalmente zero). Como resultado, consegue reduzir a complexidade da computação do DFT O(N2)(N^{2}right)}, que surge se se aplica simplesmente a definição de DFT, a O(Nlog⁡ ⁡ N)(Nlog N)}, onde NNão. é o tamanho dos dados. A diferença de velocidade pode ser enorme, especialmente para conjuntos de dados longos onde N pode estar nos milhares ou milhões. Na presença de erro round-off, muitos algoritmos FFT são muito mais precisos do que avaliar a definição DFT direta ou indiretamente. Existem muitos algoritmos FFT diferentes baseados em uma ampla gama de teorias publicadas, de aritmética simples de números complexos a teoria de grupos e teoria de números.

Representação baseada no tempo (acima) e representação baseada na frequência (abaixo) do mesmo sinal, onde a representação inferior pode ser obtida a partir da parte superior por transformação de Fourier

As transformadas rápidas de Fourier são amplamente utilizadas para aplicações em engenharia, música, ciências e matemática. As ideias básicas foram popularizadas em 1965, mas alguns algoritmos foram derivados já em 1805. Em 1994, Gilbert Strang descreveu o FFT como "o algoritmo numérico mais importante de nossa vida", e foi incluído no Top 10 Algoritmos do Século 20 pela revista IEEE Computing in Science & Engenharia.

Os algoritmos FFT mais conhecidos dependem da fatoração de N, mas há FFTs com complexidade O(N log N) para todos N, mesmo para o primeiroN. Muitos algoritmos FFT dependem apenas do fato de que e- Sim. - Sim. 2D D Eu.../N{textstyle e^{-2pi i/N}} é um N-a raiz primitiva da unidade, e assim pode ser aplicada a transformaçÃμes análogas sobre qualquer campo finito, como transformaçÃμes numéricas teoréticas. Uma vez que o DFT inverso é o mesmo que o DFT, mas com o sinal oposto no expoente e um 1/N fator, qualquer algoritmo FFT pode ser facilmente adaptado para ele.

História

O desenvolvimento de algoritmos rápidos para DFT pode ser rastreado até o trabalho não publicado de Carl Friedrich Gauss em 1805, quando ele precisou dele para interpolar a órbita dos asteróides Pallas e Juno a partir de observações de amostras. Seu método era muito semelhante ao publicado em 1965 por James Cooley e John Tukey, que geralmente são creditados pela invenção do algoritmo FFT genérico moderno. Embora o trabalho de Gauss seja anterior até mesmo aos resultados de Joseph Fourier em 1822, ele não analisou o tempo de computação e acabou usando outros métodos para atingir seu objetivo.

Entre 1805 e 1965, algumas versões do FFT foram publicadas por outros autores. Frank Yates em 1932 publicou sua versão chamada algoritmo de interação, que forneceu computação eficiente de Hadamard e Walsh transforma. 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 DFT para a cristalografia de raios-x, um campo onde o cálculo das transformações de Fourier apresentou um gargalo formidável. Enquanto muitos métodos no passado se concentraram em reduzir o fator constante para O(N2)(N^{2}right)} computação tirando vantagem de "símmetros", Danielson e Lanczos perceberam que se poderia usar a "periodicidade" e aplicar um "duplo truque" para "double [N] com apenas um pouco mais do que o dobro do trabalho", embora como Gauss eles não analisaram que isso levou a O(Nlog⁡ ⁡ N)(Nlog N)} escaldante.

James Cooley e John Tukey independentemente redescobriram esses algoritmos anteriores e publicaram um FFT mais geral em 1965 que é aplicável quando N é composto e não necessariamente um poder de 2, bem como analisar o O(Nlog⁡ ⁡ N)(Nlog N)} escaldante. Tukey surgiu com a ideia durante uma reunião do Comitê Consultivo da Ciência do Presidente Kennedy, onde um tema de discussão envolveu a detecção de testes nucleares pela União Soviética, estabelecendo sensores para cercar o país de fora. Para analisar a saída desses sensores, seria necessário um algoritmo FFT. Em discussão com Tukey, Richard Garwin reconheceu a aplicabilidade geral do algoritmo não apenas para problemas de segurança nacional, mas também para uma ampla gama de problemas, incluindo um de interesse imediato para ele, determinando as periodicidades das orientações de rotação em um cristal 3D de Helium-3. Garwin deu a ideia de Tukey para Cooley (ambos trabalharam nos laboratórios Watson da IBM) para implementação. Cooley e Tukey publicaram o papel em um tempo relativamente curto de seis meses. Como Tukey não trabalhou na IBM, a patenteabilidade da ideia foi duvidada e o algoritmo entrou no domínio público, que, através da revolução de computação da próxima década, fez da FFT um dos algoritmos indispensáveis no processamento digital de sinais.

Definição

Vamos. x0{displaystyle x_{0}}, xN- Sim. - Sim. 1{displaystyle x_{N-1}} ser números complexos. O DFT é definido pela fórmula

Xk= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Gerenciamento Gerenciamento n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0N- Sim. - Sim. 1xne- Sim. - Sim. Eu...2D D kn/Nk= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0,...... ,N- Sim. - Sim. 1,{displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-i2pi kn/N}qquad k=0,ldotsN-1,}

Onde? eEu...2D D /N{displaystyle e^{i2pi /N}} é um primitivo Na raiz de 1.

Avaliar esta definição requer diretamente O(N2)(N^{2}right)} operações: há N saídas X_k, e cada saída requer uma soma de N termos. Um FFT é qualquer método para calcular os mesmos resultados em O(Nlog⁡ ⁡ N)(Nlog N)} operações. Todos os algoritmos FFT conhecidos exigem Θ Θ (Nlog⁡ ⁡ N)(Nlog N)} operações, embora não haja nenhuma prova conhecida de que a menor complexidade é impossível.

Para ilustrar a economia de um FFT, considere a contagem de multiplicações complexas e adições para N= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =4096- Sim. pontos de dados. Avaliar as somas do DFT envolve diretamente N2(textstyle N^{2}} multiplicações complexas e N(N- Sim. - Sim. 1)(N-1)} adições complexas, das quais O(N)(N)} as operações podem ser salvas eliminando operações triviais como multiplicações até 1, deixando cerca de 30 milhões de operações. Em contraste, o algoritmo radix-2 Cooley-Tukey, para N um poder de 2, pode calcular o mesmo resultado com apenas (N/2)log2⁡ ⁡ (N)(N/2)log _{2}(N)} multiplicações complexas (novamente, ignorando simplificações de multiplicações por 1 e similar) e Nlog2⁡ ⁡ (N)(N)} adições complexas, no total cerca de 30.000 operações — mil vezes menos do que com avaliação direta. Na prática, o desempenho real em computadores modernos é geralmente dominado por fatores que não a velocidade de operações aritméticas e a análise é um assunto complicado (por exemplo, ver Frigo & Johnson, 2005), mas a melhoria geral de O(N2)(N^{2}right)} para O(Nlog⁡ ⁡ N)(Nlog N)} restos.

Algoritmos

Algoritmo de Cooley–Tukey

De longe, o FFT mais comumente usado é o algoritmo Cooley-Tukey. Este é um algoritmo de divisão e conquista que recursivamente quebra um DFT de qualquer tamanho composto N= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =N1N2Não. N=N_{1}N_{2}} em muitos DFTs menores de tamanhos N1(texto N_{1}} e N2(textstyle N_{2}}, junto com O(N)O(N)} multiplicações por raízes complexas de unidade tradicionalmente chamado fatores twiddle (depois 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 foi descoberto mais tarde que esses dois autores reinventaram independentemente um algoritmo conhecido por Carl Friedrich Gauss por volta de 1805 (e subsequentemente redescoberto várias vezes em formas limitadas).

O uso mais conhecido do algoritmo de Cooley-Tukey é dividir a transformada em duas partes de tamanho N/2 em cada etapa e, portanto, é limitado a potências de dois tamanhos, mas qualquer fatoração pode ser usada em geral (como era conhecido tanto por Gauss quanto por Cooley/Tukey). Estes são chamados de casos radix-2 e mixed-radix, respectivamente (e outras variantes como a FFT split-radix também têm seus próprios nomes). Embora a ideia básica seja recursiva, a maioria das implementações tradicionais reorganiza o algoritmo para evitar a recursão explícita. Além disso, como o algoritmo Cooley-Tukey divide a DFT em DFTs menores, ele pode ser combinado arbitrariamente com qualquer outro algoritmo para a DFT, como os descritos abaixo.

Outros algoritmos FFT

Existem algoritmos FFT diferentes de Cooley–Tukey.

Para N = N₁N₂ com coprime N₁ e N₂, pode-se usar o algoritmo de fator primo (Good–Thomas) (PFA), baseado em o teorema do resto chinês, para fatorar o DFT de forma semelhante a Cooley-Tukey, mas sem os fatores de rotação. O algoritmo de Rader-Brenner (1976) é uma fatoração semelhante a Cooley-Tukey, mas com fatores de rotação puramente imaginários, reduzindo multiplicações ao custo de adições aumentadas e estabilidade numérica reduzida; foi posteriormente substituído pela variante split-radix de Cooley-Tukey (que atinge a mesma contagem de multiplicação, mas com menos adições e sem sacrificar a precisão). Algoritmos que fatorizam recursivamente a DFT em operações menores que não sejam DFTs incluem os algoritmos Bruun e QFT. (Os algoritmos de Rader-Brenner e QFT foram propostos para tamanhos de potência de dois, mas é possível que eles possam ser adaptados para N composto geral. O algoritmo de Bruun se aplica a compostos arbitrários pares tamanhos.) O algoritmo de Bruun, em particular, é baseado na interpretação da FFT como uma fatoração recursiva do polinômio z^N − 1, aqui em polinômios de coeficiente real da forma z^M − 1 e z^2M + az^M + 1.

Outro ponto de vista polinomial é explorado pelo algoritmo Winograd FFT, que fatoriza z^N − 1 em polinômios ciclotômicos—estes geralmente têm coeficientes de 1, 0 ou −1 e, portanto, requer poucas (se houver) multiplicações, portanto, Winograd pode ser usado para obter FFTs de multiplicação mínima e é frequentemente usado para encontrar algoritmos eficientes para pequenos fatores. De fato, Winograd mostrou que a DFT pode ser calculada apenas com O(N) multiplicações irracionais, levando a um limite inferior alcançável comprovado no número de multiplicações para tamanhos de potência de dois; infelizmente, isso vem com o custo de muito mais acréscimos, uma compensação que não é mais favorável em processadores modernos com multiplicadores de hardware. Em particular, Winograd também faz uso do PFA, bem como um algoritmo de Rader para FFTs de tamanhos primários.

O algoritmo de Rader, explorando a existência de um gerador para o grupo multiplicativo módulo primo N, expressa uma DFT de tamanho primo N como uma convolução cíclica de (composto) tamanho N − 1, que pode então ser calculado por um par de FFTs comuns por meio do teorema da convolução (embora Winograd use outros métodos de convolução). Outra FFT de tamanho primo é devida a L. I. Bluestein, e às vezes é chamada de algoritmo chirp-z; ele também reexpressa uma DFT como uma convolução, mas desta vez do mesmo tamanho (que pode ser preenchido com zeros até uma potência de dois e avaliado por FFTs de base 2 Cooley–Tukey, por exemplo), através da identidade

nk= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. (k- Sim. - Sim. n)22+n22+k22.{displaystyle nk=-{frac {(k-n)^{2}}{2}}+{frac {n^{2}}{2}}+{frac {k^{2}}{2}}.}

A transformada hexagonal rápida de Fourier (HFFT) visa calcular uma FFT eficiente para os dados amostrados hexagonalmente usando um novo esquema de endereçamento para grades hexagonais, chamado Array Set Addressing (ASA).

Algoritmos FFT especializados para dados reais ou simétricos

Em muitas aplicações, os dados de entrada para a DFT são puramente reais, caso em que as saídas satisfazem a simetria

XN- Sim. - Sim. k= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Xk∗ ∗ Não. X_{N-k}=X_{k}^{*}}

e algoritmos FFT eficientes foram projetados para esta situação (ver, por exemplo, Sorensen, 1987). Uma abordagem consiste em pegar um algoritmo comum (por exemplo, Cooley-Tukey) e remover as partes redundantes da computação, economizando aproximadamente um fator de dois em tempo e memória. Alternativamente, é possível expressar uma DFT de entrada real de comprimento par como uma DFT complexa de metade do comprimento (cujas partes reais e imaginárias são os elementos pares/ímpares dos dados reais originais), seguida por O(N) operações de pós-processamento.

Acreditava-se que as DFTs de entrada real poderiam ser calculadas de forma mais eficiente por meio da transformada discreta de Hartley (DHT), mas posteriormente foi argumentado que um algoritmo DFT de entrada real especializado (FFT) pode ser encontrado normalmente e requer menos operações do que o algoritmo DHT correspondente (FHT) para o mesmo número de entradas. O algoritmo de Bruun (acima) é outro método que foi inicialmente proposto para tirar proveito de entradas reais, mas não se mostrou popular.

Existem outras especializações de FFT para os casos de dados reais que possuem simetria par/ímpar, caso em que se pode ganhar outro fator de aproximadamente dois em tempo e memória e a DFT se torna a(s) transformada(s) discreta(s) de cosseno/seno (DCT/DST). Em vez de modificar diretamente um algoritmo FFT para esses casos, DCTs/DSTs também podem ser calculados por meio de FFTs de dados reais combinados com O(N) pré e pós-processamento.

Problemas computacionais

Limites de complexidade e contagem de operações

Uma questão fundamental de longo interesse teórico é provar limites mais baixos sobre a complexidade e a operação exata conta de transformações rápidas de Fourier, e muitos problemas abertos permanecem. Não é rigorosamente provado se os DFT realmente exigem Ω Ω (Nlog⁡ ⁡ N)(Nlog N)} (i.e., ordem Nlog⁡ ⁡ NNão. Nlog N ou maiores) operações, mesmo para o caso simples de poder de dois tamanhos, embora nenhum algoritmo com menor complexidade seja conhecido. Em particular, a contagem de operações aritméticas é geralmente o foco de tais perguntas, embora o desempenho real em computadores modernos é determinado por muitos outros fatores, como cache ou otimização de pipeline de CPU.

Após o trabalho de Shmuel Winograd (1978), um apertado Θ(N) o limite inferior é conhecido pelo número de multiplicações reais exigidas por um FFT. Pode-se mostrar que só 4N- Sim. - Sim. 2log22⁡ ⁡ (N)- Sim. - Sim. 2log2⁡ ⁡ (N)- Sim. - Sim. 4- Sim. _{2}^{2}(N)-2log _{2}(N)-4} multiplicações reais irracionais são necessárias para computar um DFT de potência de dois comprimentos N= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2mNão. N=2^{m}}. Além disso, algoritmos explícitos que atingem esta contagem são conhecidos (Heideman & Burrus, 1986; Duhamel, 1990). No entanto, estes algoritmos exigem muitas adições para ser prático, pelo menos em computadores modernos com multiplicadores de hardware (Duhamel, 1990; Frigo & Johnson, 2005).

Um limite inferior apertado não é conhecido no número de adições necessárias, embora limites inferiores tenham sido provados sob algumas suposições restritivas sobre os algoritmos. Em 1973, Morgenstern provou ser um Ω Ω (Nlog⁡ ⁡ N)Não. Omega (Nlog N)} menor ligado à contagem de adição para algoritmos onde as constantes multiplicativas têm magnitudes limitadas (que é verdade para a maioria, mas não todos os algoritmos FFT). Pan (1986) provou ser um Ω Ω (Nlog⁡ ⁡ N)Não. Omega (Nlog N)} menor limite assumindo um limite em uma medida da "asynchronicity" do algoritmo FFT, mas a generalidade desta suposição não é clara. Para o caso do poder de dois N, Papadimitriou (1979) argumentou que o número Nlog2⁡ ⁡ NNão. de adições complexas de números alcançados por algoritmos Cooley-Tukey é ideal sob certas suposições sobre o gráfico do algoritmo (suas suposições implicam, entre outras coisas, que nenhuma identidade aditiva nas raízes da unidade é explorada). (Este argumento implicaria pelo menos 2Nlog2⁡ ⁡ N- Sim. são necessárias adições reais, embora isso não seja um limite apertado porque as adições extras são necessárias como parte de multiplicações de números complexos.) Até agora, nenhum algoritmo FFT publicado alcançou menos do que Nlog2⁡ ⁡ NNão. adições complexas (ou equivalentes) para potência de doisN.

Um terceiro problema é minimizar o total número de multiplicações e adições reais, às vezes chamado de "complexidade aritmética" (embora neste contexto seja a contagem exata e não a complexidade assintótica que está sendo considerada). Mais uma vez, nenhum limite inferior apertado foi provado. Desde 1968, no entanto, a contagem mais baixa publicada para power-of-two N foi alcançado por muito tempo pelo algoritmo FFT split-radix, que requer 4Nlog2⁡ ⁡ (N)- Sim. - Sim. 6N+8(N)-6N+8} multiplicações reais e adições para N > 1. Isto foi recentemente reduzido a ∼ ∼ 349Nlog2⁡ ⁡ N- Sim. {34}{9}}Nlog _{2}N} (Johnson e Frigo, 2007; Lundy e Van Buskirk, 2007). Uma contagem ligeiramente maior (mas ainda melhor do que o radix dividido para N ≥ 256) foi mostrado para ser comprovadamente ideal para N ≤ 512 sob restrições adicionais sobre os possíveis algoritmos (split-radix-como fluxogramas com fatores multiplicadores unit-modulus), pela redução a um problema de teorias modulo satisfatibilidade solvável pela força bruta (Haynal & Haynal, 2011).

A maioria das tentativas de diminuir ou provar a complexidade dos algoritmos FFT tem se concentrado no caso comum de dados complexos, porque é o mais simples. No entanto, FFTs de dados complexos estão tão intimamente relacionados a algoritmos para problemas relacionados, como FFTs de dados reais, transformadas discretas de cosseno, transformadas discretas de Hartley e assim por diante, que qualquer melhoria em um deles levaria imediatamente a melhorias nos outros (Duhamel & Vetterli, 1990).

Aproximações

Todos os algoritmos FFT discutidos acima calculam a DFT exatamente (ou seja, negligenciando erros de ponto flutuante). Alguns "FFT" algoritmos foram propostos, no entanto, que calculam a DFT aproximadamente, com um erro que pode ser feito arbitrariamente pequeno às custas de cálculos aumentados. Esses algoritmos trocam o erro de aproximação por velocidade aumentada ou outras propriedades. Por exemplo, um algoritmo FFT aproximado de Edelman et al. (1999) alcança menores requisitos de comunicação para computação paralela com a ajuda de um método multipolar rápido. Uma FFT aproximada baseada em wavelets de Guo e Burrus (1996) leva em consideração entradas/saídas esparsas (localização de tempo/frequência) com mais eficiência do que é possível com uma FFT exata. Outro algoritmo para cálculo aproximado de um subconjunto das saídas DFT é devido a Shentov et al. (1995). O algoritmo de Edelman funciona igualmente bem para dados esparsos e não esparsos, pois é baseado na compressibilidade (deficiência de classificação) da própria matriz de Fourier, e não na compressibilidade (esparsidade) dos dados. Por outro lado, se os dados forem esparsos - isto é, se apenas K de N coeficientes de Fourier forem diferentes de zero - então a complexidade pode ser reduzida para O(Klog(N)log(N/K)), e foi demonstrado que isso leva a acelerações práticas em comparação com um normal FFT para N/K > 32 em um exemplo de N grande (N = 2²²) usando um algoritmo aproximado probabilístico (que estima o maior K coeficientes com várias casas decimais).

Precisão

Os algoritmos FFT têm erros quando a aritmética de ponto flutuante de precisão finita é usada, mas esses erros são tipicamente bastante pequenos; a maioria dos algoritmos FFT, por exemplo. Cooley-Tukey, tem excelentes propriedades numéricas como consequência da estrutura de soma dos algoritmos. O limite superior no erro relativo para o algoritmo Cooley-Tukey é O(ε ε log⁡ ⁡ N)[textstyle O(epsilon log N)}, em comparação com O(ε ε N3/2)(epsilon N^{3/2})} para a fórmula DFT ingênua, onde ε é a precisão relativa ponto flutuante da máquina. Na verdade, os erros quadrados (rms) da raiz são muito melhores do que esses limites superiores, sendo apenas O(ε ε log⁡ ⁡ N)- Sim. para Cooley-Tukey e O(ε ε N)- Sim. para o ingênuo DFT (Schatzman, 1996). Estes resultados, no entanto, são muito sensíveis à precisão dos fatores médios utilizados no FFT (ou seja, os valores de função trigonométrica), e não é incomum para implementações FFT incauciosas ter muito pior precisão, por exemplo, se eles usam fórmulas de recorrência trigonométricas inexatas. Alguns FFTs além de Cooley-Tukey, como o algoritmo Rader-Brenner, são intrinsecamente menos estáveis.

Na aritmética de ponto fixo, os erros de precisão finitos acumulados por algoritmos FFT são piores, com erros de rms crescendo como O(N)(N}})} para o algoritmo Cooley-Tukey (Welch, 1969). Alcançar essa precisão requer atenção cuidadosa ao dimensionamento para minimizar a perda de precisão, e algoritmos FFT de ponto fixo envolvem recaling em cada etapa intermediária de decomposições como Cooley-Tukey.

Para verificar a correção de uma implementação FFT, podem ser obtidas garantias rigorosas O(Nlog⁡ ⁡ N)(Nlog N)} tempo por um procedimento simples verificando a linearidade, resposta a impulsos e propriedades de mudança de tempo da transformação em entradas aleatórias (Ergün, 1995).

FFTs multidimensionais

Conforme definido no artigo DFT multidimensional, o DFT multidimensional

Xk= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Gerenciamento Gerenciamento n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0N- Sim. - Sim. 1e- Sim. - Sim. 2D D Eu...k)) (n/N)xn[displaystyle X_{mathbf {k} }=sum _{mathbf {n}] = 0} (N) -1}e^{-2pi imathbf {k} cdot (mathbf {n} /mathbf {N})}x_{mathbf {n} }}

transforma um array x_n com um Dvetor -dimensional de índices n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(n1,...... ,nD){textstyle mathbf {n} =left(n_{1},ldotsn_{d}right)} por um conjunto de D somas aninhadas (mais nJJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0...... NJJ- Sim. - Sim. 1{textstyle n_{j}=0ldots N_{j}-1} para cada JJ), onde a divisão n/N, definido como n/N= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(n1/N1,...... ,nD/ND)- Sim. /mathbf {N} =left(n_{1}/N_{1},ldotsn_{d}/N_{d}right)}, é realizada element-wise. Equivalentemente, é a composição de uma sequência de D conjuntos de DFT unidimensionais, realizados ao longo de uma dimensão de cada vez (em qualquer ordem).

Este ponto de vista compositivo imediatamente fornece o algoritmo DFT multidimensional mais simples e mais comum, conhecido como o linha-coluna algoritmo (depois do caso bidimensional, abaixo). Ou seja, simplesmente executa uma sequência de D FFTs unidimensionais (por qualquer um dos algoritmos acima): primeiro você se transforma ao longo do n₁ dimensão, então ao longo da n₂ dimensão, e assim por diante (ou, na verdade, qualquer trabalho de encomenda). Este método é facilmente mostrado para ter o habitual O(Nlog⁡ ⁡ N)(Nlog N)} complexidade, onde N= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =N1)) N2)) ⋯ ⋯ )) ND{textstyle N=N_{1}cdot N_{2}cdot cdot cdot cdot N_{d}} é o número total de pontos de dados transformados. Em particular, há N/N₁ transformadores de tamanho N₁, etcetera, então a complexidade da sequência de FFTs é:

NN1O(N1log⁡ ⁡ N1)+⋯ ⋯ +NNDO(NDlog⁡ ⁡ ND)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =O(NNão.log⁡ ⁡ N1+⋯ ⋯ +log⁡ ⁡ ND])= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =O(Nlog⁡ ⁡ N).{displaystyle {begin{aligned}&{frac {N}{N_{1}}}O(N_{1}log N_{1})+cdots +{frac {N}{N_{d}}}O(N_{d}log N_{d})[6pt]={}&Oleft(Nleft[log N_{1}+cdots +log N_{d}right]right)=O(Nlog N).end{aligned}}}

Em duas dimensões, o x_k pode ser visto como um n1× × n2{displaystyle n_{1}times n_{2}} matriz, e este algoritmo corresponde ao primeiro executando o FFT de todas as linhas (colunas de reposição), agrupando as linhas transformadas resultantes (colunas de reposição) juntos como outro n1× × n2{displaystyle n_{1}times n_{2}} matriz, e então executando o FFT em cada uma das colunas (resp. linhas) desta segunda matriz, e similarmente agrupando os resultados na matriz de resultado final.

Em mais de duas dimensões, muitas vezes é vantajoso para a localidade de cache agrupar as dimensões recursivamente. Por exemplo, um FFT tridimensional pode primeiro executar FFT bidimensional de cada "slice" planar para cada fixo n₁, e então executar os FFT unidimensional ao longo dos n₁ direcção. Mais geralmente, um algoritmo assintoticamente ideal de cache-oblivious consiste em dividir recursivamente as dimensões em dois grupos (n1,...... ,nD/2)(n_{1},ldotsn_{d/2})} e (nD/2+1,...... ,nD)(n_{d/2+1},ldotsn_{d})} que são transformados recursivamente (arredondando se D (ver Frigo e Johnson, 2005). Ainda assim, isso permanece uma variação direta do algoritmo de coluna de linha que, em última análise, requer apenas um algoritmo FFT unidimensional como o caso base, e ainda tem O(NlogN) complexidade. No entanto, uma outra variação é realizar transposições de matriz entre transformar dimensões subseqüentes, de modo que as transformas operam em dados contíguos; isso é especialmente importante para situações de memória fora do núcleo e distribuídas onde acessar dados não contíguos é extremamente demorado.

Existem outros algoritmos multidimensionais FFT que são distintos do algoritmo de coluna de linha, embora todos eles tenham O(Nlog⁡ ⁡ N)(Nlog N)} complexidade. Talvez o FFT não coluna mais simples é o algoritmo FFT vector-radix, que é uma generalização do algoritmo Cooley-Tukey comum, onde se divide as dimensões de transformação por um vetor R= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(R1,R2,...... ,RD){textstyle mathbf {r} =left(r_{1},r_{2},ldotsr_{d}right)} de radiações em cada etapa. (Isso também pode ter benefícios de cache.) O caso mais simples de vector-radix é onde todos os raios são iguais (por exemplo, vetor-radix-2 divide-se Todos das dimensões por dois), mas isso não é necessário. Raix vetorial com apenas um único radix não-unidade de cada vez, isto é, R= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(1,...... ,1,R,1,...... ,1){textstyle mathbf {r} =left(1,ldots1,r,1,ldots1right)}, é essencialmente um algoritmo de coluna de linha. Outros, mais complicados, métodos incluem algoritmos de transformação polinomial devido ao Nussbaumer (1977), que visualizam a transformação em termos de convoluções e produtos polinomiais. Ver Duhamel e Vetterli (1990) para mais informações e referências.

Outras generalizações

Um O(N5/2log⁡ ⁡ N)(N^{5/2}log N)} generalização para harmônicos esféricos na esfera S² com N² nós foi descrito por Mohlenkamp, juntamente com um algoritmo conjectured (mas não provado) ter O(N2log2⁡ ⁡ (N))(N^{2}log ^{2}(N)} complexidade; Mohlenkamp também fornece uma implementação na biblioteca libftsh. Um algoritmo esférico-harmônico com O(N2log⁡ ⁡ N)(N^{2}log N)}a complexidade é descrita por Rokhlin e Tygert.

O algoritmo de dobramento rápido é análogo ao FFT, exceto que ele opera em uma série de formas de onda agrupadas em vez de uma série de valores escalares reais ou complexos. A rotação (que na FFT é a multiplicação por um fasor complexo) é um deslocamento circular da forma de onda do componente.

Vários grupos também publicaram "FFT" algoritmos para dados não-equipados, conforme revisado em Potts et al. (2001). Esses algoritmos não calculam estritamente a DFT (que é definida apenas para dados equiespaçados), mas sim alguma aproximação dela (uma transformada de Fourier discreta não uniforme, ou NDFT, que geralmente é calculada apenas aproximadamente). Mais geralmente, existem vários outros métodos de estimativa espectral.

Aplicativos

O FFT é usado em gravação digital, amostragem, síntese aditiva e software de correção de pitch.

A importância da FFT deriva do fato de que ela tornou o trabalho no domínio da frequência tão viável computacionalmente quanto o trabalho no domínio temporal ou espacial. Algumas das aplicações importantes da FFT incluem:

• algoritmos de multiplicação de grande inteiro rápido e multiplicação polinomial,
• multiplicação eficiente de matriz-vector para Toeplitz, matrizes circulantes e outras matrizes estruturadas,
• algoritmos de filtragem (veja métodos de sobreposição e sobreposição)
• algoritmos rápidos para transformaçÃμes de cosseno ou sine discretas (por exemplo, DCT rápido usado para codificação e decodificação JPEG e MPEG/MP3),
• aproximação rápida Chebyshev,
• resolver equações de diferença,
• computação de distribuições isotópicas.
• modulação e demodulação de símbolos de dados complexos usando multiplexação de divisão de frequência ortogonal (OFDM) para 5G, LTE, Wi-Fi, DSL e outros sistemas de comunicação modernos.

Áreas de pesquisa

Grandes FFTs

Com a explosão de grandes dados em campos como astronomia, a necessidade de 512K FFTs surgiu para certos cálculos de interferometria. Os dados coletados por projetos como WMAP e LIGO exigem FFTs de dezenas de bilhões de pontos. Como este tamanho não se encaixa na memória principal, assim chamados FFTs out-of-core são uma área ativa de pesquisa.

FFTs aproximados

Para aplicações como RM, é necessário computar DFTs para pontos de grade não uniformemente espaçados e / ou frequências. As abordagens baseadas em vários pólos podem calcular quantidades aproximadas com fator de aumento de tempo de execução.

Grupo FFTs

O FFT também pode ser explicado e interpretado usando a teoria da representação do grupo, permitindo uma maior generalização. Uma função em qualquer grupo compacto, incluindo não cíclico, tem uma expansão em termos de uma base de elementos de matriz irredutíveis. Ele permanece área ativa de pesquisa para encontrar algoritmo eficiente para realizar esta mudança de base. Aplicações incluindo expansão harmônica esférica eficiente, analisando certos processos Markov, robótica etc.

Quantum FFTs

O algoritmo rápido de Shor para a fatoração de inteiro em um computador quântico tem uma subrotina para calcular DFT de um vetor binário. Isso é implementado como sequência de portas quânticas de 1 ou 2 bits agora conhecidas como FFT quântica, que é efetivamente o Cooley-Tukey FFT realizado como uma fatoração particular da matriz Fourier. A extensão a essas ideias está sendo explorada atualmente.

Referência de idioma