Transformada Rápida de Fourier

Transformada Rapida de Fourier

L. S. Sousa, M. B. Rodrigues

Instituto Federal do Ceara

[email protected], [email protected]

December 9, 2013

L. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 1 / 48

Indice

1 Conceitos BasicosSeries de FourierTransformada de FourierRepresentacao de Sinais

2 Raızes Complexas da Unidade3 Transformada Discreta de Fourier

Definicao4 Transformada Rapida de Fourier

IntroducaoAlgoritmo de Cooley-TukeyPasso-a-PassoAnalise da Complexidade ParcialContinuando com a melhoriaAnalise da ComplexidadeBorboletaAlgoritmo de Cooley-TukeyReferencias e Agradecimentos


Series de Fourier

Figure: Jean Baptiste Joseph Fourier

Series de Fourier

“Qualquer funcao periodica, por mais complicada que seja, pode serdecomposta a partir de uma soma de senos e cossenos”


Series de Fourier

Series de Fourier

Uma serie de fourier decompoe funcoes periodicas ou sinais periodicos paraa soma de um conjunto, possivelmente finito, de funcoes simples deoscilacao(Senos e Cossenos). (Wikipedia)


Series de Fourier


Transformada de Fourier

A Transformada de Fourier e deduzida atraves das Series deFourier.

E utilizada para mudar o domınio de uma Representacao de Sinal.


Representacao de Sinais

Um sinal, naturalmente, e representado no domınio do tempo.

Exibe um grupo de caracterısticas do sinal.

Figure: Sinal no domınio do tempo


Representacao de Sinais

Para que algumas caracterısticas do sinal sejam exibidas, e necessarioque ele esteja no Domınio da Frequencia.

Exibe outro grupo de caracterısticas do sinal.

Figure: Sinal no domınio da frequencia.


Raızes Complexas da Unidade

Uma n-esima raiz complexa da unidade e um numero W tal que:

W n = 1

Existem exatamente n raızes n-esimas complexas da unidade, que sao:

e2πikn , para k = 0, 1, ..., n-1

e iu = cos(u) + isen(u)

O valor Wn = e2πin e a principal raız complexa da unidade, assim:

W 0n , W 1

n , W 2n , ..., W n−1

n . Sao as n raızes da unidade.


Raızes Complexas da Unidade

Formam o grupo aditivo (Zn, +) modulo n.

W nn = W 0

n = 1

W jnW k

n = W j+kn = W

(j+k)mod(n)n

W−1n = W n−1

n

Figure: Raizes Complexas n = 8


Transformada Discreta de Fourier

Considere a sequencia x[n] que e periodica em tempo T, ou seja.

x [n] = x [n + rT ], ∀rεZ (1)

Tal sequencia pode ser representada por uma serie de Fourier,correspondendo a soma de sequencias exponenciais relacionadasharmonicamente.

x [n] =1

N

∞∑m

X [m]ei2πmn

N (2)



A representacao em serie de Fourier de um sinal periodico contınuono tempo, geralmente, precisa de infinitas exponenciais complexas.

No entanto, a Serie de Fourier para qualquer sinal discreto no tempocom perıodo N requer apenas N exponenciais complexas ja que elassao periodicas.



Assim, a representacao torna-se:

x [n] =1

N

N−1∑m=0

X [m]ei2πmn

N (3)

E os coeficientes da serie de Fourier X[m] sao obtidos a partir de x[n]pela relacao.

X [m] =N−1∑n=0

x [n]e−i2πmn

N (4)



Se fizermos Wn = e−i(2πN

) Temos que:

Equacao de Analise:

X [k] =N−1∑n=0

x [n]W knN

(DFT )

(5)

Equacao de Sıntese:

X [k] =1

N

N−1∑k=0

X [k]W−knN

(IDFT )

(6)



Alta complexidade computacional com custo assintotico de O(n2)

Para diminuir essa complexidade, e proposto o uso da TransformadaRapida de Fourier.


Introducao

Algoritmo criado em 1965

Autores: J.W. Cooley(IBM) e J.W. Tukey(Bell Labs)

Dividir a subsequencia x[n] em duas sequencias.

Decimacao em Tempo

Algoritmos no qual a sequencia e decomposta sucessivamente emsequencias menores.


Algoritmo de Cooley-Tukey

Figure: Algoritmo de Cooley-Tukey



X (k) =∞∑

nPar

x [n]W nkN +

∞∑nImpar

x [n]W nkN (7)

Fazendo n = 2r e n = 2r + 1, temos que:

X (k) =

N/2−1∑r=0

x [2r ]W 2rkN +

N/2−1∑r=0

x [2r + 1]W(2r+1)kN (8)

X (k) =

