8.6: La Transformada Rápida de Fourier - Una FFT basada en simetrías

El desarrollo de algoritmos rápidos suele consistir en utilizar propiedades especiales del algoritmo de interés para eliminar operaciones redundantes o innecesarias de una implementación directa. La transformada discreta de Fourier (DFT) definida por

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

donde

\[W_{N}=e^{-j2\pi /N} \nonumber \]

tiene una enorme capacidad de mejora de su eficiencia aritmética. La mayoría de los algoritmos rápidos utilizan las propiedades periódicas y simétricas de sus funciones básicas. La FFT clásica de Cooley-Tukey y la FFT de factor primo explotan las propiedades periódicas de las funciones coseno y seno. Su uso de las periodicidades para compartir y, por lo tanto, reducir las operaciones aritméticas depende de la factoriabilidad de la longitud de los datos a transformar. Para longitudes altamente compuestas, el número de operaciones en coma flotante es de orden\(N\log (N)\) y para longitudes primos es de orden\(N^2\).

Esta sección analizará un enfoque utilizando las propiedades simétricas para eliminar redundancias. Esta posibilidad ha sido reconocida desde hace mucho tiempo pero no se ha desarrollado de ninguna manera sistemática en la literatura abierta. Desarrollaremos un algoritmo, llamado la transformada rápida de Fourier (QFT), que reducirá el número de operaciones de punto flotante necesarias para calcular la DFT por un factor de dos a cuatro sobre métodos directos o el método de Goertzel para longitudes primos. En efecto, parece ser el mejor algoritmo general disponible para DFT de longitud prime. Siempre se puede hacer mejor usando algoritmos de tipo Winograd, pero deben diseñarse individualmente para cada longitud. La transformada Z Chirp se puede utilizar para longitudes más largas.

Simetrías de entrada y salida

Utilizamos el hecho de que el coseno es una función par y el seno es una función impar. El kernel de la DFT o las funciones base de la expansión viene dado por

\[W_{N}^{nk}=e^{-j2\pi nk/N}=\cos (2\pi nk/N)+j\sin (2\pi nk/N) \nonumber \]

que tiene una parte real par y una parte imaginaria extraña. Si los datos\(x(n)\) se descomponen en sus partes reales e imaginarias y esas en sus partes pares e impares, tenemos

\[x(n)=u(n)+jv(n)=\left [ u_e(n)+u_o(n) \right ]+j\left [ v_e(n)+v_o(n) \right ] \nonumber \]

donde la parte par de la parte real de\(x(n)\) está dada por

\[u_e(n)=(u(n)+u(-n))/2 \nonumber \]

y la parte extraña de la parte real es

\[u_o(n)=(u(n)-u(-n))/2 \nonumber \]

con las definiciones correspondientes de\(v_e(n)\) y\(v_o(n)\). Usando algoritmos de convolución con una notación más simple, el DFT de algoritmos de convolución se convierte en

\[C(k)=\sum_{n=0}^{N-1}(u+jv)(\cos -j\sin ) \nonumber \]

La suma sobre un número integral de períodos de una función impar es cero y la suma de una función par durante la mitad del período es la mitad de la suma en todo el período. Esto hace que las ecuaciones se conviertan

\[C(k)=\sum_{n=0}^{N/2-1}\left [ u_e\cos +v_o\sin \right ]+j\left [ v_e\cos -v_o\sin \right ] \nonumber \]

para\(k=0,1,2,...,N-1\)

La evaluación de la DFT usando la ecuación del algoritmo de convolución requiere la mitad de multiplicación real y la mitad de adiciones reales que evaluarla usando las otras ecuaciones. Hemos explotado las simetrías del seno y del coseno como funciones del índice de tiempo\(n\). Esto es independiente de si la longitud es compuesta o no. Otra visión de esta formulación es que hemos utilizado la propiedad de asociativamente de multiplicación y suma. En otras palabras, en lugar de multiplicar dos puntos de datos por el mismo valor de un seno o coseno luego agregar los resultados, primero se deben agregar los puntos de datos y luego multiplicar la suma por el seno o coseno que requiere una en lugar de dos multiplicaciones.

A continuación aprovechamos las simetrías del seno y el coseno como funciones del índice de frecuencia\(k\). El uso de estas simetrías en la ecuación da

\[C(k)=\sum_{n=0}^{N/2-1}\left [ u_e\cos +v_o\sin \right ]+j\left [ v_e\cos -v_o\sin \right ] \nonumber \]

\[C(N-k)=\sum_{n=0}^{N/2-1}\left [ u_e\cos -v_o\sin \right ]+j\left [ v_e\cos +v_o\sin \right ] \nonumber \]

para\(k=0,1,2,...,N/2-1\). Esto nuevamente reduce el número de operaciones en un factor de dos, esta vez porque calcula dos valores de salida a la vez. La primera reducción por un factor de dos siempre está disponible. El segundo solo es posible si se necesitan ambos valores de DFT. No está disponible si está calculando solo un valor de DFT. El desarrollo anterior no ha tratado los detalles que surgen con la diferencia entre una longitud par y otra impar. Eso es sencillo.

