Funcionalmente, a transformada rápida de Fourier decompõe conjuntos de dados em uma série de conjuntos de dados menores. Explique como isso é feito.

Passo 1

O enunciado pergunta como, funcionalmente, a Transformada Rápida de Fourier (FFT) decompõe um conjunto de dados de tamanho N em conjuntos menores para reduzir o custo de cálculo da DFT. Para isso, vamos usar a definição da DFT e o método de “dividir para conquistar” do algoritmo de Cooley–Tukey.

Passo 2

Começamos pela definição da DFT de um vetor x[n] de comprimento N:
X[k] \;=\;\sum_{n=0}^{N-1} x[n]\,e^{-2\pi i\,\frac{k\,n}{N}}, \quad k=0,1,\dots,N-1.
Agora, separamos a soma em termos de índices pares n=2m e ímpares n=2m+1, com m=0,1,\dots,\tfrac{N}{2}-1:
X[k] =\sum_{m=0}^{\frac{N}{2}-1}x[2m]\,e^{-2\pi i\frac{k\,(2m)}{N}} +\sum_{m=0}^{\frac{N}{2}-1}x[2m+1]\,e^{-2\pi i\frac{k\,(2m+1)}{N}}.

Passo 3

Observe que cada uma dessas somas é justamente uma DFT de tamanho N/2:
E[k]=\sum_{m=0}^{\frac{N}{2}-1}x[2m]\,e^{-2\pi i\frac{k\,m}{N/2}}, \quad O[k]=\sum_{m=0}^{\frac{N}{2}-1}x[2m+1]\,e^{-2\pi i\frac{k\,m}{N/2}}.
A segunda soma original traz ainda um fator extra e^{-2\pi i\,\frac{k}{N}}, chamado de “twiddle factor”:
X[k]=E[k]+e^{-2\pi i\frac{k}{N}}\,O[k].

Passo 4

Portanto, em vez de calcular diretamente uma DFT de tamanho N, calculamos duas DFTs de tamanho N/2 (as de E[k] e O[k]) e depois combinamos os resultados em custo linear.
Repetimos recursivamente esse procedimento até chegarmos a transformadas de tamanho 1, que são triviais. Na etapa de recombinação, para k=0,1,\dots,\tfrac{N}{2}-1,
X[k] = E[k] + W_N^k\,O[k], \quad X[k+\tfrac{N}{2}] = E[k] - W_N^k\,O[k],
onde W_N = e^{-2\pi i/N}.
Assim construímos uma árvore de recursão com \log_2 N níveis, em cada nível envolvendo N operações de soma e multiplicação por W_N^k. A complexidade total cai de O(N^2) na DFT direta para O(N\log N).

Resposta

Funcionalmente, a FFT divide o problema de calcular uma DFT de tamanho N em duas DFTs de tamanho N/2 (índices pares e ímpares), combinando-as com fatores e^{-2\pi i k/N} e repetindo recursivamente até casos triviais, reduzindo a complexidade de O(N^2) para O(N\log N).

Exercícios de Livros Relacionados