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
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
de comprimento
:
Agora, separamos a soma em termos de índices pares
e ímpares
, com
:
Passo 3
Observe que cada uma dessas somas é justamente uma DFT de tamanho
:
A segunda soma original traz ainda um fator extra
, chamado de “twiddle factor”:
Passo 4
Portanto, em vez de calcular diretamente uma DFT de tamanho
, calculamos duas DFTs de tamanho
(as de
e
) e depois combinamos os resultados em custo linear.
Repetimos recursivamente esse procedimento até chegarmos a transformadas de tamanho , que são triviais. Na etapa de recombinação, para
,
Repetimos recursivamente esse procedimento até chegarmos a transformadas de tamanho
onde
.
Assim construímos uma árvore de recursão com níveis, em cada nível envolvendo
operações de soma e multiplicação por
. A complexidade total cai de
na DFT direta para
.
Assim construímos uma árvore de recursão com
Resposta
Funcionalmente, a FFT divide o problema de calcular uma DFT de tamanho
em duas DFTs de tamanho
(índices pares e ímpares), combinando-as com fatores
e repetindo recursivamente até casos triviais, reduzindo a complexidade de
para
.