DTF E FFT

Prévia do material em texto

A DFT E A FFT 
 
Em casos práticos, normalmente a avaliação da transformada de Fourier 
não é feita utilizando os procedimentos analíticos. 
 
Muitas vezes não se dispõe de uma expressão analítica para a função que 
se deseja analisar o espectro. 
 
A Transformada Discreta de Fourier (DFT) é muito usada no 
estudo do espectro de sinais e é determinada numericamente com o 
auxílio de computador digital. 
Considerando-se N amostras do sinal no domínio do tempo, denotadas 
f(k), k=0,1,2,...,N-1, a DFT é dada por um conjunto de N amostras do sinal 
no domínio da freqüência, denotadas por F(n), n= 0,1,2,...,N-1 e definidas por 
F (n) 
1
N
f (k) e- j2 nk /N
N-1≡
=
∑ π
k 0 . 
 
Diz-se então que f(k) ↔ F(n) formam um par transformada e a reobtenção 
do sinal no domínio do temporal pode ser feita usando a transformada inversa 
discreta de Fourier: 
f (k) = F (n) ej2 kn /N
n=0
N-1 π∑ . 
 
PROPRIEDADES DA DFT 
 
Propriedades similares àquelas da transformada de Fourier são 
demonstráveis para a DFT. Em particular: 
Se x (kT X 
n
NT
 e y (kT Y 
n
NTs s
s
s
) )↔ ⎛⎝⎜
⎞
⎠⎟ ↔
⎛
⎝⎜
⎞
⎠⎟ , 
 
 
P1 - Linearidade. 
x (kT y (kT X 
n
NT
Y 
n
NTs s s s
) )+ ↔ ⎛⎝⎜
⎞
⎠⎟+
⎛
⎝⎜
⎞
⎠⎟ 
 
P2 - Simetria. 
( )1
N
X kT x 
n
NTs s
↔ −⎛⎝⎜
⎞
⎠⎟ 
 
P3 - Deslocamento no Tempo. 
x (kT lT X
n
NT
 es s
s
j nl/N− ↔ ⎛⎝⎜
⎞
⎠⎟)
π
 
 
P4-Teorema da Convolução em Freqüência. 
x (kT y (kT
N
 X 
i
NT
 Y
n - i
NT
 
1
N
 X 
n
NT
Y 
n
NT
s s
s si= 0
N-1
s s
) )
*
↔ ⎛⎝⎜
⎞
⎠⎟
⎛
⎝⎜
⎞
⎠⎟
≡ ⎛⎝⎜
⎞
⎠⎟
⎛
⎝⎜
⎞
⎠⎟
∑1
 
 
P5 - Teorema de Parseval. 
 x (kT
N
 X 
n
NT
2
s
sn =0
N-1
) = ⎛⎝⎜
⎞
⎠⎟∑∑=
− 1
2
0
1
k
N 
 
As amostras da DFT são periódicas, verificando as relações: 
 
F(n+mN) = F(n) e f(k+mN) = f(k) m=1,2,3,... 
 
 
 
 
 
Quando se deseja trabalhar com os valores de freqüência e tempo, usa-se: 
 
f (kT F 
n
NT
 , onde F 
n
NT
 f (kT es
s s
s
- j 
2 kn
N) )↔ ⎛⎝⎜
⎞
⎠⎟
⎛
⎝⎜
⎞
⎠⎟ = =
−∑ π
k
N
0
1
 
ao invés da notação simplificada f(k) ↔ F(n). 
 
Um aumento na quantidade N de amostras consideradas (e uma escolha do 
tempo de amostragem Ts) implica em uma melhor representação do espectro. 
 
 
J.W. Cooley (IBM) em colaboração com J.W. Tukey (Bell Labs) 
conseguiram uma revolução maior no tratamento digital de sinais em 1965 com a 
publicação da transformada rápida de Fourier, a FFT. Trata-se de um método 
engenhoso e altamente eficiente de reagrupar os cálculos dos coeficientes de uma 
DFT. 
 
 
Muitos “softwares” dispõem de rotinas para o cálculo da FFT, e.g., 
MATEMATICATM, MATLABTM, MATHCADTM etc. 
 
Ao invés do cálculo da DFT diretamente pela definição, faz-se uso de um 
algoritmo conhecido como a FFT (Transformada Rápida de Fourier) que 
permite avaliar a DFT com menor esforço computacional. 
 
 
A FFT não é um tipo diferente de transformada e sim uma técnica 
que possibilita avaliar DFT de forma mais rápida e econômica. 
 
 
A FT não basta? Por que a DFT? 
 
 As potencialidades da análise espectral com base na Transformada de Fourier 