Reducciones adicionales si la longitud es par

Si la longitud de la secuencia a transformar es par, hay más simetrías que se pueden explotar. Habrá cuatro valores de datos que se multiplican todos por más o menos el mismo valor de seno o coseno. Esto significa que un proceso de pre-adición más complicado que es una generalización del cálculo simple de las partes pares e impares en las ecuaciones reducirá el tamaño de la\(N^2\) parte de orden del algoritmo en otro factor más de dos o cuatro. Si la longitud es divisible por 4, el proceso se puede repetir. En efecto, si la longitud es una potencia de 2, se puede demostrar que este proceso equivale a calcular la DFT en términos de transformaciones discretas de coseno y coseno con una complejidad aritmética resultante de orden\(N\log (N)\) y con una estructura que se adapta bien a cálculos de datos reales y poda.

Si se compara la gráfica de flujo de la FFT de Cooley-Tukey con la gráfica de flujo del QFT, se notan similitudes y diferencias. Ambos avanzan en etapas ya que la longitud se divide continuamente por dos. El algoritmo Cooley-Tukey utiliza las propiedades periódicas del seno y el coseno para dar el familiar árbol horizontal de las mariposas. Las líneas diagonales paralelas en esta gráfica representan el paso paralelo a través de los datos en sincronismo con las funciones de base periódica. El QFT tiene líneas diagonales que conectan el primer punto de datos con el último, luego el segundo con el siguiente al último, y así sucesivamente para dar una imagen como “estrella”. Esto es interesante porque se puede mirar el gráfico de flujo de un algoritmo desarrollado por alguna estrategia completamente diferente y a menudo encontrar sección con las estructuras paralelas y otras partes con la estructura estelar. Estos deben estar utilizando algunas propiedades periódicas y simétricas subyacentes de las funciones base.

Complejidad Aritmética y Temporizaciones

Un análisis cuidadoso del QFT muestra que\(2N\) las adiciones son necesarias para calcular las partes pares e impares de los datos de entrada. A esto le sigue la longitud del producto\(N/2\) interno que requiere multiplicaciones\(4(N/2)^2=N^2\) reales y un número igual de adiciones. A esto le siguen los cálculos necesarios para los cálculos simultáneos de la primera mitad y la última mitad de los\(C(k)\) cuales requieren adiciones\(4(N/2)=2N\) reales. Esto significa que el algoritmo QFT total requiere\(M^2\) multiplicaciones\(N^2+4N\) reales y adiciones reales. Estos números junto con los del algoritmo de Goertzel y el cálculo directo de la DFT se incluyen en la siguiente tabla. De los diversos algoritmos de orden-\(N^2\) DFT, el QFT parece ser el método general más eficiente para una longitud arbitraria\(N\).

Algorithm	Mults reales.	Adiciones reales	Trig Eval.
DFT Directo	\(4N^2\)	\(4N^2\)	\(2N^2\)
Mod. 2da Orden Goertzel	\(N^2+N\)	\(2N^2+N\)	\(N\)
QFT	\(N^2\)	\(N^2+4N\)	\(2N\)

Los tiempos de los algoritmos en una PC en milisegundos se dan en la siguiente tabla.

Algorithm	\(N=125\)	\(N=256\)
DFT Directo	4.90	19.83
Mod. 2O. Goertzel	1.32	5.55
QFT	1.09	4.50
Chirp + FFT	1.70	3.52

Estos tiempos rastrean bastante bien los recuentos de operación de punto flotante.

Conclusiones

El QFT es un algoritmo de DFT directo que utiliza todas las simetrías posibles de la función de base DFT sin requisitos sobre la longitud que es compuesta. Estas ideas han sido propuestas antes, pero no han sido publicadas ni claramente desarrolladas. Parece que el QFT básico es práctico y útil como algoritmo general para longitudes de hasta un centenar o así. Por encima de eso, la transformada z chirp u otros métodos basados en filtros serán superiores. Para casos especiales y longitudes más cortas, los métodos basados en las teorías de Winograd siempre serán superiores. Sin embargo, el QFT tiene un lugar definido en la matriz de algoritmos DFT y no es bien conocido. En el apéndice se incluye un programa Fortran.

Es posible, pero poco probable, que se pueda lograr una mayor reducción aritmética utilizando el hecho de que\(W_N\) tiene magnitud de unidad como se hizo en el algoritmo de Goertzel de segundo orden. También es posible que alguna forma de combinar el algoritmo Goertzel y QFT tenga algunas ventajas. Un desarrollo de una descomposición QFT completa de un DFT de longitud-\(2^M\) muestra una estructura interesante y complejidad aritmética comparable a las FFT promedio de Cooley-Tukey. Parece más adecuado para cálculos de datos reales con poda.

Colaborador

• ContribeeBurrus