O que o FFT realmente mostra

A pergunta

Toque um acorde num piano — digamos, C e E juntos. O teu ouvido ouve um som. Mas esse som tem duas frequências sobrepostas: 261.6 Hz e 329,6 Hz. Sua cóclea os separa fisicamente — diferentes células ciliadas ressoam em frequências diferentes, enviando sinais distintos para seu cérebro.

A Transformação Rápida de Fourier faz a mesma coisa, mas com números em vez de células ciliadas. Dê-lhe um sinal (uma sequência de amostras de amplitude ao longo do tempo) e retorna uma lista de frequências e suas forças. Responde: que frequências estão presentes, e quanto de cada?

O que realmente está acontecendo

Um sinal amostrado ao longo do tempo é uma lista de números: a amplitude em cada ponto da amostra. Uma gravação de 1 segundo a 44.100 Hz é 44.100 números. Estes números descrevem o sinal no domínio time — amplitude em função do tempo.

O FFT converte isto para o domínio frequência — amplitude em função da frequência. Mesma informação, representação diferente. Como alternar entre coordenadas cartesianas e polares: nada é criado ou destruído, apenas reexpresso.

O núcleo matemático: cada sinal periódico pode ser escrito como uma soma de ondas seno e cosseno em diferentes frequências. Este é o teorema de Fourier (1807). O FFT calcula os coeficientes dessa soma — quanto de cada frequência está no sinal.

Porquê "Rápido"

A maneira ingênua de calcular uma transformada de Fourier requer Operações N2 para amostras N. Para 1024 amostras, são cerca de 1 milhão de operações. O algoritmo Cooley-Tukey (1965) reduz isso para N·log2(N) — cerca de 10.000 operações para a mesma entrada. Uma velocidade de 100x. Para um milhão de amostras, a velocidade é de 50.000x.

O truque: dividir a N-ponto transformar em duas N/2-ponto transforma, recursivamente. Isto requer N para ser uma potência de 2 (ou você almofada com zeros). Cada divisão metade do problema. A operação "butterfly" combina as metades:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

Onde W é um complexo exponencial (uma rotação no plano complexo). Os mesmos dois sub-resultados dão-lhe dois pontos de saída. É por isso que o algoritmo é "rápido" — ele reutiliza cada computação duas vezes.

A implementação do PinePaper é um manual Cooley-Tukey radix-2 DIT (decimação no tempo). 40 linhas de JavaScript. Escrevemos do zero em vez de importar uma biblioteca porque queríamos que os alunos pudessem ler a fonte e entender cada linha.

O que significam essas barras

Quando você vê um analisador de espectro — barras pulando para a música — cada barra representa uma caixa de frequência. A altura é a magnitude (força) dessa frequência no sinal atual.

• Uma onda de seno puro produz uma barra alta em sua frequência e nada mais.
• Uma onda quadrada produz barras no fundamental e cada harmônico ímpar (3rd, 5th, 7th...), diminuindo em 1/n. É por isso que as ondas quadradas soam "buzzy" — elas contêm energia de alta frequência que os senos puros não fazem.
• ** O ruído branco** produz barras de altura aproximadamente igual em todos os lugares. Cada frequência está presente com igual probabilidade.
• Uma voz humana produz um fundamental (o tom que você ouve) mais formantes — picos ressonantes da forma do seu trato vocal que distinguem vogais.

Janelas: Por que as bordas importam

Há um senão. O FFT assume que o sinal se repete para sempre. Mas nossa amostra é finita — ela começa e pára. Se o sinal não estiver em zero em ambos os terminais, o corte abrupto cria conteúdo artificial de alta frequência. Isto é chamado de ** vazamento espectral**.

A correção: multiplicar o sinal por uma função de janela que liga suavemente a zero nas bordas. Janelas comuns:

