CONSULTA #2
TRASFORMADA RAPIDA DE FOURIER(FFT)
López Loor Javier Alejandro
[email protected]Resumen: Es considerado un algoritmo clásico, que
La Transformada rápida de Fourier (FFT) es un permite obtener a partir de una serie de
algoritmo eficiente que permite calcular valores temporales las componentes
la transformada de Fourier discreta (DFT) y su espectrales en frecuencia, y viceversa con
inversa. La FFT es de gran importancia en una un costo O(n log n). Como veremos es un
amplia variedad de aplicaciones, desde caso particular del problema más general
el tratamiento digital de señales y filtrado de calcular polinomios. Existen dos formas
digital en general a la resolución de ecuaciones de cálculo: una es evaluar un polinomio
en derivadas parciales o los algoritmos de representado por sus coeficientes. La otra
multiplicación rápida de grandes enteros. es representar el polinomio por una serie de
Cuando se habla del tratamiento digital de puntos.
señales, el algoritmo FFT impone algunas 2. OBJETIVOS:
limitaciones en la señal y en el espectro Consultar el algoritmo de la
resultante ya que la señal muestreada y que se transformada rápida de Fourier.
va a transformar debe consistir de un número Entender el funcionamiento de la
de muestras igual a una potencia de dos. Transformada rápida de Fourier.
Palabras Clave: 3. MARCO TEORICO:
FFT, Transformada rápida de Fourier, Fourier.
El algoritmo que se plantea está basado en
ABSTRACT. el método denominado “doblamiento
The fast Fourier transformation (FFT) is an
sucesivo”. Para simplificar las expresiones,
efficient algorithm that allows calculating the
discrete Fourier transformation (DFT) and its la ec. se reescribe:
inverse. FFT is of great importance in a wide
variety of applications, from the digital signal
processing and digital filtering in general to the
resolution of partial differential equations or
the algorithms of rapid multiplication of large
Donde
integers. When talking about the processing of
digital signals, the FFT algorithm imposes
some limitations on the signal and on the
resulting spectrum and the signal is shown and
a transformation must be seen to consist of a
number of samples equal to a power of two. y N se supone de la forma :
Keywords:
FFT, Fast Fourier Transform, Fourier.
1. INTRODUCCIÓN.
con N entero positivo. Entonces puede También, dado que
expresarse:
Un análisis cuidadoso de las ecuaciones a
con M también entero positivo.
muestra algunas propiedades interesantes
Sustituyendo en se tiene
de dichas expresiones. Nótese que una
transformada de N-puntos puede ser
calculada dividiendo la expresión original
en dos partes, como se indica en las ecs. El
cálculo de la primera mitad de F(µ)
requiere de la evaluación de las dos
Puesto que, de ec(6.2), x M 2 x W2M W µ
transformadas de N/2 puntos según las ecs.
µ = , la ec. (6.5) puede expresarse:
Los valores resultantes de Fimpar ( ) µ y
Fpar ( ) µ se sustituyen en la ecuación (6.9)
para obtener F(µ) para µ = 0, 1, 2, …, (N/2-
1). La otra mitad se obtiene mediante la
Si se define: ecuación sin requerir evaluaciones
adicionales de la transformada.
Considerando un número de muestras igual
a 2n , con n entero positivo, se puede
demostrar que el número de operaciones
para µ = 0, 1, …, M-1 y: complejas (multiplicaciones y sumas) está
dado por:
para µ = 0, 1, …, M-1, entonces la ec. se
expresiones recursivas que indican el
hace:
número de multiplicaciones y de sumas
para las que m(0) y a(0) son iguales a cero,
puesto que la transformada de un punto no
requiere operación alguna. Número de
operaciones. Es posible concluir, por
inducción, que el número de operaciones,
sumas y multiplicaciones complejas, que
se requiere para implementar un algoritmo
para FFT como el recién descrito está dado
por:
Debido a que , donde es un entero, es
posible factorizar la matriz en el producto de
dos matrices:
Los elementos y han cambiado de
lugar en el vector que se encuentra del lado
izquierdo. Cuando se multipliquen las
matrices, los renglones 1 y 2, también se
intercambiarán. Después, se calcula el número
de multiplicaciones y adiciones que se
requieren. Primero, se identifica el resultado de
Para este caso de 4 puntos de datos, recordando multiplicar la segunda matriz cuadrada por el
el álgebra lineal, es posible escribir la FFT en conjunto de datos de entrada como:
forma de matriz como:
puesto que los datos de entrada están Recordando como se multiplican las matrices,
representados por un vector-columna de 4 el primer elemento del vector de la izquierda
componentes. Efectuar la multiplicación usual es:
De manera similar, el cálculo de y requieren de
de matrices directa requeriría una multiplicación y una adición.
multiplicaciones complejas y adiciones Aunque es uno, se hará que y el producto ya
complejas. Por lo tanto, puede escribirse de la se ha obtenido en el cálculo del primer
siguiente manera: elemento y puede, en consecuencia, sólo
almacenarse hasta que se necesite y luego
restarse en vez de sumarse. De manera
similar, sólo requiere una adición más. Hasta
ahora se tienen dos multiplicaciones y cuatro
sumas. Apelando a condiciones de simetrías
similares en la segunda multiplicación de
matrices, se encuentra que se requieren dos
multiplicaciones y cuatro sumas más. Así, en
total, se necesitan cuatro multiplicaciones y
ocho adiciones. Puesto que,
computacionalmente, las multiplicaciones
requieren por lo general mucho más tiempo de
cómputo que las adiciones, el algoritmo de
FFT para cuatro puntos es alrededor de cuatro
veces más rápido que la FDT directa. El
siguiente diagrama muestra, en forma de
gráfica de flujo de señales, como se realizan las
operaciones necesarias.
4. BIBLIOGRAFIA:
[1 ]. Proakis, John; Manolakis, Dimitris (2014). «7.
The Discrete Fourier Transform: Its Properties and
Applications». Digital Signal Processing (Pearson
New International Edition) (en inglés) (4 edición).
Pearson Education Limited. p. 468. ISBN 978-1-292-
02573-5.
[2 ]. Saltar a:Ramírez Cortés, Juan Manuel; Gómez
Gil, María del Pilar; Báez López, David (marzo-abril
de 1998). «El algoritmo de la Transformada Rápida
de Fourier y su controvertido origen». Ciencia y
Desarrollo 24 (139): 70-77. Consultado el 20 de
octubre de 2018.
