Transformada de Fourier Juan-Pablo C´aceres CCRMA Stanford University

Agosto, 2007

Contenidos Introducci´ on S´ıntesis Aditiva An´ alisis Espectral Transformada Continua de Fourier DFT Teoremas de Fourier FFT Convoluci´ on

Introducci´ on

Toda se˜ nal peri´ odica, sin importar cuan complicada parezca, puede ser reconstruida a partir de sinusoides cuyas frecuencias son m´ ultiplos enteros de una frecuencia fundamental, eligiendo las amplitudes y fases adecuadas.

Matem´ atico franc´es Joseph Fourier (1768-1830)

S´ıntesis Aditiva

Reglas de la S´ıntesis Aditiva (o s´ıntesis de Fourier): ◮

S´olo sinusoides pueden ser combinadas

◮

Las frecuencias de todas las sinusoides deben estar arm´onicamente relacionas

S´olo tenemos libertad para cada sinusoide en la elecci´ on de: ◮

Frecuencia fundamental

◮

Amplitud

◮

Fase

Expansi´ on de S´ıntesis Aditiva

Deep Note: La pieza de m´ usica por computador m´ as famosa del mundo (James ”Andy” Moorer) deep note.wav

Arm´ onicos y Periodicidad

Para una frecuencia fundamental f , cualquier m´ ultiplo entero de f es un arm´onico. Una serie arm´onica puede expresarse entonce:

f + 2f + 3f + 4f + 5f + 6f + 7f + · · · Una funci´on (se˜ nal) f (t) es periodica son periodo τ si para cualquier t, f (t) = f (t + τ ), (−∞ < t < ∞)

Ejemplo: Onda Cuadrada

Ejemplos de S´ıntesis Aditiva: Clarinete Con las siguientes reglas se puede construir un sonido tipo clarinete:

◮

S´olo los armonicos impares estan presentes

◮

La Amplitud de los arm´onicos decrece a medida que el n´ umero de arm´onico crece

◮

No hay diferencia de fase entre los armonicos (esto simplifica la s´ıntesis) ∞ X 1 s(t) = sin(nωt + 0) con n impar n n=1

s(t) = sin(ωt + 0) +

1 1 sin(3ωt + 0) + sin(5ωt + 0) + · · · 3 5

An´ alisis Espectral Cualquier se˜ nal (waveform) per´odica puede ser descompuesta en sinusoides ◮ Estudio de timbres musicales ◮ Clasificaci´ on de sonidos por contenido espectral ◮ Res´ ıntesis usando s´ıntesis de Fourier ◮ Sintetizaci´ on de sonidos hibridos (mezcla de sonidos analizados, morphing) ◮ Creaci´ on arbitraria de mezclas de frecuencias El espectro (analizado) del clarinete debiera verse as´ı:

Como detectamos (analizamos) las Frecuenias?

En el espectro anterior, aparecen claramente la energ´ıa de cada sinusoide del clarinete. Como detectamos esto con an´alisis? Preambulo: Multiplicaci´on de Se˜ nales

Multiplicaci´ on de Se˜ nales

Detector de Frecuencias Multiplicaci´on de se˜ nales id´enticas genera una se˜ nal que es siempre positiva. ◮

x(t): sinusoide como se˜ nal de prueba (se˜ nal que ser´a analizada)

◮

y(t): se˜ nal de sondeo, sinusoide con frecuencia variable

◮

c(t): el producto de las 2 se˜ n´ales x(t)y(t)

c(t) ser´ a mayor cuando x(t) e y(t) sean id´enticas.

Formalizaci´ on del Detector Como se˜ nal de sondeo usamos un fasor: e−j2πf t Este fasor tiene una s´ ola componente en frecuencia. Primero, multipicamos la se˜ n´al de input con el fasor de sondeo: x(t) · e−j2πf t Finalmente sumamos (integramos) el producto: Z x(t)e−j2πf t

Transformada Continua de Fourier X(f ) =

Z

∞

x(t)e−j2πf t dt Transformada de Fourier

−∞

◮

t: Tiempo

◮

f : Frecuencia en Hz

◮

x(t): Se˜ nal de prueba

◮

e−j2πf t : Fasor de Sondeo (Kernel Function)

◮

X(f ): Espectro en funci´on de la frecuencia f

x(t) ↔ X(f ), es decir para una funci´on x(t) existe un equivalente X(f ). X(f ), el espectro, revela la fuerza (energ´ıa) de varias componentes de frecuencia, ordenadas por frecuencia. La transformada de Fourier act´ ua como un detector de energia en frecuencia-dependiente

