Mariposa (FFT)

Butterfly  es un paso elemental en el algoritmo Cooley-Tukey FFT para calcular la transformada rápida de Fourier .

La duración del paso de mariposa determina la duración del cálculo de la transformada de Fourier. [una]

En su forma más simple (mariposa radix-2) es una transformación de dos puntos.

Fórmula para calcular "Mariposas": [1]

Designaciones: , – puntos iniciales; , – puntos de resultado, – coeficiente complejo.

Para datos FFT de tamaño , se requiere calcular la operación Mariposa de 2 Radix. [1] [2] [3]

A veces se utilizan operaciones de mariposa de orden superior: Radix-4, Radix-8. Radix-4 es aproximadamente un 20 % más eficiente para la transformada de Fourier de grandes cantidades de datos. Una operación superior a 8 prácticamente no se utiliza debido a ganancias de rendimiento insignificantes y dificultades en la implementación (consumo de recursos). [4] [5]

Se puede utilizar una estructura similar en las implementaciones del algoritmo de Viterbi (operación ACS - Añadir-Comparar-Seleccionar) [6] .

Notas

  1. ↑ 1 2 3 Implementación de una FFT entera en procesadores con arquitectura ARM // Circuito No. 3 Marzo 2001
  2. ↑ L. Rabiner y B. Gould "Teoría y aplicaciones del procesamiento de señales digitales".
  3. ↑ Copia archivada (enlace no disponible) . Consultado el 29 de diciembre de 2012. Archivado desde el original el 14 de agosto de 2003. 
  4. ↑ http://www.ece.ucdavis.edu/~bbaas/281/slides/Handout.fft2.pdf Archivado el 6 de diciembre de 2012 en Wayback Machine Higher Radices
  5. ↑ http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html Archivado el 30 de abril de 2010 en Wayback Machine Radix-4 FFT Algorithm; Figura TC.3.9 Cálculo mariposa básico en un algoritmo FFT radix-4
  6. ↑ Implementing the Viterbi Algorithm in Today's Digital Communications Systems Archivado el 25 de diciembre de 2012 en Wayback Machine // Design And Reuse (EETimes): "Las instrucciones de Viterbi ACS se basan en la estructura y simetría de la mariposa de Viterbi. La estructura se llama "mariposa" debido a su parecido físico con el animal.”, Figuras 8-10

Enlaces