INSTITUTO FEDERAL DO ESPIRITO SANTO

- ENGENHARIA ELÉTRICA -

Abílio Marcos Coelho de Azevedo

Caio Cesar Batista Brito

Gustavo Breda

Transformada Rápida de Fourier – FFT

Construção do “Diagrama Butterfly”

VITÓRIA

2016

ÍNDICE 1. RESUMO.................................................................................................................3

2. INTRODUÇÃO........................................................................................................3

3. DESENVOLVIMENTO...........................................................................................43.1 TRANSFORMADARÁPIDADEFOURIER–FFT...................................................................43.2 “DIAGRAMADEBUTTERFLY”...........................................................................................6

3.2.1 Teoria...............................................................................................................................63.2.2 ExplicaçãoAlgébricadoButterfly....................................................................................73.2.3 Exemplo...........................................................................................................................9

3.3 ALGORITIMO...................................................................................................................9

4. RESULTADOS......................................................................................................104.1 TESTEDAFUNÇÃOFFTDOMATLABEDADESENVOLVIDA.............................................104.2 EXEMPLODAFFTDESENVOLVIDA..................................................................................11

5. CONCLUSÕES......................................................................................................11

6. BIBLIOGRAFIA.....................................................................................................12

3

1. RESUMO

O trabalho se baseia na Transformada Rápida de Fourier (Fast

Fourier Transform - FFT) e a construção do diagrama de Butterfly.

A FFT é um algoritmo eficiente para calcular a Transformada

Discreta de Fourier (Discrete Fourier Transform - DFT) e sua inversa.

Esse algoritmo é muito usado em processamento digital de sinais e tem

diversas aplicações.

O “Diagrama de Butterfly” é a representação computacional do

algoritmo da Transformada Rápida de Fourier.

2. INTRODUÇÃO

O “custo computacional” da transformada convencional é de

𝑂(𝑛!). Para reduzir este custo utilizamos o algoritmo FFT, cujo “custo

computacional” é 𝑂(𝑁 ∙ log!𝑁).

Este algoritmo foi criado em 1965 por J.W. Cooley (IBM) e J.W.

Tukey (Bell Labs) e a idéia principal foi dividir a sequência discreta 𝑥[𝑛]

em sequências menores (decimação do tempo).

A representação gráfica deste algoritmo é o “diagrama de

Butterfly. Gauss foi o pioneiro em seu desenvolvimento que ocorrera

em 1805, porém tal algoritmo não foi devidamente reconhecido, devido

ao fato da época em que foi desenvolvido. Entretanto, em 1965 J.W.

Cooley (IBM) e J.W. Tukey (Bell Labs) publicaram um artigo sobre a

FFT(Fast Fourier Transform) que realmente despertou o interesse

geral, pois essa era a época em que computadores digitais estavam

ganhando mais território, e por conseguinte uma maneira rápida de

análise de dados era importante.

4

O trabalho está organizado em três partes: explicação teórica e

exemplo da FFT, explicação teórica e exemplo do “diagrama de

Butterfly” e o algoritmo desenvolvido para efetuar a FFT.

3. DESENVOLVIMENTO

3.1 TRANSFORMADA RÁPIDA DE FOURIER – FFT

A transformada rápida de Fourier é um aprimoramento da

transformada discreta de Fourier para uso computacional. Sua

motivação veio do alto custo computacional da DFT:

𝑂(𝑁!)

A ideia da FFT é subdividir uma DFT em sequências menores

gerando um custo operacional de:

𝑂(𝑁 log!𝑁)

As subdivisões se dão a partir da DFT:

𝑋 𝑘 = 𝑥 𝑛 𝑊!!"

!!!

!!!

Considerando o comprimento N de x[n] igual a 2v, podemos

separar x[n] em duas séries, g[n] e h[n], uma de coeficientes pares e

uma de coeficientes ímpares:

𝑋 𝑘 = 𝑔 𝑛 𝑊!!"

!!!"#

+ ℎ 𝑛 𝑊!!"

!!í!"#$

𝑋 𝑘 = 𝑔[𝑛]𝑊!!!"

!!!!

!!!

+ ℎ[𝑛]𝑊!!!!! !

!!!!

!!!

Onde:

𝑊! = 𝑒!!(!!! )

5

Note que k=1, 2, 3, ..., !!− 1, pois daí em diante, até 𝑁 − 1, os

coeficientes da DFT serão simétricos e iguais.

