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)
1
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
2
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
3
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[n],
~
x[n]  
 0,
X (e )  x[n]
TF

  
~
X [k ]  X e j (2 / N )k  X e j
 ( 2 / N ) k
0  n  N 1
cc
Amostras do
espectro do sinal
4
Propriedades da Série de Fourier
Discreta
5
Propriedades da Série de Fourier
Discreta
6
A Transformada de Fourier
Discreta (DFT)
vector
N 1
X [k ]   x[n]WNk n
n 0
1
x[n] 
N
N 1
k n
X
[
k
]
W

N
k 0
Matriz
(dois índices)
x[n],
~
x[n]  
 0,
~

 X [k ],
X [k ]  

 0,
WN  e  j ( 2 / N )
0  n  N 1
cc
0  k  N 1
cc
DFT
x[n] 
 X [ k ]
DFT- Discrete Fourier Transform
7
A Transformada de Fourier Discreta
(DFT)
x[n]  IDFTDFTx[n]
1
N
A DFT corresponde a
representação de x[n]
numa base diferente,
sendo sempre possível
recuperar o sinal original.
 N 1
ln 
k n
x
[
l
]
W
W





N
N
k 0  l 0

N 1
N 1
1
N
k ,l  0
1
N
 N 1 j 2 ( l  n ) k 
x[l ]  e


l 0
 k 0

1
N
j 2 ( l  n ) k
x
[
l
]
e


N 1
N 1
 x[l ] n  l   x[n]
l 0
8
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.
9
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
m 0
x1[n]* ~
x2 [n] 

 x [n]* x [n]* [n  k N ]
k - 
1
2
DCT = DTFT Amostrada
aliasing no tempo
10
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!
11
Goertzel Algorithm
N 1
N 1
X [k ]   x[r ]W
r 0
y k [ n] 

kr
N
 x[r ]W
r  
  x[r ]WNk ( N r )
r 0
k ( N r )
N
u[n  r ] com X [k ]  yk [n] n N
H k [ z] 
Notar que:
x[n]=0 para
n<0
1
1  WNk z 1
1  WNk z 1
H k [ z] 
1  2 cos(2 k / N ) z 1  z 2
12
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 log2N
multiplicações
13
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
X [k ]  DFT[ x[2r ]]  WNk DFT[ x[2r  1]]
kr
N /2

14
Grapho de uma FFT
Butterfly
FFT
N log2 N  8 * 3  24
multiplicações
DFT
N 2  64
x[n]
X[k]
multiplicações
15
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:
 R2  ( N 1) B2
  4
2
B
2
a
2
2
a 
12
2
B
1 Multiplicação Complexa =
4 Multiplicações reais
16
Efeito do Ruído de Quantificação
 Para prevenir a saturação no pior caso do resultado devemos 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
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
17
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”
18
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 permitem computação no local
19
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
20
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
21
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
22
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
23
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]
24
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]
25