FFT: o algoritmo de 60 anos que ainda está por trás da tecnologia moderna

Você ouve um equalizador, conecta no Wi-Fi e abre um JPEG. Em cada um desses passos, alguém transformou um sinal do tempo (ou do espaço) em frequências, fez um trabalho barato nesse domínio, e voltou. A peça que torna isso viável em escala é a FFT: a transformada rápida de Fourier. Tem cerca de 60 anos na forma que a engenharia usa hoje. Continua no caminho crítico de codecs, rádios digitais, bibliotecas numéricas e features de machine learning.

Este texto não é aula de análise complexa. É o mapa prático: o que a FFT calcula, por que a complexidade importa, onde você já a usa sem saber, e onde ela mente se você tratar o espectro como verdade absoluta.

O problema: tempo versus frequência

Um microfone entrega amostras no tempo. Uma sequência x[0], x[1], …, x[n-1]. Olhando só essa lista, é difícil responder perguntas simples: qual a nota dominante? Onde está o ruído de 60 Hz? Quanta energia há acima de 8 kHz, onde o ouvido já perdoa mais?

No domínio da frequência, a mesma informação aparece como amplitudes e fases de senoides. Um tom puro vira um pico. Um acorde vira um punhado de picos. Um clique espalha energia por muitas frequências. Filtrar passa a ser “apagar ou atenuar bins”, não convoluir um kernel longo no tempo.

A troca não é gratuita. A DFT (transformada discreta de Fourier) é a definição correta para dados amostrados: ela decompõe o bloco finito em n componentes de frequência. O problema clássico é o custo. Na forma ingênua, cada uma das n saídas mistura as n entradas. Isso é O(n²). Para n = 1024, já incomoda. Para áudio em tempo real, OFDM a dezenas de megahertz, ou espectrogramas em batch, o quadrático some do orçamento.

A FFT não inventa outra transformada. Ela calcula a mesma DFT, com menos aritmética, explorando estrutura e reutilização. Cooley e Tukey publicaram o algoritmo moderno em 1965; a demonstração em máquina na IBM já tinha rodado em 1964. A ideia de fatorar o problema é mais antiga — Gauss já tinha um método parecido no século XIX — mas foi a versão computável e divulgada que abriu o processamento digital de sinais como engenharia cotidiana.

O que a FFT calcula, em uma frase útil

A FFT devolve, para um bloco de n amostras, os n coeficientes complexos da DFT: quanto de cada frequência discreta cabe naquele bloco, com amplitude e fase.

No NumPy, numpy.fft.fft(a) é exatamente isso: a DFT unidimensional, implementada com um algoritmo rápido. A[0] é a componente de frequência zero (a “média” do sinal). Os índices seguintes carregam frequências positivas e negativas, na ordem convencional da biblioteca. Para entrada real, a saída é hermitiana: a metade negativa não traz informação nova, e por isso existe rfft. Magnitude np.abs(A) é o espectro de amplitude; np.abs(A)**2 é o de potência. A inversa reconstrói o tempo.

Se você só precisa dessa frase e de fftfreq para rotular o eixo em hertz, já dá para diagnosticar muita coisa. O resto do artigo é onde essa caixa preta aparece em sistemas reais — e onde a caixa mente.

Por que O(n log n) importa

Compare ordens de grandeza, não slogans. DFT ingênua: ~n² operações. FFT típica (tamanho composto, em especial potência de 2): ~n log n. Para n = 10⁶, a razão n / log₂(n) já passa de 50 mil. Não é “um pouco mais rápido”. É a diferença entre “roda no notebook” e “só no cluster, e mesmo assim tarde”.

Na prática, três consequências:

1. Tempo real. Equalizador, cancelamento de eco, análise espectral ao vivo e demodulação OFDM precisam de uma transformada por bloco, dezenas ou milhares de vezes por segundo. O(n²) estoura o deadline; O(n log n) cabe.
2. Convolução rápida. Multiplicar espectros e voltar ao tempo é convolução circular (com o cuidado do zero-padding). Filtros longos, correlação e overlap-add/overlap-save existem porque a FFT barateia essa ida e volta.
3. Hardware e software otimizados. Bibliotecas como a FFTW não fixam um único algoritmo: um planner escolhe fatorações (Cooley–Tukey, prime-factor, Rader, split-radix, etc.) e codelets gerados para o tamanho e a máquina. O NumPy e o SciPy se apoiam nesse ecossistema. Você raramente escreve a FFT; você escolhe tamanho, layout e se vale cachear o plano.

Eu trato n potência de 2 como default de laboratório não por misticismo, e sim porque a simetria é máxima e as implementações estão mais afiadas. Tamanhos arbitrários funcionam — a FFTW promete O(n log n) inclusive para primos — mas o custo constante muda. Em protocolo de rádio, o tamanho nem é escolha sua: o padrão manda 64, 128, 256…