Continuando o desenvolvimento, manipulamos 𝑊 da seguinte

forma:

𝑊!!! = 𝑒!!!"(

!!! ) = 𝑒

!!!"( !!!)=𝑊!

!

!

E assim obtemos:

𝑋 𝑘 = 𝑔[𝑛]𝑊!!

!"

!!!!

!!!

+ ℎ[𝑛]𝑊!!

!𝑊!!

!!!!

!!!

𝑋 𝑘 = 𝑔[𝑛]𝑊!!

!"

!!!!

!!!

+𝑊!! ℎ[𝑛]𝑊!

!

!

!!!!

!!!

E constatamos que:

𝑋 𝑘 = 𝐺 𝑘 +𝑊!!𝐻 𝑘 𝑝𝑎𝑟𝑎 𝑘 = 0,1,2,… ,

𝑁2− 1

O menor custo operacional da FFT é proveniente da grande

quantidade de subdivisões que podem ser feitas nas sequências

derivada de x[n]. Dessa forma, podemos continuar subdividindo, agora,

g[n] e h[n] enquanto seus comprimentos Ng e Nh forem 2v:

𝐺 𝑘 = 𝑔 2𝑛 𝑊!!

!" +𝑊!!

! 𝑔[2𝑛 + 1]𝑊!!

!"

!!!!

!!!

!!!!

!!!

E assim sucessivamente. Para sequências com N diferente de

2! basta completar o sinal com zeros até que o mesmo atinja o

comprimento desejado.

6

3.2 “DIAGRAMA DE BUTTERFLY”

3.2.1 Teoria

O desenvolvimento do algoritmo explora a simetria do termo

𝑒!!!!"#/!. Define-se 𝑊! = е!!!!/!. Agora, pela simetria do complexo

conjugado tem-se 𝑊!!(!!!) =𝑊!

!!" = 𝑊!!" ∗

. Vale notar que 𝑊!!" =

𝑒!!!!" = 1. Por essa propriedade pode-se afirmar que existe uma

periodicidade em 𝑛 ∙ 𝑘, 𝑊!!" =𝑊!

!(!!!) =𝑊!!!! !.

Para o método da decimação em tempo, o algoritmo é

sucessivamente decomposto em sequências menores.

Dado as relações anteriores tem-se, portanto, que a DFT é:

Então, separa-se essa série para n pares e n ímpares:

Sendo 𝑟 = 0, 1, . . . ,𝑁/2 − 1; e fazendo com que a parte de 𝑛 Par

seja 𝑛 = 2 ∙ 𝑟, e 𝑛 ímpar 𝑛 = 2 ∙ 𝑟 + 1, tem-se:

Mas, 𝑊!! = 𝑒!!

!!! ! = 𝑒

!!!!!! =𝑊!/!. Então:

7

Então tem-se que 𝑋 𝑘 = 𝑋!"#$% 𝑘 +𝑊!!𝑋í!"#$%& 𝑘 , onde

𝑋!"#$% 𝑘 é o resultado da série de fatores pares, e 𝑋í!"#$%& 𝑘 a fatores

ímpares. Nota-se que cada parte da equação é uma DFT com !!

pontos. O custo computacional será 2 !!

!+ 𝑁, o que não é tão bom.

Porém, se continuar dividindo em mais partes até o máximo que é !!!= 1, onde 𝑝 = log!𝑁 vezes. Assim o custo computacional será de

𝑁 ∙ log!𝑁 .

3.2.2 Explicação Algébrica do Butterfly

a) Separa os índices pares dos ímpares espaçados somando 𝑁!"!#$/2,

onde 𝑁!"!#$ é o número de entradas, uma maneira fácil de fazer isso

é colocar os índices em números em binários na ordem

decrescente.

b) Então, no exemplo a ordem será 𝑁!"!#$/2 = 2 e a parte par fica

𝑥[0] 𝑥[2] e a parte ímpar fica 𝑥[1] 𝑥[3].

c) A primeira iteração é como se o sistema estivesse divido em

𝑁!"!#$/2 partes de duas entradas. Para avançar no diagrama cruza-

se as linhas na primeira iteração. É importante dizer, neste ponto,

que as linhas que sobem são multiplicadas pelo fator ‘W’ e são

somadas com o valor contido na linha que chegam, e a linha que

desce é adicionada a linha que ela encosta multiplica pelo fator 'W'

negativo. E os resultados dos nós é a soma dos valores atuais que

esses vetores carregam. Ou seja, multiplicando-as por 𝑊!!, onde 𝑁

