Algoritmo Fft

MATEMATICAS V

TRANSFORMADA RAPIDA DE FOURIER

TRANSFORMADA RÁPIDA DE FOURIER (FFT) 1. RESUMEN La transformada rápida de Fourier (Fast Fourier Transform FFT) es un algoritmo extremadamente rápido para calcular la transformada discreta de Fourier (Discrete Fourier Transform DFT), ambos son métodos que en la práctica ejecuta un computador sobre datos discretos. A menudo cuando se presentanseñales en el tiempo de larga duración, se hace inviable ejecutar la DFT, por esto fue necesaria la creación de la FFT, originalmente descubierta por Gauss (1805), fue redescubierta por J. W. Cooley y O. W. Tukey en IBM durante 1960 C.S. Burrus, de la Universidad de Rice University siendo jefe del departamento de Ingeniería, literalmente "escribió el libro" de los algoritmos de la rápida TransformadaDiscreta de Fourier DFT. Existen distintos métodos para calcular la FFT, en general los podemos dividir en 2 tipos: decimación en el tiempo, y diezmado en la frecuencia. El algoritmo busca reducir el número de multiplicaciones efectuadas en la DFT, reduciendo el número de cálculos para N datos de 2N2 a 2N·log2N, donde N debe ser una potencia de 2.Usualmente la presentación del algoritmo FFT serealiza de forma polinomial pero también puede ser presentado de forma matricial. La FFT explota las simetrías en la matriz W (ec.2.7) para aproximarse a una matriz diagonal. En la actualidad existen algoritmos aun más eficientes de calcular la DFT que inclusive el algoritmo FFT de Cooley y Tukey. No hablaremos del actual algoritmo de la FFT aquí. 2. FUNDAMENTO: 2.1 ANALSÍS DE FOURIER EN TIEMPODISCRETO: Una señal discreta x [n ] será periódica si se cumple: x [n ]  x[n  N ] , en donde 2 N, periodo fundamental, es un entero mínimo. La exponencial compleja e  j N n es un ejemplo de función periódica discreta. El análisis de Fourier en tiempo discreto es similar a su análogo en tiempo continuo, pero una de las grandes diferencias que presenta en que las series ahora no presentaran infinitostérminos sino que estarán determinados por el número del periodo N. Una señal periódica puede representarse en términos de exponenciales complejas de la forma: x [n ] 
k  N1

ae
k

N2

jk 2  n N

con N2  ( N1 )  N

(2.1)

Esta es la representación de una serie de Fourier de una señal discreta 2 periódica; para hallar el k-ésimo coeficiente ak multipliquemos por e  jr N nambos miembros en (2.1): e D. L. LL.
 jr 2 n N

x [n ] 

k  N1

ae
k

N2

jr 2  n N

e

 jk 2  n N

1

FIEE-UNI

MATEMATICAS V

TRANSFORMADA RAPIDA DE FOURIER

Puesto que x[n] es periódica da lo mismo que n  [ N1, N2 o n  [0, N . Ahora tomando sumatoria para 0  n  N :

e
n 0

N 1

 jr 2  n N

x [n ]   ak e
n 0 k 0

N 1 N 1

jr 2  nN

e

 jk 2  n N

  ak  e
k 0 n 0

N 1

N 1

j ( r  k ) 2 n N

(*)

Pero veamos que:

åe
n =0

N- 1

js 2 p n N

ì (e j 2Np s )N - 1 ï ï = 0 ; s ¹ 0, ±N, ±2N,K ï = ï e j 2Np s - 1 í ï ï ï N ; s = 0, ±N, ±2N,K ï î
N 1 k 0 N 1 n 0 j ( r  k ) 2 n N

Entonces en (*):

e
n 0

N 1

 jr 2  n N

x [n ]   ak  e ak 

 ar N , luego: (2.2)1 N 1  jk 2N n  e x [n ] N n 0

Esta última se llama ecuación de análisis, es aplicable solo a una función periódica para obtener su la serie discreta de Fourier (SDF). Veamos ahora que en analogía a la variable continua nuestros resultados se pueden extender para hallar la SDF de señales de duración finita como se ve en la figura: x[n] (a)

-N1 xp[n]

N2

n

(b)

-N1

N2 FIGURA1:

n

Ahora, sea x[n] una señal aperiódica de duración N podemos construir una señal periódica xp[n] de periodo N tal que:  x [n ] ; N1  n  N2 x [n ]   p (**)  0 ; N2  n y n  N1 Entonces podemos hallar la representación de la SDF de xp[n] sobre 2 1 1 N1  n  N2 en donde se debe cumplir que ak  N  N0 e  jk N n x p [n ] ; ahora para n D. L. LL. 2 FIEE-UNI

MATEMATICAS V...