A Transformada de Fourier Discreta
 A DTFT transforma um sinal discreto num sinal continuo. No
entanto o sinal continuo não pode ser processado numa maquina
digital, PC, DSP…
 Solução: DFT
 Corresponde a amostragem da DTFT, ou seja a calcular a DTFT
num conjunto finito de pontos:

H[k]=H(ej) para  = 2 k/N
A amostragem no domínio da frequência é equivalente á formação de
réplicas no domínio do tempo, o que conduz á série de fourier discreta.
1
A Transformada de Fourier
Discreta
 Existe uma correspondência entre sequências
finitas e sequências periódicas

A Transformada de Fourier Discreta de uma sequência finita,
corresponde à Transformada de Fourier da Sequência
periódica obtida por repetição da sequência finita
x[n],
0  n  N 1
~
~
~
x [n]  x [n  N ]
x[n]  
cc
 0,
Série de Fourier
(DFS)
Transformada
de Fourier
Discreta (DFT)
Transformada de
Fourier (DTFT)
2
A Série de Fourier Discreta (DFS)
~
x [n] periódicode periodoN
~ j
X (e ) 
Com:
2 ~
2 k 

X
[
k
]






N 

k  N

N 1
~
X [k ]   ~
x [n]WNk n
WN  e  j ( 2 / N )
n0
3
A Série de Fourier Discreta (DFS)
1
~
x [ n] 
N
N 1
~
k n
X
[
k
]
W

N
k 0
N 1
~
X [k ]   ~
x [n]WNk n
n0
WN  e
 j ( 2 / N )
~
DFS
~
x [ n] 
 X [ k ]
Série de Fourier
Discreta Inversa
Série de Fourier
Discreta
~
x [n]  ~
x [n  N ]
DFS – Discrete Fourier Series
4
Relações da Série de Fourier
Transformada de Fourier do
sinal periódico
~ j
X (e ) 


k 
Temos ainda
2 ~
2 k 

X [k ]  

N
N 

Relações entre
a Série de
Fourier
Discreta e a
Transformada
de Fourier
Transformada de Fourier do
sinal finito
j
X (e )  x[n]
TF

  
~
j ( 2 / N ) k
j
X [k ]  X e
X e
x[n],
0  n  N 1
~
x[n]  
cc
 0,
Amostras do
espectro do sinal
 ( 2 / N ) k
5
Relações com a Série de Fourier
1
1
0.5
0
0
-0.5
-1
-1
0
5
10
15
20
DFT
25
30
DTFT
20
40
60
80
100
20
40
60
80
100
120
140
40
20
8
0
6
120
140
4
2
0
0
2
4
6
8
10
12
14
6
Frequências negativas
1
8
0.5
6
0
4
-0.5
2
-1
0
5
10
15
20
25
30
0
X[k] = X[N-k]
0
2
4
6
6
4
2
0
-2
10
12
14
Valores de k
maiores que
N/2 são
equivalentes a
k negativos
8
-4
8
0
2
4
6
7
Propriedades da Série de Fourier
Discreta
8
Propriedades da Série de Fourier
Discreta
9
A Transformada de Fourier
Discreta (DFT)
vector
N 1
X [k ]   x[n]WNk n
n 0
1
x[n] 
N
N 1
 X [k ] W
k 0
k n
N
WN  e  j ( 2 / N )
DFT- Discrete Fourier Transform
Matriz
(dois índices)
A matriz é Otonormal á
parte do factor 1/N,
sendo a inversa dada
pelo matriz transposta,
W-knN
x[n],
~
x[n]  
 0,
~

 X [k ],
X [k ]  

 0,
0  n  N 1
cc
0  k  N 1
cc
DFT
x[n] 
 X [ k ]
10
A Transformada de Fourier Discreta
(DFT)
A DFT corresponde a
representação de x[n] numa base
diferente, sendo sempre possível
recuperar o sinal original.
x[n]  IDFTDFTx[n]
1
N
 N 1
ln 
k n
x
[
n
]
W
W





N
N
k 0  l 0

N 1
1
x[n]
N
N 1
e
j
2
( k l ) n
N

k ,l  0
1 N 1
x[n] 1 
N k 0
1
x[n] N  x[n]
N
11
Convolução Periódica (circular)
 Convolução periódica
~
~
DFS
~
x1[n] * x2[n] 
 X1[k ] X 2[k ]
A convolução no tempo só
corresponde a multiplicação
na frequência para a DFS.
Para a DFT temos de utilizar
a convolução circular.
 Convolução circular
DFT
x1[n] *circular( N ) x2[n] 
 X1[k ] X 2[k ]
