ÍNDICE
1. INTRODUCCIÓN .........................................................................................................................2
2. MARCO TEÓRICO ......................................................................................................................3
2.1 Conceptos de la Transformada Rápida de Fourier ..................................................................3
2.1.1 Definición .........................................................................................................................3
2.1.2 Implementación matricial .................................................................................................3
2.1.3 Divide y vencerás .............................................................................................................4
2.1.4 Transformada rápida de Fourier (FFT) .............................................................................6
2.1.5 Introducción básica a la Transformada rápida de Fourier (FFT) ......................................8
2.2 Ejemplos de transformada rápida de Fourier (FFT) .............................................................. 12
2.2.1 Ejercicio 1 .......................................................................................................................12
2.5.3 Cuadro comparativo .......................................................................................................13
3. CONCLUSIÓN ............................................................................................................................13
1. INTRODUCCIÓN
Toda señal periódica puede ser representada por la suma de series de Fourier. Con un
análisis adecuado es posible obtener una representación de Fourier para señales de duración
finita. Esta representación es la que se conoce como la Transformada de Fourier Discreta
(TFD). La TFD se puede representar como:
Se puede observar a simple vista que su resolución directa implica N multiplicaciones
complejas y N-1 adiciones complejas por cada k. Por lo tanto, el cálculo directo de una TFD
es de orden 0 (N2). Para valores pequeños de N la resolución en sí no consume mucho tiempo
ni recursos. Sin embargo, para valores de N lo suficientemente grandes el cálculo directo se
torna poco eficiente, no sólo por el gran tiempo que consume sino también por el
acaparamiento de los recursos necesarios. Se puede ver, entonces, que el orden del cálculo
directo impone un límite en aquellas aplicaciones que hacen uso de la TFD, especialmente
las de tiempo real, dado que para valores mayores a cierto N el cálculo podrá resultar
demasiado lento y los recursos disponibles podrán ser insuficientes. Es así que aparece la
Transformada Rápida de Fourier (en inglés Fast Fourier Transform, FFT), un algoritmo para
el cálculo eficiente de la TFD. Su importancia radica en el hecho que elimina una gran parte
de los cálculos repetitivos a los que se ve sometida la TFD, por lo que se logra un cálculo
más rápido a menor costo. El algoritmo de la FFT fue originalmente inventado por Carl
Friedrich Gauss en 1805. Diferentes versiones del algoritmo fueron descubiertas a lo largo
de los años, pero la FFT no se hizo popular sino hasta 1965, con la publicación de James
Cooley y John Tukey, quienes reinventaron el algoritmo al describir como ejecutarlo de
forma eficiente en una computadora.
2. MARCO TEÓRICO
2.1 Conceptos de la Transformada Rápida de Fourier
Transformada rápida de Fourier (FFT)
El algoritmo de la transformada de Fourier Rápida (FFT), fue popularizado por los
matemáticos estadounidenses James William Cooley y John Wilder Tukey en 1965. La FFT
es un método eficiente para realizar el cálculo de la transformada discreta de Fourier (DFT),
el cual se puede realizar por:
2.1.1 Definición.
La DFT se puede calcular directamente con la expresión, como una suma utilizando
forloops para cada bin de frecuencia, generando N operaciones complejas por cada bin y N 2
operaciones complejas en total.
2.1.2 Implementación matricial.
Es posible escribir la ecuación anterior como un producto entre una matriz y un vector
de la siguiente manera:
Donde:
X y x son vectores Nx1.
WN es una matriz NxN.
El factor W=e-j2π/N=cos(2 π/N)-jsen(2 π/N), denominado Twiddle Constant.
Por lo que Wn= cos(2 πn/N)-jsen(2 πn/N)
Con lo anterior, el cálculo de un punto de la transformada discreta de Fourier está dada
por:
De esta forma la complejidad numérica no varía tanto, presenta mejoras notables, ya que
el cálculo de la DFT y su inversa solo requieren la multiplicación de un matriz y un vector.
Sin embargo, el cálculo directo de la DFT no es eficiente debido, fundamentalmente, a que
no explota las propiedades de simetría y periodicidad del factor de fase W que son de la
siguiente manera:
La periodicidad y simetría de los factores W se muestra en la siguiente figura:
2.1.3 Divide y vencerás.
Aquí la DFT se divide, de modo que para N se suman dos DFT de N/2, dividiendo la
complejidad numérica casi a la mitad y esto es lo que marca la base del algoritmo. Se parte
dividiendo el cálculo en pares e impares.
Y si tenemos que x0=x(2m) para la muestra par y x1=x(2m+1) para impar, tenemos:
Descomposición de una DFT de N puntos en 2 DFTs de N/2 puntos, para N = 8 se ilustra
en la siguiente figura:
2.1.4 Transformada rápida de Fourier (FFT)
Este algoritmo entrega los mismos resultados que por definición de la DFT pero optimiza
el uso computacional. La división que se presentó antes se puede emplear recursivamente
hasta llegar al bloque más pequeño posible de DFT de N=2.
Esta implementación recursiva de FFT se conoce como radix 2 la cual es una de las más
comunes y baja la complejidad numérica de la DFT de N2 a Nlog2(N).
La siguiente figura presenta el esquema de una estructura de reducción de orden en la
DFT
Un punto importante es que, aunque este algoritmo nos ofrezca los mismos resultados si
observamos la salida podemos ver que esta desorganizada, por lo que es necesario
reorganizarla, por lo que se desarrolla el algoritmo de Bit Reversal para ordenamiento de
datos.
El Bit Reversal permite que una secuencia de entrada o salida del cálculo de la FFT sea
reordenada para obtener un resultado deseado. Como se vio en el caso de DIF, la salida es la
que se desea reordenar.
Para ilustrar este algoritmo se verá el caso de N = 8, representado por tres bits. El bit 3 y
el 1 deben ser intercambiados de sus posiciones. Ejemplo, (100)b queda (001)b. Esto hace
que el dato que estaba en la posición de memoria 4 = (100)b pase a la posición 1 = (001)b.
Similarmente, (110)b es intercambiado por (011)b.
Lo anterior se resume gráficamente en la siguiente figura:
Otra forma de realizar el Bit Reverse es crear una tabla con las ubicaciones finales de los
coeficientes y ordenarlos mediante el uso de punteros. El siguiente código crea dicha tabla
para transformadas de N puntos:
Existe diversidad de algoritmos para la FFT. Esquemas anteriores asumen que N = 2n
(Radix-2) otros esquemas reducen multiplicaciones si N = 4n o N = 8n (Radix-4, Radix-8),
algoritmo de Factores Primos (Good-Thomas) y el de Radix Mixto asumen N = N1 N2, lo que
permite optimizar casos donde N es diferente de 2n
La siguiente grafica representa la complejidad de los cálculos de DFT y FFT
2.1.5 Introducción básica a la Transformada rápida de Fourier (FFT)
La Transformada rápida de Fourier (FFT) básicamente es una optimización de la
transformada discreta de Fourier, esta nos permite ejecutar mucho más rápido la
transformación discreta y que para ciertos casos nos permite hacer el análisis de señales en
tiempo real. La fórmula a utilizar será la siguiente:
Es habitual cambiar la exponencial compleja con el número de WN, este número recibe
el nombre de “Twiddle Factor” o “Factor de Fase” también es nombrado habitualmente como
Factor de Giro.
Al efectuar el cambio la expresión tomara la siguiente forma:
𝑁=−1
𝑋[𝑘] = ∑ 𝑥(𝑛)(𝑊𝑁)𝑛𝑘
𝑛=0
Para comprender más a fondo la transformada rápida de Fourier primero determinaremos
el factor de giro, esto lo realizaremos mediante la transformada discreta de Fourier como se
muestran en el siguiente ejemplo
➢ DFT de 2 puntos
Para iniciar se determinará la amplitud de la frecuencia X (0)
Donde el factor de giro será:
𝑊20∗0 = 𝑊20 = 1
𝑊20∗1 = 𝑊20 = 1
Al sustituir el factor de giro podemos expresar la amplitud de la siguiente forma
𝑋(0) = 𝑊20𝑥(0) + 𝑊20𝑥(1) = 𝑥(0) + 𝑥(1)
Ahora se determinará la amplitud de la frecuencia X (1)
Donde el factor de giro será:
𝑊20∗1 = 𝑊20 = 1
𝑊21∗1 = 𝑊21 = −1 = −𝑊20
Al sustituir el factor de giro podemos expresar la amplitud de la siguiente forma
𝑋(0) = 𝑊20𝑥(0) − 𝑊20𝑥(1) = 𝑥(0) − 𝑥(1)
Con los datos recolectados la transformada discreta de Fourier se puede expresar en
forma de matrices
En el cual tendremos un vector columna que representaran los armónicos esto será igual
a la matriz de los factores de giro esto multiplicado por un vector columna que será la muestra
que se han tomado.
Una vez comprendido como se determina el factor de giro podemos utilizar una
representación gráfica que facilitara determinar la transformada rápida de Fourier, dicha
representación recibe el nombre de “Diagrama de Mariposa”. Con el ejemplo anterior de la
transformada discreta de Fourier se tomaran los dos puntos donde se determinó el factor de
giro y se determinaran las ecuaciones de los armónicos.
➢ Diagrama de Mariposa
DFT de 2 puntos → 𝑋(0) = 𝑥(0) + 𝑥(1)
𝑋(1) = 𝑥(0) − 𝑥(1)
xx(0) +
xx(0) -
Básicamente el diagrama de mariposa funciona de la siguiente forma a partir de las dos
muestras [x(0) y x(1)], se realizaran sumas que están representadas al final de cada línea por
un circulo con un sigma más (+) en su interior. Como se observa en el diagrama el x(0) llega
hasta la suma donde se encuentra con la muestra x(1) dando como resultado la primera
ecuación del armónico X(0). De igual forma en el diagrama podemos observar que la muestra
x(1) llega a la suma pero el factor de giro (𝑊21 𝑜 − 𝑊20) afecta a dicha muestra cambiando
de signo a la misma , dando como resultado la segunda ecuación del armónico X(1). Al
examinar el diagrama de mariposa este nos ayudara a entender mucho mejor como se
distribuyen las muestras cuando las misma son demasiado grande (8, 16,…).
Comprendiendo los pasos anteriores ahora se buscara optimizar muchos más la
transformada discreta de Fourier, brindado así un resultado que volverá más rápido la
obtención de la transformada rápida de Fourier. Esta optimización será el lema de
DanielsonLanczos.
➢ Lema de Danielson-Lanczos
La transformada de una señal de tamaño N se puede descomponer en 2 transformadas de
señales de tamaño N/2. Es la base de la FFT.
Ejemplo
Se tomara una muestra de 8, que va desde 0 hasta 7 como se muestra en los recuadros
0 1 2 3 4 5 6 7
Se dividen cada elemento de la muestra en primer lugar en grupos de pares e impares y
luego estos se agrupan de dos en dos como se mira a continuación.
0 2 4 6 1 3 5 7
0 4 2 6 1 5 3 7
Para determinar el orden que presentan las muestras se utiliza el método del Bit Reversal
o Inversión de Bits.
Orden Numero en Bits en Nuevo
Original Binario Reverso Orden
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7
Al realizar la inversión a los números binarios podemos establecer el orden en el cual se
agruparan cada número con su respectiva pareja como se demostró en los recuadros de la
parte de arriba.
2.2 Ejemplos de transformada rápida de Fourier (FFT)
2.2.1 Ejercicio 1
Se analizara la siguiente función y = 2 sen(2π ∗ t) + 5 cos(2π ∗ 3t), para la cual se
determinaran 8 muestras.
Para efectuar este ejercicio es necesario utilizar el software de síntesis de Fourier con
DAC MCP4725 y Arduino, este programa básicamente lo que realiza es generar los datos de
la función que introduzcamos, en este casi para la función del ejercicio solo se analizaran 8
puntos. Los datos que arroja el programa son los siguientes
Ecuación: y = 2 sen(2π ∗ t) + 5 cos(2π ∗ 3t)
Muestra Amplitud
𝑥0 5.0000
𝑥1 -2.1213
𝑥2 2.0000
𝑥3 4.9497
𝑥4 -5.0000
𝑥5 2.1213
𝑥6 -2.0000
𝑥7 -4.9497
Ahora se aplicara al cuadro de las muestra el lema de Danielson-Lanczos para subdividir
las muestras en grupos más pequeños siempre múltiplos de 2.
0 1 2 3 4 5 6 7
0 2 4 6 1 3 5 7
0 4 2 6 1 5 3 7
Se debe recordar que la organización establecida con lema de Danielson-Lanczos se
puede determinar a partir de utilizar el algoritmo bit reversal o inversión de bit. Luego de
establecer la agrupación de las muestras se debe agrupar de la siguiente manera Tabla de
muestras reagrupada
Muestra Amplitud
𝑥0 5.0000
𝑥4 -5.0000
𝑥2 2.0000
𝑥6 -2.0000
𝑥1 -2.1213
𝑥5 2.1213
𝑥3 4.9497
𝑥7 -4.9497
Como se realizaran transformadas de dos puntos necesitamos el factor de giro que este
caso será . Con el factor de giro establecido procederemos a realizar diagramas de
mariposas para las diferentes transformadas.
Tabla de frecuencias intermedias
Al determinar todas los diagramas de mariposa se procede a agrupar los valores para las
X” de cuatro en cuatro, estas serán las frecuencias intermedias
Frecuencia Amplitud
𝑋0" 0.0000
𝑋1" 10.0000
𝑋2" 0.0000
𝑋3" 4.0000
𝑋4" 0.0000
𝑋5" -4.2426
𝑋6" 0.0000
𝑋7" 9.8994
Se realizaran transformadas de cuatro puntos necesitamos los factores de giros que este
caso será . Con los factores de giros establecidos procederemos a
realizar diagramas de mariposas para las diferentes transformadas.
Al determinar todas los diagramas de mariposa se procede ahora con las X’ a determinar
las frecuencias, para efectuar este procedimiento se necesita los factores de giros que este
caso será .
Con los factores de giros establecidos procederemos a realizar diagramas de mariposas.
Como se puede apreciar esta sera la última parte de los diagramas de mariposa ya que se
obtuvieron las frecuencias, asi mismo como se observa que dichas frecuencias se repiten,ha estas
se le conocen como frecuencias de Nyquist. Con las 8 muestras que se consideraron lo maximo
que se tendra en el orden de resolucion de frecuencias deberia estar hasta los 4 Hz.
Como hay presencia de frecuencias complejas se debe encontrar la magnitud de las
mismas esto se hace básicamente aplicando el teorema de Pitágoras, ha esto le llamaremos
frecuencia 𝑋.
Al aplicar el teorema de Pitágoras se obtendrán el valores real de las frecuencias
complejas, de esta forma se tendrá el valor definitivo de todas las frecuencias que se presentan
en el siguiente cuadro.
Frecuencia Amplitud
𝑋0 0
𝑋1 8
𝑋2 0
𝑋3 20
𝑋4 0
𝑋5 20
𝑋6 0
𝑋7 8
Para finalizar el ejercicio los valores obtenido con la transformada discreta de Fourier se
debe sacarle el promedio a cada una. Básicamente al promediar estos valores se deben dividir
por la cantidad de muestras, donde el resultado será la frecuencia final. La fórmula que se
utilizara para promediar será la siguiente
Al promediar se alcanzarán las frecuencias deseas, las cuales se resumen en el siguiente
cuadro
Frecuencia Amplitud
𝑋0 0
𝑋1 2
𝑋2 0
𝑋3 5
𝑋4 0
𝑋5 5
𝑋6 0
𝑋7 2
Si se observa nuevamente la ecuación: y = 2 sen(2π ∗ 1t) + 5 cos(2π ∗ 3t)
Se concluye que efectivamente para una frecuencia de 1 Hz la amplitud será de 2 y para
una frecuencia de 3 Hz se tendrá una amplitud de 5 Hz.
2.2.2 Ejercicio 2
Se desarrollará a continuación el programa en código Python, siguiendo el diagrama de flujo
expuesto por Brigham (Fig. 1). Cabe mencionar que en el desarrollo se considera que el
número de muestras, N, es una potencia de 2 (N = 2 γ). Además recordar que el diagrama
surge de la aplicación de la transformada discreta de Fourier y sus propiedades, y en sí el
algoritmo no requiere una análisis profundo ya que solamente ayuda a calcular más rápida y
eficientemente la transformada discreta de Fourier, por lo tanto no se dará mayor detalle.
Para ejemplo se utilizarán muestras de la función 𝐴𝑠𝑒𝑛(2π𝑓𝑜𝑡), tomando A = 1, 𝑓𝑜= 250 Hz
y N =210 = 1024 muestras:
Se puede apreciar que en el programa en Python no se consideró la subrutina de inversión
de bit ya que se utilizó una de las muchas ventajas de Python para realizar esto en una sola
línea de comando, siendo estas líneas la 44 y la 58 (estas líneas son la caja 1 y la caja 2 del
diagrama de flujo, que utilizan la subrutina de inversión de bit). Además la línea 12
corresponde a la potencia de la base 2 que genera el número de muestras tomadas en la
función antes mencionada, definiendo parámetros y muestras de la misma entre las líneas 19
a la 29. Las líneas entre la 31 a la 66 corresponden al programa indicado en el diagrama de
flujo de la Fig. 1. La línea 65 corresponde al factor de escala resultante del análisis de la
transformada discreta de Fourier. Las líneas entre la 69 a la 74 corresponden a los ajustes de
los datos de frecuencia con los que se representa la transformada contínua de Fourier, siendo
los límites de −𝑓𝑜 a 𝑓𝑜.
En la Fig. 2 se muestran los datos obtenidos para el caso mencionado [𝐴𝑠𝑒𝑛(2π𝑓𝑜𝑡)], y al
comparar con el par transformado para esta función
Se observa coincidencia con los resultados arrojados por el programa.
Además en la Fig. 3 se observa el caso para 𝐴𝑐𝑜𝑠(2π𝑓𝑜𝑡), tomando A = 1, 𝑓𝑜 = 250 Hz y
N = 210 = 1024 muestras y cuyo par transformado de Fourier es
Nótese el color de línea diferente en el gráfico de la transformada de Fourier de la Fig. 3, en
contraste con el correspondiente de la Fig. 2.
Precisamente, ya que la transforma de Fourier en general es una función compleja
En el programa la parte real [R(f)] deberá graficarse con línea de color diferente o tipo de
línea a la de la parte imaginaria [I(f)] [en estos gráficos R(f) e I(f) aparecen con color de línea
azul y verde respectivamente]. Para ejemplo tómese la función:
Cuya transformada de Fourier es:
En la Fig. se muestra el gráfico correspondiente.
3. CONCLUSIÓN
La Transformada Rápida de Fourier es un algoritmo para el cálculo de la Transformada
Discreta de Fourier basado en la división del tiempo, eliminando así gran parte de los cálculos
repetitivos que hay que llevar a cabo si se desea resolver la TFD de forma directa. Si hacemos
una comparación del costo de los dos métodos, el cálculo directo de la TFD y la FFT,
podemos observar el factor de mejora que brinda la FFT. La FFT tiene una gran importancia
debido a que tiene diferentes aplicaciones como ser: tratamiento de imagen y audio, reducción
de ruido en señales y análisis en frecuencia de cualquier señal discreta.
