6: Algoritmos DFT cortos de Winograd

Última actualización
Guardar como PDF

Page ID: 86847

\( \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}}\)

En 1976, S. Winograd presentó un nuevo algoritmo DFT que tuvo significativamente menos multiplicaciones que el FFT Cooley-Tukey que había sido publicado once años antes. Este nuevo Algoritmo de Transformada de Fourier de Winograd (WFTA) se basa en el mapa de índice tipo uno del Mapeo de Índice Multidimensional con cada una de las DFT cortas de longitud relativamente prima calculadas por algoritmos especiales muy eficientes. Son estos algoritmos cortos los que desarrollará esta sección. Utilizan la permutación de índice de Rader descrita en el otro módulo para convertir las DFT cortas de longitud prima en circunvoluciones cíclicas. Winograd desarrolló un método para calcular la convolución digital con el número mínimo de multiplicaciones. Estos algoritmos óptimos se basan en las técnicas de reducción de residuos polinomiales de Descripción polinómica de señales para romper la convolución en múltiples pequeñas.