AI e Transformada de Fourier

Um guia interativo para a Transformada de Fourier

A Transformada de Fourier é um dos insights mais profundos já feitos. Infelizmente, o significado está enterrado em equações densas, que sinceramente mal entendo.

Em vez de pular para os símbolos, aqui no hurb decidimos experimentar a ideia-chave em primeira mão. Aqui vai uma metáfora simples:

• O que a Transformada de Fourier faz? Dado um smoothie, ela encontra a receita.
• Como? Passe o smoothie por filtros para extrair cada ingrediente.
• Por quê? Receitas são mais fáceis de analisar, comparar e modificar do que o próprio smoothie.
• Como recuperamos o smoothie? Misture os ingredientes.

Aqui está a versão “matemática” do texto acima:

• A Transformada de Fourier pega um padrão baseado no tempo, mede todos os ciclos possíveis e retorna a “receita do ciclo” geral (amplitude, deslocamento e velocidade de rotação para cada ciclo encontrado).

Hora das equações? Não! Vamos sujar as mãos e experimentar como qualquer padrão pode ser construído com ciclos, com simulações ao vivo.

Um guia interativo para a transformada de Fourier

A Transformada de Fourier é um dos insights mais profundos já feitos. Infelizmente, o significado está enterrado em equações densas:

Caramba. Em vez de pular para os símbolos, vamos experimentar a ideia-chave em primeira mão. Aqui vai uma metáfora em inglês simples:

• O que a Transformada de Fourier faz? Dado um smoothie, ela encontra a receita.
• Como? Passe o smoothie por filtros para extrair cada ingrediente.
• Por quê? Receitas são mais fáceis de analisar, comparar e modificar do que o próprio smoothie.
• Como recuperamos o smoothie? Misture os ingredientes.

Aqui está a versão “matemática em inglês” do texto acima:

• A Transformada de Fourier pega um padrão baseado no tempo, mede todos os ciclos possíveis e retorna a “receita do ciclo” geral (amplitude, deslocamento e velocidade de rotação para cada ciclo encontrado).

Hora das equações? Não! Vamos sujar as mãos e experimentar como qualquer padrão pode ser construído com ciclos, com simulações ao vivo.

Se tudo correr bem, teremos um momento aha! e intuitivamente perceberemos por que a Transformada de Fourier é possível. Deixaremos a análise matemática detalhada para o acompanhamento.

Esta não é uma marcha forçada através das equações, é o passeio casual que eu queria ter.

Do Smoothie à Receita

Uma transformação matemática é uma mudança de perspectiva. Mudamos nossa noção de quantidade de “itens únicos” (linhas na areia, sistema de contagem) para “grupos de 10” (decimal) dependendo do que estamos contando. Pontuando um jogo? Conte tudo. Multiplicando? Decimais, por favor.

A Transformada de Fourier muda nossa perspectiva de consumidor para produtor, transformando O que eu tenho? em Como foi feito?

Em outras palavras: dado um smoothie, vamos encontrar a receita.

Por que? Bem, as receitas são ótimas descrições de bebidas. Você não compartilharia uma análise gota a gota, você diria “Eu comi um smoothie de laranja/banana”. Uma receita é mais facilmente categorizada, comparada e modificada do que o próprio objeto.

Então… dado um smoothie, como encontramos a receita?

Bem, imagine que você tivesse alguns filtros espalhados por aí:

• Despeje no filtro “banana”. 1 onça de bananas são extraídas.
• Despeje pelo filtro “laranja”. 2 onças de laranjas.
• Despeje pelo filtro “leite”. 3 onças de leite.
• Despeje pelo filtro “água”. 3 onças de água.

Podemos fazer engenharia reversa da receita filtrando cada ingrediente. A pegada?

• Os filtros devem ser independentes . O filtro de banana precisa capturar bananas e nada mais. Adicionar mais laranjas nunca deve afetar a leitura da banana.
• Os filtros devem ser completos . Não obteremos a receita real se deixarmos de fora um filtro (“Havia mangas também!”). Nossa coleção de filtros deve capturar todos os ingredientes possíveis.
• Os ingredientes devem ser combináveis . Smoothies podem ser separados e re-combinados sem problemas (Um biscoito? Nem tanto. Quem quer migalhas?). Os ingredientes, quando separados e combinados em qualquer ordem, devem dar o mesmo resultado.

Veja o mundo como ciclos

A Transformada de Fourier adota um ponto de vista específico: e se qualquer sinal pudesse ser filtrado em vários caminhos circulares?

Uau. Este conceito é alucinante, e o pobre Joseph Fourier teve sua ideia rejeitada a princípio.

E apesar de décadas de debate na comunidade matemática, esperamos que os alunos internalizem a ideia sem problemas. Vamos percorrer a intuição.

A Transformada de Fourier encontra a receita para um sinal, como nosso processo de smoothie:

• Comece com um sinal baseado em tempo
• Aplique filtros para medir cada possível “ingrediente circular”
• Colete a receita completa, listando a quantidade de cada “ingrediente circular”

Pare. É aqui que a maioria dos tutoriais jogam aplicações de engenharia na sua cara, animadamente. Não se assuste; pense nos exemplos como “Uau, finalmente estamos vendo o código-fonte (DNA) por trás de ideias antes confusas”.

