Diagrama de mariposa

Diagrama de flujo de señales que conecta las entradas x (izquierda) con las salidas y que dependen de ellas (derecha) para un paso en "mariposa" de una FFT de Cooley-Tukey de base 2. Este diagrama se parece a una mariposa (como en la mariposa morfo que se muestra a modo de comparación), de ahí el nombre, aunque en algunos países también se lo denomina diagrama de reloj de arena.

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 ).

Diagrama de mariposa de base 2

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 ₀ ,  x ₁ ) (salidas correspondientes de las dos subtransformadas) y da dos salidas ( y ₀ ,  y ₁ ) mediante la fórmula (sin incluir los factores de torsión ):

${\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í el nombre (véase también la ilustración a la derecha).

Una FFT de radix 2 con diezmado en el tiempo divide una DFT de longitud N en dos DFT de longitud N /2 seguida de una etapa de combinación que consta de muchas operaciones de mariposa.

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 ₂ n ) mariposas de la forma:  ${\displaystyle \omega _{n}^{k}=e^{-{\frac {2\pi ik}{n}}}}$ 

${\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 ω ⁻¹ (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 diezmado en frecuencia.

Otros usos

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]

Véase también

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

Referencias

1. Alan V. Oppenheim, Ronald W. Schafer y John R. Buck, Procesamiento de señales en tiempo discreto , 2.ª edición (Upper Saddle River, NJ: Prentice Hall, 1989)
2. CJ Weinstein (1969-11-21). Efectos de cuantificación en filtros digitales (informe). MIT Lincoln Laboratory . p. 42. Archivado desde el original el 11 de febrero de 2015 . Consultado el 10 de febrero de 2015 . Este cálculo, al que se hace referencia como "mariposa",
3. Cipra, Barry A. (4 de junio de 2012). "FFT y diagrama de mariposa". mathoverflow.net . Consultado el 10 de febrero de 2015 .
4. * Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 7.2 Hashing completo de una matriz grande", Recetas numéricas: el arte de la computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8, archivado desde el original el 11-08-2011 , consultado el 13-08-2011

Enlaces externos

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