13.1: Comentarios

Última actualización
Guardar como PDF

Page ID: 87037

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

Esta sección proviene de una nota que describe los resultados de algoritmos eficientes para calcular la transformada discreta de Fourier (DFT) que se recolectaron a lo largo de los años. Quizás lo más interesante es el descubrimiento de que la FFT Cooley-Tukey fue descrita por Gauss en 1805. Eso da alguna indicación de la era de la investigación sobre el tema, y el hecho de que una bibliografía compilada en 1995 sobre algoritmos eficientes contenga más de 3400 entradas indica su volumen. Tres libros reimpresos de IEEE Press contienen artículos sobre la FFT. Un excelente programa FFT de propósito general se ha descrito y se utiliza en Matlab y está disponible a través de Internet.

Además de este libro hay varios otros que dan una buena base teórica moderna para la FFT, un libro que da la teoría básica más los programas de lenguaje ensamblador FORTRAN y TMS 320, y otros libros que contienen capítulos sobre temas avanzados de FFT. Existe una buena referencia on-line actualizada tanto con teoría como con técnicas de programación. También se puede encontrar la historia de la FFT y excelentes artículos de encuestas. El fundamento de gran parte del trabajo moderno sobre algoritmos eficientes fue realizado por S. Winograd.

Los algoritmos FFT eficientes para la longitud$2^M$ fueron descritos por Gauss y descubiertos en los tiempos modernos por Cooley y Tukey. Estos han sido altamente desarrollados y se pueden encontrar buenos ejemplos de programas FORTRAN. Se han publicado varios algoritmos nuevos que requieren la cantidad menos conocida de aritmética total. De estos, la FFT de base dividida parece tener la mejor estructura para la programación, y se ha escrito un programa eficiente para implementarlo. Se da una mezcla de decimation-in-time y decimation-in-frequency con muy buena eficiencia y una llamada FT sino-coseno. Recientemente se ha descrito una modificación al algoritmo split-radix que tiene un conteo aritmético total ligeramente mejor. Se pueden encontrar límites teóricos sobre el número de multiplicaciones requeridas para la FFT con base en las teorías y esquemas de Winograd para calcular una FFT in situ y en orden radix-2. También se encuentran diversas formas de unscramblers. Se puede encontrar una discusión sobre la relación entre la arquitectura de la computadora, el algoritmo y el compilador. Una modificación sería permitir longitudes de$N=q2^m$ for$q$.

El “otro” FFT es el algoritmo de factor primo (PFA) que utiliza un mapa de índices originalmente desarrollado por Thomas y por Good. La teoría del PFA se derivó y se desarrolló en un programa eficiente en orden y en el lugar. Se ha desarrollado un método para utilizar la programación dinámica para diseñar programas FFT óptimos que minimicen el número de adiciones y transferencias de datos, así como multiplicaciones. Este nuevo enfoque diseña algoritmos personalizados para una arquitectura informática particular. Un desarrollo eficiente y práctico de las ideas de Winograd ha dado un método de diseño que no requiere el teorema del resto chino bastante difícil para FFT's de corta longitud prima. Estas ideas han sido utilizadas para diseñar módulos de longitud 11, 13, 17, 19 y 25. Se pueden encontrar otros métodos para diseñar DFT cortos. También se encuentra un programa que implementa el algoritmo de transformada de Fourier de Winograd anidado (WFTA) pero no ha demostrado ser tan rápido o tan versátil como el PFA. Se anunció un interesante uso del PFA en la búsqueda de grandes números primos.

Estos algoritmos eficientes no solo pueden ser utilizados en DFT sino en otras transformaciones con una estructura similar. Se han aplicado a la transformada discreta de Hartley y a la transformada discreta del coseno.

La transformación rápida de Hartley se ha propuesto como un método superior para el análisis de datos reales, pero se ha demostrado que no es el caso. Una FFT de datos reales bien diseñada siempre es tan buena o mejor que una transformada Hartley bien diseñada. El algoritmo Bruun también parece prometedor para aplicaciones de datos reales al igual que el algoritmo Rader-Brenner.

Aparte de los algoritmos de longitud general, para longitudes que no son altamente compuestas o primos, la transformada z chirp es un buen candidato para longitudes más largas y un$N^2$ algoritmo de orden eficiente llamado QFT para longitudes más cortas. Está disponible un método que genera automáticamente programas basados en Winograd de longitud primo casi óptima. Esto da la misma eficiencia para longitudes más cortas (i.e. $N≤19N≤19“role="presentation” style="position:relative;” tabindex="0"> $N\leq 19$$ y nuevos algoritmos para longitudes mucho más largas y con algoritmos bien estructurados. Hay métodos especiales disponibles para longitudes muy largas. Un sistema FFT de longitud general muy interesante llamado FFTW ha sido desarrollado por Frigo y Johnson en el MIT. Utiliza una biblioteca de “codelets” eficientes que se componen para un cálculo muy eficiente del DFT en una amplia variedad de computadoras. Para la mayoría de las longitudes y en la mayoría de las computadoras, esta es la FFT más rápida hoy en Sorprendentemente, utiliza una estructura de programa recursiva. El FFTW ganó el Premio Wilkinson de 1999 de Software Numérico.

El uso de la FFT para calcular la convolución discreta fue uno de sus primeros usos. Aunque la transformación rectangular más directa parecería ser más eficiente, el uso de FFT o PFA sigue siendo probablemente el método más rápido en una computadora de propósito general o chip DSP. En hardware de propósito especial o arquitecturas especiales, el uso de transformaciones aritméticas distribuidas o teóricas numéricas [link] puede ser aún más rápido. También se han desarrollado algoritmos especiales para su uso con la transformada de Fourier de corta duración y para el cálculo de algunos valores de DFT y para la implementación recursiva. Las formulaciones del DFT en términos de tensor o productos Kronecker parecen prometedoras para desarrollar algoritmos para arquitecturas de computadora paralelas y vectoriales.

Diversos enfoques para calcular las DFT aproximadas se han basado en métodos cordicos, longitudes de palabras cortas o alguna forma de poda. Un nuevo método que utiliza las características de las señales que se transforman ha combinado la transformada de ondícula discreta (DWT) combinada con la DFT para dar una FFT aproximada con $O (N) “role="presentation” style="position:relative;” tabindex="0">$