• Se as vibrações dos terremotos puderem ser separadas em “ingredientes” (vibrações de diferentes velocidades e amplitudes), os edifícios podem ser projetados para evitar a interação com as mais fortes.
• Se as ondas sonoras puderem ser separadas em ingredientes (frequências graves e agudas), podemos aumentar as partes que nos interessam e esconder as que não nos interessam. O estalo do ruído aleatório pode ser removido. Talvez “receitas sonoras” semelhantes possam ser comparadas (serviços de reconhecimento de música comparam receitas, não os clipes de áudio brutos).
• Se os dados do computador podem ser representados com padrões oscilantes, talvez os menos importantes possam ser ignorados. Essa “compressão com perdas” pode reduzir drasticamente o tamanho dos arquivos (e por que os arquivos JPEG e MP3 são muito menores do que os arquivos .bmp ou .wav brutos).
• Se uma onda de rádio é o nosso sinal, podemos usar filtros para ouvir um canal em particular. No mundo dos smoothies, imagine que cada pessoa prestou atenção a um ingrediente diferente: Adam procura maçãs, Bob procura bananas e Charlie pega couve-flor (desculpe, broto).

A Transformada de Fourier é útil na engenharia, claro, mas é uma metáfora sobre encontrar as causas raízes por trás de um efeito observado.

Pense com círculos, não apenas com sinusóides

Uma das minhas confusões gigantescas foi separar as definições de “sinusóide” e “círculo”.

• Uma “senoide” é um padrão específico de vaivém (uma onda senoidal ou cosseno) e, 99% das vezes, refere-se ao movimento em uma dimensão.
• Um “círculo” é um padrão redondo, 2d, que você provavelmente conhece. Se você gosta de usar palavras de 10 dólares para descrever ideias de 10 centavos, você pode chamar um caminho circular de “senoide complexo”.

Rotular um caminho circular como uma “sinuóide complexa” é como descrever uma palavra como uma “letra múltipla”. Você ampliou o nível de detalhe errado. As palavras são sobre conceitos, não sobre as letras em que podem ser divididas!

A Transformada de Fourier trata de caminhos circulares (não sinusoides unidimensionais) e a fórmula de Euler é uma maneira inteligente de gerar uma:

Devemos usar expoentes imaginários para nos movermos em círculo? Não. Mas é conveniente e compacto. E claro, podemos descrever nosso caminho como um movimento coordenado em duas dimensões (real e imaginária), mas não se esqueça do panorama geral: estamos apenas nos movendo em círculo.

Seguindo Caminhos Circulares

Digamos que estamos conversando ao telefone e, como de costume, quero que desenhem o mesmo círculo simultaneamente. ( Você prometeu! ) O que devo dizer?

• Qual é o tamanho do círculo? (Amplitude, ou seja, tamanho do raio)
• Com que rapidez o desenhamos? (Frequência. 1 círculo/segundo é uma frequência de 1 Hertz (Hz) ou 2*pi radianos/s)
• Por onde começamos? (Ângulo de fase, onde 0 graus é o eixo x)

Eu poderia dizer “raio de 2 polegadas, comece em 45 graus, 1 círculo por segundo, vá!”. Depois de meio segundo, cada um de nós deve estar apontando para: ponto de partida + quantidade percorrida = 45 + 180 = 225 graus (em um círculo de 2 polegadas).

Cada caminho circular precisa de um tamanho, velocidade e ângulo inicial (amplitude/frequência/fase). Podemos até combinar caminhos: imagine pequenos automóveis, dirigindo em círculos em velocidades diferentes.

A posição combinada de todos os ciclos é o nosso sinal, assim como o sabor combinado de todos os ingredientes é o nosso smoothie.

Aqui está uma simulação de um caminho circular básico:

(Com base nesta animação , aqui está o código-fonte . É necessário um navegador moderno. Clique no gráfico para pausar/retomar.)

A magnitude de cada ciclo é listada em ordem, começando em 0Hz. Ciclos [0 1]significa

• 0 amplitude para o ciclo de 0 Hz (0 Hz = um ciclo constante, preso no eixo x em zero graus)
• 1 amplitude para o ciclo de 1 Hz (completa 1 ciclo por intervalo de tempo)

Agora a parte complicada:

• O gráfico azul mede a parte real do ciclo . Outra bela confusão matemática: o eixo real do círculo, que geralmente é horizontal, tem sua magnitude mostrada no eixo vertical. Você pode girar mentalmente o círculo em 90 graus, se desejar.
• Os pontos de tempo são espaçados na frequência mais rápida . Um sinal de 1 Hz precisa de 2 pontos de tempo para iniciar e parar (um único ponto de dados não tem frequência). Os valores de tempo [1 -1]mostram a amplitude nesses intervalos igualmente espaçados.

Comigo? [0 1]é um ciclo puro de 1 Hz.

Agora vamos adicionar um ciclo de 2 Hz à mistura. [0 1 1]significa "Nada em 0 Hz, 1 Hz de amplitude 1, 2 Hz de amplitude 1":

Uau. Os pequenos automóveis estão ficando selvagens: as linhas verdes são os ciclos de 1 Hz e 2 Hz, e a linha azul é o resultado combinado. Tente alternar a caixa de seleção verde para ver o resultado final com clareza. O “sabor” combinado é uma oscilação que começa no máximo e diminui durante o resto do intervalo.

