FFT — Transformada Rápida de Fourier explicada de forma simples

A FFT, ou transformada rápida de Fourier, é uma forma rápida de calcular a transformada discreta de Fourier (DFT). Se você começa com amostras igualmente espaçadas, a DFT informa quanto de cada padrão discreto de frequência aparece nessas amostras.

O ponto importante é que a FFT não muda o resultado. Ela fornece os mesmos valores da DFT que a fórmula direta, mas chega a eles com muito menos trabalho repetido.

FFT em uma frase

A FFT é um algoritmo mais rápido para obter os mesmos números no domínio da frequência que a DFT já define.

O que a DFT mede

Suponha que você tenha amostras $x_0, x_1, \dots, x_{N-1}$. A DFT produz números $X_0, X_1, \dots, X_{N-1}$ definidos por

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Cada $X_k$ mede com que intensidade os dados correspondem a um padrão discreto de frequência.

Se as amostras forem igualmente espaçadas com taxa de amostragem $f_s$, então os bins de frequência adjacentes ficam separados por

$$\frac{f_s}{N}$$

Essa condição importa. Sem uma taxa de amostragem conhecida, você ainda tem bins da DFT, mas não pode rotulá-los como frequências físicas, como hertz.

Por que a FFT é mais rápida

A FFT é uma família de algoritmos para calcular a DFT de forma eficiente. O truque principal é reaproveitar a estrutura dos fatores exponenciais complexos em vez de recalcular do zero somas quase idênticas.

A versão mais fácil de visualizar é a FFT radix-2. Ela funciona de forma mais natural quando $N$ é uma potência de $2$ e divide uma transformada de comprimento $N$ em duas transformadas de comprimento $N/2$ antes de combinar os resultados.

Na DFT direta, a quantidade de operações aritméticas cresce na ordem de $N^2$. Nos métodos comuns de FFT, isso cai para cerca de $N \log N$.

Essa diferença é o motivo de as FFTs serem importantes na prática. Para entradas pequenas, os dois métodos podem parecer aceitáveis. Para entradas grandes, a FFT é dramaticamente mais rápida.

Como a FFT divide o trabalho

Em vez de comparar diretamente cada amostra com cada padrão de frequência, a FFT divide o problema em transformadas menores e depois as recompõe com fatores de fase.

Uma divisão padrão é:

1. Colocar as amostras de índices pares em uma lista.
2. Colocar as amostras de índices ímpares em outra lista.
3. Calcular transformadas menores nessas listas.
4. Combinar as duas metades.

Isso é a estratégia de dividir para conquistar aplicada à análise em frequência.

Exemplo de FFT de 4 pontos

Considere o sinal de 4 pontos

$$x = [1, 0, 1, 0]$$

Esse padrão alterna entre $1$ e $0$, então esperamos alguma estrutura de frequência em vez de um resultado completamente plano.

Separe em índices pares e ímpares:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

A DFT de 2 pontos da parte par é

$$E = [2, 0]$$

e a DFT de 2 pontos da parte ímpar é

$$O = [0, 0]$$

Para uma FFT de 4 pontos, a etapa de combinação é

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

onde

$$W_4 = e^{-i 2 \pi / 4}$$

Como $O_k = 0$, a combinação fica especialmente simples:

$$X = [2, 0, 2, 0]$$

Agora interprete o resultado.

$X_0 = 2$ é o termo de frequência zero, então ele reflete o valor médio não nulo das amostras. O valor não nulo em $X_2$ captura a parte alternante do padrão neste caso de 4 pontos. Se você subtrair primeiro a média, o termo $X_0$ desaparece e o componente alternante se destaca com mais clareza.

Este exemplo é pequeno, mas a ideia escala: resolva transformadas menores e depois combine os resultados, em vez de reconstruir a soma inteira a cada vez.

Erros comuns com FFT

Tratar FFT e DFT como resultados diferentes

Não são. A FFT é um método mais rápido para calcular a DFT.

Ler os bins como frequências físicas cedo demais

As posições dos bins só se tornam frequências físicas quando o espaçamento entre amostras é conhecido. Se a taxa de amostragem for $f_s$, então o espaçamento entre bins é $f_s/N$ para amostras igualmente espaçadas.

Supor que zero-padding adiciona nova informação

O zero-padding pode fazer um espectro parecer mais suave porque amostra a transformada subjacente de forma mais fina, mas não adiciona novos dados medidos.

Ignorar a preparação do sinal

Remoção da média, aplicação de janela e escolhas cuidadosas de amostragem podem importar muito. Se essas condições forem ignoradas, a saída da FFT ainda pode estar matematicamente correta para as amostras dadas, mas ser enganosa na interpretação.

Onde a FFT é usada

A FFT aparece em qualquer situação em que você precise de informações rápidas no domínio da frequência a partir de dados amostrados. Exemplos comuns incluem análise espectral, filtragem, processamento de imagens, análise de vibrações, solução numérica de equações diferenciais e cálculos rápidos de polinômios ou convolução.

O motivo é prático: muitas operações ficam mais fáceis ou mais rápidas depois de passar do domínio das amostras para o domínio da frequência.

Tente um caso parecido

Pegue $8$ amostras igualmente espaçadas de uma onda senoidal ao longo de um período completo e calcule a DFT com uma calculadora ou script. Depois adicione um deslocamento constante e compare a nova saída. O valor mais forte em $X_0$ é uma forma simples de ver o que a FFT separa.