• Author / Uploaded
• JorGe D Moralez

Citation preview

FFT

Fast Fourier Transform Robinson L´ opez Monz´ on

12 de abril de 2013

Laboratorio de Electr´ onica y Autom´ atica

FFT

Indice 1 Introducci´ on

Transformada Discreta de Fourier Forma Vectorial Forma Matricial 2 Fast Fourier Transform

Introducci´on Demostraci´on Algoritmos Comparaci´on de Algoritmos 3 Aplicaciones de la FFT

Bluestein FFT

FFT Introducci´ on DFT

¿Qu´e es la Transformada Discreta de Fourier?

Definici´on Es un transformaci´on que permite obtener una representaci´on en el dominio de la frecuencia, siendo la funci´ on original, una funci´on en el dominio del tiempo Xk =

N−1 X n=0

xn e −

2πi kn N

(1)

FFT Introducci´ on Forma Vectorial

FFT Introducci´ on Forma Vectorial

Expresi´on vectorial de la Transformada Discreta de Fourier Definici´on A modo de introducci´on a la implementaci´ on de la transformaci´on expresaremos la forma vectorial de la DFT, que es la forma como computacionalmente se obtiene

Ff [m] =

N−1 X

f [k]w −km

k=0

w =e

−2π N

− − − − w k [m] = w km

Los vectores y matrices en los lenguajes de programaci´on se indexan desde 0. Adem´as observamos lo siguiente para m=0 Ff [0] =

N−1 X k=0

f [k]w −k [0]

(2)

FFT Introducci´ on Forma Matricial

Expresi´on matricial de la Transofrmada Discreta de Fourier Definici´on Debido a que la transformada de Fourier es una transformaci´on lineal de C n a C n se puede obtener una expresi´ on matricial.

    

F[0] F[1] .. .





1  1    =  ..  .

F[N − 1]

1 w −1∗1 .. .

··· ··· .. .

1 w −(N−1)∗1 · · ·

1



w −1∗(N−1) .. .

   

w −(N−1)∗(N−1)

Tambi´en debemos tener en cuenta lo siguiente ”e 2πi = w N = 1” ”e πi = w N/2 = −1”

f [0] f [1] .. .



    f [N − 1]

FFT Introducci´ on Forma Matricial

Tener en cuenta que... Para el valor de N/2 ocurre lo siguiente Ff [N/2] =

N−1 X k=0

N

f [k]w −k 2 =

N−1 X

(−1)−k f [k]

k=0

Por lo tanto el valor en N/2 es real +/- y por lo tanto se cumple que Ff [−f ] = Ff [f ] Por lo tanto podemos concluir que para entradas reales de f, la informaci´on del espectro est´a dada en los primeros componentes antes de N/2, es decir comprende a Ff [0] y Ff [1] hasta Ff [N/2 − 1]

FFT Fast Fourier Transform Introducci´ on

¿Qu´e es la FFT?

Definici´on Algoritmo que permite calcular la DFT y su inversa de manera eficiente reduciendo el n´ umero de operaciones aritm´eticas 2 realizadas de O(n ) hasta O(n log n) El algoritmo establece que el n´ umero de muestras debe ser igual a una potencia de 2 Para poder explicar la deducci´ on del algoritmos haremos la expansi´on del caso de la transformada discreta de Fourier en forma matricial para un caso N=4

FFT Fast Fourier Transform Demostraci´ on

Demostrac´on   1 1 1 1 1 w −1 w −2 w −3  4 4 4  F4 =  1 w −2 w −4 w −6  4 4 4 1 w4−3 w4−6 w4−9    1 1 1 1 f [0] 1 w −1 −1 −w −1  f [1] 4 4   F4 f =  1 −1 1 −1  f [2] f [3] 1 −w4−1 −1 w4−1   f [0] + f [1] + f [2] + f [3] f [0] + f [1]w −1 − f [2] − f [3]w −1  4 4  F4 f =    f [0] − f [1] + f [2] − f [3] f [0] − f [1]w4−1 − f [2] + f [3]w4−1

FFT Fast Fourier Transform Demostraci´ on

Con las derivaciones anteriores podemos generalizar la forma vectorial w [p, q] = wpq w [N/2, −1] = e −2πi/(N/2) = e −4πi/N = w [N, −2] Con esto vemos que existe una diferencia para los casos en que k es par y cuando m es impar Par w [N, −2nm] = w [N/2, −m, ] Impar w [N, −2(n + 1)m] = w [N, −m]w [N/2, −nm] Generalizando N/2−1

F [m] =

X n=0

f [2n]w [N−(2n)m]+w [N, −m]

N/2 X n=0

f [2n+1]w [N, −(2n+1)m]

FFT Fast Fourier Transform Demostraci´ on

Obtenemos N/2−1

F[m] =

X

N/2−1

f [2n]w [N/2, −nm] + w [N, −m]

n=0

X

f [2n + 1]w [N/2, −nm]

n=0

F[m] = (FN/2 feven )[m] + ω[N, −m](FN/2 fodd )[m] La u ´ltima expresi´on se cumple para m desde 0 hasta N/2 − 1. Pero seg´ un esta expresi´on obtenemos N/2-1 expresiones de F para N entradas. Lo ideal es obtener N expresiones a partir de N entradas debido a que la transformada de Fourier es del tipo C n − C n . Para ello analizaremos el comportamiento en F [m + N/2] ω[N, −(m + N/2)] = ω[N, −m]ω[N, −N/2] = −ω[N, −m] N/2−1

F[m] =

X n=0

N/2−1

f [2n]w [N/2, −nm] − w [N, −m]

X

f [2n + 1]w [N/2, −nm]

n=0

F[m] = (FN/2 feven )[m] − ω[N, −m](FN/2 fodd )[m]