contínua são bem estabelecidas. Ainda que teoricamente atrativo, o cálculo prático do 
espectro via a transformada clássica (empregando propriedades ou soluções 
analíticas) não é comum. 
 
Vários sinais de interesse (como voz, vídeo etc.) não possuem expressões 
analíticas para descrevê-los. 
 
 
A maneira usual de lidar com sinais físicos é "calcular" a transformada 
através de um equipamento (Hardware): analisador de espectro. 
 
 
Este instrumento realiza o cálculo da Transformada de Fourier e exibe o 
resultado em tela. Entretanto, com o desenvolvimento de técnicas de 
Processamento de Sinais DSP (e Processadores em chip), a DFT aparece 
como uma solução prática cada vez mais atrativa. 
 
 
 
 
A redução acentuada no custo dos DSPs e o aumento da capacidade de 
processamento (e.g. milhões de MIPS- Mega Instruções Por Segundo), em conjunto 
com o aparecimento de novas técnicas eficientes para a avaliação de transformadas 
discretas (as ditas Transformadas Rápidas), vêm permitindo "operar" em tempo real 
com muitos sinais. 
 
Assim, as transformadas discretas vêm se firmando como ferramentas 
"por excelência" na análise espectral. 
 
O tamanho dos analisadores de espectro não pode ser comparado ao 
tamanho reduzido dos DSPs, que adicionalmente permitem operação em 
grande velocidade, viabilizando numerosas aplicações. 
f(t)
tensão
F(w) espectro
 
 
Aplicação do algoritmo FFT é ilustrada estimando-se um espectro de um 
pulso retangular amostrado a uma taxa de Ts-1= 1amostra/seg a partir da 
origem e empregando N=128 amostras no cálculo da DFT. 
Assim, as amostras são dadas por: 
x(k) = 1+ j0 para k = 1,2,...,29 
x(k) = 0+ j0 para k = 31,32,...,127 
x(0) = x(30) = 1/2+ j0. 
Naturalmente, as amplitudes teóricas do módulo da transformada valem: 
 
 X (nf Sa (n 30 / 128) , n = 0,1,2, ...,127 .s ) = 30 π 
 
A tabela exibe valores do módulo da transformada calculados segundo a 
expressão analítica e pela transformada discreta via FFT. 
 
Tabela I. DFT versus Fourier- Caso de um pulso. 
n DFT teórico n DFT teórico 
1 30.00 30.00 33 1.000 1.273 
2 27.36 27.36 34 0.705 0.915 
3 20.26 20.27 35 0.089 0.117 
4 10.89 10.91 36 0.514 0.693 
5 1.981 1.987 37 0.805 1.110 
6 4.168 4.189 38 0.669 0.944 
7 6.451 6.498 39 0.215 0.311 
8 5.210 5.262 40 0.301 0.447 
9 1.924 1.949 41 0.617 0.941 
10 1.500 1.525 42 0.596 0.936 
11 3.521 3.593 43 0.282 0.457 
12 3.505 3.593 44 0.137 0.230 
13 1.831 1.886 45 0.444 0.770 
14 0.444 0.460 46 0.498 0.896 
15 2.160 2.250 47 0.300 0.562 
16 2.589 2.713 48 0.022 0.042 
17 1.707 1.801 49 0.293 0.600 
18 0.107 0.118 50 0.385 0.830 
19 1.341 1.436 51 0.276 0.630 
20 1.965 2.121 52 0.048 0.117 
21 1.555 1.694 53 0.168 0.435 
22 0.429 0.471 54 0.268 0.746 
23 0.786 0.873 55 0.221 0.665 
24 1.487 1.668 56 0.075 0.249 
25 1.383 1.568 57 0.076 0.278 
26 0.607 0.697 58 0.157 0.646 
27 0.391 0.455 59 0.142 0.672 
28 1.100 1.294 60 0.063 0.355 
29 1.195 1.427 61 0.019 0.132 
30 0.691 0.837 62 0.059 0.536 
31 0.108 0.133 63 0.049 0.654 
32 0.778 0.974 64 0.016 0.434 
 
1281129680644832160
0
10
20
30
30 |Sa(x)|
|F(n)|
Espectro de um porta:
 FFT vs teórico
n
3
0
 
|
S
a
(
n
 
p
i
 
3
0
/
1
8
0
)
|
 
e
 
|
X
(
n
)
|
 
6456484032241680
.01
.1
1
10
100
30 |Sa(x)|
|F(n) |
n
E
s
p
e
c
t
r
o
 
Figura. Espectro discreto da função porta. 
 
