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

La Transformada de Fourier rápida (FFT)

La complejidad computacional de la trasformada de Fourier discreta puede mejorarse considerablemente si se utiliza la propiedad de que los valores de $ \omega_N^j$ tienden a repetirse y si suponemos que $ N$ es divisble entre 2, con estas condiciones tenemos que

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

$\displaystyle \frac{1}{N}\sum_{j\in\{0,1,\ldots,N-1\}}f_j\omega_N^{jk} =
$

$\displaystyle \frac{1}{N}\left(\sum_{j\in \{0,2,\ldots, N-2\}}f_j\omega_N^{jk}
+ \sum_{j\in\{1,3,\ldots,N-1\}}f_j\omega_N^{jk}\right) =
$

$\displaystyle \frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j}\omega_N^{2jk}
+ \frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j+1}\omega_N^{(2j+1)k} =
$

$\displaystyle \frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j}\omega_N^{2jk}
+ \omega_N^k\frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j+1}\omega_N^{2jk} =
$

$\displaystyle \frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j}\left(\omega_N^2\right)^{jk}
+ \omega_N^k\frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j+1}\left(\omega_N^2\right)^{jk} =
$

$\displaystyle \frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j}\omega_{N/2}^{jk}
+ \omega_N^k\frac{1}{N}\sum_{j=0}^{N/2-1}f_{2j+1}\omega_{N/2}^{jk} =
$

$\displaystyle \frac{1}{2}\left(\underbrace{ \frac{1}{N/2}\sum_{j=0}^{N/2-1}f_{2...
...um_{j=0}^{N/2-1}f_{2j+1}\omega_{N/2}^{jk} }_{\mathrm{Transf. \; impar}} \right)$ (3.4)

Ahora bien, el valor de $ k$ en la ecuación 3.4 puede variar de 0 a $ N-1$, lo cual indica que solo para los valores de $ k \in \{0, 1, \ldots \frac{N}{2} - 1\}$ tanto la transformada par como la impar son transformadas de Fourier con $ N/2$ puntos.

Sin embargo, todos los valores mayores o iguales a $ \frac N 2$ se pueden expresar como $ k+\frac N 2$ donde $ k \in \{0, 1, \ldots \frac N 2 - 1\}$ y para estos la ecuación 3.4 se expresa como

$\displaystyle F_{k+\frac N 2} =
\frac{1}{2}\left(
\frac{1}{N/2}\sum_{j=0}^{N/2-...
...rac{1}{N/2}\sum_{j=0}^{N/2-1}f_{2j+1}\omega_{N/2}^{j(k + \frac N 2)}
\right) =
$

$\displaystyle \frac{1}{2}\left(
\frac{1}{N/2}\sum_{j=0}^{N/2-1}f_{2j}\omega_{N/...
...}{N/2}\sum_{j=0}^{N/2-1}f_{2j+1}\omega_{N/2}^{jk}\omega_{N/2}^{jN/2}
\right) =
$

$\displaystyle \frac{1}{2}\left(
\frac{1}{N/2}\sum_{j=0}^{N/2-1}f_{2j}\omega_{N/...
...0}^{N/2-1}f_{2j+1}\omega_{N/2}^{jk}\left(\omega_{N/2}^{N/2}\right)^j
\right) =
$

$\displaystyle \frac{1}{2}\left(
\frac{1}{N/2}\sum_{j=0}^{N/2-1}f_{2j}\omega_{N/...
...c{1}{N/2}\sum_{j=0}^{N/2-1}f_{2j+1}\omega_{N/2}^{jk}\left(1\right)^j
\right) =
$

$\displaystyle \frac{1}{2}\left(
\frac{1}{N/2}\sum_{j=0}^{N/2-1}f_{2j}\omega_{N/...
...
- \omega_N^k
\frac{1}{N/2}\sum_{j=0}^{N/2-1}f_{2j+1}\omega_{N/2}^{jk}
\right)
$


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