Os pontos amarelos são quando realmente medimos o sinal. Com 3 ciclos definidos (0Hz, 1Hz, 2Hz), cada ponto é 1/3 do caminho através do sinal. Neste caso, os ciclos [0 1 1]geram os valores de tempo [2 -1 -1], que começam no máximo (2) e caem para baixo (-1).

Ah! Não podemos esquecer da fase, o ângulo inicial! Use magnitude:anglepara definir a fase. Então [0 1:45]é um ciclo de 1Hz que começa em 45 graus:

Esta é uma versão alterada do [0 1]. No lado do tempo, obtemos [.7 -.7]em vez de [1 -1], porque nosso ciclo não está exatamente alinhado com nossos intervalos de medição, que ainda estão na metade do caminho (isso poderia ser desejado!).

A Transformada de Fourier encontra o conjunto de velocidades, amplitudes e fases do ciclo para corresponder a qualquer sinal de tempo.

Nosso sinal se torna uma noção abstrata que consideramos como “observações no domínio do tempo” ou “ingredientes no domínio da frequência”.

Chega de conversa: experimente! No simulador, digite qualquer padrão de tempo ou ciclo que você gostaria de ver. Se forem pontos de tempo, você obterá uma coleção de ciclos (que se combinam em uma “onda”) que correspondem aos seus pontos desejados.

Mas… a onda combinada não tem valores estranhos entre os intervalos de tempo amarelos? Claro. Mas quem pode dizer se um sinal viaja em linhas retas, ou curvas, ou voa para outras dimensões quando não o estamos medindo? Ele se comporta exatamente como precisamos nos momentos igualmente espaçados que pedimos.

Fazendo um pico no tempo

Podemos aumentar o tempo, como (4 0 0 0), usando ciclos? Usarei parênteses ()para uma sequência de pontos no tempo e colchetes []para uma sequência de ciclos.

Embora o pico pareça enfadonho para nós, moradores do tempo ( um ponto de dados, é isso? ), pense na complexidade do mundo dos ciclos. Os ingredientes do nosso ciclo devem começar alinhados (no valor máximo, 4) e depois “explodir para fora”, cada ciclo com parceiros que o cancelam no futuro. Cada ponto restante é zero, o que é um equilíbrio complicado com vários ciclos em execução (não podemos simplesmente “desligá-los”).

Vamos examinar cada ponto no tempo:

• No tempo 0, o primeiro instante, cada ingrediente do ciclo está no máximo. Ignorando os demais pontos de tempo, (4 ? ? ?)podem ser feitos 4 ciclos (0Hz 1Hz 2Hz 3Hz), cada um com magnitude 1 e fase 0 (ou seja, 1 + 1 + 1 + 1 = 4).
• Em cada ponto futuro (t = 1, 2, 3), a soma de todos os ciclos deve ser cancelada.

Aqui está o truque: quando dois ciclos estão em lados opostos do círculo (Norte e Sul, Leste e Oeste, etc.), sua posição combinada é zero (3 ciclos podem ser cancelados se estiverem espalhados uniformemente em 0, 120 e 240 graus ).

Imagine uma constelação de pontos movendo-se ao redor do círculo. Aqui está a posição de cada ciclo em cada instante:

Tempo 0 1 2 3
------------
0 Hz: 0 0 0 0
1Hz: 0 1 2 3
2Hz: 0 2 0 2
3Hz: 0 3 2 1

Observe como o ciclo de 3 Hz começa em 0, chega à posição 3, depois à posição “6” (com apenas 4 posições, 6 módulo 4 = 2), depois à posição “9” (9 módulo 4 = 1).

Quando nosso ciclo tem 4 unidades de comprimento, as velocidades do ciclo separadas por meio ciclo (2 unidades) serão alinhadas (diferença de 0, 4, 8…) ou em lados opostos (diferença de 2, 6, 10…).

OK. Vamos detalhar cada ponto no tempo:

• Tempo 0: Todos os ciclos no máximo (total de 4)
• Tempo 1: 1Hz e 3Hz cancelam (posições 1 e 3 são opostas), 0Hz e 2Hz cancelam também. A rede é 0.
• Tempo 2: 0Hz e 2Hz se alinham na posição 0, enquanto 1Hz e 3Hz se alinham na posição 2 (o lado oposto). O total ainda é 0.
• Tempo 3: cancelamento de 0 Hz e 2 Hz. Cancelamento de 1 Hz e 3 Hz.
• Tempo 4 (repetição de t=0): Todos os ciclos se alinham.

O truque é cancelar as velocidades individuais (0 Hz vs 2 Hz, 1 Hz vs 3 Hz) ou cancelar os pares alinhados (0 Hz + 2 Hz vs 1 Hz + 3 Hz).

Quando cada ciclo tem potência igual e fase 0, começamos alinhados e cancelamos depois. (Ainda não tenho uma boa prova — alguém se interessa? — mas você pode ver por si mesmo. Tente [1 1], [1 1 1], [1 1 1 1]e observe os sinais que geramos: (2 0), (3 0 0), (4 0 0 0)).

Na minha cabeça, eu rotulo esses sinais como “picos de tempo”: eles têm um valor para um único instante e são zero em outros casos (o nome chique é função delta ).

Veja como eu e meu colega enxergamos o alinhamento inicial, seguido por um cancelamento líquido:

Movendo o pico do tempo

Nem tudo acontece em t=0. Podemos mudar nosso pico para (0 4 0 0)?

Parece que os ingredientes do ciclo devem ser similares a (4 0 0 0), mas os ciclos devem se alinhar em t=1 (um segundo no futuro). É aqui que a fase entra.

Imagine uma corrida com 4 corredores. As corridas normais têm todos alinhados na linha de partida, o (4 0 0 0)padrão de tempo. Tedioso.

E se quisermos que todos terminem ao mesmo tempo? Fácil. Basta mover as pessoas para frente ou para trás na distância apropriada. Talvez a vovó possa começar 2 pés à frente da linha de chegada, Usain Bolt possa começar 100 metros atrás e eles possam cruzar a fita de mãos dadas.

As mudanças de fase, o ângulo inicial, são atrasos no universo do ciclo. Veja como ajustamos a posição inicial para atrasar cada ciclo em 1 segundo:

• Um ciclo de 0 Hz não se move, então já está alinhado
• Um ciclo de 1Hz faz 1 revolução em todos os 4 segundos, então um atraso de 1 segundo é um quarto de volta. Desloque a fase 90 graus para trás (-90) e ele chega a fase=0, o valor máximo, em t=1.
• Um ciclo de 2 Hz é duas vezes mais rápido, então dê a ele o dobro do ângulo para cobrir (mudança de fase de -180 ou 180 — é através do círculo, de qualquer maneira).
• Um ciclo de 3 Hz é 3x mais rápido, então dê a ele 3x a distância para se mover (deslocamento de fase de -270 ou +90)

Se os pontos de tempo (4 0 0 0)são feitos de ciclos [1 1 1 1], então os pontos de tempo (0 4 0 0)são feitos de [1 1:-90 1:180 1:90]. (Observação: estou usando "1 Hz", mas quero dizer "1 ciclo durante todo o período de tempo").

Uau, estamos resolvendo os ciclos em nossas cabeças!

A visualização da interferência é semelhante, exceto que o alinhamento está em t=1.

Teste sua intuição: você consegue fazer (0 0 4 0), ou seja, um atraso de 2 segundos? 0Hz não tem fase. 1 Hz tem 180 graus, 2 Hz tem 360 (também conhecido como 0) e 3 Hz tem 540 (também conhecido como 180), então é [1 1:180 1 1:180].

Descobrindo a transformação completa

O grande insight: nosso sinal é apenas um monte de picos de tempo! Se mesclarmos as receitas para cada pico de tempo, devemos obter a receita para o sinal completo.

A Transformada de Fourier constrói a receita frequência por frequência:

• Separe o sinal completo (abcd) em “picos de tempo”: (a 0 0 0) (0 b 0 0) (0 0 c 0) (0 0 0 d)
• Para qualquer frequência (como 2 Hz), a receita provisória é “a/4 + b/4 + c/4 + d/4” (a amplitude de cada pico é dividida entre todas as frequências)
• Espere! Precisamos compensar cada pico com um atraso de fase (o ângulo para um “atraso de 1 segundo” depende da frequência).
• Receita real para uma frequência = a/4 (sem deslocamento) + b/4 (deslocamento de 1 segundo) + c/4 (deslocamento de 2 segundos) + d/4 (deslocamento de 3 segundos).

Podemos então percorrer cada frequência para obter a transformação completa.

Aqui está a conversão de “math English” para matemática completa:

Algumas notas:

• N = número de amostras de tempo que temos
• n = amostra atual que estamos considerando (0 .. N-1)
• x n = valor do sinal no tempo n
• k = frequência atual que estamos considerando (0 Hertz até N-1 Hertz)
• X k = quantidade de frequência k no sinal (amplitude e fase, um número complexo)
• O fator 1/N é geralmente movido para a transformação reversa (indo de frequências de volta para o tempo). Isso é permitido , embora eu prefira 1/N na transformação direta, pois ele fornece os tamanhos reais para os picos de tempo. Você pode ficar selvagem e até mesmo usar1/Nãoem ambas as transformações (avançar e voltar cria o fator 1/N).
• n/N é a porcentagem do tempo que passamos. 2 * pi * k é a nossa velocidade em radianos/s. e^-ix é nosso caminho circular que se move para trás. A combinação é o quão longe avançamos, nesta velocidade e tempo.
• As equações brutas para a Transformada de Fourier dizem apenas “adicionar os números complexos”. Muitas linguagens de programação não conseguem lidar diretamente com números complexos, então você converte tudo em coordenadas retangulares e as soma.

Avante

Este foi meu artigo mais desafiador até agora. A Transformada de Fourier tem vários sabores (discreta/contínua/finita/infinita), abrange matemática profunda (funções delta de Dirac) e é fácil se perder em detalhes. Eu estava constantemente esbarrando no limite do meu conhecimento.

Mas sempre há analogias simples por aí — eu me recuso a pensar o contrário. Seja um smoothie ou Usain Bolt e a vovó cruzando a linha de chegada, pegue um entendimento simples e refine-o. A analogia é falha, e tudo bem: é uma jangada para usar e deixar para trás quando cruzarmos o rio.