Devido à presença de descontinuidades, o valor mostrado no instante t 
deve ser consistente com 
f(t) = 1/2 [ f(t +) + f(t -) ] 
de modo que a fórmula de inversão continue válida. 
 
Note-se que a DFT é simétrica em torno do ponto n=N/2. 
 
Isto se segue do fato que a parte real (resposta imaginária) da 
transformada de um sinal real é par (respectivamente ímpar). 
 
Assim, o resultado obtido para n>N/2 corresponde simplesmente às 
freqüências negativas. 
 
Claramente, as aproximações são mais pobres nas altas freqüências. 
 
Exercício 
Avaliar com auxílio de microcomputador a DFT do sinal h (t) = e u (t)
- t
 
tomando N=32 amostras e considerando o intervalo entre as amostras 
Ts=0,25 seg. (taxa de amostragem). No exemplo, assume-se h(0)=0,5. 
 
É fácil perceber novamente que as aproximações são bastante pobres nas altas 
freqüências. Para reduzir o erro, torna-se necessário um aumento de N e/ou 
uma diminuição de Ts. 
 
Supondo que a transformada discreta de Fourier é empregada na avaliação 
do espectro de sinais reais contínuos, são requeridas operações de: 
c discretização (amostragem), 
d truncamento e 
e periodicidade s/ sinal original. 
 
h(t) H(w)
t w
w
w
w
Sa(x)
t
t
t
t w
(a) Sinal original.
(b) Relógio amostrador
(c) Discretização
(d) função de truncamento
(e) Sinal truncado
w
t
(f) trem de periodização 
t
(g) Periodicidade.w 
Figura. Desenvolvimento da DFT: Discretização, truncamento e periodização. 
COMPLEXIDADE: 
ALGORITMOS COM ARQUITETURAS PARALELAS 
 
Formalmente, supõe-se que um algoritmo é implementado por intermédio de L 
máquinas seqüenciais interconectadas: S=(S1,S2,...,SL). 
 
Cada uma possui uma complexidade espacial X=(X1,X2,...,XL) e uma 
complexidade temporal T=(T1,T2,...,TL). 
 
O trabalho de cálculo W é definido pelo produto escalar destes vetores, 
∑
=
=•=
L
i
iiTXTXW
1
. Globalmente, a complexidade no espaço é ∑==
L
i
iXX
1
 e a 
complexidade no tempo é T:=MAX (Ti). 
 
 
Pode haver um compromisso entre complexidade temporal e espacial, 
nos algoritmos de implementação paralela. 
 
 
 
 
 
 
O esforço computacional pode ser definido como o número máximo de 
operações elementares necessárias para resolver o problema. No caso da 
DFT, pode-se tratar da complexidade multiplicativa e complexidade aditiva 
i.e., número de multiplicações ponto flutuante (respectivamente adições) 
necessárias para calculá-la. 
 
Tradicionalmente tem-se usado apenas a complexidade multiplicativa como 
o parâmetro mais importante. 
 
FFT- Transformada Rápida de Fourier 
(Cooley-Tukey base 2) 
 
A FFT foi implementada com o objetivo de diminuir complexidade (temporal) 
necessária para calcular uma DFT (Transformada Discreta de Fourier), visando 
aplicações em tempo real. 
 
O número de operações realizadas no cálculo da DFT através da 
definição é proporcional à N2, i.é., para cada dos N valores de u, a expansão 
de F(u) requer N multiplicações complexas de x(n) por Wux além de (N-1) 
adições dos resultados. 
 