FFT Fast Fourier Transform Demostraci´ on

Reordenamos pares e impares para N=4 



1 0  1 0

0 1 0 1

    1 1 0 0 f [0] f [0] + f [2] −  1 ω − 1 0    0  2   f [2] = f [0] + f [2]ω2 1     0 0 1 1 f [1] f [1] + f [3]  − 0 0 1 ω2 1 f [3] f [1] + f [3]ω2− 1   1 1 0 0   1 ω − 1 0 0  2   = B2 0 0 0 B2 0 1 1  0 0 1 ω2− 1     f [0] + f [1] + f [2] + f [3] 1 0 f [0] + f [2] −  −1 −1    0 ω4− 1  f [0] + f [2]ω2 1 = f [0] + f [1]w4 − f [2] − f [3]w4       −1 0 f [1] + f [3] f [0] − f [1] + f [2] − f [3] − − −1 −1 0 ω4 1 f [1] + f [3]ω2 1 f [0] − f [1]w4 − f [2] + f [3]w4

FFT Fast Fourier Transform Demostraci´ on

 F = F4 f = B4



1 0 B4 =  1 0

B2 0 0 B2



  f [0] f [2]   f [1] f [3]

 0 1 0   1 0 w4−1   = IN/2 ΩN/2 0 −1 0  IN/2 −ΩN/2 −1 1 0 −w4

Con esto podemos darnos cuenta que lo que hace este algoritmo es trabajar por capas desde dentro hacia afuera trabajando matricialmente, lo cual nos permite ahorrar muchas operaciones. Adicionalmente debe notarse que los valores de f son ordenados y separados en pares e impares. Este ordanmiento en particular se llama Bit Reversing porque coincide con la invesri´on de los correspondiente a su posici´ on escrita en binario

FFT Fast Fourier Transform Demostraci´ on

Bit Reversal y Butterfly

Figura 1: Algoritmo Bit Reversal y Esquema Butterfly

FFT Fast Fourier Transform Algoritmos

Algoritmos

La transformada r´apida de Fourier ha sido el foco de trabajo de muchas investigadores, los cuales han logrado muchos avances en el procesamiento del mismo. En el presente trabajo hemos trabajado 3 de los enfoques mas conocidos. FFT Recursiva Este enfoque de FFT aprovecha las ventajas brindadas por los lenguajes de programaci´ on actuales que permiten realizar funcinoes recursivas permitiendo llamar a la misma funci´ on dentro de ella. El concepto es que realiza la llamada para N muestras, luego dentro de la misma lo hace para N/2 muestras, hasta llegar a N=2

FFT Fast Fourier Transform Algoritmos

Algoritmos FFT Compleja Este otro enfoque de FFT es la que computacionalmente refleja mejor el algoritmo anteriormente descrito. Realiza primero el BitReversal para ordenar las entradas seg´ un el orden necesario para realizar el esquema Butterfly, tratando de mantener la forma matricial de la transformaci´ on. FFT Real El algoritmo FFT Complejo toma como entrada pares de la se˜ nal, conteniendo la parte real e imaginaria, lo cual es aplicable sobretodo para aplicaciones de se˜ nales de radar. En el caso de se˜ nales reales se puede separar la se˜ nal en dos partes tomandolas como parte real e imaginaria y luego bas´andonos en las relaciones 1 1 ∗ ∗ Fne = (Fn + FN/2−n ) y Fno = e −2πin/N (Fn + FN/2−n ) 2 2

FFT Fast Fourier Transform Algoritmos

Figura 2: Descripci´ on de Entradas y Salidas del Algoritmo

FFT Fast Fourier Transform Comparaci´ on de Algoritmos

Benchmark de Tiempo de Ejecuci´on

Figura 3: Benchmark de los 3 algoritmos. N muestras vs Tiempo (s)

FFT Fast Fourier Transform Comparaci´ on de Algoritmos

Benchmark de Tiempo de Ejecuci´on

Figura 4: Benchmark de los 3 algoritmos. N muestras vs Tiempo (s)

FFT Fast Fourier Transform Comparaci´ on de Algoritmos

Comparaci´on en Calidad

Figura 5: Resultados de FFT en Matlab

FFT Fast Fourier Transform Comparaci´ on de Algoritmos

Comparaci´on en Calidad

Figura 6: Resultados de FFT en Python - Raspberry

FFT Aplicaciones de la FFT Bluestein FFT

Chirpz Z Transform Definici´on El algoritmo FFT de Bluestein, com´ unmente llamado Transformada Chirp Z realiza la DFT de tama˜ nos arbitrarios reexpresando la transformada como una convoluci´ on. Este algoritmo inclusive puede hallar la transformada Z de una se˜ nal.

Xk =

N−1 X

x(n)zk−n

n=0

Xk =

N−1 X n=0

x(n)A−n W nk

FFT Aplicaciones de la FFT Bluestein FFT

Chirp Z

Figura 7: Relaci´ on entre Plano Z y Plano S

FFT Aplicaciones de la FFT Bluestein FFT

Chirp Z

Bluestein n2 + k 2 − (k − n)2 2

nk =

Xk = W

k 2 /2

N−1 X

y (n)v (k − n)

n=0

Donde: y (n) = x(n)A−n W n v (n) = W n

2 /2

2 /2

FFT Aplicaciones de la FFT Bluestein FFT

Chirp Z

Figura 8: Esquema del Algoritmo Chirp Z - Rabiner

FFT Aplicaciones de la FFT Bluestein FFT

Chirp Z aplicado a Zoom FFT

Figura 9: Resultado Zoom FFT Chirp Z en Raspberry/Python

FFT Aplicaciones de la FFT Bluestein FFT

Gracias