Transformada Inversa de Fourier

A partir de la transformada, podemos recuperar la se˜ nal original tomando la Transformada Inversa de Fourier. Z ∞ X(f )ej2πf t df Transformada Inversa de Fourier x(t) = −∞

Notar la simetr´ıa con respecto a la Transformada de Fourier.

Tranformadas Discretas (DFT) El equivalente en tiempo y frecuencia discreta es la Transformada Discreta de Fourier (DFT)

X[k] =

N −1 X

x[n]e−

2πj kn N

DFT

n=0

◮

N : N´ umero de Samplers en x[n]

◮

x[n]: Se˜ nal de prueba discreta (con ´ındice n)

◮

X[k]: Espectro en funci´on de la frecuencia discreta (con ´ındice k)

◮

e−jkωn/N : Fasor de Sondeo discreto (Kernel Function)

Ejemplo

 n x(n) = A sin f 2π N

Para simplificar este analisis, descomponemos nuestra transformada: X[k] =

N −1 X n=0

X[k] =

N −1 X n=0

x[n] · cos



x[n] · −j sin

2π kn N





2π kn N

DCT



DST

Ejemplo Para simplificar m´ as operemos en una DST real positiva X[k] =

N −1 X

x[n] sin

n=0



2π kn N



DST

Para N = 8, f = 1 y k = 1, es decir ambas se˜ nal de sondeo y de prueba son iguales: Sample Input Sondeo Producto

0 0 0 0

1 A √ 2 √1 2 A √ 2

2 A 1 A

3 A √ 2 √1 2 A √ 2

4 0 0 0

5 − √A2 − √12 A √ 2

6 −A −1 0

7 − √A2 − √12 A √ 2

Ejemplo
n Para x(n) = A sin f 2π N con k = f , N −1 X

x[n] sin

n=0



2π kn N



=0+

A A A A +A+ +0+ +A+ 2 2 2 2

= 4A Para un N general, se obtiene:   N −1 1 X 2πj A x[n] sin kn = N n=0 N 2

Caso de Frecuencia sin Energ´ıa

Para k = 2f   N −1 1 X 2π x[n] sin 2f n N N n=0

Se hace el mismo proceso y se suman los t´erminos: A A A A 0+ √ +0− √ +0− √ +0+ √ =0 2 2 2 2 ⇒ No hay energ´ıa en k = 2f

Energ´ıa en las Frencuencias Negativas Veamos que pasa para k = −f N −1 X



2π x[n] sin −k n N n=0



Nuevamente haciendo la tabla y sumando, 0−

A A A A − A − + 0 − − A − = −4A 2 2 2 2

Normalizando:   N −1 A 2πj 1 X n =− x[n] sin −k N N 2 n=0

Se˜ nal Combinada (Reconstrucci´ on) Podemos reconstruir la se˜ nal a partir de las componentes en frecuencia, A [sin(f 2πn/N ) − sin(−f 2πn/N )] 2 = A sin(f 2πn/N )

x[n] =

Si hacemos el mismo ejemplo con se˜ nal de prueba cos(f 2πn/N ) y DCT, obtenemos: A [cos(f 2πn/N ) + cos(−f 2πn/N )] 2 = A cos(f 2πn/N )

x[n] =

◮

◮

DST s´ olo “ve” se˜ nales tipo sin, es decir componenter impares del Espectro DCT s´ olo “ve” se˜ nales tipo cos, es decir componenter pares del Espectro

Se˜ nales con Fase Arbitraria Si se toma como se˜ nal de prueba: x[n] = a cos(f 2πn/N ) + b sin(f 2πn/N ) Cualquier se˜ nal sinusoidal con fase arbitraria puede ser representada por una suma de sin y cos: A sin(θ + φ) = a cos θ + b sin θ Por lo tanto, usando la DCS y la DST juntas podemos detectar cualquier se˜ nal con frecuencia y fase arbitrarias. Usando la DFT combinamos ambas en forma m´as elegante: X[k] =

N −1 X

x[n]e−

2πj kn N

DFT

n=0

M´ as Complejo es M´as Simple

Teoremas de Fourier Tenemos entonces la transformada discreta de Fourier, X[k] =

N −1 X

x[n]e−

2πj kn N

n=0

, k = 0, 1, 2, . . . , N − 1

DFT

Y su inversa, N −1 2πj 1 X x[n] = X[k]e N kn , n = 0, 1, 2, . . . , N − 1 N k=0

Definimos ωk , 2πk/N con lo que e

2πj kn N

= ejωk n

