2.1: Introducción

Última actualización
Guardar como PDF

Page ID: 86975

$ \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}}$

Objetivos de aprendizaje

Se utiliza un cambio de variable de índice o un mapeo de índices para desacoplar los cálculos de la transformada discreta de Fourier (DFT).
Esto puede dar como resultado una reducción significativa en la aritmética requerida y el algoritmo resultante se denomina transformada rápida de Fourier (FFT).

Un enfoque poderoso para el desarrollo de algoritmos eficientes es romper un problema grande en múltiples pequeños. Un método para hacer esto tanto con la DFT como con la convolución utiliza un cambio lineal de variables de índice para mapear el problema unidimensional original en un problema multidimensional. Este enfoque proporciona una derivación unificada de la FFT de Cooley-Tukey, la FFT del algoritmo de factor primo (PFA) y la FFT del algoritmo de transformada de Fourier de Winograd (WFTA). También se puede aplicar directamente a la convolución para dividirla en múltiples circunvoluciones cortas que se pueden ejecutar más rápido que una implementación directa. A menudo es fácil traducir un algoritmo usando el mapeo de índices en un programa eficiente.

Definición

La definición básica de la transformada discreta de Fourier (DFT) es

\[C(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{nk} \nonumber \]

donde $n “role="presentation” style="position:relative;” tabindex="0"> n, k y N$

los valores de la transformada se calculan a partir de los$N$ valores de los datos$x(n)$, se ve fácilmente que las multiplicaciones$N^2$ complejas y aproximadamente ese mismo número de adiciones complejas son requerido. Un método para reducir esta aritmética requerida es usar un mapeo de índices (un cambio de variables) para cambiar la DFT unidimensional en una DFT bidimensional o superior. Esta es una de las ideas detrás de los muy eficientes algoritmos Cooley-Tukey y Winograd. El propósito del mapeo de índices es cambiar un problema grande en varios más fáciles. Esto a veces se llama el enfoque de “dividir y conquistar” pero una descripción más precisa sería “organizar y compartir” lo que explica el proceso de eliminación o reducción de redundancia.