Transformada de Fourier discreta
Resumo
Com estas notas pretende-se explicar a forma das expressões das transformadas de Fourier discretas e dar significado intuitivo claro às diferentes componentes do desenvolvimento de um conjunto numérico. O ponto de partida é o desenvolvimento em série de Fourier de uma função periódica, e é usado o teorema de Nyquist. Mais de resto, este texto é autónomo.
Série de Fourier
Uma função \(x(t)\) periódica com período \(T\) pode ser escrita como uma série de funções trignométricas com períodos submúltiplos de \(T\), \[\label{eq:ift} x(t) = \sum_{k=-\infty}^{\infty}X_ke^{2\pi i kt/T}\] O \(k\)-ésimo termo desta série é uma função periódica com período \(T/k\) ou frequência angular \(\omega_n=2\pi k/T\), com valor médio nulo em intervalos com amplitude \(T\), excepto nos casos em que o argumento é identicamente nulo, isto é, \[\int_{t_0}^{t_0+T}e^{2\pi i (k-k')t/T} dt = T \delta_{kk'}.\] Com esta constatação é fácil obter expressões para os coeficientes \(X_n\). Multipliquem-se ambos os membros da eq. por \(e^{-2\pi i k'n/T}\) e integre-se ao longo de um período. Usando a igualdade acima resulta imediatamente \[\label{eq:ft} X_k=\frac{1}{T}\int_{t_0}^{t_0+T}e^{-2\pi i k t/T} x(t)dt\]
Esta análise da função \(x\) pode ser levada a cabo se o seu domínio for um intervalo finito, mesmo que não apresente, nesse intervalo, qualquer periodicidade. Considerando \(T\) a largura do domínio da função, podemos definir coeficientes \(X_k\) com a eq. e substituí-los na eq. . A função resultante \(\tilde{x}(t)\) é idêntica à função original em todos os pontos do domínio, mas o seu domínio é toda a reta real, onde é periódica com período \(T\).
Transformada de Fourier discreta
Uma aplicação prática importante das transformadas é a descrição aproximada de funções obtidas por observação empírica. Em particular, sucede frequentemente que a função observada é determinada por amostragem. Nesses casos, a informação disponível sobre a função \(x(t)\) reduz-se à sequência de valores resultante da amostragem. O significado do desenvolvimento em série de Fourier da eq. é agora diferente. Espera-se1 que o valor da soma no lado direito seja próximo do da função em cada ponto do intervalo de amostragem. Como apenas são conhecidos os valores efetivamente amostrados, esta espetativa só se pode objetivar para esses valores. Sejam \(x_0,\ x_1,\ \ldots,\ x_{N-1}\) os valores amostrados. Em vez do desenvolvimento da eq. , passa a escrever-se \[\label{eq:dft1} x_n = \sum_{k=-\infty}^{\infty} X_ke^{2\pi ikt_n/T}\] Esta igualdade representa um sistema de \(N\) equações (uma por cada valor amostrado) e com um número infinito de incógnitas (os infinitos \(X_k\)), o que é desencorajador. No entanto, o teorema de Nyquist mostra que, numa amostragem dos valores de uma função com passo \(\delta t\), se perdem as componentes da função amostrada com frequências superiores em módulo a metade da frequência de amostragem. Assim, no desenvolvimento acima só se devem considerar termos com frequência \(k/T\) com módulo inferior a \(1/(2\delta t)\). Consideremos uma amostragem uniforme \(\{x_0,\ x_1,\ldots,\ x_{N-1}\}\) de \(x(t)\), com dimensão \(N\) e com passo \(\delta t\), num intervalo \([t_0, t_0+\delta t[\). Os valores observados são \[x_n=x(t_n),\qquad\text{com }t_n=t_0+n\delta t=t_0+n\frac{T}{N}.\] Com esta amostragem, só se devem considerar no desenvolvimento da eq. os termos tais que \(|k/T|<1/(2\delta t)\), ou seja, com \(k\) na gama de inteiros \(-N/2<k<N/2\), e substituindo \(t_n\) resulta \[\label{eq:idft2} x_n=\sum_{k=-N/2}^{N/2} X_k e^{2\pi i kt_0/T}\,e^{2\pi ikn/N}.\]
As exponenciais \(\exp(2\pi i kn/N)\) são periódicas em \(k\) e \(n\), com período \(N\). Álem disso, os seus valores para diferentes \(n\) formam uma sucessão geométrica complexa. É fácil demonstrar que a sua soma na gama de valores de \(n\) (\(0,\ldots, N-1\)) é nula, a menos que seja nulo o expoente, verificando-se \[\sum_{n=0}^{N-1}e^{2\pi in(k-k')/N} = N\delta_{kk'}.\] Multiplicando ambos os membros da eq. por \(\exp(-2\pi i nk'/N)\) e somando em \(n\) obtem-se a transformação inversa, \[X_k=\frac{1}{N}e^{-2\pi ikt_0/T}\sum_{n=0}^{N-1} e^{-2\pi i kn/N}x_n.\] A comparação deste desenvolvimento com o da eq. sugere a redifinição dos coeficientes \(X_k\) \[X_k\rightarrow Ne^{2\pi ikt_0/T} X_k,\] com a qual as expressões da transformada de Fourier discreta tomam a forma mais simples \[\begin{aligned} \label{eq:dft} X_k &=\sum_{n=0}^{N-1} e^{-2\pi ikn/N} x_n& x_n &= \frac{1}{N} \sum_{k=-N/2}^{N/2} X_k e^{2\pi ikn/N}.\end{aligned}\] Estas são as expressões usuais da transformada de Fourier discreta. Existem métodos computacionalmente avançados para as processar rapidamente, com o nome genérico fast Fourier transform. Todas as linguagens de programação e plataformas computacionais usadas em contexto científico dispõem de implementações desses métodos.
Há um aspeto nestas igualdades que merece alguma reflexão. É que a variável \(t\) está completamente ausente. Deste modo, a duração da amostragem \(T\) e, com ela, as sucessivas frequências \(2\pi k/T\) já não estão aparentes. Assim, a ideia intuitiva da análise de Fourier como método para a análise espectral de um sinal fica, de certa maneira, camuflada. Vejamos isto melhor. A segunda das eqs. escreve os valores amostrados \(x_n\) como combinação dos valores de funções que num sentido estritamente numérico, são periódicas. Por exemplo, o termo de ordem 0 é constante; a sequência de valores \(x^{(0)}_n\) que gera é constante, ou seja, neste sentido estritamente numérico, periódica com período 1. Mas, mais em geral, o termo de ordem \(k\) gera uma sequência de valores de \(x^{(k)}\) com período \(N/k\). Assim, a ideia intuitiva da análise de Fourier é ainda aplicável nestas aplicações discretizadas: descreve-se uma sequência numérica como uma sobreposição de sequências periódicas amostradas de funções sinusoidais com períodos iguais a frações inteiras do número de elementos da amostragem dada. A expressão frequência de uma componente da decomposição de uma amostra refere-se a quantos períodos dessa componente ocorrem na amostra.
Há ainda outra questão nas eqs. que deve ser visto com cuidado, que é a dos limites dos somatórios em \(k\). Se \(N\) é par, então o somatório na segunda das eqs. ,tal como está escrito, tem \(N+1\) parcelas, que envolvem \(N+1\) amplitudes \(X_k\). Mas a exponencial \(\exp\{2\pi i kn/N\}\) tem o mesmo valor, \((-1)^n\), para \(k=\pm N/2\). Assim, os dois valores extremos não são independentes, um deles é redundante e deve ser descartado. Escolhemos descartar o de índice \(k\) negativo. Restam assim \(N\) variáveis \(X_k\), número igual ao dos \(x_n\). Por outro lado, se \(N\) é ímpar, então os limites do somatório na segunda das eqs. são fracionários; deve-se truncar ou arredondar o resultado? Aqui é o próprio teorema de Nyquist que dá a resposta: não se deve comsiderar termos com frequência superior em módulo a \(\delta/2\), logo, \(|k|\) não deve ser maior que \(N/2\). Ou seja, o valor de \(\pm N/2\) deve ser truncado (isto é, deve descartar-se a parte fracionária) nos limites de variação do somatório. Resumindo os limites do somatório da segunda das eqs. são \(N/2<k\leq N/2\) se \(N\) for par e \(-N/2<k<N/2\) se for ímpar. Mas é tão complicado deixar isso explicitado na notação, que manteremos a forma apresentada. Fica ao cuidado do leitor compreender corretamente as expressões.
Um exemplo: a função afim
Quando os elementos da sequência \(x_n\), \(n=0, 1, \ldots, N-1\) são todos reais, as ampitudes \(X_k\) ficam necessariamente relacionadas umas com as outras, verificando-se \(X_k = X^*_{-k}\), e a segunda das eqs. pode escrever-se como \[\label{eq:cdft} x_n=X_0 + \sum_{k=1}^{N/2}\left(X_ke^{2\pi i nk/N} +\text{c. c.}\right).\] É mais intuitiva a análise do comportamento da soma quando se emparelham os termos como na igualdade acima, porque cada termo do somatório é real. No que se segue, quando for referida soma dos primeiros \(k\) termos de uma transformação de Fourier, pretende-se indicar os primeiros \(k\) termos do somatório na eq. .
Sejam \[x_n=x_0+nv,\quad\text{com }x_0, v\in R,\ n=0, 1, \ldots, N-1.\] os elementos de uma amostragem da função \(x(t)=x_0+vt\). A sua transformada de Fourier é o conjunto \[X_k = \sum_{n=0}^{N-1} x_ne^{-2\pi ikn/N}= x_0\sum_{n=0}^{N}e^{-2\pi ikn/N} +v\sum_{n=0}^N ne^{-2\pi ikn/N}.\] O primeiroi somatório é a soma dos primeiros \(N\) termos de uma sucessão geométrica com razão \(r=\exp\{-2\pi i k/N\}\); o segundo somatório é a soma dos primeiros \(N\) termos de uma sucessão do terceiro tipo das estudadas no apontamento Três Simples Somas. Deduziram-se nesse apontamento as fórmulas \[\begin{aligned} S_N(r) &= \sum_{n=0}^{N-1} r^n = \begin{cases} \displaystyle \frac{1-r^N}{1-r},&\text{ se } r\neq 1\\ \displaystyle N,&\text{ se } r=1, \end{cases}\\[2mm] T_N(r)&=\sum_{n=0}^{N-1}nr^n = \begin{cases} \displaystyle\frac{rS_N-Nr^N}{1-r},&\text{ se } r\neq 1\\ \displaystyle\frac{1}{2}N(N-1),&\text{ se } r=1 \end{cases}\end{aligned}\] Com \(r=\exp\{-2\pi i k/N\}\), temos \(r^N=1\) e \(S_N=N\delta_{k0}\). Assim, \[\begin{aligned} X_0&=x_0N+\frac{1}{2}vN(N-1)&X_{k\neq0}=-\frac{vN}{1-e^{-2\pi i k/N}} =\frac{-vN}{2}\;\frac{1-e^{2\pi i k/N}}{1-\cos{\frac{2\pi k}{N}}}.\end{aligned}\] É interessante notar que a parte real das amplitudes de ordem \(k\neq0\) é constante, com valor \(-vN/2\).
Concretizemos ainda melhor esta sucessão; tomemos \(x_0=-3,5\), \(v=1\), \(N=8\), resultando a sequência \[x_n=\left\{-3,5,\ -2,5,\ -1,5,\ -0,5,\ 0,5,\ 1,5,\ 2,5,\ 3,5\right\}.\] A transformada de Fourier deste conjunto é formada pelo conjunto \[\begin{aligned} X_k&=-4\left(1-i\frac{\sin\pi k/4}{1-\cos\pi k/4}\right),\quad k\in \{-3, -2, -1, 0, 1, 2, 3, 4\},& X_0&=0,\end{aligned}\] \[X_k\simeq\{ -4-1,66i, -4-4i, -4-9,66i, 0, -4+9,66i, -4+4i, -4+1,66i, -4 \}\]
A Figura em baixo mostra os gráficos das componentes reais da decomposição de Fourier da sequência \(x_n\) (cada componente é um dos termos do somátório na eq. ) e das suas somas acumuladas, que se vão aproximando, a cada nova parcela, da sequência original.
Gráficos de cada contribuição real para a decomplosição de Fourier da sequência x_n (à esquerda) e somas parciais acumuladas dessas contribuições (à direita).
O sentido em que este termo é usado fica por clarificar.↩