Percebi o quão fraca era minha compreensão quando não conseguia entender a transformação (1 0 0 0)em minha cabeça. Para mim, era como dizer que sabia adição, mas, caramba, não tenho certeza do que seria "1 + 1 + 1 + 1". Por que não? Não deveríamos ter intuição para as operações mais simples?

Esse desconforto me levou a navegar na web para construir minha intuição. Além das referências no artigo, gostaria de agradecer:

• Scott Young , pelo impulso inicial para esta postagem
• Shaheen Gandhi , Roger Cheng e Brit Cruise por apresentarem ideias e refinarem a analogia
• Steve Lehar pelos ótimos exemplos da Transformada de Fourier em imagens
• Charan Langton por seu passo a passo detalhado
• Julius Smith por um fantástico passo a passo da Transformada Discreta de Fourier (o que abordamos hoje)
• Bret Victor por suas técnicas de visualização da aprendizagem

O objetivo de hoje era experimentar a Transformada de Fourier. Salvaremos a análise avançada para a próxima vez.

Feliz matemática.

Apêndice: Projetando em Ciclos

Stuart Riffle tem uma ótima interpretação da Transformada de Fourier:

Imagine girar seu sinal em uma centrífuga e verificar se há tendência. Tenho uma correção: devemos girar para trás (o expoente na equação acima deveria ser𝑒−eu2𝜋…). Você já sabe por quê: precisamos de um atraso de fase para que os picos apareçam no futuro .

Apêndice: Outra visualização incrível

Lucas Vieira , autor de excelentes animações da Wikipédia , se inspirou para fazer esta animação interativa:

Fourier Toy — Clique para baixar, requer flash

( Lista detalhada de opções de controle)

A Transformada de Fourier é sobre ciclos adicionados a ciclos adicionados a ciclos. Tente fazer um “pico de tempo” definindo uma amplitude de 1 para cada componente (pressione Enter após inserir cada número). Fato curioso: com termos suficientes, você pode desenhar qualquer forma, até mesmo Homer Simpson .

Se tudo correr bem, teremos um momento aha! e intuitivamente perceberemos por que a Transformada de Fourier é possível. Deixaremos a análise matemática detalhada para o acompanhamento.

Esta não é uma marcha forçada através das equações, é o passeio casual que eu queria ter. Avante!

Do Smoothie à Receita

Uma transformação matemática é uma mudança de perspectiva. Mudamos nossa noção de quantidade de “itens únicos” (linhas na areia, sistema de contagem) para “grupos de 10” (decimal) dependendo do que estamos contando. Pontuando um jogo? Conte tudo. Multiplicando? Decimais, por favor.

A Transformada de Fourier muda nossa perspectiva de consumidor para produtor, transformando O que eu tenho? em Como foi feito?

Em outras palavras: dado um smoothie, vamos encontrar a receita.

Por que? Bem, as receitas são ótimas descrições de bebidas. Você não compartilharia uma análise gota a gota, você diria “Eu comi um smoothie de laranja/banana”. Uma receita é mais facilmente categorizada, comparada e modificada do que o próprio objeto.

Então… dado um smoothie, como encontramos a receita?

Bem, imagine que você tivesse alguns filtros espalhados por aí:

• Despeje no filtro “banana”. 1 onça de bananas são extraídas.
• Despeje pelo filtro “laranja”. 2 onças de laranjas.
• Despeje pelo filtro “leite”. 3 onças de leite.
• Despeje pelo filtro “água”. 3 onças de água.

Podemos fazer engenharia reversa da receita filtrando cada ingrediente. A pegada?

• Os filtros devem ser independentes . O filtro de banana precisa capturar bananas e nada mais. Adicionar mais laranjas nunca deve afetar a leitura da banana.
• Os filtros devem ser completos . Não obteremos a receita real se deixarmos de fora um filtro (“Havia mangas também!”). Nossa coleção de filtros deve capturar todos os ingredientes possíveis.
• Os ingredientes devem ser combináveis . Smoothies podem ser separados e recombinados sem problemas (Um biscoito? Nem tanto. Quem quer migalhas?). Os ingredientes, quando separados e combinados em qualquer ordem, devem dar o mesmo resultado.

Veja o mundo como ciclos

A Transformada de Fourier adota um ponto de vista específico: e se qualquer sinal pudesse ser filtrado em vários caminhos circulares?

Uau. Este conceito é alucinante, e o pobre Joseph Fourier teve sua ideia rejeitada a princípio. ( Sério, Joe, até mesmo um padrão de escada pode ser feito a partir de círculos? )

E apesar de décadas de debate na comunidade matemática, esperamos que os alunos internalizem a ideia sem problemas. Ugh. Vamos percorrer a intuição.

A Transformada de Fourier encontra a receita para um sinal, como nosso processo de smoothie:

• Comece com um sinal baseado em tempo
• Aplique filtros para medir cada possível “ingrediente circular”
• Colete a receita completa, listando a quantidade de cada “ingrediente circular”

Pare. É aqui que a maioria dos tutoriais jogam aplicações de engenharia na sua cara, animadamente. Não se assuste; pense nos exemplos como “Uau, finalmente estamos vendo o código-fonte (DNA) por trás de ideias antes confusas”.