Onde você já usa FFT sem saber

Áudio: equalização, visualização e codecs

O equalizador gráfico do player não “mexe no waveform” amostra a amostra de forma ingênua. Em muitos pipelines, o sinal vira espectro (FFT ou banco de filtros relacionado), ganho por banda, e volta. O analisador de espectro do DAW é STFT: DFT em janelas curtas e sobrepostas. A librosa documenta isso sem rodeio: stft calcula DFTs em janelas; recomenda n_fft potência de 2 “para otimizar a velocidade da FFT”.

Nos codecs, a história é um pouco mais sutil — e mais honesta. O MP3 não é “só FFT”. O banco híbrido combina filtro polifásico com MDCT (transformada discreta de cosseno modificada) para obter linhas espectrais finas e permitir mascaramento psicoacústico. Em paralelo, o modelo perceptual do encoder clássico usa FFTs (por exemplo 1024 e 256 pontos) para estimar limiares de mascaramento. O AAC simplifica o caminho de codificação com MDCT comutada, e ainda assim o modelo psicoacústico tradicional calcula FFTs de 2048 e 256 amostras. Ou seja: o que você escuta comprimido passou por análise tempo-frequência; a FFT está no encoder mesmo quando o bitstream carrega coeficientes de outra transformada da família Fourier/cosseno.

Wi-Fi e OFDM: a FFT é o modem

No IEEE 802.11a/g (e na base dos Wi-Fis OFDM que vieram depois), os dados não vão num único portador largo. Vão em dezenas de subportadoras ortogonais. No transmissor, os símbolos modulados preenchem bins de frequência; uma IFFT de 64 pontos (no caso clássico de 20 MHz) gera o símbolo no tempo; um prefixo cíclico cola na frente. No receptor, remove-se o prefixo, faz-se a FFT de 64 pontos, equaliza-se por subportadora com ajuda dos pilots, e só então se demapeia bits.

Números que importam no 802.11a legado: espaçamento de 312,5 kHz (20 MHz / 64), período de FFT de 3,2 µs, símbolo de 4 µs com guard interval. 48 subportadoras de dados, 4 de piloto. Sem FFT/IFFT baratas e estáveis, OFDM de banda larga em silício barato não fecha. Quando o notebook associa na rede, a pilha de rádio está fazendo exatamente essa ida e volta — milhões de vezes por segundo, em hardware ou firmware.

Imagens: DCT, JPEG e o primo da FFT

O JPEG baseline não usa a FFT complexa no bitstream. Usa a DCT em blocos 8×8: energia concentrada em poucos coeficientes, quantização agressiva no que o olho perdoa, Huffman no resto. Wallace descreve o pipeline; a recomendação ITU-T T.81 / ISO JPEG formaliza FDCT e IDCT. A DCT é prima próxima da DFT: mesma família de decomposição em frequências espaciais, implementações rápidas no mesmo espírito de fatoração. Em visão computacional e em filtros de imagem, a FFT 2D aparece de forma explícita — numpy.fft.fft2 — para convolução, correlação e análise de padrões periódicos. Abrir uma foto na galeria é, em algum ponto da cadeia, transformada + quantização + entropia. A FFT ensinou a indústria a viver no domínio da frequência; a DCT é a variante que o JPEG escolheu.

Machine learning: features espectrais antes (e ainda dentro) das redes

Antes de “deep learning come espectro cru”, o padrão em fala e áudio era MFCC e afins: STFT → filtro mel → log → DCT. A librosa expõe mfcc e melspectrogram com n_fft e hop_length explícitos. Centróide espectral, rolloff, flatness — tudo parte de magnitudes de STFT. Mesmo quando o modelo engole espectrogramas como imagem, alguém calculou essas magnitudes com FFT por frame. Em sistemas de produção, essa etapa ainda é CPU/GPU barata e interpretável: você debuga um classificador de áudio olhando o espectro muito antes de olhar o gradiente.

Stacks numéricos: FFTW, NumPy, SciPy

Se o seu código chama np.fft.rfft num array de sensores, você está na ponta de uma pilha que inclui décadas de algoritmo e de engenharia de implementação. A FFTW (Frigo e Johnson) é a referência aberta de desempenho adaptativo: planeja, mede, reutiliza wisdom. O SciPy recomenda scipy.fft como conjunto mais completo; o NumPy mantém o núcleo. Em 2026, “usar FFT” quase nunca significa reimplementar Cooley–Tukey. Significa escolher tamanho de janela, taxa de amostragem e se a convolução no tempo já não seria mais clara.

