1

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.

2

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)

3

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

4

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

5

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

6

Relações com a Série de Fourier

0 5 10 15 20 25 30-1

-0.5

0

0.5

1

DTFTDFT

0 2 4 6 8 10 12 140

2

4

6

8

20 40 60 80 100 120 140-1

0

1

20 40 60 80 100 120 140

0

20

40

7

Frequências negativas

0 2 4 6 8 10 12 140

2

4

6

8

0 2 4 60

2

4

6

8

-2-4

Valores de k maiores que

N/2 são equivalentes a

k negativos

X[k] = X[N-k]

0 5 10 15 20 25 30

-1

-0.5

0

0.5

1

8

Propriedades da SérieSérie de Fourier Discreta

9

Propriedades da SérieSérie de Fourier Discreta

10

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 A matriz é Otonormal á parte do factor 1/N, sendo a inversa dada

pelo matriz transposta, W-kn

N

11

A Transformada de Fourier Discreta (DFT)

][1

][

11

][

1][

][1

1

0

1

0,

)(2

1

0

1

0

nxNN

nx

Nnx

eN

nx

WWnxN

N

k

N

lk

nlkNj

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.

12

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

13

Aproximando a DTFT através da DFT

Extensão com zeros

DFT DFT

0 1 2 3 4 5 60

2

4

6

8

0 1 2 3 4 5 60

2

4

6

8

0 5 10 15 20 25 30

-1

-0.5

0

0.5

1

0 50 100 150 200 250-1

-0.5

0

0.5

1

14

Aproximando a Transformada de Fourier através da DFT

0 1 2 3 4 5 60

2

4

6

8

0 5 10 15 20 25 30

-1

-0.5

0

0.5

1

Período de amostragemT=1/Fa

Comprimento da DFT NT

Resolução na frequência = 1/(NT)

Banda de frequências0 a Fa/2

15

DFT de uma sinusóide

0 5 10 15 200

5

10

15

0 5 10 15 20-1

0

1

0 5 10 15 20-1

0

1

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….

0 5 10 15 200

2

4

6

16

Convolução Periódica (circular)

NnnxnxmnxmxnxnxN

m

N

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

0212121

])[*][(*][ ][~*][-k

2121

Nknnxnxnxnx

DCT = DTFT Amostrada

aliasing no tempo

][*][ com ][*])[*][( 21-k-k

21 nxnxnzNknzNknnxnx

17

-10 -5 0 5 10 15 200

0.5

1

-10 -5 0 5 10 15 200

0.5

1

-10 -5 0 5 10 15 200

0.5

1

-10 -5 0 5 10 15 200

1

2

Convolução Periódica (aliasing no tempo)

][*][ com

][][

21

-k21

nxnxnz

Nknznxnx N

O produto do domínio da

DFT é equivalente á convolução no domínio do tempo

com aliasing

z[n]

z[n-N]

z[n+N]

resultado

N=10N=10

18

Convolução Periódica

][O]1[ 2N nxn

1

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

N

mNmnxmxnxnx

Um atraso corresponde a rodarrodar a sequência!

19

Goertzel Algorithm

Nnkr

rNkNk

N

r

rNkN

N

r

rkN

nykXrnuWrxny

WrxWrxkX

][][ com ][][][

][][][

0

)(

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

20

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/2 logN/2 log22NN

multiplicações

21

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

22

Grapho de uma FFT

Butterfly

çõesmultiplica

243*8log2 NN

x[n] X[k]

FFT

DFT

çõesmultiplica

642 N

23

Butterfly

rNW

rN

NrN WW )2/(

-1

Estágiom-1

Estágiom

Redução do peso computacional para

N/2 log(N)

Permite que os cálculos sejamEfectuados no local (in place),

Necessita apenas de uma variavel auxiliar:aux = WN

r yy=x-auxx=x+aux

x

y

x

y

24

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 reais22 4 aB

25

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:

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

N – Dimensão da FFT

B – Numero de bits de para representação dos números

26

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”

27

Twiddle factors

Necessários para o cálculo das butterflys

Calculo Off-line e armazenados numa tabela Iterativo: (pode ser efectuado com maior precisão)

WNr+1 = WN

WNr

Imediato:

rNW

iNrNreW Nrjr

N)/2sin()/2cos()/2(

28

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

29

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

30

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

31

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

32

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

33

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

34

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