36
Algoritmo da Algoritmo da Transformada Rápida de Transformada Rápida de Fourier (FFT) Fourier (FFT) Prof. José Mauricio Neto [email protected] 1 Universidade Federal da Paraíba Departamento de Engenharia Elétrica Centro de Energias Alternativas e Renováveis

Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto [email protected] 1 Universidade Federal da Paraíba Departamento de Engenharia

Embed Size (px)

Citation preview

Page 1: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

Algoritmo da Transformada Algoritmo da Transformada Rápida de Fourier (FFT)Rápida de Fourier (FFT)

Prof. José Mauricio [email protected]

1

Universidade Federal da ParaíbaDepartamento de Engenharia ElétricaCentro de Energias Alternativas e Renováveis

Page 2: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• A FFT (Fast Fourier Transform) é um algoritmo eficiente para o cálculo dos coeficientes da DFT reduzindo a complexidade computacional (somas e multiplicações).

• Considera-se uma sequência x[n] consistindo de 2 amostras, em que “” é um número inteiro positivo, ou seja o número de amostras da sequência discreta é uma potência de 2 (N=2,4,8,16, etc)

2

Transformada Rápida de Fourier

Page 3: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Se x[n] não é uma sequência contendo 2 amostras, então x[n] é preenchidos com zeros até que o tamanho seja um número potência de 2.

• Existem dois métodos para a implementação do algoritmo da FFT:

Método de Decimação na Frequência Método de Decimação no Tempo

3

Transformada Rápida de Fourier

Page 4: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

4

Transformada Rápida de Fourier

Método da Decimação na Frequência

Page 5: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• A partir da DFT

5

Método de Decimação na Frequência

1

0

( ) [ ] , 0,1,2,...., 1N

knN

n

X k x n W k N

0

2

2,4,8,16,...jj N

NW e e Para N

2 ( 1)( ) [0] [1] [2] ... [ 1]k k k NN N NX k x x W x W x N W

Page 6: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• A partir da DFT

6

Método de Decimação na Frequência

2 ( 1)( ) [0] [1] [2] ... [ 1]k k k NN N NX k x x W x W x N W

1 2 ( 1)

2 4 2( 1)

( 1) 2( 1) ( 1)( 1)

1 1 1 ... 1[0]1 ...[1]

1 ......

...[ 1]

1 ...

NN N N

NN N N

N N N NN N N

xW W Wx

X W W W

x NW W W

Page 7: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

7

Método de Decimação na Frequência

2 ( 1)( ) [0] [1] [2] ... [ 1]k k k NN N NX k x x W x W x N W

( /2 1)

/2 ( 1)

( ) [0] [1] ... [ / 2 1]

[ / 2] ... [ 1]

k k NN N

kN k NN N

X k x x W x N W

x N W x N W

• Reescrevendo a formula da DFT

( / 2 1) ( 1)

0 /2

( ) [ ] [ ]N N

kn knN N

n n N

X k x n W x n W

Page 8: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Modificando o limite da somatória do termo da direita

8

Método de Decimação na Frequência

( / 2 1) ( 1)

0 /2

( ) [ ] [ ]N N

kn knN N

n n N

X k x n W x n W

( 1)

/2

[ ] Realizando a mudança de variávelcom / 2

Então / 2 e os novos limites são/ 2 0

1 / 2 1

Nkn

Nn N

x n W n N

n NPara n N entãoPara n N então N

Page 9: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Modificando a variável de para n:

9

Método de Decimação na Frequência( /2 1) ( 1)

0 / 2

( ) [ ] [ ]N N

kn knN N

n n N

X k x n W x n W

( 1) ( /2 1) ( /2 1)

( / 2) /2

/2 0 0

[ ] [ / 2] [ / 2]N N N

kn k N kN kN N N N

n N

x n W x N W W x N W

( /2 1)/2

0

[ / 2]N

kN knN N

n

W x n N W

( /2 1) ( /2 1)( / 2)

0 0

( ) [ ] [ / 2]N N