Alguns dos termos podem ser computados uma vez e armazenados para serem 
usados em operações futuras. Logo tais multiplicações de x(n) não são consideradas 
na implementação. 
∑−
=
⋅=
1
0
)(1)(
N
x
ux
NWxfNuF Eq. 1 
 
Algumas decomposições apropriadas na Eq.1 podem tornar o número de 
multiplicações e adições proporcionais a N.Log2N. 
 
Este procedimento é denominado de Transformada Rápida de Fourier ou 
FFT (Fast Fourier Transform). 
 
N N2 (DFT) N.log2N (FFT) Vantagem
2 4 2 2 
4 16 8 2 
8 64 24 2,67 
16 256 64 4 
32 1024 160 6,4 
64 4096 384 10,67 
128 16384 896 18,29 
256 65536 2048 32 
512 262144 4068 56,89 
1024 1048576 10240 102,4 
2048 4194304 22528 186,18 
4096 16777216 49512 341,33 
8192 671088964 106496 630,15 
 
 
O Algoritmo FFT 
 
Por conveniência, a Eq. 1 pode ser rescrita sob a seguinte forma: 
∑−
=
⋅=
1
0
)(1)(
N
x
ux
NWxfNuF onde ]2exp[ NjWN
π⋅⋅−= . 
 
Assumindo que N é da forma: N=2n; em que n é inteiro positivo, então N pode 
ser expresso como: N=2*M; em que M é um inteiro positivo. 
 
Substituindo esta relação na Eq. 1 tem-se: 
∑−
=⋅=
12
0
2)(2
1)(
M
x
ux
MWxfMuF . 
 
Dividindo-se o somatório em duas partes, relativas aos índices pares e ímpares: 
 
⎥⎦
⎤⎢⎣
⎡ ++= +
−
=
−
=
∑∑ WW xuMM
x
xu
M
M
x
xf
M
xf
M
uF )12(2
1
0
)2(
2
1
0
)12(1)2(1
2
1)( Eq. 2 
 
 Como WW uxMuxM =22 , é possível rescrever a eq. 2 na forma: 
 
⎥⎦
⎤⎢⎣
⎡ ++= ∑∑ −
=
−
=
WWW umxuM
M
x
ux
M
M
x
xf
M
xf
M
uF
2
)2(
2
1
0
1
0
)12(1)2(1
2
1)( Eq. 3 
 
 
 
 
Agora considerando as seguintes DFTs: 
 
WuxM
M
x
even xf
M
uF ∑−
=
=
1
0
)2(1)( 
 
WuxM
M
x
odd xf
M
uF ∑−
=
+=
1
0
)12(1)( ; para u=0,1,2,....,M-1. 
 
 
 
 
 
Chega-se a uma relação que decompõe a DFT F(u) de comprimento 2M 
em duas DFTs Feven(u) e Fodd(u), ambas de comprimento M: 
 
[ ]WuModdeven uFuFuF 2)()(21)( += Eq. 4 
 
Observa-se também: WW uMMuM =+ e WW uMMuM 22 −=+ , de modo que segue-se da eq.3, 
 
[ ]WuModdeven uFuFMuF 2)()(21)( −=+ Eq. 5 
 
 
Uma transformada de comprimento N pode ser computada dividindo a 
expressão original em duas partes, como indicado. 
 
Número de Operações 
 
Por indução, o número de multiplicações complexas a adições requeridas na 
implementação do algoritmo FFT é, respectivamente: 
NNnm 2log
2
1)( = 
e : 
NNna 2log)( = 
 
 
Implementação da FFT 
 
O principal ponto das implementações diz respeito ao arranjo dos dados de 
entrada visando à aplicação da divisão de uma transformada em termos de 
outras de menor comprimento. 
 
O procedimento de reordenação pode ser ilustrado através de um exemplo 
simples (N=8). 
 
 
 
 
Entrada {f(0), f(1), f(2), f(3), f(4), f(5), f(6), f(7)}. 
 
Separando as amostras de argumentos pares e ímpares: 
 
Pares {f(0), f(2), f(4), f(6)}. 
Ímpares {f(1), f(3), f(5), f(7)}. 
 
 
 
 
 
 
Contudo, para reaplicar o procedimento, as componentes pares e ímpares 
devem ser novamente separadas: 
 
Pares {f(0), f(4)}. {f(1), f(5)}. 
 
Ímpares {f(2), f(6)}. {f(3), f(7)}. 
 
 
 
 
 
 
REARRANJO: 
Entrada {f(0), f(1), f(2), f(3), f(4), f(5), f(6), f(7)}. 
 
{f(0), f(4), f(2), f(6), f(1), f(5), f(3), f(7)}. 
 
Reordenação do arranjo e leitura inversa de bits 
Numeração 
original 
Arranjo 
original
Numeração 
bits invertidos 
Arranjo 
reordenado
0 0 0 f(0) 0 0 0 f(0) 
0 0 1 f(1) 1 0 0 f(4) 
0 1 0 f(2) 0 1 0 f(2) 
0 1 1 f(3) 1 1 0 f(6) 
1 0 0 f(4) 0 0 1 f(1) 
1 0 1 f(5) 1 0 1 f(5) 
1 1 0 f(6) 0 1 1 f(3) 
1 1 1 f(7) 1 1 1 f(7) 
A existência de algoritmos rápidos é um fator decisivo nas inúmeras 
aplicações em tempo real da DFT. 
Devido ao algoritmo Cooley-Tukey base 2, freqüentemente usam-se 
comprimentos que são potência de 2. 
Uma curta tabela com uma cota inferior na complexidade para determinar 
uma DFT de comprimento N, denotada µ(DFT(N), é mostrada. 
 
N µ(DFT(N) N µ(DFT(N) 
4 0 120 120 
8 2 240 274 
12 4 720 986 
24 12 ... ... 
48 38 65520 108594 
60 56 ... ...