Processamento Digital de Sinais - Notas de Aula sobre DFS e DFT

Processamento Digital de Sinais Notas de Aula Série e Transformada Discreta de Fourier DFS DFT Ricardo Tokio Higuti Departamento de Engenharia Elétrica FEIS Unesp Observação Estas notas de aula estão baseadas no livro DiscreteTime Signal Processing AV Oppenheim and RW Schafer Prentice Hall 19891999 Transformadas para sinais de tempo discreto DTFT Xejomegasumninftyinftyxnejomega n É uma transformada da variável contínua omega Usada para sinais de duração finitainfinita Não pode ser implementada de maneira exata num computador Uso de outras ferramentas matemáticas que a aproximam DFT Aplicada a sinais de tempo discreto de duração finita O resultado é um sinal de frequência discreta e de duração finita Pode ser implementada de maneira exata num computador É uma aproximação da DTFT Existem algoritmos eficientes para seu cálculo FFT Fast Fourier Transform Está relacionada com sinais periódicos DFS Discrete Fourier Series Aplicações Análise espectral de sinais resposta em frequência Implementação de SLITs Série Discreta de Fourier DFS Seja um sinal de tempo discreto periódico com período N que obedece a ildexn ildexnrN r N inteiros em que definese a frequência fundamental do sinal por omega0 frac2piN Analogamente ao caso de tempo contínuo este sinal também pode ser representado por uma série composta por uma soma de exponenciais complexas de tempo discreto cujas frequências são múltiplas da frequência fundamental ildexn sumk frac ildeXkN ej frac2piN kn Devido à periodicidade das frequências das exponenciais complexas há apenas N frequências distintas ek n ej frac2piN kn Para k inteiro ficase com as exponenciais e0 n e1 n eN1 n Quando k N temse eN n ej frac2piN N n ej 2 pi n 1 e0 n De forma análoga eN1 n e1 n e assim por diante Série Discreta de Fourier DFS Portanto há apenas N diferentes frequências omegak frac2piN k para k0 1 2 cdots N1 e portanto a série fica ildexnfrac1N sumk0N1 ildeXk ej frac2piNkn frac1N sumk0N1 ildeXk ej frac2piN kn Os valores ildeXk são os coeficientes da série discreta de Fourier DFS que representam a contribuição de cada componente de frequência 2pi k N na composição do sinal periódico Os coeficientes são obtidos por ildeXk sumn0N1 ildexn ej frac2piN kn infty k infty Chagandose ao par transformado ildexn xleftrightarrowDFS ildeXk Observações ildeXk é de frequência discreta Para cada k há uma frequência 2 pi k N ildeXk é periódico com N ildeXkN ildeXk por isso basta observar seus valores no intervalo entre 0 e N1 Relação entre a DFS e a DTFT Seja um sinal periódico de tempo discreto xn com período N Tomandose um período desse sinal ficase com o sinal xn xn xn 0 n N 1 0 caso contrário A DTFT de xn é Xejω n xnejωn n0N1 xnejωn E a DFS de xn Xk n0N1 xnej2πNkn k Comparando as equações temse que a DFS e a DTFT nessas condições estão relacionadas por Xk Xejωω2πN k k Ou seja a DFS é composta por amostras da DTFT em pontos equiespaçados de 2πN Exemplo DFS Calcule a DFS da sequência ildexnA cos pi n2 Inicialmente verificase que a sequência é periódica com período N4 e valores A 0 A 0 em um período 0 leq n leq 3 Portanto a os coeficientes da DFS são ildeXk sumn0N1 ildexn ej frac2piN kn A 1 ej frac3 pi4 2k Com valores ildeX0A1ej pi 00 ildeX1A1ej pi 12A ildeX2A1ej pi 20 ildeX3A1ej pi 32A e percebese que ildeX4 ildeX0 e assim por diante Exemplo xn 1 1 1 1 1 0 0 N7 L5 Xejω n04 ejωn ej2ω sin5ω2sinω2 Xk n04 ej2π7n ej4π7k sin5πk7sinπk7 Exemplo DFS cont Outra forma de verificar o resultado é reescrevendo a sequência ildexn em termos de exponenciais complexas ildexn A cos pi n2 fracA2 ej fracpi2 n fracA2 ej fracpi2n fracA2 ej frac2pi4 n fracA2 ej frac2pi4 n Devese notar que ej frac2piNkn ej frac2piN Nkn e portanto ildexn pode ser escrito como ildexn fracA2 ej frac2pi4 n fracA2 ej frac2pi4 3n Como a expansão de ildexn em termos da DFS é ildexn frac14 sumk0N1 ildeXk ej frac2pi4 kn Notase que ildeX0 0 ildeX14 A2 portanto ildeX1 2A ildeX2 0 ildeX34 A2 portanto ildeX3 2A Exemplo xn 1 1 1 1 1 0 0 0 0 N10 L5 Xejω n04 ejωn ej2ω sin5ω2sinω2 Xk n04 ej2π10n ej4π10k sinπk2sinπk10 Série e Transformada Discreta de Fourier 13 Amostragem da DTFT Foi visto que se a partir de uma sequência de duração finita L xn se produz uma sequência periódica 𝑥𝑛 com período 𝑁 𝐿 os coeficientes da DFS 𝑋𝑘 são as amostras da DTFT 𝑋𝑒𝑗𝜔 nas frequências 𝜔𝑘2𝜋𝑘𝑁 𝑥𝑛𝑥𝑛𝑚𝑥𝑛𝑚𝑁𝐷𝐹𝑆𝑋𝑘𝑋𝑒𝑗𝜔𝜔2𝜋𝑁𝑘 Suponha agora que se tenha uma DTFT de um sinal 𝑥𝑛 qualquer dada por 𝑋𝑒𝑗𝜔 e se tomam amostras da DTFT formando coeficientes de uma DFS 𝑋𝑘𝑋𝑒𝑗𝜔𝜔2𝜋𝑁𝑘 em que a DTFT é dada por 𝑋𝑒𝑗𝜔𝑚𝑥𝑚𝑒𝑗𝜔𝑚 Ou seja a DFS pode ser escrita em função de 𝑥𝑛 como 𝑋𝑘𝑚𝑥𝑚𝑒𝑗2𝜋𝑁𝑘𝑚 Calculandose a DFS inversa podese chegar a uma relação entre a sequência periódica 𝑥𝑛 e a sequência 𝑥𝑛 Série e Transformada Discreta de Fourier 15 Amostragem da DTFT Logo ao se tomar N amostras da DTFT de um sinal xn obtendose coeficientes de uma DFS a sequência periódica correspondente pode ser obtida por meio da adição de infinitas cópias de xn deslocadas de múltiplos de N 𝑥𝑛 DTFT 𝑋𝑒𝑗𝜔 𝑁 amostras 𝑋𝑘𝑋𝑒𝑗𝜔𝜔2𝜋𝑁𝑘 DFS 𝑥𝑛𝑟𝑥𝑛𝑟𝑁 Logo se a sequência xn possuir um comprimento L N haverá sobreposição no domínio do tempo e um período de 𝑥𝑛 não representará corretamente a sequência xn Há um número mínimo de amostras de 𝑋𝑒𝑗𝜔 para que a sequência xn possa ser recuperada a partir de 𝑥𝑛 ou a partir das amostras da DTFT Série e Transformada Discreta de Fourier 16 Amostragem da DTFT Exemplo Seja xn um pulso de duração 5 amostras L5 sequências DTFT DFS 3 2 1 0 0 5 10 15 20 3 2 1 0 0 5 10 15 20 3 2 1 0 0 5 10 15 20 3 2 1 0 0 5 10 15 20 amostra n 𝑋𝑒𝑗𝜔 5 0 0 5 10 5 0 0 2 4 5 0 0 1 2 3 4 amostra k 𝑥1𝑛𝑟𝑥𝑛10𝑟 𝑁10 𝑋1𝑘𝑋𝑒𝑗𝜔𝜔2𝜋10 𝑘 𝑥2𝑛𝑟𝑥𝑛5𝑟 𝑁5 𝑋2𝑘𝑋𝑒𝑗𝜔𝜔2𝜋5 𝑘 𝑥3𝑛𝑟𝑥𝑛4𝑟 𝑁4 𝑋3𝑘𝑋𝑒𝑗𝜔𝜔2𝜋4 𝑘 Propriedades da DFS Sequências xn e yn e suas séries de período N Propriedade Sequência DFS período N Linearidade axn byn aXk bYk Atraso no tempo xn m ej2𝛑NkmXk Deslocamento em frequência ej2𝛑Nk0 nxn Xk k0 Dualidade Xn Nxk Convolução periódica yn Σm0N1 xmhn m Yk Xk Ĥk Modulação vn xn wn Vk 1N Σl0N1 XlWkl Simetria xn Xk xn Xk ℜxn Xek Xk Xk2 ℑxn Xok Xk Xk2 xen xn xn2 ℜXk xon xn xn2 ℑXk xn real Xk Xk Xk Xk Xk Xk Exemplo Convolução periódica Desejase fazer a convolução periódica entre as sequências x2m yn Σm0N1 xmhn m x1m Notase que a somatória é realizada em um período apenas Para n0 devese ter o sinal x20 m e multiplicálo por x1m Devese perceber que como o sinal é periódico deslocamentos posteriores do sinal serão da forma e amostras que saem pelo lado direito entram pelo lado esquerdo quando se considera um período dos sinais Para obter os valores da saída devese multiplicar as duas sequências e realizar a soma das amostras em um período Exemplo Convolução periódica Desejase fazer a convolução periódica entre as sequências xn hn yn Σm0N1 xmhn m Para n0 y0 Σm0N1 xmh0 m xm hm Exemplo Convolução periódica Para n1 y1 Σm0N1 xmh1 m xm h1 m Para n2 y2 Σm0N1 xmh2 m xm h2 m Exemplo Convolução periódica Para n3 y3 Σm0N1 xmh3 m xm h3 m Para n4 y4 Σm0N1 xmh4 m xm h4 m Transformada Discreta de Fourier DFT Seja um sinal xn de duração finita N ou de comprimento L N xn 0 para n 0 e n N Podese montar com essa sequência uma outra periódica tal que xn Σr xn rN xn modulo N xnN Dessa sequência periódica podese calcular a DFS Xk que é periódica com período N Xk Σn0N1 xnej2𝛑Nkn Para manter a dualidade entre os domínios do tempo e frequência tomase um período dessa sequência periódica e dáse o nome de Xk Xk Xk k 0 1 N 1 0 caso contrário de modo que Xk Xk modulo N XkN Exemplo para L6 e N8 xn xn DFT XkDFS DFT Dessa forma temse Xk n0N1 xnej2πNkn k01N1 0 caso contrário xn 1N n0N1 Xkej2πNkn n01N1 0 caso contrário xn DFT Xk OBSERVAÇÕES Os sinais xn e Xk são ambos discretos e de duração finita N Da mesma forma que antes a DFT pode ser vista como amostras da DTFT do sinal xn nas frequências ωk2πkN k0N1 Ao se trabalhar com as sequências xn e Xk e a DFT devese sempre lembrar que há sequências periódicas envolvidas Ao se usar a DFT devese trabalhar com as sequências considerando que estas são periódicas e ao final tomase apenas um período 0 n N1 0 k N1 Fora desse intervalo considerase que as sequências têm valor zero sinais de duração finita N Operações com N Ao se trabalhar com a DFT lembrar que as sequências de duração finita no tempo e na frequência são na verdade um período das sequências periódicas correspondentes xn e Xk Convolução Linear Usando a DFSDFT Vimos que se um sinal de duração finita yn tem DTFT Yejω as amostras de Yejω nas frequências ωk 2πkN formam uma DFS Ỹk Ỹk Yejωω2πN k e cuja sequência periódica no tempo é ỹn ynN r yn rN Note que se o comprimento de yn for menor ou igual a N não haverá sobreposição no tempo e um período de ỹn será igual a yn Serie e Transformada Discreta de Fourier 33 Convolucao Circular xn hn xn4hn n xn hn xn5hn Serie e Transformada Discreta de Fourier 34 Convolucao Circular n xn hn xn6hn n xn hn xn7hn Serie e Transformada Discreta de Fourier 35 Convolucao Linear Usando a DFT Conclusao sendo xn de comprimento L hn de comprimento M A convolucao circular entre xn e hn e igual a convolucao linear se for utilizado um valor de N L M 1 no calculo da DFSDFT Convolucao rapida Fast Convolution 1 Calcular a DFSDFT Xk de comprimento N L M 1 2 Calcular a DFSDFT Hk de comprimento N 3 Obter Y k Xk Hk 4 Calcular a DFSDFT inversa de Y k para obter yn Nestas operacoes se utilizam algoritmos eficientes para o calculo da DFSDFT que sao os algoritmos de FFT Fast Fourier Transform 10 0 10 1 10 2 10 3 10 4 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 flops Convolução rápida Convolução linear L M N 2L Serie e Transformada Discreta de Fourier 36 Convolucao por Blocos Convolucao rapida para sinais de duracao finita Sistemas praticos a entrada pode ter duracao muito grande Se a resposta impulsiva tiver duracao finita podese separar a en trada em blocos de comprimento finito e utilizar a convolucao rapida aplicada aos blocos linearidade da operacao de filtragem O comprimento da convolucao linear entre dois sinais e maior que a duracao de cada sinal necessario um ajuste entre resultados de convolucoes aplicadas a blocos adjacentes Serie e Transformada Discreta de Fourier 37 OverlapAdd Neste metodo considerase o seguinte O sistema FIR tem resposta impulsiva hn com comprimento M O sinal de entrada xn tem comprimento muito maior que M Separase o sinal xn em blocos de comprimento L produzindo sinais xin Calculase a convolucao rapida entre xin e hn produzindo os sinais yin Como visto anteriormente a convolucao rapida deve ser realizada com um numero de pontos N LM 1 que e o comprimento resultante das sequˆencias yin No processamento por blocos Na pratica adicionamse zeros a xin e hn para que atinjam o com primento N A saıda y0n corresponde as amostras entre 0 e N 1 A saıda y1n corresponde as amostras entre L e L N 1 Ha uma sobreposicao entre y0n e y1n para L n N 1 Essas amostras devem ser somadas na resposta total Ha um atraso no processamento Serie e Transformada Discreta de Fourier 38 OverlapAdd M 1 zeros M 1 zeros M 1 zeros L L L adiciona adiciona M 1 M 1 pontos pontos xn x0n x1n x2n yn y0n y1n y2n xin xn iL 0 n L 1 i 0 1 yin DFT1Hk Xik N L M 1 yn y0n y1n L y2n 2L OverlapAdd Exemplo OverlapSave Neste método se faz a sobreposição dos blocos de entrada de modo que não seja necessário adicionar saídas adjacentes Separase a entrada xn em sequências de comprimento L N M Calculase a DFT com comprimento N O comprimento de hn é igual a M L e adicionamse N M zeros para que fique com comprimento N Fazse uma sobreposição das entradas em que as M 1 últimas amostras de xin serão as M 1 primeiras amostras de xi1n A sequência x0n é montada com zeros nas primeiras M 1 amostras e depois com as L M 1 primeiras amostras de xn A convolução circular entre hn e xin yin terá valores diferentes da convolução linear nas M 1 primeiras amostras Essas M 1 primeiras amostras de yin são descartadas