N 1
x1[n] *circular ( N ) x2 [n]  x1[n] O x2 [n]   x1[m]x2 [(( n  m)) N ]
N
m0
(( n)) N  n moduloM  resto da divisãode n por M
A convolução circular é comutativa.
12
Aproximando a DTFT através da
DFT
1
1
0.5
0.5
0
0
Extensão
com zeros -0.5
-0.5
-1
0
5
10
15
20
25
-1
0
30
50
100
150
DFT
8
6
6
4
4
2
2
1
2
3
4
5
250
DFT
8
0
0
200
6
0
0
1
2
3
4
5
6
13
Aproximando a Transformada de
Fourier através da DFT
1
0.5
0
8
-0.5
6
-1
0
5
10
15
20
25
Período de amostragem
T=1/Fa
30
4
2
0
0
1
2
3
4
5
6
Resolução na frequência = 1/(NT)
Comprimento da DFT
NT
Banda de frequências
0 a Fa/2
14
DFT de uma sinusóide
1
1
0
0
-1
0
5
10
15
20
-1
0
15
6
10
4
5
2
0
0
5
10
15
20
0
0
5
5
10
10
15
15
20
20
A sinusóide tem de ser sempre truncada por uma janela
mesmo que seja a janela rectangular.
O espectro não é exactamente uma dirac… Com uma
janela que não a rectangular o espectro melhora….
15
Convolução Periódica (circular)
N 1
~
~
~
N x [ n] 
x1[n] 
x
[
m
]
x
[
n

m
]

x
[
n
]
*
x2 [n] para 0  n  N
1 2
2
1
x1[n]* ~
x2 [n] 

m 0

 x [n]* ( x [n] * [n  k N ]) 
k - 
1
2

 ( x [n]* x [n]) * [n  k N ]   zn  k N  com zn  x [n]* x [n]
k - 
1
2
k - 
1
2
DCT = DTFT Amostrada
aliasing no tempo
16
Convolução Periódica
(aliasing no tempo)
1
N x [ n] 
x1[n] 
2
0.5
0
-10
1
-5
0
5
10
15
20
z[n+N]
-5
0
5
10
15
20
z[n-N]
0.5
0
-10
2
-5
0
5
10
15
20
resultado
1
0
-10
 zn  k N 
k - 
z[n] com zn  x1[n]* x2 [n]
0.5
0
-10
1

O produto do
domínio da
DFT é
equivalente á
convolução
no domínio
do tempo
com aliasing
N=10
-5
0
5
10
15
20
17
Convolução Periódica
 [ n  1] O x2 [ n]
N
N 1
x1[n] O x2 [n]   x1[m]x2 [(( n  m)) N ]
N
m0
Um atraso corresponde a rodar
a sequência!
18
Goertzel Algorithm
N 1
X [k ]   x[r ]W
kr
N
r 0
N 1
  x[r ]WNk ( N r )
r 0

yk [n]   x[r ]WNk ( N r ) u[n  r ] com X [k ]  yk [n] n N
r 0
Notar que:
x[n]=0 para
n<0
H k [ z] 
1
1  WNk z 1
1  WNk z 1
H k [ z] 
1  2 cos(2 k / N ) z 1  z 2
19
A Transformada Rápida de Fourier
(FFT)
 Fast Fourier Transform (FFT)
 É uma algoritmo computacionalmente
eficiente para o cálculo da DFT
N 1
DFT:
X [k ]   x(n)W
n0
FFT
kn
N
Requer N^2
multiplicações
N/2 log2N
multiplicações
20
Principio Básico da FFT

A DFT de um vector de dimensão N pode ser
calculada à custa de duas DFT de dimensão N/2
N 1
X [k ]   x[n]WNk n 
n 0
X [k ] 
kn
x
[
n
]
W

N 
n par
n impar
N /2
X [k ]   x[2r ]W
r 0
k 2r
N
W
kr
N /2
W
N /2
X [k ]   x[2r ]W
r 0
kn
x
[
n
]
W

N 
N /2
k
N
k 2r
x
[
2
r

1
]
W


N
r 0
N /2
k
N
 x[2r  1]W
r 0
kr
N /2

X [k ]  DFT[ x[2r ]]  WNk DFT[ x[2r  1]]
21
Grapho de uma FFT
Butterfly
FFT
N log2 N  8 * 3  24
multiplicações
DFT
N 2  64
x[n]
X[k]
multiplicações
22
Butterfly
x
x
Estágio
m-1
y
W
Estágio
m
-1
r
N
y
Permite que os cálculos sejam
Efectuados no local (in place),
Necessita apenas de uma variavel auxiliar:
aux = WNr y
y=x-aux
x=x+aux
( r  N / 2)
N
W
 W
Redução do peso
computacional para
N/2 log(N)
r
N
23
Efeito do Ruído de Quantificação
(virgula fixa)
 Cada valor é calculado através de N-1
Butterflys
 Em cada Butterfly há um
arredondamento (o erro é b)
Ruído no resultado (pior caso):
(N-1)b
Ruído no resultado assumindo sinais de
ruído independentes:
  ( N 1)
2
R
 B2  4 a2
 a2 

12
2
2
B
  2 B
