Upload
terezinha-camarinho-macedo
View
221
Download
5
Embed Size (px)
Citation preview
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
• 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
• 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
4
Transformada Rápida de Fourier
Método da Decimação na Frequência
• 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
• 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
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
• 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
• 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
• 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
• 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
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
• 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
• 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
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
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
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
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
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
• Primeira IteraçãoPrimeira Iteração
20
Se x[n] é uma sequência de N=4 amostra
• Segunda IteraçãoSegunda Iteração
21
Se x[n] é uma sequência de N=4 amostra
• 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
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
• 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
• 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
• 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
• A FFT de uma sequência de 8 pontosA FFT de uma sequência de 8 pontos
27
28
29
Transformada Rápida de Fourier
Método da Decimação no Tempo
• 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
• 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
• 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
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
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
35
Para uma sequência x[n] de 8 pontos
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)