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 ) n0 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 n0 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] IDFTDFTx[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 m0 (( 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 m0 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 ]WNk ( 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 WNk 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 n0 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