Inicio
Ingeniería
Transformadas Rápidas de Fourier (Burrus)
8: El algoritmo de transformada rápida de Fourier Cooley-Tukey

8: El algoritmo de transformada rápida de Fourier Cooley-Tukey

Última actualización
Guardar como PDF

Page ID: 86790

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

La publicación por Cooley y Tukey en 1965 de un algoritmo eficiente para el cálculo de la DFT fue un importante punto de inflexión en el desarrollo del procesamiento digital de señales. Durante los cinco años siguientes, se realizaron diversas ampliaciones y modificaciones al algoritmo original. A principios de la década de 1970 los programas prácticos estaban básicamente en la forma utilizada hoy en día. El desarrollo estándar muestra cómo la DFT de una secuencia de longitud N se puede calcular simplemente a partir de los dos DFT de longitud-N/2 de los términos del índice par y los términos del índice impar. Esto se aplica entonces a los dos DFT de longitud media para dar cuatro DFT de cuarto de longitud, y se repite hasta que quedan N escalares que son los valores de DFT. Debido a tomar alternativamente los términos pares e impares del índice, dos formas de los programas resultantes se llaman decimation-in-time y decimation-in-frequency. Durante una duración de\(2^M\), el proceso de división se repite\(M=\log _{2}N\) veces y requiere N multiplicaciones cada vez. Esto da la famosa fórmula para la complejidad computacional de la FFT de la\(N\log _{2}N\) cual se derivó en Mapeo de Índice Multidimensional.