TWIDDLE FACTOR
Para comprender la importancia del
Twiddle Factor y su importancia en el cálculo de la FFT (es decir, Fast Fourier
Transform, en inglés), es vital recordar que es la FFT, donde radica su
importancia, cuales son las características del algoritmo para su evaluación,
entre otros detalles que se mencionarán a continuación:
FFT (Fast Fourier
Transform) es la abreviatura usual
de un eficiente algoritmo que permite calcular la transformada de Fourier discreta (DFT) y su inversa. La FFT es de
gran importancia en una amplia variedad de aplicaciones, desde el tratamiento digital de señales y filtrado
digital en general a la resolución de ecuaciones en derivadas parciales o los algoritmos de multiplicación rápida de grandes
enteros. Las aplicaciones de la transformada rápida
de Fourier son múltiples. Es la base de muchas operaciones fundamentales del
procesamiento de señales, donde tiene amplia utilización. Además, proporciona
un medio oportuno para mejorar el rendimiento de los algoritmos para un
conjunto de problemas aritméticos comunes.
Brevemente se revisará en qué consiste el
algoritmo para determinar la DFT (del Inglés Discrete Fourier Transform). Sean x0, ...., xn-1 números
complejos. La transformada discreta de Fourier (DFT) se define como:
La evaluación directa de esa fórmula requiere
O(n²) operaciones aritméticas. Mediante un algoritmo la FFT se puede
obtener el mismo resultado con sólo O(n log n)
operaciones reduciendo su tiempo de ejecución. En general, dichos algoritmos
dependen de la factorización de n pero, al contrario de lo que
frecuentemente se cree, existen FFTs para cualquier n, incluso con n primo.
La idea que permite esta optimización es la
descomposición de la transformada a tratar en otras más simples y éstas a su
vez hasta llegar a transformadas de 2 elementos donde k puede tomar los valores
0 y 1 (Ver Diagrama de Mariposa). Una vez resueltas las transformadas más
simples hay que agruparlas en otras de nivel superior que deben resolverse de
nuevo y así sucesivamente hasta llegar al nivel más alto. Al final de este
proceso, los resultados obtenidos deben reordenarse (es lo que hace el algoritmo
de Cooley- Tukey).
Históricamente, el desarrollo de la
FFT, se remonta a la guerra fría, periodo durante el cual EEUU buscaba obtener
información acerca de las pruebas nucleares
realizadas en la extinta Unión Soviética,
y de los cuales uno de los desarrollos obtenidos fue Twiddle Factor, lo cual
permitió optimizar el cálculo de la FFT, al combinarlo con el algoritmo de
Cooley-Tukey. Al parecer, a Tukey, se le ocurrió la idea durante una reunión de un
comité asesor presidencial de EE.UU. discutiendo maneras de detectar ensayos de armas
nucleares en la Unión Soviética. Otro de los participantes en esa reunión,
Richard Garwin de IBM, reconoció el potencial del método de Tukey y lo puso en contacto con
Cooley, quien implementó un método diferente (y menos-clasificado): análisis de
los datos cristalográficos 3D (algo así como: FFT Multidimensional). Cooley y
Tukey posteriormente publicaron su documento conjunto, y fue aceptado
rápidamente.
El algoritmo para el cálculo de la FFT no es reciente, data de 1805 y fue inventado por Carl Friedrich Gauss, quien lo usó para interpolar la trayectoria de los asteroides Pallas y Juno, sin embargo su trabajo no fue reconocido hasta después de su muerte. La FFT se hizo popular después de que J. Cooley y J. Tukey publicaran su trabajo en el cual reinventaron el algoritmo describiendo como desarrollarlo convenientemente en una computadora. El hecho de que Gauss haya descrito el mismo algoritmo (aunque sin analizar su costo asintótico) no se realizó sino hasta varios años después en 1965.
El algoritmo para el cálculo de la FFT no es reciente, data de 1805 y fue inventado por Carl Friedrich Gauss, quien lo usó para interpolar la trayectoria de los asteroides Pallas y Juno, sin embargo su trabajo no fue reconocido hasta después de su muerte. La FFT se hizo popular después de que J. Cooley y J. Tukey publicaran su trabajo en el cual reinventaron el algoritmo describiendo como desarrollarlo convenientemente en una computadora. El hecho de que Gauss haya descrito el mismo algoritmo (aunque sin analizar su costo asintótico) no se realizó sino hasta varios años después en 1965.
Ampliando un poco, El algoritmo de Cooley-Tukey,
debe su nombre a: J.W. Cooley de
IBM y John Tukey
de Princenton, y es el algoritmo
más común para calcular la transformada
rápida de Fourier (FFT). El cual, re-expresa la transformada
discreta de Fourier (DFT) de
un tamaño arbitrario compuesto N = n1n2 en términos de DFT más pequeñas de
tamaños N1 y N2,
de forma alternativa, con el fin de
reducir el tiempo de cálculo a O (N log N). Debido a
la importancia del algoritmo, el
cual es considerado la piedra angular de la informática; las variantes específicas
y formas de ejecución lo ha dado a
conocer por el nombre de sus creadores.
Debido a que el algoritmo de Cooley-Tukey fragmenta la DFT en DFT más pequeñas, se puede combinar arbitrariamente con cualquier otro algoritmo para la DFT. Por ejemplo, el algoritmo de Rader o Bluestein que se puede utilizar para manejar grandes factores primos que no pueden ser descompuestos por el algoritmo: Cooley-Tukey.
Debido a que el algoritmo de Cooley-Tukey fragmenta la DFT en DFT más pequeñas, se puede combinar arbitrariamente con cualquier otro algoritmo para la DFT. Por ejemplo, el algoritmo de Rader o Bluestein que se puede utilizar para manejar grandes factores primos que no pueden ser descompuestos por el algoritmo: Cooley-Tukey.
Ahora si responderemos a la pregunta: ¿Qué
es el Twiddle Factor? El Twiddle Factor, es un coeficiente trigonométrico que
se multiplica con los datos durante la FFT (Fast Fourier Transform) y que fue
estandarizado por Gentleman & Sandle
en 1966.
El Twiddle Factor, puede entenderse
como un vector que gira en forma circular a través del plano complejo S y el
cual tiene un valor para cada una de las muestras usadas para calcular la
transformada de Fourier, los cuales están separados por un ángulo definido también por un numero de muestras.
Gráficamente, puede describirse por la siguiente imagen:
Figura 1. El Twiddle Factor, W,
describe un "vector giratorio", que gira en incrementos de acuerdo con el número de muestras, N.
Figura 2. El
mismo conjunto de valores de W, se repite una y otra vez para diferentes
valores de n. También los que están en
180° aparte de los valores negativos.
Estos valores son usados en el cálculo de la DFT y hacen posible como ya
se dijo la FFT.
Como se muestra
en la figura anterior, el Twiddle Factor es redundante en los valores,
como el vector rota alrededor. Por ejemplo W para N
= 2, es la misma para n =
0, 2, 4, 6, etc, y W para
N = 8 es la misma para n
= 3, 11, 19, 27, etc.
Además, es simétrico por el hecho de que los valores que están 180 grados fuera de fase son el negativo de uno al otro. Así, por ejemplo, W para N = 4 muestras, siendo n = 0, 4,8, etc., son el negativo de n = 2, 6,10, etc.
El diagrama de la mariposa se aprovecha de esta redundancia y la simetría, que es parte de lo que hace la FFT posible.
El diagrama de la mariposa se basa en la expresión Danielson-Lanczos y el factor twiddle para crear un algoritmo eficiente. El diagrama de la mariposa, corresponde a una representación gráfica del algoritmo FFT.
A continuación, se muestra el diagrama de una mariposa simple. Es una unidad básica, que consiste en sólo dos entradas y dos salidas.
Además, es simétrico por el hecho de que los valores que están 180 grados fuera de fase son el negativo de uno al otro. Así, por ejemplo, W para N = 4 muestras, siendo n = 0, 4,8, etc., son el negativo de n = 2, 6,10, etc.
El diagrama de la mariposa se aprovecha de esta redundancia y la simetría, que es parte de lo que hace la FFT posible.
El diagrama de la mariposa se basa en la expresión Danielson-Lanczos y el factor twiddle para crear un algoritmo eficiente. El diagrama de la mariposa, corresponde a una representación gráfica del algoritmo FFT.
A continuación, se muestra el diagrama de una mariposa simple. Es una unidad básica, que consiste en sólo dos entradas y dos salidas.
A continuación se muestra paso a paso como se construye un diagrama de mariposa de 4-entradas.
Para
4 entradas:
Contando
desde 0 a 3 en binario 00, 01, 10, 11. Ahora el inverso los bits de cada número
obtenida: 00, 10, 01,11. En decimal esto es 0, 2, 1, y 3.
El algoritmo de Cooley- Tukey ilustrado por
el diagrama de Mariposa. Se puede ilustrar mediante el siguiente ejemplo,
calculando la TFR de un conjunto de cuatro muestras de datos utilizando el
algoritmo. Definiendo el conjunto de muestras de una señal como la señal X₀[n]
en TD de forma que los datos de entrada para el algoritmo sea {X₀[0], X₀[1], X₀[2], X₀[3]}.
La fórmula de la TFD es la siguiente:
Tomando como entrada una señal discreta x[n]
con N muestras, se basa en dividir la señal de entrada en otras dos señales de
N/2 muestras (por un lado los coeficientes pares y por otro los impares), y se
envían cada una de estas sub-señales a una FFT de tamaño N/2 puntos. Cada uno
de los coeficientes de salida de la FFT de las muestras impares se multiplica por, donde k es la posición del vector salida, y se suma a
las muestras pares. A su vez, las FFT de N/2 puntos se pueden resolver de esta
misma manera, realizando esta operación de manera recursiva hasta obtener una
FFT de una señal de tamaño 2, cuyo resultado es:
A estos números
marcados como W se conocen como “Twiddle Factors” y como se mencionó, sirven
para facilitar el cálculo de la FFT cuyas utilidades disfrutamos hoy, como son:
Tratamiento de imagen (JPEG) y
audio (MP3),Reducción de ruido en señales, como el ruido blanco, Análisis en frecuencia de cualquier señal discreta,
Análisis de materiales y estadística, Síntesis, mediante la transformada inversa IFFT
BIBLIOGRAFIA:
http://es.wikipedia.org/wiki/Transformada_r%C3%A1pida_de_Fourier
Wikipedia, the free encyclopedia
No hay comentarios:
Publicar un comentario