• Se as vibrações dos terremotos puderem ser separadas em “ingredientes” (vibrações de diferentes velocidades e amplitudes), os edifícios podem ser projetados para evitar a interação com as mais fortes.
• Se as ondas sonoras puderem ser separadas em ingredientes (frequências graves e agudas), podemos aumentar as partes que nos interessam e esconder as que não nos interessam. O estalo do ruído aleatório pode ser removido. Talvez “receitas sonoras” semelhantes possam ser comparadas (serviços de reconhecimento de música comparam receitas, não os clipes de áudio brutos).
• Se os dados do computador podem ser representados com padrões oscilantes, talvez os menos importantes possam ser ignorados. Essa “compressão com perdas” pode reduzir drasticamente o tamanho dos arquivos (e por que os arquivos JPEG e MP3 são muito menores do que os arquivos .bmp ou .wav brutos).
• Se uma onda de rádio é o nosso sinal, podemos usar filtros para ouvir um canal em particular. No mundo dos smoothies, imagine que cada pessoa prestou atenção a um ingrediente diferente: Adam procura maçãs, Bob procura bananas e Charlie pega couve-flor (desculpe, broto).

A Transformada de Fourier é útil na engenharia, claro, mas é uma metáfora sobre encontrar as causas raízes por trás de um efeito observado.

Pense com círculos, não apenas com sinusóides

Uma das minhas confusões gigantescas foi separar as definições de “sinusóide” e “círculo”.

• Uma “senoide” é um padrão específico de vaivém (uma onda senoidal ou cosseno) e, 99% das vezes, refere-se ao movimento em uma dimensão.
• Um “círculo” é um padrão redondo, 2d, que você provavelmente conhece. Se você gosta de usar palavras de 10 dólares para descrever ideias de 10 centavos, você pode chamar um caminho circular de “senoide complexo”.

Rotular um caminho circular como uma “sinuóide complexa” é como descrever uma palavra como uma “letra múltipla”. Você ampliou o nível de detalhe errado. As palavras são sobre conceitos, não sobre as letras em que podem ser divididas!

A Transformada de Fourier trata de caminhos circulares (não sinusoides unidimensionais) e a fórmula de Euler é uma maneira inteligente de gerar uma:

Devemos usar expoentes imaginários para nos movermos em círculo? Não. Mas é conveniente e compacto. E claro, podemos descrever nosso caminho como um movimento coordenado em duas dimensões (real e imaginária), mas não se esqueça do panorama geral: estamos apenas nos movendo em círculo.

Seguindo Caminhos Circulares

Digamos que estamos conversando ao telefone e, como de costume, quero que desenhem o mesmo círculo simultaneamente. ( Você prometeu! ) O que devo dizer?

• Qual é o tamanho do círculo? (Amplitude, ou seja, tamanho do raio)
• Com que rapidez o desenhamos? (Frequência. 1 círculo/segundo é uma frequência de 1 Hertz (Hz) ou 2*pi radianos/s)
• Por onde começamos? (Ângulo de fase, onde 0 graus é o eixo x)

Eu poderia dizer “raio de 2 polegadas, comece em 45 graus, 1 círculo por segundo, vá!”. Depois de meio segundo, cada um de nós deve estar apontando para: ponto de partida + quantidade percorrida = 45 + 180 = 225 graus (em um círculo de 2 polegadas).

Cada caminho circular precisa de um tamanho, velocidade e ângulo inicial (amplitude/frequência/fase). Podemos até combinar caminhos: imagine pequenos automóveis, dirigindo em círculos em velocidades diferentes.

A posição combinada de todos os ciclos é o nosso sinal, assim como o sabor combinado de todos os ingredientes é o nosso smoothie.

Aqui está uma simulação de um caminho circular básico:

(Com base nesta animação , aqui está o código-fonte . É necessário um navegador moderno. Clique no gráfico para pausar/retomar.)

A magnitude de cada ciclo é listada em ordem, começando em 0Hz. Ciclos [0 1]significa

• 0 amplitude para o ciclo de 0 Hz (0 Hz = um ciclo constante, preso no eixo x em zero graus)
• 1 amplitude para o ciclo de 1 Hz (completa 1 ciclo por intervalo de tempo)

Agora a parte complicada:

• O gráfico azul mede a parte real do ciclo . Outra bela confusão matemática: o eixo real do círculo, que geralmente é horizontal, tem sua magnitude mostrada no eixo vertical. Você pode girar mentalmente o círculo em 90 graus, se desejar.
• Os pontos de tempo são espaçados na frequência mais rápida . Um sinal de 1 Hz precisa de 2 pontos de tempo para iniciar e parar (um único ponto de dados não tem frequência). Os valores de tempo [1 -1]mostram a amplitude nesses intervalos igualmente espaçados.

Comigo? [0 1]é um ciclo puro de 1 Hz.

Agora vamos adicionar um ciclo de 2 Hz à mistura. [0 1 1]significa "Nada em 0 Hz, 1 Hz de amplitude 1, 2 Hz de amplitude 1":

Os pequenos automóveis estão ficando selvagens: as linhas verdes são os ciclos de 1 Hz e 2 Hz, e a linha azul é o resultado combinado. Tente alternar a caixa de seleção verde para ver o resultado final com clareza. O “sabor” combinado é uma oscilação que começa no máximo e diminui durante o resto do intervalo.

Os pontos amarelos são quando realmente medimos o sinal. Com 3 ciclos definidos (0Hz, 1Hz, 2Hz), cada ponto é 1/3 do caminho através do sinal. Neste caso, os ciclos [0 1 1]geram os valores de tempo [2 -1 -1], que começam no máximo (2) e caem para baixo (-1).

