A transformada de Fourier aparece com frequência na física e na matemática, o que faz com que 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 transforma-o para o domínio da frequência.
E, mais concretamente, quando o sinal de entrada é um amontoado (ou seja, uma sobreposição) de frequências diferentes, a transformada separa as frequências individuais e mostra a força relativa de cada uma.
Isto 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, é 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 revelam indispensáveis, dado 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, por isso estamos interessados na versão discreta.
A dedução da transformada está além do âmbito deste exercício, mas a transformada discreta direta (para o domínio da frequência) tem 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 isto drasticamente.
Isto é feito tipicamente através de uma estratégia de divisão e conquista, que explora algumas simetrias na formulação e resulta numa complexidade assintótica de O(Nlog(N)).
Esta aceleração melhora bastante a praticidade e o leque de aplicações adequadas à transformada.
