Discretizações da Transformada de Fourier

Transformada Discreta de Fourier e Transformada Rápida (FFT)


O personagem central deste Curso foi a Transformada de Fourier de $f(t)$, definida como a integral
\[F(w) := \int_{-\infty}^{+\infty} f(t) \cdot e^{- i w t}\, dt \]
Para que seja compatível com a Interação do final desta Seção que calcula a importante Transformada Rápida de Fourier (FFT), adotaremos daqui em diante a definição alternativa
\[ F(w) := \int_{-\infty}^{+\infty} f(t) \cdot e^{- i \, 2\pi \, w t}\, dt \]
(com o fator $2\pi$). Somente nesta Seção fazemos essa convenção.

Para que tenha aplicações práticas, é preciso poder implementar esse conceito em computadores. E para isso é preciso tomar um intervalo limitado de tempo \[t\in [0,b],\]
ao invés de toda a reta $\mathbb{R}$, e ainda discretizar tanto $[0,b]$ quanto um intervalo limitado de frequências $w$:
Definição 1 (Transformada de Fourier Discreta): Sejam $N\in \mathbb{N}$ e um intervalo de tempo $[0,b]$ fixados. Definimos
\[\begin{cases} \tau := \frac{b}{N}\\ w_n = \frac{n}{b}, \quad n = 0, \ldots, N\\ t_k := \tau \cdot k, \quad k = 0,\ldots , N-1\end{cases}\]
Relativa a essas escolhas, a Transformada de Fourier Discreta é
\[F( w_n ) := \sum_{k=0}^{N-1} f( t_k ) \cdot \tau \cdot e^{ - i \, 2\pi \, w_n \, t_k}\]

No parágrafo a seguir implementaremos de modo ingênuo - direto - a Definição 1.
Em seguida explicaremos a necessidade de acelerar as aproximações de $F(w_n)$, pois em em situações reais os números $N$ envolvidos são muito grandes.
O algoritmo de Cooley e Tukey que implementa de modo rápido as Transformadas Discretas de Fourier é considerado um dos mais importantes do século XX, devido às inúmeras aplicações.
Vamos explicar a idéia matemática de base do algoritmo e, ao final da Seção, teremos Interações que calculam as Transformadas Rápidas.





Cursos

Tópicos