Diagrama de mariposa

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 discretas de Fourier (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 base 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" suele aparecer en el contexto del algoritmo FFT de Cooley-Tukey , 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 base de la transformada. Estas DFT más pequeñas se combinan mediante mariposas de tamaño r , que a su vez son DFT de tamaño r (realizadas m veces sobre las salidas correspondientes de las subtransformadas) premultiplicadas por raíces de la unidad (conocidas como factores de rotación ). (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 se aplican primero y se postmultiplican por factores de rotación. Véase también el artículo sobre la FFT de Cooley-Tukey ). 

_{En el} caso del algoritmo Cooley-Tukey de base 2, la mariposa es simplemente una DFT de tamaño 2 que toma dos entradas ( _{x0 ,} x1 ) ( salidas correspondientes de las dos subtransformadas) y da dos salidas ( y0 _, y1 ) mediante la fórmula (sin incluir factores de giro ):  

${\displaystyle y_{0}=x_{0}+x_{1}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}.\,}$

Si se dibuja el diagrama de flujo de datos para este par de operaciones, las líneas ( x ₀ , x ₁ ) a ( y ₀ , y ₁ ) se cruzan y se asemejan a las alas de una mariposa , de ahí su nombre (véase también la ilustración de la derecha).  

Más específicamente, un algoritmo FFT de decimación en el tiempo de base 2 sobre n  =  2 ^p entradas con respecto a una raíz n -ésima primitiva de la unidad. ${\displaystyle \omega _{n}^{k}=e^{-{\frac {2\pi ik}{n}}}}$Se basa en O( n  log ₂ n ) mariposas de la forma: 

${\displaystyle y_{0}=x_{0}+x_{1}\omega _{n}^{k}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}\omega _{n}^{k},\,}$

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:

${\displaystyle x_{0}={\frac {1}{2}}(y_{0}+y_{1})\,}$

${\displaystyle x_{1}={\frac {\omega _ {n}^{-k}}{2}}(y_{0}-y_{1}),\,}$

correspondiente a un algoritmo FFT de decimación en frecuencia.

La mariposa también puede utilizarse para mejorar la aleatoriedad de grandes conjuntos de números parcialmente aleatorios, poniendo en contacto causal cada palabra de 32 o 64 bits con todas las demás palabras mediante un algoritmo de hash deseado, de modo que un cambio en cualquier bit tenga la posibilidad de cambiar todos los bits del conjunto grande. ^{[ 4 ]}

• Diagrama matemático
• Lema de Zassenhaus
• Diagrama de flujo de señales

• Explicación de la FFT y los diagramas de mariposa .
• Diagramas de mariposa de varias implementaciones de FFT (Radix-2, Radix-4, Split-Radix) .