kn N k knN N N

n n

X k x n W W x n N W

Page 10: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Avaliando-se o coeficiente

10

Método de Decimação na Frequência

( /2 1) ( /2 1)( / 2)

0 0

( ) [ ] [ / 2]N N

kn N k knN N N

n n

X k x n W W x n N W

2

2 ( /2)/2

( / 2)

1

( 1)

jN

N

j NN jNN

N k kN

W e

W e e

W

Page 11: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Finalmente temos a representação da DFT:

11

Método de Decimação na Frequência

( / 2 1) ( / 2 1)

0 0

( ) [ ] ( 1) [ / 2]N N

kn k knN N

n n

X k x n W x n N W

( /2 1)

0

( ) [ ] ( 1) [ / 2]N

k knN

n

X k x n x n N W

1

0

( ) [ ] , 0,1, 2,...., 1N

knN

n

X k x n W k N

Page 12: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

Realizando-se a mudança de variável de k=0,...,(N-1) para m=0,...,(N/2-1)

Se k=2m (um número par)

12

Método de Decimação na Frequência

( / 2 1)

2

0

(2 ) [ ] [ / 2]N

mnN

n

X m x n x n N W

Se k=2m+1 (um número impar)

( /2 1)

2

0

(2 1) [ ] [ / 2]N

n mnN N

n

X m x n x n N W W

( / 2 1)

0

( ) [ ] ( 1) [ / 2]N

k knN

n

X k x n x n N W

Page 13: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Se Se k=2mk=2m (um número par) (um número par)

13

( / 2 1)

2

0

(2 ) [ ] [ / 2]N

mnN

n

X m x n x n N W

22 22 ( /2)/2

jj NNN NW e e W

( / 2 1) ( / 2 1)

2/2

0 0

[ ] [ ] [ / 2] 0,1,...., / 2 1

(2 ) [ ] [ ]N Nmn mn

N Nn n

a n x n x n N Para n N

X m a n W a n W

( / 2 1)

/20

(2 ) [ ] { [ ] / 2 }N

mnN

n

X m a n W DFT a n com N pontos

Page 14: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Se Se k=2m+k=2m+11 (um número impar) (um número impar)

14

22 22 ( / 2)/2

jj NNN NW e e W

( / 2 1) ( / 2 1)

2/2

0 0

[ ] [ ] [ / 2] 0,1,...., / 2 1

(2 1) [ ] [ ]N Nmn mnn n

N N N Nn n

b n x n x n N Para n N

X m b n W W b n W W

( /2 1)

/20

(2 1) [ ] { [ ] / 2 }N

n mn nN N N

n

X m b n W W DFT b n W com N pontos

( / 2 1)

2

0

(2 1) [ ] [ / 2]N

n mnN N

n

X m x n x n N W W

Page 15: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

15

[ ]

{ [ ] / 2 }{ [ ]}

{ [ ] / 2 }nN

DFT x n com N pontos

DFT a n com N pontosDFT x n

DFT b n W com N pontos

[ ] [ ] [ / 2][ ] [ ] [ / 2]

a n x n x n Nb n x n x n N

Notação das operaçõesNotação das operações

Page 16: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

16

Núcleo básico da FFT (operação borboleta - Núcleo básico da FFT (operação borboleta - butterflybutterfly))

Para uma FFT de tamanho N=2

O número de fatores de giro ( ) na i-ésima etapa é P=2M-i

Para cada etapa, o número “t ” nos fatores de giro é

tNW

1

2

2 0,1,..., ( 1)

M i

i

P

t Q em que Q P

Page 17: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

17

[ ] [ ] [ / 2][ ] [ ] [ / 2]

a n x n x n Nb n x n x n N

Se x[n] é uma sequência de N=4 amostras

( /2 1)

/20

( /2 1)

/20

(2 ) [ ] { [ ] / 2 }

(2 1) [ ] { [ ] / 2 }

Nmn

Nn

Nn mn n

N N Nn

