8.1: Introducción
- Page ID
- 86812
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Objetivos de aprendizaje
- Desarrollar la FFT de Cooley-Tukey usando el mapa de índices del Mapeo de Índice Multidimensional
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 extensiones 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 índice par e impar, 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.
Aunque los métodos de diezmación son sencillos y fáciles de entender, no generalizan bien. Por esa razón se asumirá que el lector está familiarizado con esa descripción y en este capítulo se desarrollará la FFT utilizando el mapa índice de Mapeo de Índice Multidimensional.
Colaborador
- ContribeeBurrus