next up previous
Next: La Transformada de Fourier Up: Transformada de Fourier Cuántica Previous: La Transformada de Fourier

La Transformada de Fourier discreta

El planteamiento básico de la trasformada de fourier se puede especificar tanto en el campo discreto como en el continuo. Sin embargo, para nuestros casos nos interesara la transformada de Fourier discreta, el planteamiento de la trasformada es el siguiente.

Dada una funcion $ f(x)$ tal que contamos con $ N$ muestras de $ f(x)$ denominadas $ f_0, f_1, \ldots,
f_{N-1}$. Se llama trasformada de Fourier discreta de $ \{f_0, \ldots, f_{N-1}\}$ al conjunto de valores $ \{F_0, F_1, \ldots, F_{N-1}\}$ definido como

$\displaystyle F_k = \frac{1}{N}\sum_{j=0}^{N-1}f_j\omega_N^{jk}$ (3.3)

donde

$\displaystyle \omega_N = e^{-\frac{2i\pi}{N}}
$

Es importante resaltar las siguientes propiedades
  1. $ \omega_N$ es una raiz $ N$-ésima de 1, tal que

    $\displaystyle \omega_N^N= \left(e^{-\frac{2i\pi}{N}}\right)^N = e^{-\frac{2i\pi N}{N}} =
e^{-2i\pi} = \cos(2\pi) - i\sin(2\pi) = 1
$

  2. $ \omega_N^j$ es también una raiz $ N$-ésima de 1 ya que

    $\displaystyle \left(\omega_N^j\right)^N = \omega_N^{jN} = \omega_N^{Nj} = \left(\omega_N^N\right)^j = 1^j = 1
$

  3. todos los $ \omega_N^j$ son distintos para $ j \in \{0, \ldots, N-1\}$
  4. $ \omega_N^2 = \omega_{N/2}$ ya que

    $\displaystyle \omega_N^2 = \left(e^{-\frac{2i\pi}{N}}\right)^2 = e^{-\frac{2i\pi2}{N}} =
e^{-\frac{2i\pi}{N/2}} = \omega_{N/2}
$

  5. $ \omega_N^{N/2} = -1$ ya que

    $\displaystyle \omega_N^{N/2} = \left(e^{-\frac{2i\pi}{N}}\right)^{N/2} = e^{-\frac{2i\pi N}{N2}} =
e^{-i\pi} = \cos(\pi) - i\sin(\pi) = -1
$

Dada la ecuación 3.3 y las anteriores propiedades, la transformada de Fourier discreta puede expresarse como una multiplicación de matrices de la forma

$\displaystyle \Omega \vec{f} = \vec{F}
$

donde

$\displaystyle \vec{f} =
\left(
\begin{array}{c}
f_0  f_1  \vdots  f_{N-1}...
...ft(
\begin{array}{c}
F_0  F_1  \vdots  F_{N-1}
\end{array}\right), \quad
$

$\displaystyle \Omega = \frac 1 {N}\left(
\begin{array}{cccccc}
1 & 1 & \cdots &...
... & \cdots & \omega_N^{(N-1)j} & \cdots & \omega_N^{(N-1)^2}
\end{array}\right)
$

Bajo esta notación, la trasformada de Fourier se convierte en una multiplicación de una matriz por un vector, y su complejidad computacional es $ O(N^2)$


next up previous
Next: La Transformada de Fourier Up: Transformada de Fourier Cuántica Previous: La Transformada de Fourier
Jose Castro 2004-10-06