Transformadas Discretas - Resumo Teórico e Aplicações

1 Transformadas Discretas 1º semestre de 2022 2 Estas notas são um mero resumo dos tópicos da disciplina não devendo ser usadas como referência para estudo 3 Para que serve Processamento sismológico Processamento forênsico Codificação de voz e imagens Sinais biomédicos Karaoke e produtos de consumo Análise de falhas vibrações Telecomunicações OFDM Qualquer análise de sinais reais no domínio da frequência etc Transformadas Discretas 4 httpswwwyoutubecomwatchvAS5RA8B9P9U Qualidade da energia Transformadas Discretas 5 httpsdynamoxnetendetectionbearingfailure Transformadas Discretas The following image makes a comparison between two triaxial spectra one realized before the fault represented by blue pink and yellow curves and another one realized after the appearance of the anomaly in gray 6 Transformada discreta de Fourier DFT Discrete Fourier Transform Transformadas Discretas 7 Transformada de Fourier tradicional Exemplo 1 V C R t0 Transformadas Discretas 8 Transformada de Fourier tradicional Exemplo 1 V C R v0t t0 Transformadas Discretas Transformadas Discretas Função TFexpat RC1 Mod TF exp uni w 10 Claramente esta caracterização da sequência no domínio das frequência depende da variável contínua ω tornando difícil seu uso em análises feitas em computadores digitais Além disso precisamos ter o sinal expresso como uma equação Como por exemplo calcular a distorção harmônica em um medidor de qualidade de energia Ou caracterizar um sinal de voz Transformadas Discretas 11 O que fazer quando temos apenas amostras de um sinal obtido por meio de um sistema de coleta de dados Tornase necessário utilizar algum método para calcularmos as amostras do espectro para viabilizar o uso de computadores em análises de sinais Transformadas Discretas Uma ideia Poderíamos calcular uma transformada e amostrar em valores espaçados uniformemente da variável independente ω Mas será que é possível calcular estas amostras da transformada de Fourier diretamente das amostras do sinal a ser analisado 12 Vamos considerar que o sinal no tempo tenha sido amostrado Sabemos que as características em frequência deste sinal podem ser obtidas a partir da sua Transformada Z 𝑋 𝑒 𝑗𝜔 𝑋 𝑧𝑧𝑒 𝑗 𝜔 𝑇 𝑛 𝑥𝑛𝑒 𝑗 𝜔𝑛𝑇 Sem perda de generalidade vamos considerar que os sinais que nos interessam foram coletados durante um certo período de tempo iniciado em t0 e que L amostras foram coletada Adicionalmente para termos uma notação mais compacta vamos considerar T1 L 4 xn n Transformadas Discretas 13 O espectro de um sinal amostrado é periódico no eixo ωT com período igual a 2π 0 45553093477052 91106186954104 136659280431156 0 05 1 15 2 25 Módulo 2π 4π Podemos amostrar o espectro acima usando uma frequência de amostragem igual a um submúltiplo inteiro do seu período Isto é k012 N1 0 0392699081698724 0785398163397448 117809724509617 15707963267949 196349540849362 235619449019235 274889357189107 314159265358979 353429173528852 392699081698724 431968989868597 471238898038469 510508806208341 549778714378214 589048622548086 628318530717959 0 1 2 Módulo N4 ωT radianos Transformadas Discretas Mas será que estas amostras representarão o sinal de forma fiel 14 𝑋𝑠𝑎𝑒 𝑗 𝜔𝑋𝑒 𝑗 𝜔 𝑘 𝛿𝜔𝑘 2 𝜋 𝑁 Modelando esta amostragem no domínio da frequência matematicamente Calculando o equivalente no tempo deste espectro Mas E portanto Transformadas Discretas 15 Modelando esta amostragem no domínio da frequência matematicamente L 6 N6 n A sequência n é obtida partir da sequência xn repetindo esta última a cada N períodos de amostragem xn n Transformadas Discretas 16 L 4 𝑋𝑒 𝑗 𝜔 𝑛 𝑥𝑛𝑒 𝑗 𝜔𝑛 xn Amostragem Voltando para o tempo Das amostras do espectro um sinal n constituído por repetições periódicas do sinal discreto original xn é recuperado Resumo do que discutimos até o momento n n n 0 15 Módulo ωT rad N4 0 15 Módulo ωT rad Transformadas Discretas 17 𝑋𝑒 𝑗 𝜔 𝑛 𝑥𝑛𝑒 𝑗 𝜔𝑛 0 15 Módulo Amostragem Voltando para o tempo L deve ser menor ou igual a N L 6 N4 L 6 Problema n xn 0 15 Módulo N4 n n ωT rad ωT rad xn Transformadas Discretas 18 Conclusões a Se L N n é uma repetição exata de xn e esta última sequencia pode ser obtida isolandose N amostras de n b As amostras da transformada de Fourier constituem uma representação eficiente de uma sequencia discreta de comprimento finito c Esta representação só é útil se o número de amostras N em um período da transformada de Fourier for maior ou igual ao comprimento do sinal original L Em geral utilizase NL na prática 𝑥 𝑛 2𝜋 𝑁 𝑥𝑠𝑎 𝑛𝑝𝑎𝑟𝑎0𝑛 𝑁 1 Transformadas Discretas 19 A Transformada de Fourier Discreta DFT é definida como A Transformada Inversa de Fourier Discreta IDFT é definida como Transformada de Fourier Discreta DFT Twiddle factor Transformadas Discretas 20 Exemplo Calcule a DFT para a seguinte sequencia Solução Antes de resolver o exemplo vamos enunciar uma propriedade simples do twidle factor xn 1 1 1 0 2 9 8 7 6 5 4 3 n Transformadas Discretas N 10 21 Exemplo Calcule a DFT para a seguinte sequencia Solução Para a sequencia dada se k for diferente de 0 usando a fórmula da soma dos termos de uma PG Mas e Transformadas Discretas 22 Solução Para a sequencia dada se k for diferente de 0 Considerando que Para k 0 Xk 0 Transformadas Discretas 23 Solução Para k 0 Xk 0 Podemos ver que a Se k for um inteiro par Xk 0 b Se k for um inteiro ímpar Transformadas Discretas 24 ωT rad 2𝜋 10 2 𝜋 𝑁 2 𝜋 10 0 2 2𝜋 10 3 2𝜋 10 4 2𝜋 10 5 2𝜋 10 6 2 𝜋 10 7 2𝜋 10 8 2 𝜋 10 9 2𝜋 10 Transformadas Discretas Como relacionar estes valores a frequências físicas 25 Resolução da DFT N pontos de 0 a 2π no eixo ωT radiano intervalo entre os pontos N pontos de 0 a 2πfsa no eixo ω rads intervalo entre os pontos N pontos de 0 a fsa no eixo f Hz intervalo entre os pontos Exemplo fsa 8000 amostrass e N 1048 Resolução 8000 1048 763359 Hz Transformadas Discretas 26 Aumento da resolução da DFT Encher as amostras do sinal com amostras nulas aumentando N 10 pontos e nenhum preenchimento ωT rads 2𝜋 10 Transformadas Discretas 27 Aumento da resolução da DFT Encher as amostras do sinal com amostras nulas aumentando N 10 pontos e mais 10 iguais a zero ωT rads 2𝜋 20 Transformadas Discretas 28 Aumento da resolução da DFT Encher as amostras do sinal com amostras nulas aumentando N 10 pontos e mais 90 iguais a zero ωT rads Resolução Transformadas Discretas 29 Aumento da resolução da DFT Encher as amostras do sinal com amostras nulas aumentando N 10 pontos e nenhum preenchimento 10 pontos e mais 10 iguais a zero 10 pontos e mais 90 iguais a zero ωT rads ωT rads ωT rads 2𝜋 10 2𝜋 20 Resolução Transformadas Discretas 30 Propriedades Transformadas Discretas 31 Linearidade Observese que as duas DFTs devem apresentar o mesmo número de pontos assim como as sequências mesmo que seja necessário completar com zeros xn k1 x1n k2x2n Xk k1 X1k k2X2k Transformadas Discretas 32 Reversão no tempo Deve ser observado que se tanto n quanto k são restritos ao interval entre 0 e N1 n e k estão fora deste interval Portanto para que esta propriedade seja consistente xn xNn e Xk XNk Estas relações são coerentes com a consideração de que tanto xn quanto Xk são periódicas com período N xn Xk xn Xk Transformadas Discretas 33 Transformadas Discretas x0 8 x1 0 x2 7 X3 1 x4 6 x5 2 x6 5 x7 3 x0 x80 8 x1 x81 x7 3 x2 x82 x6 5 X3 x83 x5 2 x4 x84 x4 6 x5 x85 x3 1 x6 x86 x2 7 x7 x87 x1 0 X 320000 00000i 20000 08284i 20000 20000i 20000 48284i 200000 00000i 20000 48284i 20000 20000i 20000 08284i X1 320000 00000i 20000 08284i 20000 20000i 20000 48284i 200000 00000i 20000 48284i 20000 20000i 20000 08284i n n 34 Deslocamento no tempo Deve ser observado que se permitirmos que n varie fora do interval entre 0 e N1 então xn deve ser interpretado como um sinal periódico com período N Então o sinal xnl corresponde a um deslocamento circular de xn xn Xk xnl WN lkXk 𝑥0𝑥1𝑥2𝑥3𝑥4 l2 N 5 𝑥2𝑥3𝑥4𝑥0𝑥1 Sequência xn Sequência xn2 Transformadas Discretas 35 Deslocamento no tempo Deve ser observado que se permitirmos que n varie fora do interval entre 0 e N1 então xn deve ser interpretado como um sinal periódico com período N Então o sinal xnl corresponde a um deslocamento circular de xn xn Xk xnl WN lkXk 𝑥0𝑥1𝑥2𝑥3𝑥4 l2 N 5 𝑥2𝑥3𝑥4𝑥0𝑥1 Sequência xn Sequência xn2 Transformadas Discretas 36 𝑥0𝑥1𝑥2𝑥3𝑥4 l2 N 5 𝑥2𝑥3𝑥400 Sequência xn Sequência xn2 Transformadas Discretas Shift 𝑥0𝑥1𝑥2𝑥3𝑥4 l2 N 5 𝑥2𝑥3𝑥4𝑥0𝑥1 Sequência xn Sequência xn2 Rotate 37 Deslocamento na frequência modulação Deve ser observado que se permitirmos que n varie fora do interval entre 0 e N1 então Xk deve ser interpretado como um sinal periódico com período N Então o sinal Xkl corresponde a um deslocamento circular de Xk xn Xk WN lkxn Xkl Transformadas Discretas 38 Convolução circular no tempo 𝑁 𝑋 𝑘 𝐻𝑘 Prova Se Deslocamento circular Transformadas Discretas 39 Transformada Rápida de Fourier FFT Transformadas Discretas A Transformada Rápida de Fourier é uma coleção de algoritmos para realizar o cálculo da DFT de maneira computacionalmente eficiente httpsenwikipediaorgwikiFastFouriertransform 40 clear allclose allclc vetor de entrada pulso N 8 x 05 05 05 05 0 0 0 0 twidle factor WN exp i 2 pi N Calculo da DFT pela formula for i 11N Yi 0 for j 11N Yi Yi xj WN i1j1 end end Y 200 j 0 05 j 1207 0 j0 05 j0207 0 j 0 05 j 0207 0 j 0 05 j 1207 N2 multiplicações complexas 𝑋 𝑘 𝑛0 𝑁 1 𝑥𝑛𝑊 𝑁 𝑘𝑛𝑝𝑎𝑟𝑎0𝑘 𝑁 1 Transformadas Discretas 41 N2 multiplicações complexas 𝑋 𝑘 𝑛0 𝑁 1 𝑥𝑛𝑊 𝑁 𝑘𝑛𝑝𝑎𝑟𝑎0𝑘 𝑁 1 Transformadas Discretas Para valores de N muito elevados o tempo e recursos gastos no cálculo da DFT é proibitivo James W Cooley John W Tukey 1965 An algorithm for the machine calculation of complex Fourier series Math Comput 19 297301 Transformadas Discretas Implementation of Fast Fourier Transform Algorithms with the TMS32020 APPLICATION REPORT SPRA122 Authors Panos Papamichalis Digital Signal Processing Semiconductor Group John So Atlanta Regional Technology 43 Decimação no Tempo N2 multiplicações complexas Transformadas Discretas 44 a Simetria Demonstração Propriedades do Twiddle factor b Periodicidade Demonstração Transformadas Discretas 45 x0 x1 x2 x3 x4 x5 x6 x7 x0 x2 x4 x6 x1 x3 x5 x7 Amostras de ordem par Amostras de ordem ímpar Transformadas Discretas 46 𝑵 𝟐 Mas 2 DFTs de N2 pontos Transformadas Discretas 47 Ordem das amostras x0 x1 x2 x3 x4 x5 x6 x7 x0 x2 x4 x6 x1 x3 x5 x7 x0 x4 x2 x6 x1 x5 x3 x7 Log2N Transformadas Discretas Este processo pode ser repetido várias vezes até que resultem N2 DFTs de 2 elementos Por exemplo para N8 48 Ordem das amostras x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x0 x2 x4 x6 x8 x10 x12 x14 x1 x3 x5 x7 x9 x11 x13 x15 x0 x4 x8 x12 x2 x6 x10 x14 x1 x5 x9 x13 x3 x7 x11 x15 x0 x8 x4 x12 x2 x10 x6 x14 x1 x9 x5 x13 x3 x11 x7 x15 Log2N 4 níveis Transformadas Discretas Este processo pode ser repetido várias vezes até que resultem N2 DFTs de 2 elementos Por exemplo para N16 49 N2 multiplicações N2 multiplicações N2 multiplicações N2 log2N multiplicações Transformadas Discretas Transformadas Discretas Exemplo xn 05 0 1 2 3 4 5 6 7 n Transformadas Discretas x0 050 x1 050 x2 050 x3 050 x4 00 x5 00 x6 00 x7 00 w80 1 w80 1 w80 1 w80 1 w80 1 w81 w82 j w82 j w83 X0 20 X4 00 X2 00 X6 00 X1 05 12071 X5 0502071 X3 05 02071 X7 0512071 51 Transformadas Discretas TWIDDLE FACTOR VALUE w80 1 w81 eπ4 07071 j 07071 w82 eπ2 j w83 e3π4 07071 j 07071 w84 eπ w80 1 w85 e5π4 w81 07071 j 07071 w86 e3π2 w82 j w87 e7π4 w83 07071 j 07071 50 Transformadas Discretas Xk 2 13066 05412 05412 13066 k 0 1 2 3 4 5 6 7 Transformadas Discretas STAGE 1 STAGE 2 STAGE 3 x0 x4 W0 x2 W0 x6 W0 W2 x1 W0 x5 W0 W1 x3 W0 W2 x7 W0 W2 W3 X0 X1 X2 X3 X4 X5 X6 X7 LEGEND FOR TWIDDLE FACTOR W0 W80 W1 W81 W2 W82 W3 W83 55 Reversão dos bits ou embaralhamento Transformadas Discretas 56 Exemplo prático Alguns engenheiros formados no Mackenzie foram convocados para ir até uma cidade do interior de Minas Gerais e investigarem um possível contato imediato que os habitantes alegam ter tido com um ser extraterreno Lá chegando eles receberam uma gravação de áudio amostrada com a taxa de 441 K amostrass Esta gravação está no arquivo Etsomwav anexa a esta lista A única informação adicional é que esta gravação parece representar uma espécie de nota musical alegadamente emitida pelos tais seres Não há informação adicional Sua missão neste exercício é ajudar os engenheiros e determinar que nota musical foi emitida Com este objetivo você deve escrever um script no Octave ou Matlab se você tiver acesso a uma licença para realizar uma análise espectral e determinar qual a frequência da nota 57 close all clear all clc leitura do arquivo info audioinfo coctaveETsomwav filecoctaveETsomwav M fs audioreadfilereproduz o áudio playeraudioplayerM fs play player 58 converte para o dominio das frequencias Y absfftM plotY procura a raia espectral de valor máximo Max 0 nmax 1 for ii 2lengthY if Yii Max Max Yii nmax ii Endifendfor calcula a frequencia do tom nmaxfreq nmax1fsinfoTotalSamples 59 Um engenheiro deseja analisar o conteúdo espectral de um pulso de duração rápida xt usando um computador digital Para realizar essa tarefa ele projetou um sistema de aquisição de dados que detecta o início do pulso e o digitaliza Sabendo que a A duração do pulso é de aproximadamente 3 ns b O pulso não apresenta componentes de frequência acima de 15 GHz c O engenheiro necessita discriminar frequências espaçadas de 15 MHz Pedese d Determine a menor taxa de amostragem do conversor AD do sistema de aquisição de dados que viabilize esse sistema e Descreva o procedimento de medida fornecendo os valores de todos os parâmetros relevantes no caso de utilização da frequência mínima determinada acima Obs Lembrese que para uma DFT o número de pontos não precisa ser potência de 2 60 a O Teorema da Amostragem nos diz que a frequência de amostragem tem que ser pelo menos duas vezes a frequência máxima do sinal A maior frequência do sinal pelo enunciado é 15 GHz A frequência de amostragem mínima é o dobro deste valor 3 GHz b Resolução fsaN N fsaresolução 3 Ghz 15e6 200 O problema é que em 3 ns amostrando a 3GHz tenho apenas 9 pontos Preciso acrescentar 200 9 zeros à sequencia de amostras em que vou aplicar a DFT Procedimento i Coleto as 9 amostras do pulso usando a frequencia de amostragem igual a 3Gz ii Acrescento 191 zeros à sequencia de amostras iii Calculo aDFT de 200 pontos iv Cada amostra estará espaçada 15 MHz uma da outras em um segmento de o a 3GHz