Ah! Não podemos esquecer da fase, o ângulo inicial! Use magnitude:anglepara definir a fase. Então [0 1:45]é um ciclo de 1Hz que começa em 45 graus:

Esta é uma versão alterada do [0 1]. No lado do tempo, obtemos [.7 -.7]em vez de [1 -1], porque nosso ciclo não está exatamente alinhado com nossos intervalos de medição, que ainda estão na metade do caminho (isso poderia ser desejado!).

A Transformada de Fourier encontra o conjunto de velocidades, amplitudes e fases do ciclo para corresponder a qualquer sinal de tempo.

Nosso sinal se torna uma noção abstrata que consideramos como “observações no domínio do tempo” ou “ingredientes no domínio da frequência”.

Chega de conversa: experimente! No simulador, digite qualquer padrão de tempo ou ciclo que você gostaria de ver. Se forem pontos de tempo, você obterá uma coleção de ciclos (que se combinam em uma “onda”) que correspondem aos seus pontos desejados.

Mas… a onda combinada não tem valores estranhos entre os intervalos de tempo amarelos? Claro. Mas quem pode dizer se um sinal viaja em linhas retas, ou curvas, ou voa para outras dimensões quando não o estamos medindo? Ele se comporta exatamente como precisamos nos momentos igualmente espaçados que pedimos.

Fazendo um pico no tempo

Podemos aumentar o tempo, como (4 0 0 0), usando ciclos? Usarei parênteses ()para uma sequência de pontos no tempo e colchetes []para uma sequência de ciclos.

Embora o pico pareça enfadonho para nós, moradores do tempo ( um ponto de dados, é isso? ), pense na complexidade do mundo dos ciclos. Os ingredientes do nosso ciclo devem começar alinhados (no valor máximo, 4) e depois “explodir para fora”, cada ciclo com parceiros que o cancelam no futuro. Cada ponto restante é zero, o que é um equilíbrio complicado com vários ciclos em execução (não podemos simplesmente “desligá-los”).

Vamos examinar cada ponto no tempo:

• No tempo 0, o primeiro instante, cada ingrediente do ciclo está no máximo. Ignorando os demais pontos de tempo, (4 ? ? ?)podem ser feitos 4 ciclos (0Hz 1Hz 2Hz 3Hz), cada um com magnitude 1 e fase 0 (ou seja, 1 + 1 + 1 + 1 = 4).
• Em cada ponto futuro (t = 1, 2, 3), a soma de todos os ciclos deve ser cancelada.

Aqui está o truque: quando dois ciclos estão em lados opostos do círculo (Norte e Sul, Leste e Oeste, etc.), sua posição combinada é zero (3 ciclos podem ser cancelados se estiverem espalhados uniformemente em 0, 120 e 240 graus ).

Imagine uma constelação de pontos movendo-se ao redor do círculo. Aqui está a posição de cada ciclo em cada instante:

Tempo 0 1 2 3
------------
0 Hz: 0 0 0 0
1Hz: 0 1 2 3
2Hz: 0 2 0 2
3Hz: 0 3 2 1

Observe como o ciclo de 3 Hz começa em 0, chega à posição 3, depois à posição “6” (com apenas 4 posições, 6 módulo 4 = 2), depois à posição “9” (9 módulo 4 = 1).

Quando nosso ciclo tem 4 unidades de comprimento, as velocidades do ciclo separadas por meio ciclo (2 unidades) serão alinhadas (diferença de 0, 4, 8…) ou em lados opostos (diferença de 2, 6, 10…).

OK. Vamos detalhar cada ponto no tempo:

• Tempo 0: Todos os ciclos no máximo (total de 4)
• Tempo 1: 1Hz e 3Hz cancelam (posições 1 e 3 são opostas), 0Hz e 2Hz cancelam também. A rede é 0.
• Tempo 2: 0Hz e 2Hz se alinham na posição 0, enquanto 1Hz e 3Hz se alinham na posição 2 (o lado oposto). O total ainda é 0.
• Tempo 3: cancelamento de 0 Hz e 2 Hz. Cancelamento de 1 Hz e 3 Hz.
• Tempo 4 (repetição de t=0): Todos os ciclos se alinham.

O truque é cancelar as velocidades individuais (0 Hz vs 2 Hz, 1 Hz vs 3 Hz) ou cancelar os pares alinhados (0 Hz + 2 Hz vs 1 Hz + 3 Hz).

Quando cada ciclo tem potência igual e fase 0, começamos alinhados e cancelamos depois. (Ainda não tenho uma boa prova — alguém se interessa? — mas você pode ver por si mesmo. Tente [1 1], [1 1 1], [1 1 1 1]e observe os sinais que geramos: (2 0), (3 0 0), (4 0 0 0)).

Na minha cabeça, eu rotulo esses sinais como “picos de tempo”: eles têm um valor para um único instante e são zero em outros casos (o nome chique é função delta ).

Veja como visualizo o alinhamento inicial, seguido por um cancelamento líquido:

Movendo o pico do tempo

Nem tudo acontece em t=0. Podemos mudar nosso pico para (0 4 0 0)?

