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.
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 Transformada de Fourier Discreta (DFT) Série de Fourier (DFS) Transformada de Fourier (DTFT)
vector A matriz é Otonormal á parte do factor 1/N, sendo a inversa dada pelo matriz transposta, W-knN Matriz (dois índices) DFT- Discrete Fourier Transform
A DFT corresponde a representação de x[n] numa base diferente, sendo sempre possível recuperar o sinal original.
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 A convolução circular é comutativa.
5 10 15 20 25 30 -1 -0.5 0.5 1 1 2 3 4 5 6 8 Período de amostragem T=1/Fa Resolução na frequência = 1/(NT) Comprimento da DFT NT Banda de frequências 0 a Fa/2
15 DFT de uma sinusóide 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….
z[n] O produto do domínio da DFT é equivalente á convolução no domínio do tempo com aliasing z[n+N] z[n-N] resultado N=10
Fast Fourier Transform (FFT) É uma algoritmo computacionalmente eficiente para o cálculo da DFT Requer N^2 multiplicações DFT: N/2 log2N multiplicações FFT
Butterfly x x Estágio m-1 Estágio m y y -1 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 Redução do peso computacional para N/2 log(N)
(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: 1 Multiplicação Complexa = 4 Multiplicações reais
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: N – Dimensão da FFT B – Numero de bits de para representação dos números 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: Para processadores de virgula flutuante: Sinais de banda larga: 4N2-2B Sinais sinusoidais: 4 log2N 2-2B
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”
Off-line e armazenados numa tabela Iterativo: (pode ser efectuado com maior precisão) WNr+1 = WN WNr Imediato:
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
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
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. Desvantagem: atraso na saída