X m a n W DFT a n com N pontos

X m b n W W DFT b n W com N pontos

1

20

1

4 2 20

(2 ) [ ] { [ ] 2 }

(2 1) [ ] { [ ] 2 }

mn

n

n mn n

n

X m a n W DFT a n com pontos

X m b n W W DFT b n W com pontos

m=0,...,(N/2-1)

• Desenvolvendo a somatória m=0,1

Page 18: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

18

Núcleo básico da FFT (operação borboleta - Núcleo básico da FFT (operação borboleta - butterflybutterfly))

Para uma FFT de tamanho N=4=22, M=2

Na etapa 1, P=2M-1=22-1=2 fatores de giro

Na etapa 2, P=2M-2=22-2=1 fator de giro

1 1 0 14 42 1 {0,1} ,t Q W W

2 1 042 2 {0}t Q W

1

2

2 0,1,..., ( 1)

M i

i

P

t Q em que Q P

Page 19: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

19

Se x[n] é uma sequência de N=4 amostra

10

20

10 1

4 2 40

(0) ( [ ] [ 2]) ( [0] [2]) ( [1] [3])

(1) ( [ ] [ 2]) ( [0] [2]) ( [1] [3])

n

n

n n

n

X x n x n W x x x x

X x n x n W W x x x x W

• Para m=0Para m=0

• Para m=1Para m=1

11

2 20

11 1

4 2 4 20

(2) ( [ ] [ 2]) ( [0] [2]) ( [1] [3])

(3) ( [ ] [ 2]) ( [0] [2]) ( [1] [3])

n

n

n n

n

X x n x n W x x x x W

X x n x n W W x x x x W W

Page 20: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Primeira IteraçãoPrimeira Iteração

20

Se x[n] é uma sequência de N=4 amostra

Page 21: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Segunda IteraçãoSegunda Iteração

21

Se x[n] é uma sequência de N=4 amostra

Page 22: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Desenvolvendo a somatória

22

[ ] [ ] [ / 2][ ] [ ] [ / 2]

a n x n x n Nb n x n x n N

Se x[n] é uma sequência de N=8 amostra

( /2 1)

/20

( /2 1)

/20

(2 ) [ ] { [ ] / 2 }

(2 1) [ ] { [ ] / 2 }

Nmn

Nn

Nn mn n

N N Nn

X m a n W DFT a n com N pontos

X m b n W W DFT b n W com N pontos

3

40

3

8 4 20

(2 ) [ ] { [ ] 4 }

(2 1) [ ] { [ ] 4 }

mn

n

n mn n

n

X m a n W DFT a n com pontos

X m b n W W DFT b n W com pontos

m=0,...,(N/2-1)

m=0,1,2,3

Page 23: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

23

Núcleo básico da FFT (operação borboleta - Núcleo básico da FFT (operação borboleta - butterflybutterfly))

Para uma FFT de tamanho N=8=23, M=3

Na etapa 1, P=2M-1=23-1=4 fatores de giro

Na etapa 2, P=2M-2=23-2=2 fatores de giro

Na etapa 3, P=2M-3=23-3=1 fator de giro

1 1 0 1 2 38 8 8 82 1 {0,1, 2,3} , , ,t Q W W W W

2 1 0 28 82 2 {0,1} ,t Q W W

3 1 082 4 {0}t Q W

1

2

2 0,1,..., ( 1)

M i

i

P

t Q em que Q P

Page 24: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Para m=0 (etapa 1)Para m=0 (etapa 1)

24

30

40

30 1 2 3

8 4 8 8 80

(0) ( [ ] [ 4]) ( [0] [4]) ( [1] [5]) ( [2] [6]) ( [3] [7])

(1) ( [ ] [ 4]) ( [0] [4]) ( [1] [5]) ( [2] [6]) ( [3] [7])

n

n

n n

n

X x n x n W x x x x x x x x

X x n x n W W x x x x W x x W x x W

Page 25: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Para m=1 (etapa 2)Para m=1 (etapa 2)