Parece que os ingredientes do ciclo devem ser similares a (4 0 0 0), mas os ciclos devem se alinhar em t=1 (um segundo no futuro). É aqui que a fase entra.

Imagine uma corrida com 4 corredores. As corridas normais têm todos alinhados na linha de partida, o (4 0 0 0)padrão de tempo. Tedioso.

E se quisermos que todos terminem ao mesmo tempo? Fácil. Basta mover as pessoas para frente ou para trás na distância apropriada. Talvez a vovó possa começar 2 pés à frente da linha de chegada, Usain Bolt possa começar 100 metros atrás e eles possam cruzar a fita de mãos dadas.

As mudanças de fase, o ângulo inicial, são atrasos no universo do ciclo. Veja como ajustamos a posição inicial para atrasar cada ciclo em 1 segundo:

• Um ciclo de 0 Hz não se move, então já está alinhado
• Um ciclo de 1Hz faz 1 revolução em todos os 4 segundos, então um atraso de 1 segundo é um quarto de volta. Desloque a fase 90 graus para trás (-90) e ele chega a fase=0, o valor máximo, em t=1.
• Um ciclo de 2 Hz é duas vezes mais rápido, então dê a ele o dobro do ângulo para cobrir (mudança de fase de -180 ou 180 — é através do círculo, de qualquer maneira).
• Um ciclo de 3 Hz é 3x mais rápido, então dê a ele 3x a distância para se mover (deslocamento de fase de -270 ou +90)

Se os pontos de tempo (4 0 0 0)são feitos de ciclos [1 1 1 1], então os pontos de tempo (0 4 0 0)são feitos de [1 1:-90 1:180 1:90]. (Observação: estou usando "1 Hz", mas quero dizer "1 ciclo durante todo o período de tempo").

Uau, estamos resolvendo os ciclos em nossas cabeças!

A visualização da interferência é semelhante, exceto que o alinhamento está em t=1.

Teste sua intuição: você consegue fazer (0 0 4 0), ou seja, um atraso de 2 segundos? 0Hz não tem fase. 1 Hz tem 180 graus, 2 Hz tem 360 (também conhecido como 0) e 3 Hz tem 540 (também conhecido como 180), então é [1 1:180 1 1:180].

Descobrindo a transformação completa

O grande insight: nosso sinal é apenas um monte de picos de tempo! Se mesclarmos as receitas para cada pico de tempo, devemos obter a receita para o sinal completo.

A Transformada de Fourier constrói a receita frequência por frequência:

• Separe o sinal completo (abcd) em “picos de tempo”: (a 0 0 0) (0 b 0 0) (0 0 c 0) (0 0 0 d)
• Para qualquer frequência (como 2 Hz), a receita provisória é “a/4 + b/4 + c/4 + d/4” (a amplitude de cada pico é dividida entre todas as frequências)
• Espere! Precisamos compensar cada pico com um atraso de fase (o ângulo para um “atraso de 1 segundo” depende da frequência).
• Receita real para uma frequência = a/4 (sem deslocamento) + b/4 (deslocamento de 1 segundo) + c/4 (deslocamento de 2 segundos) + d/4 (deslocamento de 3 segundos).

Podemos então percorrer cada frequência para obter a transformação completa.

Aqui está a conversão de “math English” para matemática completa:

Algumas notas:

• N = número de amostras de tempo que temos
• n = amostra atual que estamos considerando (0 .. N-1)
• x n = valor do sinal no tempo n
• k = frequência atual que estamos considerando (0 Hertz até N-1 Hertz)
• X k = quantidade de frequência k no sinal (amplitude e fase, um número complexo)
• O fator 1/N é geralmente movido para a transformação reversa (indo de frequências de volta para o tempo). Isso é permitido , embora eu prefira 1/N na transformação direta, pois ele fornece os tamanhos reais para os picos de tempo. Você pode ficar selvagem e até mesmo usar1/Não em ambas as transformações (avançar e voltar cria o fator 1/N).
• n/N é a porcentagem do tempo que passamos. 2 * pi * k é a nossa velocidade em radianos/s. e^-ix é nosso caminho circular que se move para trás. A combinação é o quão longe avançamos, nesta velocidade e tempo.
• As equações brutas para a Transformada de Fourier dizem apenas “adicionar os números complexos”. Muitas linguagens de programação não conseguem lidar diretamente com números complexos, então você converte tudo em coordenadas retangulares e as soma.

Apêndice: Projetando em Ciclos

Stuart Riffle tem uma ótima interpretação da Transformada de Fourier:

Imagine girar seu sinal em uma centrífuga e verificar se há tendência. Tenho uma correção: devemos girar para trás (o expoente na equação acima deveria ser𝑒−eu2𝜋…). Você já sabe por quê: precisamos de um atraso de fase para que os picos apareçam no futuro .

Apêndice: Outra visualização incrível

Lucas Vieira , autor de excelentes animações da Wikipédia , se inspirou para fazer esta animação interativa:

Fourier Toy — Clique para baixar, requer flash

( Lista detalhada de opções de controle)

A Transformada de Fourier é sobre ciclos adicionados a ciclos adicionados a ciclos. Tente fazer um “pico de tempo” definindo uma amplitude de 1 para cada componente (pressione Enter após inserir cada número). Fato curioso: com termos suficientes, você pode desenhar qualquer forma, até mesmo Homer Simpson .