La FFT de base dividida es un algoritmo de transformada de Fourier rápida (FFT) para calcular la transformada de Fourier discreta (DFT), y fue descrita por primera vez en un artículo inicialmente poco apreciado por R. Yavne (1968) y posteriormente redescubierto simultáneamente por varios autores en 1984. (El nombre "split radix" fue acuñado por dos de estos reinventores, P. Duhamel y H. Hollmann .) En particular, split radix es una variante del algoritmo Cooley-Tukey FFT que usa una combinación de radix 2 y 4 : expresa de forma recursiva una DFT de longitud N en términos de una DFT más pequeña de longitud N/ 2 y dos EPS más pequeños de longitud N / 4.
La FFT split-radix, junto con sus variaciones, larga tuvo la distinción de alcanzar el recuento de operación más bajo publicado aritmética (número exacto total de requeridos reales adiciones y multiplicaciones) para calcular un DFT de poder-de-dos tamaños N . El recuento aritmético del algoritmo de base dividida original se mejoró en 2004 (con las ganancias iniciales obtenidas en un trabajo inédito de J. Van Buskirk a través de la optimización manual para N = 64 [1] [2] ), pero resulta que uno todavía puede alcanzar el nuevo recuento más bajo mediante una modificación de split radix (Johnson y Frigo, 2007). Aunque el número de operaciones aritméticas no es el único factor (o incluso necesariamente el factor dominante) para determinar el tiempo requerido para calcular una DFT en una computadora , la cuestión del conteo mínimo posible es de un interés teórico de larga data. (Actualmente no se ha probado ningún límite inferior estricto en el recuento de operaciones).
El algoritmo de base dividida solo se puede aplicar cuando N es un múltiplo de 4, pero como divide una DFT en DFT más pequeñas, se puede combinar con cualquier otro algoritmo FFT según se desee.
Descomposición de base dividida
Recuerde que la DFT se define mediante la fórmula:
dónde es un número entero que va desde a y denota la raíz primitiva de la unidad :
y por lo tanto: .
El algoritmo de base dividida funciona expresando esta suma en términos de tres sumas más pequeñas. (Aquí, damos la versión de "diezmado en el tiempo" de la FFT de base dividida; el diezmado dual en la versión de frecuencia es esencialmente el reverso de estos pasos).
Primero, una suma de los índices pares. En segundo lugar, una suma de los índices impares divididos en dos partes: y , según que el índice sea 1 o 3 módulo 4. Aquí, denota un índice que va de 0 a . Las sumas resultantes se ven así:
donde hemos utilizado el hecho de que . Estas tres sumas corresponden a porciones de radix-2 (tamaño N / 2) y radix-4 (tamaño N / 4) pasos Cooley-Tukey, respectivamente. (La idea subyacente es que la subtransformación de índice par de radix-2 no tiene un factor multiplicativo frente a ella, por lo que debe dejarse como está, mientras que la subtransformación de índice impar de radix-2 se beneficia al combinar una segunda subdivisión recursiva .)
Estas sumas más pequeñas son ahora exactamente DFT de longitud N / 2 y N / 4, que se pueden realizar de forma recursiva y luego recombinarse.
Más específicamente, dejemos denotar el resultado de la DFT de longitud N / 2 (para), y deja y denotar los resultados de las DFT de longitud N / 4 (para). Entonces la salida es simple:
Esto, sin embargo, realiza cálculos innecesarios, ya que resultan compartir muchos cálculos con . En particular, si sumamos N / 4 a k , el tamaño- N / 4 DFT no cambia (porque son periódicos en k ), mientras que el tamaño- N / 2 DFT no cambia si agregamos N / 2 a k . Entonces, las únicas cosas que cambian son las y términos, conocidos como factores twiddle . Aquí usamos las identidades:
para finalmente llegar a:
que da todas las salidas si dejamos intervalo de a en las cuatro expresiones anteriores.
Observe que estas expresiones están organizadas de modo que necesitemos combinar las distintas salidas de DFT por pares de sumas y restas, que se conocen como mariposas . Para obtener el recuento mínimo de operaciones para este algoritmo, es necesario tener en cuenta casos especiales para (donde los factores twiddle son la unidad) y para (donde los factores twiddle son y se puede multiplicar más rápidamente); véase, por ejemplo, Sorensen et al. (1986). Multiplicaciones por y normalmente se cuentan como libres (todas las negaciones se pueden absorber convirtiendo las sumas en sustracciones o viceversa).
Esta descomposición se realiza de forma recursiva cuando N es una potencia de dos. Los casos base de la recursividad son N = 1, donde la DFT es solo una copia, y N = 2, donde la DFT es una adición y una resta .
Estas consideraciones dan como resultado un recuento: Sumas y multiplicaciones reales, para N > 1 una potencia de dos. Este recuento asume que, para potencias impares de 2, el factor sobrante de 2 (después de todos los pasos de base dividida, que dividen N entre 4) es manejado directamente por la definición de DFT (4 sumas y multiplicaciones reales), o equivalentemente por un radix-2 paso Cooley – Tukey FFT.
Referencias
- R. Yavne, "Un método económico para calcular la transformada discreta de Fourier", en Proc. AFIPS Fall Joint Computer Conf. 33 , 115-125 (1968).
- P. Duhamel y H. Hollmann, "Algoritmo FFT de radix dividido", Electron. Letón. 20 (1), 14-16 (1984).
- M. Vetterli y HJ Nussbaumer, "Algoritmos simples FFT y DCT con un número reducido de operaciones", Signal Processing 6 (4), 267-278 (1984).
- JB Martens, "Factorización ciclotómica recursiva: un nuevo algoritmo para calcular la transformada discreta de Fourier", IEEE Trans. Acoust., Speech, Signal Processing 32 (4), 750–761 (1984).
- P. Duhamel y M. Vetterli, "Transformadas rápidas de Fourier: una revisión tutorial y un estado del arte", Signal Processing 19 , 259-299 (1990).
- SG Johnson y M. Frigo, " Una FFT de base dividida modificada con menos operaciones aritméticas ", IEEE Trans. Proceso de señal. 55 (1), 111-119 (2007).
- Douglas L. Jones, " Algoritmos FFT de base dividida " , sitio web de Connexions (2 de noviembre de 2006).
- HV Sorensen, MT Heideman y CS Burrus, "Sobre el cálculo de la FFT de base dividida", IEEE Trans. Acoust., Speech, Signal Processing 34 (1), 152-156 (1986).