1 Multiplicação Complexa =
4 Multiplicações reais
 B2  4 a2
24
Efeito do Ruído de Quantificação
 Para prevenir a saturação no pior caso do resultado devemos ter a
componente real e complexa de x[n] menor que 1/N ou seja:



1
1
1
2
 x[n] 
 E x[n] 
  x2
2
3N
2N
2N
E[ X [k ]2 ]  N  x2 
1
3N
N – Dimensão da FFT
B – Numero de bits de para
representação dos números
E[ F[k ]2 ]  N  B2
E[ F[k ]2 ]
2
2
2 2 B

3
N


N
2
B
2
E[ X [k ] ]
Ou seja duplicar N implica perder um
bit de relação sinal ruído
Adicionando um escalamento de ½ às
butterflys da FFT reduz a relação ruído
sinal (N/S) para:
E[ F[k ]2 ]
2 B

4
N
2
E[ X [k ]2 ]
Para processadores de virgula flutuante:
Sinais de banda larga: 4N2-2B
Sinais sinusoidais: 4 log2N 2-2B
25
Ordenação de bits Invertidos
 1ª divisão


Xx0 (pares)
Xx1 (impares)
 2ª divisão




X00
X10
X01
X11
 3ª divisão








000
100
010
110
001
101
011
111
Corresponde à
ordenação
tradicional mas
com bits
invertidos!!
A reordenação pode ser
efectuada “in place”
26
Twiddle factors
 Necessários para o cálculo das butterflys
 Calculo


W
r
N
Off-line e armazenados numa tabela
Iterativo: (pode ser efectuado com maior precisão)
WNr+1 = WN WNr

Imediato:
W r  e j (2 r / N )  cos(2 r / N )  sin(2 r / N ) i
N
27
Outras Implementações
 Decimação na frequência


Os coeficientes estão ordenados no tempo, e em ordem de bits invertidos
na frequência!
Não necessita de Bit_reversed_addressing para implementar a convolução
com a FFT.
 Outras bases que não a dois!


Permite FFT de dimensão que não são potência de dois (sem extensão com
zeros)
Pode conduzir a um menor ruído de quantificação
 Implementações com ordem directa na entrada e na saída

Não permite computação no local
28
Implementação
 Blocos: corresponde ao cálculo de uma
DFT de dimensão inferior
Um loop externo para os diferentes estágios
 Tamanho do bloco começa por ser dois e
duplica para cada novo estádio.
 Loop interno para diferentes blocos


Cálculo de half_block_size Butterflys
Os coeficientes das butterflys estão espaçados de
half_block_size
29
Implementação da Convolução
Linear com a FFT
convolução
Série de
Fourier
Discreta
A convolução de
uma sequência de
dimensão L por
uma de dimensão
N resulta numa
sequência de
dimensão L+N-1
30
Implementação da Convolução
Linear com a FFT
 Pretendemos obter a convolução de
x[n] com y[n], 0  n < N
 Estende-se x[n] e y[n] com N zeros
 xe[n] = [x[n], 0 ... 0], ye[n] = [y[n], 0 ... 0]
 Efectua-se a convolução circular de xe[n] com ye [n]
#N
#(N+M-1)
x[n]
Adicionar zeros
FFT
X
#M
y[n]
Adicionar zeros
IFFT
x[n]*y[n]
FFT
Aplicações: Overlap and Add e Overlap and Save
31
Overlap and SAVE / Overlap and
ADD
 Implementação de filtros FIR, por
blocos usando a FFT.
 Implementação de convolução de
dois vectores de sinais (x[n] e h[n])
com um dos vectores (x[n]) muito
maior que outro (h[n]).
 Solução: dividir x[n] em blocos:
X(i)
X(i-1)
x[n] 
X(i-2)
X(i-3)

X(i-4)
 x [n  N i ]
i  
i
X(i-5)
 Overlap and SAVE

Implementar a convolução
circular de dois blocos do sinal
de dados com a resposta ao
impulso….
 Overlap and ADD

Implementar a convolução de
um bloco do sinal de dados com
a resposta ao impulso. Somar
resultados de outros blocos.
Desvantagem: atraso na saída
32
Overlap and Add
x0[n]
convolução
x1[n]
x2[n]
x3[n]
x4[n]
Convolução linear
implementada com a
FFT
h[n]
x0[n]*h[n]
x1[n]*h[n]
x2[n]*h[n]
Add
y0[n]
y1[n]
y2[n]
y3[n]
y4[n]
33
Overlap and Save
x0[n]
convolução
Bloco
errado
x1[n]
h[n]
x2[n]
x3[n]
x4[n]
Convolução circular
implementada com a
FFT
aliasing
(x0[n]|x1[n])*h[n]
(x1[n]|x2[n])*h[n]
Bloco
correcto
y0[n]
(x2[n]|x3[n])*h[n]
Save
y1[n]
y2[n]
y3[n]
y4[n]
34