En el contexto de los algoritmos de transformada rápida de Fourier , una mariposa es una parte del cálculo que combina los resultados de transformadas de Fourier discretas (DFT) más pequeñas en una DFT más grande, o viceversa (dividiendo una DFT más grande en subtransformadas). El nombre "mariposa" proviene de la forma del diagrama de flujo de datos en el caso de radix-2, como se describe a continuación. [1] Se cree que la primera aparición impresa del término fue en un informe técnico del MIT de 1969. [2] [3] La misma estructura también se puede encontrar en el algoritmo de Viterbi , utilizado para encontrar la secuencia más probable de estados ocultos.
El término "mariposa" aparece más comúnmente en el contexto del algoritmo Cooley–Tukey FFT , que descompone recursivamente una DFT de tamaño compuesto n = rm en r transformadas más pequeñas de tamaño m , donde r es la "raíz" de la transformada. Estas DFT más pequeñas se combinan luego mediante mariposas de tamaño r , que a su vez son DFT de tamaño r (realizadas m veces en las salidas correspondientes de las subtransformadas) premultiplicadas por raíces de la unidad (conocidas como factores de twiddle ). (Este es el caso de "diezmado en el tiempo"; también se pueden realizar los pasos a la inversa, conocido como "diezmado en la frecuencia", donde las mariposas vienen primero y se multiplican posteriormente por factores de twiddle. Consulte también el artículo Cooley–Tukey FFT ).
En el caso del algoritmo Cooley-Tukey de base 2, la mariposa es simplemente una DFT de tamaño 2 que toma dos entradas ( x 0 , x 1 ) (salidas correspondientes de las dos subtransformadas) y da dos salidas ( y 0 , y 1 ) mediante la fórmula (sin incluir los factores de torsión ):
Si se dibuja el diagrama de flujo de datos para este par de operaciones, las líneas ( x 0 , x 1 ) a ( y 0 , y 1 ) se cruzan y se asemejan a las alas de una mariposa , de ahí el nombre (véase también la ilustración a la derecha).
Más específicamente, un algoritmo FFT de diezmado en el tiempo de base 2 sobre entradas n = 2 p con respecto a una raíz n -ésima primitiva de la unidad se basa en O( n log 2 n ) mariposas de la forma:
donde k es un número entero que depende de la parte de la transformación que se esté calculando. Mientras que la transformación inversa correspondiente se puede realizar matemáticamente reemplazando ω por ω −1 (y posiblemente multiplicando por un factor de escala general, dependiendo de la convención de normalización), también se pueden invertir directamente las mariposas:
correspondiente a un algoritmo FFT de diezmado en frecuencia.
La mariposa también se puede utilizar para mejorar la aleatoriedad de grandes conjuntos de números parcialmente aleatorios, poniendo cada palabra de 32 o 64 bits en contacto causal con cada otra palabra a través de un algoritmo hash deseado, de modo que un cambio en cualquier bit tenga la posibilidad de cambiar todos los bits en el conjunto grande. [4]
Este cálculo, al que se hace referencia como "mariposa",