N/2−1∑r=0

x [2r ](W 2N)

rk+ W k

N

N/2−1∑r=0

x [2r + 1](W 2N)

rk(9)



Mas W 2N = WN/2 ja que:

W 2N = e−2i( 2π

N) = e

−2i( π(N/2)

)= WN/2

Logo (9) pode ser reescrito como:

X (k) =

N/2−1∑r=0

x [2r ]W rkN/2 + W k

N

N/2−1∑r=0

x [2r + 1]W rkN/2 (10)

X (k) = G [k] + W kNH[k] (11)



Cada parcela da equacao (11) e uma DFT de N/2 pontos:

G[k] e H[k]

No caso de uma DFT de 8 pontos, o resultado da decimacao notempo gera o seguinte diagrama de fluxo.





























Complexidade

Analise de Complexidade:

DFT Classica

N2 Multiplicacoes complexas e adicoes.

Cooley-Tukey

X (k) = G [k] + W kNH[k]

G [k] e H[k] sao duas DFTs de N/2 pontos, portanto, ambas realizam(N/2)2 operacoes.

A multiplicacao W kNH[k] e realizada N vezes.

Assim, o custo do algoritmo de Cooley-Tukey e 2(N/2)2 + N.


Complexidade

Assim, usando o algoritmo de Cooley-Tukey, para N > 2, temos umacomplexidade menor do que usando o algoritmo de DFT classico.

Ainda podemos melhorar a complexidade se aplicarmos novamente aideia de divisao de Cooley-Tukey.


Complexidade

Figure: DivisaoL. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 32 / 48


Se N e potencia de 2, podemos dividir novamente o conjunto dedados:

G [k] =

N/4−1∑l=0

g [2l ]W lkN/4 + W k

N/2

N/4−1∑l=0

g [2l + 1]W lkN/4 (12)

H[k] =

N/4−1∑l=0

h[2l ]W lkN/4 + W k

N/2

N/4−1∑l=0

h[2l + 1]W lkN/4 (13)



G[k] = [ x[0], x[2], x[4], x[6] ], tal quex[0] = 0, x[2] = 1, x[4] = 2, x[6] = 3

Figure: Divisao




Figure: Divisao




Figure: Divisao




Figure: Divisao




Figure: Divisao




Figure: Fluxo Completo DFT 8 Pontos


Analise da Complexidade

A equacao de recorrencia que descreve o problema eT (n) = 2T (n/2) + O(n).

Aplicando o metodo mestre, tempos que 2 = 21, daı temos que ocusto e O(n log n).


Processo da Borboleta

A DFT de 8 pontos teve sua computacao reduzida ate a DFT de 2pontos:

Figure: Butterfly



A obtencao de um par de valores de um estagio depende apenas deum par de valores do estagio anterior.

Figure: Butterfly

Mas WN/2N = e−i(2π/N)N/2 = e−iπ = −1

Assim, o fator Wr+(N/2)N pode ser escrito como:

Wr+(N/2)N = W

N/2N W r

N = −W rN (14)



Isso muda o grafico da borboleta para:

Figure: Grafico Butterfly Simplificado


Fluxo Completo FFT 8 pontos

Figure: Fluxo Completo FFT 8 Pontos


Fluxo Completo FFT 8 pontos

Figure: Fluxo Completo FFT 8 Pontos


Pseudocodigo FFT

FFT(a, w)se n = 1 entao

retorne y = ax = w0 # x ira armazenar as potencias de w, entao inicialmente x = 1.# Etapa de divisao que separa ındices pares e ımparesapar = [a0, a2, a4, ..., an−2]aimpar = [a1, a3, a5, ..., an−2]# Chamadas Recursivas, com W 2 como (n/2)-esima raiz da unidade, pelapropriedade da reducaoypar = FFT (apar ,w2)y impar = FFT (aimpar ,w2)# Etapa de combinacao, usando x = w i

para i = 0 a n/2-1 facayi = ypari + xy impar

i #Usa a propriedade reflexiva

yi+n/2 = ypari − xy impari

x = xwretorne yL. S. Sousa, M. B. Rodrigues (IFCE) FFT December 9, 2013 46 / 48

MATLAB

Aplicacao no MATLAB

Barata exibira um exemplo no MATLAB da FFT em um sinal.


Referencias e Agradecimentos

Referencias

Centro de Informatica - UFPE - Carlos Alexandre Mello

Fundamentos da Matematica Elementar - Volume 6 - Gelson Iezzi

Discrete-Time Signal Processing, J.R.Buck,A.Oppenheim e R.W.Schafer, Prentice-Hall,1999

Agradecimentos

Obrigado pela atencao!


Documents

Transformada Rápida de Fourier