• Hann (cosina sino): bom propósito geral, perde alguma resolução de frequência
• Hamming: semelhante a Hann, mas não atinge zero nas bordas, um pouco melhor supressão sidelobe
• ** Blackman**: lobo principal mais estreito, melhor supressão sidelobe, perde mais resolução de frequência

A escolha é sempre um tradeoff entre resolução de frequência (como precisamente você pode identificar uma frequência) e vazamento espectral (quanto energia sangra em caixas vizinhas). Não há uma janela perfeita. Isto é uma consequência do princípio da incerteza — você não pode ter conhecimento arbitrariamente preciso de tempo e frequência simultaneamente.

Onde vive o FFT

Você interage constantemente com os resultados da FFT:

• MP3 e compressão AAC: transformar áudio em domínio de frequência, descartar frequências abaixo do limiar auditivo, comprimir o que resta. A transformada é toda a base da compressão de áudio perdida.
• ** Compressão JPEG**: a versão 2D (DCT) transforma blocos de 8x8 pixels em domínio de frequência, quantifica componentes de alta frequência. É por isso que os artefactos JPEG aparecem como blocos.
• WiFi e 5G: A codificação OFDM divide dados em muitas sub-portadoras de frequência. O FFT converte entre a transmissão do domínio do tempo e os símbolos de dados do domínio da frequência.
• ** Imagens de RM**: o sinal bruto de um scanner de RM está no espaço de frequência. O inverso FFT reconstrói a imagem espacial. Literalmente: todas as ressonâncias magnéticas que já viram são uma transformada inversa de Fourier.
• Shazam: calcula o espectrograma (FFT sobre janelas deslizantes), extrai picos, corresponde ao padrão contra um banco de dados. O FFT é o primeiro passo para reconhecer cada canção.

Um algoritmo de 60 anos, no seu bolso, a correr milhares de milhões de vezes por dia.

Tenta

Abra o PinePaper, selecione o gerador Spectrum Analyzer. Gera uma onda quadrada. Olhe para as barras - você verá os harmônicos ímpares caindo como 1/n. Mude para um dente de serra — agora todos os harmônicos estão presentes, caindo como 1/n. Mudar para ruído — espectro plano, todas as frequências igualmente prováveis.

Mudar a função da janela. Veja como Hann suaviza o espectro ao custo de picos mais amplos. Mude para Blackman — picos mais estreitos, mas lóbulos laterais inferiores.

Não estás a ler sobre o FFT. Você está medindo sinais e observando o que a transformação revela. Essa é a diferença entre saber e entender.

Referências

• Brigham, E.O. (1988). * A transformação rápida de Fourier e suas aplicações*. Prentice Hall.
• == Ligações externas == Um Algoritmo para o Cálculo de Máquina da Série Complexo Fourier. * Matemática da Computação*, 19(90), 297-301.
• Fourier, J. (1822). * Théorie analytique de la chaleur*. Paris: Firmin Didot.
• Harris, F.J. (1978). Sobre o uso de Windows para análise harmônica com a transformada de Fourier discreto. Procedimentos do IEEE, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). * Processamento de Sinal em Tempo Discreto* (3rd ed.). Prentice Hall.
• Shannon, C.E. (1949). Comunicação na Presença de Ruído. Procedimentos do IRE, 37(1), 10-21.
• Smith, S.W. (1997). * Guia do cientista e engenheiro para processamento digital de sinais*. Publicações Técnicas da Califórnia.
• Wang, A., et al. (2003). Um algoritmo de pesquisa de áudio de força industrial. Procedimentos do ISMIR 2003. (Algoritmo de impressão digital de áudio do Shazam.)
• Wallace, G.K. (1991). O padrão de compressão de imagem JPEG ainda. Comunicação da ACM, 34(4), 30-44.

---

• FFT da PinePaper é uma implementação Cooley-Tukey radix-2 com janelas Hann, Hamming e Blackman, além de filtros passa-baixo e passa-alto. Experimente grátis em pinepaper.studio/editor.*