25

31

40

31

8 40

(2) ( [ ] [ 4])

(3) ( [ ] [ 4])

n

n

n n

n

X x n x n W

X x n x n W W

Page 26: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Para m=2 (etapa 3)Para m=2 (etapa 3)

26

32

40

32

8 40

(4) ( [ ] [ 4])

(5) ( [ ] [ 4])

n

n

n n

n

X x n x n W

X x n x n W W

Page 27: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• A FFT de uma sequência de 8 pontosA FFT de uma sequência de 8 pontos

27

Page 28: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

28

Page 29: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

29

Transformada Rápida de Fourier

Método da Decimação no Tempo

Page 30: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Neste algoritmo se divide a sequência x[n] em índices pares x[2m] e impares x[2m=1]

30

Método de Decimação no Tempo

1

0

( ) [ ] , 0,1, 2,...., 1N

knN

n

X k x n W k N

( / 2 1) ( / 2 1)2 2

0 0

( ) [2 ] [2 1]N N

mk k mkN N N

m m

X k x m W x m W W

Page 31: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Usando a relação

• Definem-se novas funções:

31

Método de Decimação no Tempo2

/2N NW W( / 2 1) ( / 2 1)

/2 / 20 0

( ) [2 ] [2 1]N N

mk k mkN N N

m m

X k x m W W x m W

( /2 1)

/20

( /2 1)

/20

( ) [2 ] { [2 ] / 2 }

( ) [2 1] { [2 1] / 2 }

( ) ( / 2) 0,1,..., / 2 1( ) ( / 2) 0,1,..., / 2 1

Nmk

Nm

Nmk

Nm

G k x m W DFT x m com N pontos

H k x m W DFT x m com N pontos

G k G k N para k NH k H k N para k N

Page 32: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

• Substituindo-se as novas funções temos que a primeira metade da DFT pode ser calculada por:

• Sendo que: • A segunda metade é calculada por:

32

Método de Decimação no Tempo

( ) ( ) ( ) 0,1,..., / 2 1kNX k G k W H k k N

( /2 )N k kN NW W

( / 2 ) ( ) ( ) 0,1,..., / 2 1kNX N k G k W H k k N

Page 33: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

33

Núcleo básico da FFT (operação borboleta - Núcleo básico da FFT (operação borboleta - butterflybutterfly))

Para uma FFT de tamanho N=2

O número de fatores de giro ( ) na i-ésima etapa é P=2i-1

Para cada etapa, o número “t ” nos fatores de giro é

tNW

12

2 0,1,..., ( 1)

i

M i

P

t Q em que Q P

Page 34: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

34

Núcleo básico da FFT (operação borboleta - Núcleo básico da FFT (operação borboleta - butterflybutterfly))

Para uma FFT de tamanho N=8=23, M=3

Na etapa 1, P=21-1=20=1 fator de giro

Na etapa 2, P=22-1=2 fatores de giro

Na etapa 3, P=23-1=4 fatores de giro

3 1 082 4 {0}t Q W

3 2 0 28 82 2 {0,1} ,t Q W W

3 3 0 1 2 38 8 8 82 1 {0,1, 2,3} , , ,t Q W W W W

12

2 0,1,..., ( 1)

i

M i

P

t Q em que Q P

Page 35: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

35

Para uma sequência x[n] de 8 pontos

Page 36: Algoritmo da Transformada Rápida de Fourier (FFT) Prof. José Mauricio Neto mauricio@cear.ufpb.br 1 Universidade Federal da Paraíba Departamento de Engenharia

36

Comparação do Custo Computacional entre a DFT e a FFT

Características DFT de N pontos FFT de N pontos

Algoritmo Solução de N equações com N variáveis

0,5N borboletas/etapaP etapas

Total de borboletas = 0,5P.N

Multiplicações N por equação 1 por borboleta

Somas N-1 por equação 2 por borboleta

Total de multiplicações

N2 0,5*N*Log2(N)

Total de somas N(N-1) N.log2(N)