Y como notaci´ on ocupamos el par transformado, x ↔ X (“x” corresponde a X)

IDFT

Teoremas de Fourier Las sinusoides de la DFT sk [n] , ejωk n son periodicas tal que sk [n + mN ] = sk [n] para todo entero m. Como sabemos que cualquier se˜ nal x de largo N puede ser expresada como combinaci´on lineal de las sinusoides DFT en el dominion del tiempo, x[n] =

1 X X[k]sk (n) N k

implica que x[n] fuera del rango [0, N − 1] es de extensi´on peri´ odica, i.e., x[n + mN ] = x[n] Esto tambien sucede con la DFT con X[k + mN ] = X[k] Matem´ aticamente, las se˜ nales x en que se opera una DFT son samples (muestras) de 1 periodo de una se˜ nal periodica, con periodo N T

Teoremas de Fourier

Theorem (Linealidad) Para cualquier x, y ∈ CN y para α, β ∈ C, la DFT satisface: αx + βy ↔ αX + βY Theorem (Conjugado) Para cualquier x ∈ CN , x ↔ Flip(X)

Flip(x) ↔ X

Teoremas de Fourier Theorem (Reverso) Para cualquier x ∈ CN , Flip(x) ↔ Flip(X) Corollary (Reverso) Para cualquier x ∈ RN , Flip(x) ↔ X Flip(X) = X Theorem x ∈ RN ↔ X es Hermitiano

Teoremas de Fourier: Simetr´ıa

Theorem Para cualquier x ∈ RN , Re{X} es par y Im{X} es impar Theorem Para cualquier x ∈ RN , |X| es par y ∠X es impar Theorem x par ↔ X par x real y par ↔ X real y par

Teoremas de Fourier: Shift

Theorem Para cualquier x ∈ CN y para cualquier entero △, DF Tk [Shift△ (x)] = e−jωk △ X(k)

Se˜ nales de Fase Lineal Podemos escribir la Transformada de Fourier en forma polar, X[k] = G[k]ejΘ[k] Por el Teorema de Shift para retrasos, e−jωk △ X[k] , e−jωk △ G[k]ejΘ[k] = G[k]ej[Θ[k]−ωk △] Esto implica que la pendiente de la curva △ equivale al delay en el tiempo. ◮

Pendiente negativa lineal equivale a retraso (delay)

◮

Pendiente positiva lineal equivale a adelanto

e−jωk △ es conocido como termino de fase lineal

Teoremas de Fourier: Zero Padding

Zero padding consiste en extender la se˜ nal con ceros, por ejemplo, ZeroPad10 ([1, 2, 3, 4, 5]) = [1, 2, 3, 4, 5, 0, 0, 0, 0, 0] Theorem (Interpolaci´ on Espectral) Para se˜ nales de banda limitada, hacer Zero Pad en el tiempo corresponde a interpolaci´ on ideal en el dominio de la frecuencia.

Ejemplo Vemos que en los “agujeros” de frecuencia si hay contenido espectral cuando hacemos la interpolaci´ on,

Transformada R´ apida (FFT) En la pr´ actica, la Transformada de Fourier se calcula con una algoritmo llamado “Fast Fourier Transform” o FFT. Por ejemplo en Matlab o Octave la funci´on para calcular la transformada de Fourier se llama ’fft’. Este algoritmo es m´ as eficiente cuando N es potencias de 2, i.e., p N = 2 con p un n´ umero entero. Es por esto que en la pr´ actica en general se hace Zero Padding de modo que la se˜ nal tenga un largo N = p2 con los beneficios, ◮

Mayor eficiencia del algoritmo FFT

◮

Efecto colateral de mejorar la interpolaci´ on espectral.

FFT de una Sinusoide

FFT de una Sinusoide

FFT de una Sinusoide

Discontinuidades por extensi´on periodica,

FFT de una Sinusoide

Teoremas de Convoluci´ on Theorem (Convoluci´ on) Para cualquier x, y ∈ CN , x⊛y ↔X ·Y Theorem (Dual de la Convoluci´ on) Para cualquier x, y ∈ CN , x·y ↔

1 X ⊛Y N

Estos son quizas el m´ as importante teorema. Son la base de la implementaci´on de Filtros por convoluci´ on (Debido a la rapidez del FFT).

Otras Aplicaciones

La Transformada de Fourier es la base del an´alisis y s´ıntesis expectral, ◮

Filtros y Convoluci´on

◮

Transformada Corta de Fourier

◮

Espectrogramas

◮

Vocoders

◮

S´ıntesis sinusoidal