14.1: Apéndice 1 - Flujogramas FFT

Las siguientes cuatro cifras son gráficas de flujo para los FFT Radix-2 Cooley-Tukey. La primera es una FFT de longitud 16, decimation-in-frequency Radix-2 con los datos de entrada en orden y datos de salida cifrados. La primera etapa tiene 8 “mariposas” de longitud-2 (que se superponen en la figura) seguidas de 8 multiplicaciones por potencias de W que se denominan “factores de twiddle”. La segunda etapa tiene 2 FFT de longitud-8 los cuales son calculados cada uno por 4 mariposas seguidas de 4 multiplicaciones. La tercera etapa tiene 4 FFT de longitud-4, cada una calculada por 2 mariposas seguidas de 2 multiplica y la última etapa es simplemente 8 mariposas seguidas de multiplica trivial por una. Esta gráfica de flujo debe compararse con el mapa de índices en Descripción polinómica de señales, la descomposición polinómica en La DFT como Convolución o Filtrado, y el programa en el Apéndice 3. En el programa, las mariposas y las multiplicaciones de factores de twiddle se realizan juntas en el bucle más interno. El bucle más externo se indexa a través de las etapas. Si la longitud de la FFT es una potencia de dos, el número de etapas es esa potencia (log N).

La segunda figura a continuación es una FFT de decimation-in-time de longitud 16 con los datos de entrada cifrados y los datos de salida en orden. La primera etapa tiene 8 “mariposas” de longitud-2 seguidas de 8 multiplicaciones de factores de twiddle. La segunda etapa tiene 4 FFT de longitud-4 los cuales son calculados cada uno por 2 mariposas seguidas de 2 multiplicaciones. La tercera etapa tiene 2 FFT de longitud-8, cada una calculada por 4 mariposas seguidas de 8 multiplica y la última etapa es simplemente 8 mariposas de longitud-2. Esta gráfica de flujo debe compararse con el mapa de índices en Descripción polinómica de señales, la descomposición polinómica en La DFT como Convolución o Filtrado, y el programa en el Apéndice 3. Aquí, la FFT debe estar precedida por un codificador.

Las figuras tercera y cuarta a continuación son una decimation-in-frequency de longitud-16 y una decimation-in-time pero, a diferencia de las cifras anteriores, el DIF tiene la salida en orden que requiere una entrada cifrada y el DIT tiene la entrada en orden que requiere que la salida sea descifrada. Comparar con las dos primeras cifras. Anote el orden de los factores de twiddle. El número de adiciones y multiplicaciones en los cuatro gráficos de flujo es el mismo y la estructura del programa de tres bucles que ejecuta el gráfico de flujo es la misma.

Fig. 14.1.1 Longitud-16, Decimation-in-Frequency, Entrada en orden, Radix-2 FFT

Fig. 14.1.2 Longitud-16, Decimation-in-Frequency, Salida en orden, Radix-2 FFT

Fig. 14.1.3 Longitud-16, Decimation-in-Frequency, Salida en orden, Radix-2 FFT

Fig. 14.1.4 Longitud-16, Decimation-in-Frequency, Salida en orden, Radix-2 FFT

La siguiente es una FFT Radix-4 de decimatión-en-frecuencia de longitud 16 con los datos de entrada en orden y los datos de salida cifrados. Hay dos etapas con la primera etapa que tiene 4 “mariposas” de longitud-4 seguidas de 12 multiplicaciones por potencias de W que se denominan “factores de twiddle”. La segunda etapa tiene 4 FFT de longitud-4 los cuales son calculados cada uno por 4 mariposas seguidas de 4 multiplicaciones. Tenga en cuenta que cada etapa aquí parece dos etapas pero es una y sólo hay un lugar donde aparecen las multiplicaciones de factores de twiddle. Esta gráfica de flujo debe compararse con el mapa de índices en Descripción polinómica de señales, la descomposición polinómica en La DFT como Convolución o Filtrado, y el programa en el Apéndice 3 - Programas de Computación FFT. Log a la base 4 de 16 es 2. El número total de multiplicación del factor de twiddle aquí es 12 en comparación con 24 para la radix-2. El unscrambler es un contador de orden inverso de base cuatro en lugar de un contador inverso de bits, sin embargo, una modificación de las mariposas de base cuatro permitirá que se use un contador inverso de bits con la FFT de radix-4 como con la radix-2.

Fig. 14.1.5 Longitud-16, Decimation-in-Frequency, Salida en orden, Radix-4 FFT

Los siguientes dos diagramas de flujo son FFT de base dividida de decimacion en frecuencia de longitud 16 con los datos de entrada en orden y datos de salida cifrados. Debido a que las “mariposas” tienen forma de L, las etapas no progresan uniformemente como la Radix-2 o 4. Estas dos figuras son las mismas con la primera dibujada de manera que se compara con la Radix-2 y 4, y la segunda para ilustrar las mariposas en forma de L. Estas gráficas de flujo deben compararse con el mapa de índices en Descripción polinómica de señales y el programa en el Apéndice 3 - Programas de Computación FFT. Debido a las etapas no uniformes, la indexación del programa es más complicada. Aunque el número de multiplicaciones de factores de twiddle es 12 como fue el caso de radix-4, para longitudes más largas, el split-radix tiene un poco menos multiplicaciones que el radix-4.

Debido a que las estructuras de los FFT de radix-2, radix-4 y split-radix son las mismas, el número de adiciones de datos es el mismo para todos ellos. Sin embargo, cada multiplicación compleja de factores de twiddle requiere dos adiciones reales (y cuatro multiplicaciones reales) el número de adiciones será menor para las estructuras con menos multiplicaciones.

Fig. 14.1.6 Longitud-16, Decimation-in-Frequency, Salida en orden, FFT Split-Radix

Fig. 14.1.5 Longitud-16, Decimation-in-Frequency, Split-Radix con FFT especial de BfS

Colaborador

• ContribeeBurrus