Este apéndice discutirá programas FFT cortos eficientes que pueden ser utilizados tanto en el algoritmo de transformada rápida de Fourier Cooley-Tukey como en los algoritmos de transformada de Fourier de Factor Prime y Winograd. Se dan enlaces y referencias a listados de Fortran que se pueden usar “tal cual” o poner en los bucles indexados de programas existentes para dar mayor eficiencia y/o una mayor variedad de longitudes permitidas. Se han escrito programas especiales para longitudes:\(N=2,3,4,5,7,8,9,11,13,16,17,19,25,...\)
En los primeros días de la FFT, la multiplicación se realizó en software y fue, por lo tanto, mucho más lenta que una adición. Con el hardware del módem, se puede realizar una multiplicación de punto flotante en un ciclo de reloj de la computadora, microprocesador o chip DSP, requiriendo el mismo tiempo que una adición. De hecho, en algunas computadoras y muchos chips DSP, tanto una multiplicación como una adición (o acumulación) se pueden hacer en un ciclo mientras que la indexación y el acceso a la memoria se realizan en paralelo. La mayoría de los algoritmos descritos aquí no son específicos de la arquitectura de hardware, sino que están diseñados para minimizar tanto las multiplicaciones como las adiciones.
La longitud más básica y de uso frecuente FFT (o DFT) es paraN=2N=2“role="presentación” style="position:relative;” tabindex="0"> \(N=2\). En el Cooley Tukey FFT, se llama “mariposa” y su razón de fama es que no requiere multiplicaciones en absoluto, solo una suma compleja y una resta compleja y necesita solo una ubicación compleja de almacenamiento temporal. Esto se ilustra en la Figura 1: El factor primo y los algoritmos de transformación de Winograd y el código se muestra en la Figura 2: Los algoritmos de factor principal y de transformación de Winograd. La segunda longitud más utilizada esN=2N=2“role="presentation” style="position:relative;” tabindex="0">\(N=4\) porque es la única otra longitud corta que no requiere multiplicaciones y un mínimo de adiciones. Todas las demás FFT cortas requieren alguna multiplicación pero para potencias de dos,N=2N=2“role="presentation” style="position:relative;” tabindex="0">\(N=8\) yN=2N=2“role="presentación” style="position:relative;” tabindex="0">\(N=16\)N=8N=8“role="presentation” style="position:relative;” tabindex="0"> requieren pocos suficientes para valer una codificación especial para algunas situaciones.
Código para otras longitudes cortas como los primosN=3, 5, 7, 11, 13, 17 y 19N=3, 5, 7, 11, 13, 17 y 19“role="presentation” style="position:relative;” tabindex="0">\(N=3,5,7,11,13,17,19\) y los compuestosN=2N=2“role="presentation” style="position:relative;” tabindex="0">\(N=9\) yN=2N=2“role="presentación” style="position:relative;” tabindex="0">\(N=25\)N=8N=8“role="presentación” style="position:relative;” tabindex="0">N=9y25N=9y25“role="presentation” style="position:relative;” tabindex="0"> se incluyen en los programas para el algoritmo de factor primo o el WFTA. Se derivan utilizando la teoría de los Capítulos 5, 6 y 9.
Si estos FFT cortos se utilizan como módulos en el algoritmo básico de factor primo (PFA), entonces se utiliza el desarrollo directo utilizado para los módulos en la Figura 17.12. Sin embargo, si el uso de indexación más complicado para lograr en orden, el cálculo in place usado en {xxxxx} requieren código diferente.
Para cada una de las longitudes indicadas, el código de computadora se da en un módulo de Connexions.
No están en la colección Fast Fourier Transforms ya que la versión impresa sería demasiado larga. Sin embargo, se puede enlazar a ellos en línea desde los siguientes botones: N=2 N=3 N=4 N=5 N=7 N= 8 N= 9 N= l1 N= 13 N= 16 N= 17 N= 19 N= 25 Las versiones para el algoritmo de factor primo in place, en orden {pfa} se pueden obtener de: N=2 N=3 N=4 N=5 N=7 N=8 N=9 N=L1 N=13 N=16 N=17 =19 N=25 Un reporte técnico que describe la longitud 11, 13, 17 y 19 está en {report 8105} y otro reporte técnico que describe un programa que generará automáticamente una FFT de longitud prime y su gráfica de flujo si en {report xxx}.
