9.4: Modificaciones de los algoritmos de tipo PFA y WFTA

Última actualización
Guardar como PDF

Page ID: 86819

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

En la sección anterior se vio como el uso de la propiedad de permutación de los operadores elementales en el PFA permitió el anidamiento de las multiplicaciones para reducir su número. También se vio que un ordenamiento adecuado de los operadores podría minimizar el número de adiciones. Estas ideas se han extendido en la formulación de un problema de optimización de algoritmos más general. Si el operador DFT$F$ $F “role="presentation” style="position:relative;” tabindex="0">$

Esta formulación permite un conjunto muy grande de posibles ordenamientos, de hecho, el número es tan grande que se debe utilizar alguna técnica automática para encontrar el “mejor”. Es posible establecer un criterio de optimalidad que no solo incluya el número de multiplicaciones sino también el número de adiciones. Los efectos de tiempos relativos de multiplicación-adición, tiempos de transferencia de datos, registro de CPU y tamaños de memoria, y otras características de hardware se pueden incluir en el criterio. La programación dinámica se puede aplicar para derivar un algoritmo óptimo para una aplicación particular. Esta es una idea muy interesante ya que ya no hay un solo algoritmo, sino una clase y un procedimiento de optimización. El reto es generar una clase lo suficientemente amplia como para dar como resultado una solución cercana a un óptimo global y tener un esquema práctico para encontrar la solución.

Los resultados obtenidos aplicando el método de programación dinámica al diseño de algoritmos DFT bastante largos dieron algoritmos que tuvieron menos multiplicaciones y adiciones que un PFA puro o WFTA. Parece que alguna anidación es deseable pero no anidación total por cuatro o más factores. También hay algunas posibilidades interesantes para mezclar el Cooley-Tukey con esta formulación. Desafortunadamente, los factores de twiddle no son los mismos para todas las filas y columnas, por lo tanto, las operaciones no pueden conmutar más allá de un operador de factor de twiddle. Hay formas de romper el algoritmo total en caminos horizontales y usar diferentes ordenamientos a lo largo de los diferentes caminos. En cierto sentido, esto es lo que hace la FFT de base dividida con sus factores de twiddle cuando se compara con una FFT Cooley-Tukey convencional.

Hay otras modificaciones de la estructura básica del algoritmo DFT del mapa de índices Tipo 1. Una es usar la misma estructura de índice y conversión de los DFT cortos a convolución que el PFA pero usar algún otro método para la convolución de alta velocidad. La búsqueda en tablas de productos parciales basada en aritmética distribuida para eliminar todas las multiplicaciones parece prometedora para ciertas aplicaciones muy específicas, quizás para la implementación especializada de VLSI. Otra posibilidad es calcular las circunvoluciones cortas utilizando transformadas teóricas numéricas. Esto también requeriría hardware especial. El cálculo directo de circunvoluciones cortas es más rápido en ciertos procesadores canalizados, como el microprocesador TMS-320.

Search

Text Color

Text Size

Margin Size

Font Type