8

é 2 na primeira iteração, 4 na segunda e assim até chegar ao

número de entradas. E 𝑝 varia de 0 até 𝑁/2 − 1. E o fator 𝑊 é

multiplicado por −1 a cada vez que o grupo é repetido.

d) Na segunda iteração, considera-se o sistema divido em partes com

4 entradas cada. O que ocorre no diagrama é: Passa-se direto por

uma linha e usa-se do mesmo princípio anterior, ou seja, na linha

que está descendo um vetor que será subtraído (matematicamente

falando, pois o termo de 𝑊 será negativo) também chega um vetor

subindo, este somando com o valor atual da linha, que tem origem

da mesma linha onde chegou o vetor que desceu.

e) Após isso parte-se para a terceira iteração, agora o cruzamento

será de três linhas, ou seja, generalizando, o número de linhas que

cruza é o valor máximo de 𝑝.

Imagem 1: Explicação Algébrica do Diagrama de Butterfly.

9

3.2.3 Exemplo

Encontre os coeficientes da DFT do sinal abaixo usando o

“diagrama de Butterfly”.

O sinal possui 4 pontos, logo, 𝑁 = 4.

3.3 ALGORITIMO

N=length(x); nfft=2^ceil(log2(N)); z=zeros(1,nfft); Sum=0;

for k=1:nfft for jj=1:N Sum=Sum+x(jj)*exp(-2*pi*j*(jj-1)*(k-1)/nfft); end

X(k)=Sum; Sum=0;% Reset

end

10

4. RESULTADOS

4.1 TESTE DA FUNÇÃO FFT DO MATLAB E DA DESENVOLVIDA

Para um sinal x(t):

- x1= 1*sin(2*pi*20*t);

- x2= 20*sin(2*pi*40*t);

- x3= 5*sin(2*pi*60*t);

- x4= 10*sin(2*pi*80*t);

- x=x1+x2+x3+x4;

Amostramos com uma frequência 𝐹! = 300 ℎ𝑧 para chegar em um

𝑥[𝑛], e obtivemos o seguinte resultado da transformada (FFT), usando

a função do Matlab e o algoritmo implementado

Figura 2: FFT do sinal 𝑥[𝑛] pela função do matlab e pelo algoritmo implementado.

Podemos observar que obtivemos o mesmo resultado,

comprovando a eficácia do algoritmo implementado.

11

4.2 EXEMPLO DA FFT DESENVOLVIDA

Resolvendo o exemplo proposto na secção 3.2.3, obtivemos o

seguinte resultado para a Transformada de Fourier:

Figura 3: FFT do sinal 𝑥[𝑛] pela função do matlab e pelo algoritmo implementado.

Podemos observar que obtivemos o mesmo resultado, tanto com

a função do Matlab quanto com o algoritmo implementado.

5. CONCLUSÕES

Concluí-se que o aperfeiçoamento matemático de algoritmos

computacionais é fundamental para otimização de processamento. No

caso da Transformada de Fourier, que tem diversas aplicações em

analise e processamento de sinais, o algoritmo representado pelo

diagrama de Butterfly ampliou as aplicações da transformada como por

exemplo para o processamento de voz em tempo real.

12

6. BIBLIOGRAFIA

[L. S. Sousa, M. B. Rodrigues 2013] - Transformada Rápida de Fourier

– Disponível em

<http://pt.slideshare.net/LucasSilvadeSousa/presentation-1-29054177>

Acesso em: 1 de julho de 2016.

[Carlos Alexandre Mello] - Centro de Informática - UFPE - Carlos

Alexandre Mello.

[Gelson Iezzi] - Fundamentos da Matemática Elementar - Volume 6

[J.R.Buck, A.Oppenheim e R.W.Schafer 1999] - Discrete-Time Signal

Processing- Prentice-Hall.

[Carlos Alexandre Mello 2016] - Processamento Digital de Sinais –

Disponível em < http://www.cin.ufpe.br/~cabm/pds/PDS.pdf> Acesso

em: 1 de julho de 2016.

[IllinoisDSP, 2010] - Fast Fourier Transform – Disponível em

<https://www.youtube.com/watch?v=D5ueRUyCP58> Acesso em 13 de

Julho de 2016.

[Barry Van Veen, 2012] - The Fast Fourier Transform Algorithm –

<https://www.youtube.com/watch?v=EsJGuI7e_ZQ> Acesso em 13 de

Julho de 2016.