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

][~][~ Nnxnx

Série de Fourier

(DFS)

cc

Nnnxnx

,0

10],[~][

Transformada de Fourier (DTFT)

Transformada de Fourier Discreta (DFT)

2

A SérieSérie de Fourier Discreta (DFS)

N

kkX

NeX

k

j 2][

~2)(

~

nkN

N

n

WnxkX

1

0

][~][~

N periodo de periódico ][~ nx

Com: )/2( NjN eW

3

A SérieSérie de Fourier Discreta (DFS)

nkN

N

k

WkXN

nx

1

0

][~1

][~

nkN

N

n

WnxkX

1

0

][~][~

Série de Fourier Discreta Inversa

Série de Fourier Discreta

)/2( NjN eW

][~

][~ kXnx DFS

][~][~ Nnxnx

DFS – Discrete Fourier Series

4

Relações da Série de Fourier

N

kkX

NeX

k

j 2][

~2)(

~

Relações entre a Série de Fourier

Discreta e a Transformada

de FourierTemos ainda

][)( nxeX TFj

cc

Nnnxnx

,0

10],[~][

Transformada de Fourier do sinal periódico

Transformada de Fourier do sinal finito

kN

jkNj eXeXkX)/2(

)/2(][~

Amostras do espectro do sinal

5

Propriedades da SérieSérie de Fourier Discreta

6

Propriedades da SérieSérie de Fourier Discreta

7

A Transformada de Fourier Discreta (DFT)

nkN

N

k

WkXN

nx

1

0

][1

][

nkN

N

n

WnxkX

1

0

][][

)/2( NjN eW

][][ kXnx DFT

cc

Nnnxnx

,0

10],[~][

cc

NkkXkX

,0

10],[~

][

DFT- Discrete Fourier Transform

Matriz(dois índices)

vector

8

A Transformada de Fourier Discreta (DFT)

][][1

][1

][1

][1

1

0

1

0

)(21

0

)(21

0,

1

0

1

0

nxlnlxN

elxN

elxN

WWlxN

N

l

N

k

knljN

l

knljN

lk

nkN

N

k

nlN

N

l

][][ nxDFTIDFTnx

A DFT corresponde a representação de x[n] numa base diferente, sendo sempre possível

recuperar o sinal original.

9

Convolução Periódica (circular)

Convolução periódica][

~][

~][~*][ 2121 kXkXnxnx DFS

][][][*][ 212)(1 kXkXnxnx DFTNcircular

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.

1

021212)(1 ]))[((][][O][][*][ N

N

mNNcircular mnxmxnxnxnxnx

Mpor n de divisão da restoM modulo ))(( nn N

A convolução circular é comutativa.

Convolução circular

10

Convolução Periódica (circular)

NnnxnxmnxmxnxnxN

m

N

0 para ][~*][][~][~][][1

0212121

-k

2121 ][*][*][ ][~*][ Nknnxnxnxnx

DCT = DTFT Amostrada

aliasing no tempo

11

Convolução Periódica

][O]1[ 2N nxn

1

02121 ]))[((][][O][ N

N

mNmnxmxnxnx

Um atraso corresponde a rodarrodar a sequência!

12

Goertzel Algorithm

Nnkr

rNkNk

N

r

rNkN

N

r

rkN

nykXrnuWrxny

WrxWrxkX

][][ com ][][][

][][][

)(

1

0

)(1

0

11

1][

zWzH

kN

k

21

1

)/2cos(21

1][

zzNk

zWzH

kN

k

Notar que:

x[n]=0 para

n<0

13

A Transformada Rápida de Fourier (FFT)

nkN

N

n

WnxkX

1

0

)(][Requer N^2N^2 multiplicações

Fast Fourier Transform (FFT)É uma algoritmo computacionalmente

eficiente para o cálculo da DFT

DFT:DFT:

FFTFFT N logN log22NN

multiplicações

14

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

]]12[[DFT]]2[[DFT][

]12[]2[][

]12[]2[][

][][][

][][

2/

2/

02/

2/

0

22/

0

22/

0

impar

1

0

rxWrxkX

WrxWWrxkX

WrxWWrxkX

WnxWnxkX

WnxkX

kN

rkN

N

r

kN

rkN

N

r

rkN

N

r

kN

rkN

N

r

nkN

n

nkN

parn

nkN

N

n

15

Grapho de uma FFT

Butterfly

çõesmultiplica

243*8log2 NN

x[n] X[k]

FFT

DFT

çõesmultiplica

642 N

16

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:

12

22 a

22 4 aB B 2

22 )1( BR N 1 Multiplicação Complexa =

4 Multiplicações reais

17

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:

22

2

3

1][

2

1][

2

1xN

nxEN

nxN

NNkXE x 3

1]][[ 22 22 ]][[ BNkFE

BB NN

kXE

kFE 22222

2

23]][[

]][[ 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:

BNkXE

kFE 22

2

24]][[

]][[

Para processadores de virgula flutuante:

Sinais de banda larga: 4N2-2B Sinais sinusoidais: 4 log2N 2-2B

18

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”

19

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

20

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

21

Implementação da Convolução Linear com a FFT

Série de Fourier Discreta

convolução

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

22

Implementação da Convolução Linear com a FFT

Pretendemos obter a convolução dex[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]

Adicionar zeros

Adicionar zeros

x[n]

y[n]

FFT

FFT

X IFFT x[n]*y[n]

#N

#M

#(N+M-1)

Aplicações: Overlap and Add e Overlap and Save

23

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:

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.

i

i iNnxnx ][][

X(i) X(i-1) X(i-2) X(i-3) X(i-4) X(i-5)

Desvantagem: atraso na saída

24

Overlap and Add

x0[n] x1[n] x2[n] x3[n] x4[n]

h[n]convolução

x0[n]*h[n]

x1[n]*h[n]

x2[n]*h[n]

y0[n] y1[n] y2[n] y3[n] y4[n]

Add

Convolução linear implementada com a

FFT

25

Overlap and Save

x0[n] x1[n] x2[n] x3[n] x4[n]

h[n]convolução

(x0[n]|x1[n])*h[n]

y0[n] y1[n] y2[n] y3[n] y4[n]

Save

(x1[n]|x2[n])*h[n]

(x2[n]|x3[n])*h[n]

aliasing

Bloco errado

Bloco correcto

Convolução circular implementada com a

FFT