A Transformada de Fourier aparece com frequência na física e na matemática, o que faz com que ela tenha também muitos usos no dia a dia.
Em resumo, a Transformada de Fourier recebe um sinal de entrada, muitas vezes nos domínios do tempo ou do espaço, e o transforma para o domínio da frequência.
E, mais concretamente, com um sinal de entrada formado por uma mistura (ou seja, uma superposição) de frequências diferentes, a transformada separa as frequências individuais e mostra suas forças relativas.
Isso faz da transformada uma ferramenta principal no processamento de sinais (por exemplo, filtragem, compressão etc.) e em muitas aplicações de ciência de dados.
Por isso, ela é talvez mais usada do que se poderia imaginar à primeira vista, o que também a torna um exemplo perfeito de onde os números imaginários se mostram indispensáveis, já que a saída da Transformada de Fourier é, em geral, um número complexo.
Embora a Transformada de Fourier tenha uma formulação integral, nós somos digitais, então estamos interessados na versão discreta.
A derivação da transformada está além do escopo deste exercício, mas a transformada discreta direta (para o domínio da frequência) assume a seguinte forma:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Aqui, o somatório percorre n, e N é o número de amostras, k é a frequência, i a unidade imaginária e xₙ é uma amostra individual.
Embora seja extremamente útil, a Transformada de Fourier, implementada de forma ingênua, é um pouco lenta (O(n²)).
A Transformada Rápida de Fourier (FFT) é um algoritmo que acelera drasticamente esse processo.
Isso normalmente é feito por meio de uma estratégia de dividir para conquistar, que explora algumas simetrias na formulação e resulta em uma complexidade assintótica de O(Nlog(N)).
Essa aceleração melhora bastante a praticidade e o alcance das aplicações adequadas à transformada.
