Diagrama de mariposa

Gráfico de flujo de señal que conecta las entradas x (izquierda) a las salidas y que dependen de ellas (derecha) para un paso de "mariposa" de una FFT Cooley-Tukey radix-2. Este diagrama se asemeja 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 le llama 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 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 radix-2, como se describe a continuación. ^[1] Se cree que la primera aparición impresa del término se produjo 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.

Más comúnmente, el término "mariposa" aparece en el contexto del algoritmo FFT de Cooley-Tukey , que descompone recursivamente una DFT de tamaño compuesto n  =  rm en r transformaciones más pequeñas de tamaño m donde r es la "base" de la transformada. Estas DFT más pequeñas luego se combinan a través de mariposas de tamaño r , que a su vez son DFT de tamaño r (realizadas m veces en las salidas correspondientes de las subtransformaciones) premultiplicadas por raíces de la unidad (conocidas como factores de giro ). (Este es el caso de "diezmado en el tiempo"; también se pueden realizar los pasos a la inversa, conocidos como "diezmado en frecuencia", donde las mariposas aparecen primero y se multiplican posteriormente por factores de giro. Consulte también el artículo Cooley-Tukey FFT .)

Diagrama de mariposa Radix-2

En el caso del algoritmo Cooley-Tukey radix-2, la mariposa es simplemente una DFT de tamaño 2 que toma dos entradas ( x ₀ ,  x ₁ ) (salidas correspondientes de las dos subtransformadas) y proporciona dos salidas ( y ₀ ,  y ₁ ) por la fórmula (sin incluir los 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í el nombre (ver también la ilustración a la derecha). ).

Una FFT de diezmado en el tiempo de base 2 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 radix-2 en n  = 2 ^p entradas con respecto a una n -ésima raíz 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 calcula. Mientras que la transformación inversa correspondiente se puede realizar matemáticamente reemplazando ω con ω ⁻¹ (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 todas las demás palabras 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 la gran matriz. ^[4]

Ver también

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

Referencias

1. Alan V. Oppenheim, Ronald W. Schafer y John R. Buck, Procesamiento de señales en tiempo discreto , segunda edición (Upper Saddle River, Nueva Jersey: Prentice Hall, 1989)
2. CJ Weinstein (21 de noviembre de 1969). Efectos de cuantificación en filtros digitales (Reporte). Laboratorio Lincoln del MIT . pag. 42. Archivado desde el original el 11 de febrero de 2015 . Consultado el 10 de febrero de 2015 . Este cálculo, denominado "mariposa".
3. Cipra, Barry A. (4 de junio de 2012). "Diagrama de mariposa y FFT". mathoverflow.net . Consultado el 10 de febrero de 2015 .
4. * Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 7.2 Hash 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 de agosto de 2011 , consultado el 13 de agosto de 2011

Enlaces externos

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