Limites e armadilhas

A FFT é exata para a DFT do bloco que você passou. Ela não é um oráculo do sinal contínuo infinito. Os erros mais comuns que eu vejo — nos meus testes e nos de outras pessoas — são estes.

Janelamento e vazamento (leakage). Um bloco finito é uma multiplicação por uma janela retangular (ou Hann, Hamming, Kaiser…). No espectro, isso é convolução com o espectro da janela. Um tom puro que não cai exatamente num bin vaza energia para os vizinhos. Sidelobes altos sujam o gráfico; lóbulo principal largo mistura frequências próximas. Trocar a janela troca o compromisso: menos leakage, pior resolução, ou o inverso. Zero-padding interpola o espectro amostrado; não melhora a resolução real, que depende do comprimento efetivo da janela. Oppenheim e o material de DSP do MIT martelam isso com razão.

Aliasing. Se a taxa de amostragem não cobre o dobro da maior frequência relevante (Nyquist), frequências altas voltam disfarçadas de baixas. A FFT vai mostrar picos. Os picos estarão no lugar errado. Anti-aliasing analógico (ou oversampling + filtro digital) não é detalhe de hardware; é premissa. Sem ela, você otimiza um espectro mentiroso.

Resolução tempo × frequência. STFT com n_fft grande separa tons próximos e borra transientes. n_fft pequeno pega o ataque e mistura harmônicos. Não há um valor mágico: fala costuma querer ~20–30 ms; música, janelas maiores. A documentação da librosa deixa o trade-off explícito.

Interpretação de fase e de bin. Fase só faz sentido relativa (ao sinal, ao canal, ao piloto). Bin k corresponde a k * fs / n — até o Nyquist. Acima disso, no fft completo, você está no lado negativo, não em “frequências extras”. Confundir índice com hertz é bug silencioso.

FFT ≠ compressão. Compressão com perda (MP3, AAC, JPEG) usa transformada + modelo perceptual + quantização. Jogar fora coeficientes pequenos na mão, sem modelo, é um exercício. Não é um codec.

Por que ainda importa em 2026

Porque a física do canal e do ouvido não mudou. OFDM continua na base de Wi-Fi, 4G/5G e broadcasting digital. Codecs novos ainda vivem de análise tempo-frequência. Visão e áudio em ML ainda passam por espectrogramas ou por parentes da DFT. Aceleradores e GPUs tornaram a FFT mais presente, não menos: o custo caiu, então mais pipelines a usam como primitiva.

O que mudou é a distância entre o paper de 1965 e o import. Cooley–Tukey virou infraestrutura. FFTW e backends SIMD/GPU decidiram como fatorar para o chip da vez. O engenheiro decide se o domínio da frequência é o lugar certo para o problema — e com quais armadilhas.

Eu aposto que, daqui a dez anos, a maior parte do software que processa onda ainda terá uma FFT (ou DCT/MDCT) no caminho quente. A pergunta prática, para o seu projeto, é outra: você está olhando o espectro para entender o sinal, ou só porque um tutorial plotou abs(fft(x))? Se for a segunda, comece pela taxa de amostragem, pela janela e pelo que o bin realmente significa — antes de otimizar qualquer coisa.

Referências

• Cooley, J. W.; Tukey, J. W. “An algorithm for the machine calculation of complex Fourier series.” Mathematics of Computation 19 (1965): 297–301 — o paper que fixou a FFT na forma que a computação adotou.
• IEEE Milestone: First Demonstration of the FFT, 1964 — contexto histórico da demonstração na IBM e do impacto N log N versus N².
• NumPy: Discrete Fourier Transform (numpy.fft) — definição da DFT usada na prática, ordem dos bins, rfft e normalização.
• FFTW 3.3.11 — Introduction e Frigo, M.; Johnson, S. G. “The Design and Implementation of FFTW3.” Proc. IEEE 93 (2005) — biblioteca de referência e o planner adaptativo.
• Keysight: 802.11 OFDM WLAN Overview — parâmetros de IFFT/FFT, subportadoras e tempos de símbolo no Wi-Fi OFDM clássico.
• Brandenburg, K. “MP3 and AAC Explained.” — filterbanks, MDCT e o papel da análise espectral nos encoders MPEG.
• librosa: stft e features espectrais / MFCC — STFT como DFT em janelas e o caminho até MFCC no stack de áudio/ML.
• Wallace, G. K. “The JPEG Still Picture Compression Standard.” e ITU-T T.81 / JPEG — DCT 8×8 no JPEG e o pipeline de compressão.
• MIT OCW 6.341 — Discrete-Time Signal Processing (notas sobre windowing e aliasing) — leakage, resolução espectral e o papel do anti-aliasing.