Slides Transforamda de Fourrier Discreta Dft fft e Transformada Z-2022 1

2022-1 EL36F – Processamento Digital de Sinais Prof. Eduardo Alves Hodgson hodgson@utfpr.edu.br Transformada Z UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Câmpus Cornélio Procópio EL36F Transmissão de Dados 2 Tópicos • Transformada Z • Propriedades da região de convergência (RDC) • Transforma Z inversa • Cálculo geométrico da transforma de Fourier • Propriedades da transformada Z • Análise de Sistemas LIT usando transformada Z • Diagrama de blocos EL36F Transmissão de Dados 3 Introdução ❑ Relembrando a aula de série de Fourier: Se a entrada de um sistema LIT é uma exponencial complexa 𝑥 𝑛 = 𝑧𝑛, onde 𝑧 = 𝑟𝑒𝑗𝜔, logo, 𝑥 𝑛 = 𝑧𝑛 = 𝑟𝑒𝑗𝜔𝑛, a resposta 𝑦[𝑛] do sistema será o mesmo sinal de entrada 𝑧𝑛 multiplicado por 𝐻 𝑧 : 𝑦[𝑛] = 𝐻 𝑧 𝑧𝑛, onde 𝐻 𝑧 é 𝐻 𝑧 = ෍ 𝑛=−∞ ∞ ℎ 𝑛 𝑧−𝑛 EL36F Transmissão de Dados 4 Transformada Z Para o caso específico onde 𝒛 = 𝒆𝒋𝝎, ou seja, 𝒛 = 𝟏 e 𝑟 = 1, 𝐻 𝑧 será a transforma de Fourier de tempo discreto de ℎ[𝑛]: 𝐻 𝑒𝑗𝜔 = ෍ 𝑛=−∞ ∞ ℎ 𝑛 𝑒−𝑗𝜔𝑛 Para o caso geral onde 𝒛 = 𝒓𝒆𝒋𝝎 e 𝑧 não é restrito à unidade, 𝐻 𝑧 será a Transformada Z de ℎ[𝑛]: 𝐻 𝑧 = ෍ 𝑛=−∞ ∞ ℎ 𝑛 𝑧−𝑛 Podemos aplicar a T.Z também para um sinal genérico 𝑥[𝑛]: 𝑋 𝑧 = ෍ 𝑛=−∞ ∞ 𝑥 𝑛 𝑧−𝑛 EL36F Transmissão de Dados 5 Transformada Z A transformada Z é representada graficamente pelo plano Z abaixo em coordenadas polares de raio 𝑟 e ângulo 𝜔 do 𝑧 = 𝑟𝑒𝑗𝜔. A transformada de Fourier discreta no tempo é representada apenas pela circunferência unitária onde 𝑧 = 1 ou 𝑟 = 1 do 𝑧 = 𝑟𝑒𝑗𝜔 do plano Z. ➢ Se a circunferência unitária pertencer a região de convergência (RDC) da T.Z, então a T.F. também converge. EL36F Transmissão de Dados 6 Transformada Z Neste exemplo abaixo vamos ver o que é: • Região de convergência (RDC) de um sinal 𝑥[𝑛] • Diagrama de polos e zeros de 𝑋(𝑧) Exemplo 10.1 Opp. Calcule a T.Z de 𝑥 𝑛 = 𝑎𝑛𝑢 𝑛 , apresente o diagrama de polos e zeros e a RDC da T.F. 𝑋(𝑧) = ෍ 𝑛=−∞ ∞ 𝑎𝑛𝑢 𝑛 𝑧−𝑛 = ෍ 𝒏=𝟎 ∞ 𝑎𝑛𝑧−𝑛 = ෍ 𝑛=0 ∞ 𝑎𝑧−1 𝑛 EL36F Transmissão de Dados 7 Transformada Z Neste exemplo abaixo vamos ver o que é: • Região de convergência (RDC) de um sinal 𝑥[𝑛] • Diagrama de polos e zeros de 𝑋(𝑧) Exemplo 10.1 Opp. Calcule a T.Z de 𝑥 𝑛 = 𝑎𝑛𝑢 𝑛 , apresente o diagrama de polos e zeros e a RDC da T.F. 𝑋(𝑧) = ෍ 𝑛=−∞ ∞ 𝑎𝑛𝑢 𝑛 𝑧−𝑛 = ෍ 𝒏=𝟎 ∞ 𝑎𝑛𝑧−𝑛 = ෍ 𝑛=0 ∞ 𝑎𝑧−1 𝑛 Para 𝑋(𝑧) convergir, σ𝑛=0 ∞ 𝑎𝑧−1 𝑛 < ∞ Logo, 𝑎𝑧−1 < 1 ou 𝑧 > |𝑎|. Portanto, a T.Z de 𝑥[𝑛] é: 𝑋(𝑧) = ෍ 𝑛=0 ∞ 𝑎𝑧−1 𝑛 = 1 1 − 𝑎𝑧−1 = 𝑧 𝑧 − 𝑎 , 𝑧 > |𝑎| EL36F Transmissão de Dados 8 Transformada Z Exemplo 10.1 Opp. 𝑥 𝑛 = 𝑎𝑛𝑢 𝑛 Apresente o diagrama de polos e zeros e região de convergência no plano z 𝑋(𝑧) = ෍ 𝑛=0 ∞ 𝑎𝑧−1 𝑛 = 1 1 − 𝑎𝑧−1 = 𝑧 𝑧 − 𝑎 , 𝑧 > |𝑎| Zeros são as raízes do polinômio do numerador. Temos um zero em 𝑧 = 0, representando por um círculo no diagrama. Polos são as raízes do polinômio do denominador. Temos um polo em 𝑧 = 𝑎, representado por um x no diagrama. Circunferência unitária EL36F Transmissão de Dados 9 Transformada Z Suponha que 𝑎 = 0,5. Vamos plotar 𝑋 𝑧 = 𝑧 𝑧−𝑎 em função de z. Note que temos um zero em 𝑧 = 0 ( 𝑋 𝑧 = 0) e um polo em 𝑧 = 0,5 ( 𝑋 𝑧 = ∞) EL36F Transmissão de Dados 10 Transformada Z Note também que a transformada Z no círculo unitário em preto, onde 𝑧 = 𝑟𝑒𝑗𝜔 com 𝑟 = 1, é a transformada de Fourier 𝑋(𝑒𝑗𝜔) de 𝑥[𝑛] abaixo 𝜔 = 0 𝜔 = 𝜋 EL36F Transmissão de Dados 11 Transformada Z Exemplo 10.1 Opp. 𝑥 𝑛 = 𝑎𝑛𝑢 𝑛 Apresente o diagrama de polos e zeros e região de convergência da T.F. 𝑋(𝑧) = ෍ 𝑛=0 ∞ 𝑎𝑧−1 𝑛 = 1 1 − 𝑎𝑧−1 = 𝑧 𝑧 − 𝑎 , 𝑧 > |𝑎| • A região de convergência 𝑋(𝑧) é a região cinza do diagrama onde 𝑧 > |𝑎|. • Se 𝑎 > 1, a RDC não inclui a circunferência unitária e a T.F. de 𝑥[𝑛] não converge. • Se 𝑎 < 1, a RDC inclui a circunferência unitária e a T.F. de 𝑥[𝑛] converge. Circunferência unitária Região de convergência EL36F Transmissão de Dados 12 Transformada Z Exemplo 10.2 Opp. Calcule a T.Z de 𝑥 𝑛 = −𝑎𝑛𝑢 −𝑛 − 1 , apresente o diagrama de polos e zeros e a RDC da T.F. 𝑋(𝑧) = − ෍ 𝑛=∞ ∞ 𝑎𝑛𝑢 −𝑛 − 1 𝑧−𝑛 = − ෍ 𝒏=−∞ −𝟏 𝑎𝑛𝑧−𝑛 = − ෍ 𝒏=𝟏 ∞ 𝑎−𝑛𝑧𝑛 𝑋(𝑧) = 1 − ෍ 𝒏=𝟎 ∞ (𝑎−1𝑧)𝑛 EL36F Transmissão de Dados 13 Transformada Z Exemplo 10.2 Opp. Calcule a T.Z de 𝑥 𝑛 = −𝑎𝑛𝑢 −𝑛 − 1 , apresente o diagrama de polos e zeros e a RDC da T.F. 𝑋(𝑧) = − ෍ 𝑛=∞ ∞ 𝑎𝑛𝑢 −𝑛 − 1 𝑧−𝑛 = − ෍ 𝒏=−∞ −𝟏 𝑎𝑛𝑧−𝑛 = − ෍ 𝒏=𝟏 ∞ 𝑎−𝑛𝑧𝑛 𝑋(𝑧) = 1 − ෍ 𝒏=𝟎 ∞ (𝑎−1𝑧)𝑛 Para 𝑋(𝑧) convergir, σ𝑛=0 ∞ 𝑎−1𝑧 𝑛 < ∞ Logo, 𝑎−1𝑧 < 1 ou 𝑧 < |𝑎|. Portanto, a T.Z de 𝑥[𝑛] é: 𝑋 𝑧 = 1 − ෍ 𝑛=0 ∞ 𝑎−1𝑧 𝑛 = 1 − 1 1 − 𝑎−1𝑧 = 1 1 − 𝑎𝑧−1 = 𝑧 𝑧 − 𝑎 , 𝑧 < |𝑎| Note que T.Z é a mesma do exemplo 10.1 mas a RDC mudou. Logo, a T.Z requer a expressão algébrica E a RDC também! EL36F Transmissão de Dados 14 Transformada Z Exemplo 10.2 Opp. 𝑥 𝑛 = −𝑎𝑛𝑢 −𝑛 − 1 Apresente o diagrama de polos e zeros e região de convergência da T.F. 𝑋(𝑧) = ෍ 𝑛=0 ∞ 𝑎𝑧−1 𝑛 = 1 1 − 𝑎𝑧−1 = 𝑧 𝑧 − 𝑎 , 𝑧 < |𝑎| • A região de convergência 𝑋(𝑧) é a região cinza do diagrama onde 𝑧 < |𝑎|. • Se 𝑎 < 1, a RDC não inclui a circunferência unitária e a T.F de 𝑥[𝑛] não converge. • Se 𝑎 > 1, a RDC inclui a circunferência unitária e a T.F de 𝑥[𝑛] converge. RDC Circunferência unitária EL36F Transmissão de Dados 15 Transformada Z Exemplo 10.3 Opp. Calcule a T.Z de 𝑥 𝑛 = 7 1 3 𝑛 𝑢 𝑛 − 6 1 2 𝑛 𝑢[𝑛], apresente o diagrama de polos e zeros e a RDC da T.F. 𝑋(𝑧) = ෍ 𝑛=−∞ ∞ 𝑥[𝑛]𝑧−𝑛 = ෍ 𝑛=0 ∞ 7 1 3 𝑛 𝑧−𝑛 − ෍ 𝑛=0 ∞ 6 1 2 𝑛 𝑧−𝑛 = 𝑋(𝑧) = 7 ෍ 𝑛=0 ∞ 1 3 𝑧−1 𝑛 − ෍ 𝑛=0 ∞ 6 1 2 𝑧−1 𝑛 = 7 1 − 1 3 𝑧−1 − 6 1 − 1 2 𝑧−1 = 𝑧 𝑧 − 3 2 𝑧 − 1 3 𝑧 − 1 2 EL36F Transmissão de Dados 16 Transformada Z Exemplo 10.3 Opp. Calcule a T.Z de 𝑥 𝑛 = 7 1 3 𝑛 𝑢 𝑛 − 6 1 2 𝑛 𝑢[𝑛], apresente o diagrama de polos e zeros e a RDC da T.F. 𝑋(𝑧) = ෍ 𝑛=−∞ ∞ 𝑥[𝑛]𝑧−𝑛 = ෍ 𝒏=𝟎 ∞ 7 1 3 𝑛 𝑧−𝑛 − ෍ 𝒏=𝟎 ∞ 6 1 2 𝑛 𝑧−𝑛 = 𝑋(𝑧) = 7 ෍ 𝒏=𝟎 ∞ 1 3 𝑧−1 𝑛 − ෍ 𝒏=𝟎 ∞ 6 1 2 𝑧−1 𝑛 = 7 1 − 1 3 𝑧−1 − 6 1 − 1 2 𝑧−1 = 𝑧 𝑧 − 3 2 𝑧 − 1 3 𝑧 − 1 2 Para 𝑋(𝑧) convergir, σ𝑛=0 ∞ (1/3)𝑧−1 𝑛 < ∞ e σ𝑛=0 ∞ (1/2)𝑧−1 𝑛 < ∞ Logo, 1 3 𝑧−1 < 1 e 1 2 𝑧−1 < 1. Ou 𝑧 > 1 3 e 𝑧 > 1 2 Portanto, a T.Z de 𝑥[𝑛] é: 𝑋(𝑧) = 𝑧 𝑧 − 3 2 𝑧 − 1 3 𝑧 − 1 2 , 𝑧 > 1 3 e 𝑧 > 1 2 EL36F Transmissão de Dados 17 Transformada Z Exemplo 10.3 Opp. Calcule a T.Z de 𝑥 𝑛 = 7 1 3 𝑛 𝑢 𝑛 − 6 1 2 𝑛 𝑢[𝑛], apresente o diagrama de polos e zeros e a RDC da T.F. 𝑋(𝑧) = ෍ 𝑛=−∞ ∞ 𝑥[𝑛]𝑧−𝑛 = ෍ 𝒏=𝟎 ∞ 7 1 3 𝑛 𝑧−𝑛 − ෍ 𝒏=𝟎 ∞ 6 1 2 𝑛 𝑧−𝑛 = 𝑋(𝑧) = 7 ෍ 𝒏=𝟎 ∞ 1 3 𝑧−1 𝑛 − ෍ 𝒏=𝟎 ∞ 6 1 2 𝑧−1 𝑛 = 7 1 − 1 3 𝑧−1 − 6 1 − 1 2 𝑧−1 = 𝑧 𝑧 − 3 2 𝑧 − 1 3 𝑧 − 1 2 Ao invés de fazer todas estas contas, aqui podemos apenas aplicar o par de transformada Z do ex. 10.1 (ver tabela no slide 39): 𝑎𝑛𝑢 𝑛 ՞ 𝑍 1 1−𝑎𝑧−1 7 1 3 𝑛 𝑢 𝑛 ՞ 𝑍 7 1 − 1 3 𝑧−1 , 𝑧 > 1 3 −6 1 2 𝑛 𝑢 𝑛 ՞ 𝑍 − 6 1 − 1 2 𝑧−1 , 𝑧 > 1 2 EL36F Transmissão de Dados 18 Transformada Z Exemplo 10.3 Opp. 𝑥 𝑛 = 7 1 3 𝑛 𝑢 𝑛 − 6 1 2 𝑛 𝑢[𝑛] Apresente o diagrama de polos e zeros e região de convergência da T.F. 𝑋(𝑧) = 𝑧 𝑧 − 3 2 𝑧 − 1 3 𝑧 − 1 2 , 𝑧 > 1 3 e 𝑧 > 1 2 A RDC inclui a circunferência unitária e a T.F de 𝑥[𝑛] converge. Note que a RDC é sempre maior que o maior polo. EL36F Transmissão de Dados 19 Transformada Z Exemplo 10.4 Opp. 𝑥 𝑛 = 1 3 𝑛 sin 𝜋 4 𝑛 𝑢[𝑛] Apresente o diagrama de polos e zeros e região de convergência da T.F. 𝑥 𝑛 = 1 2𝑗 1 3 𝑒𝑗𝜋 4 𝑛 𝑢 𝑛 − 1 2𝑗 1 3 𝑒−𝑗𝜋 4 𝑛 𝑢 𝑛 𝑋 𝑧 = 1 2𝑗 1 1 − 1 3 𝑒𝑗𝜋 4𝑧−1 − 1 2𝑗 1 1 − 1 3 𝑒−𝑗𝜋 4𝑧−1 = 1 3 2 𝑧 𝑧 − 1 3 𝑒𝑗𝜋 4 𝑧 − 1 3 𝑒𝑗𝜋 4 A RDC inclui a circunferência unitária e a T.F de 𝑥[𝑛] converge. RDC: 𝑧 > 1/3 EL36F Transmissão de Dados 20 Tópicos • Transformada Z • Propriedades da região de convergência (RDC) • Transforma Z inversa • Cálculo geométrico da transforma de Fourier • Propriedades da transformada Z • Análise de Sistemas LIT usando transformada Z • Diagrama de blocos EL36F Transmissão de Dados 21 Propriedades da Região de Convergência 1) A RDC de 𝑋(𝑧) será sempre composta por um anel no plano 𝑧 centralizado na origem. 2) A RDC não contém polos. 3) Se 𝑥[𝑛] for uma sequência lateral direita, como 𝑎𝑛𝑢 𝑛 , a RDC é externa ao polo de maior magnitude. 4) Se 𝑥[𝑛] for uma sequência lateral esquerda, como − 𝑎𝑛𝑢 −𝑛 − 1 , a RDC é interna ao polo de menor magnitude. EL36F Transmissão de Dados 22 Propriedades da Região de Convergência 5) Se 𝑥[𝑛] for bilateral (exemplo 10.7 𝑥 𝑛 = 𝑏|𝑛|) a RDC pode consistir em um anel limitado por dois polos. 6) A RDC é limitada por polos ou se estende até zero ou infinito. 7) Se 𝑥[𝑛] tiver duração finita, a RDC é (a) todo o plano 𝑧, com possíveis exceções em (b) 𝑧 = 0 e (c) 𝑧 = ∞. (a) 𝛿 𝑛 ՞ 𝑍 σ𝑛=−∞ ∞ 𝛿 𝑛 𝑧−𝑛 = 1 (b) 𝛿 𝑛 − 1 ՞ 𝑍 σ𝑛=−∞ ∞ 𝛿 𝑛 − 1 𝑧−𝑛 = z−1 (c) 𝛿 𝑛 + 1 ՞ 𝑍 σ𝑛=−∞ ∞ 𝛿 𝑛 + 1 𝑧−𝑛 = 𝑧 Par de T.Z: 𝛿 𝑛 − 𝑛0 ՞ 𝑍 = z−𝑛0 EL36F Transmissão de Dados 23 Exemplo 10.8 Opp. Quais as possíveis RDCs que podem ser associadas à: 𝑋(𝑧) = 1 1 − 1 3 𝑧−1 1 − 2𝑧−1 Temos polos em 𝑧 = 1/3 e 𝑧 = 2. Propriedades da Região de Convergência RDC se 𝑥[𝑛] for uma sequência lateral direita. RDC se 𝑥[𝑛] for uma sequência lateral esquerda. RDC se 𝑥[𝑛] for uma sequência bilateral. EL36F Transmissão de Dados 24 Tópicos • Transformada Z • Propriedades da região de convergência (RDC) • Transforma Z inversa • Cálculo geométrico da transforma de Fourier • Propriedades da transformada Z • Análise de Sistemas LIT usando transformada Z • Diagrama de blocos EL36F Transmissão de Dados 25 A T.Z inversa é integral circular de 0 a 2𝜋. 𝑥 𝑛 = 1 2𝜋𝑗 ර 𝑋 𝑧 𝑧𝑛−1𝑑𝑧 Porém, é bem mais conveniente separar 𝑋(𝑧) em frações parciais: 𝑋 𝑧 = ෍ 𝑖=1 𝑚 𝐴𝑖 1 − 𝑎𝑖𝑧−1 A transformada inversa de cada fração parcial vai depender da RDC de cada polo 𝑎𝑖 𝐴𝑖𝑎𝑖 𝑛𝑢 𝑛 ՞ 𝑍 = 𝐴𝑖 1 − 𝑎𝑖𝑧−1 , 𝑧 > |𝑎𝑖| −𝐴𝑖𝑎𝑖 𝑛𝑢 −𝑛 − 1 ՞ 𝑍 = 𝐴𝑖 1 − 𝑎𝑖𝑧−1 , 𝑧 < 𝑎𝑖 Transformada Z Inversa EL36F Transmissão de Dados 26 Exemplo 10.9 Opp. Obtenha a T.Z inversa de 𝑋 𝑧 . Polos em {1/4; 1/3} 𝑋 𝑧 = 3 − 5 6 𝑧−1 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 , 𝑧 > 1 3 3 − 5 6 𝑧−1 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 = 𝐴1 1 − 1 4 𝑧−1 + 𝐴2 1 − 1 3 𝑧−1 3 − 5 6 𝑧−1 1 − 1 4 𝑧−1 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 = 1 − 1 4 𝑧−1 1 − 1 4 𝑧−1 𝐴1 + 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 𝐴2 3 − 5 6 𝑧−1 1 − 1 3 𝑧−1 = 𝐴1 + 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 𝐴2 Isolamos 𝐴1 acima e usamos 𝑧 = 1 4 para zerar o numerador da segunda fração: 3 − 5 6 4 1 − 1 3 4 = 𝐴1 = 1 Transformada Z Inversa EL36F Transmissão de Dados 27 Exemplo 10.9 Opp. Obtenha a T.Z inversa de 𝑋(𝑧) 𝑋 𝑧 = 3 − 5 6 𝑧−1 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 , 𝑧 > 1 3 3 − 5 6 𝑧−1 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 = 𝐴1 1 − 1 4 𝑧−1 + 𝐴2 1 − 1 3 𝑧−1 3 − 5 6 𝑧−1 1 − 1 3 𝑧−1 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 = 1 − 1 3 𝑧−1 1 − 1 4 𝑧−1 𝐴1 + 1 − 1 3 𝑧−1 1 − 1 3 𝑧−1 𝐴2 3 − 5 6 𝑧−1 1 − 1 4 𝑧−1 = 1 − 1 3 𝑧−1 1 − 1 4 𝑧−1 𝐴1 + 𝐴2 Isolamos 𝐴2 acima e usamos 𝑧 = 1 3 para zerar o numerador da primeira fração: 3 − 5 6 3 1 − 1 4 3 = 𝐴2 = 2 Transformada Z Inversa EL36F Transmissão de Dados 28 Exemplo 10.9 Opp. Obtenha a T.Z inversa de 𝑋(𝑧) 𝑋 𝑧 = 3 − 5 6 𝑧−1 1 − 1 4 𝑧−1 1 − 1 3 𝑧−1 , 𝑧 > 1 3 𝑋 𝑧 = 1 1 − 1 4 𝑧−1 + 2 1 − 1 3 𝑧−1 , 𝑧 > 1 3 Como a RDC é 𝑧 > 1 3 e, em consequência, 𝑧 > 1 4, a T.Z inversa é: 𝑋1 𝑧 = 𝟏 1 − 1 4 𝑧−1 , z > 1 4 ՞ 𝑍 𝑥1 𝑛 = 1 4 𝑛 𝑢[𝑛] 𝑋1 𝑧 = 𝟐 1 − 1 3 𝑧−1 , z > 1 3 ՞ 𝑍 𝑥2 𝑛 = 2 1 3 𝑛 𝑢[𝑛] 𝑥 𝑛 = 1 4 𝑛 𝑢 𝑛 + 2 1 3 𝑛 𝑢[𝑛] Transformada Z Inversa EL36F Transmissão de Dados 29 Série de potências, como 3𝑧2 + 2 + 𝑧−1, também podem ser usadas na T.Z inversa, usando os pares de T.Z abaixo: 𝛿 𝑛 − 𝑛0 ՞ 𝑍 = z−𝑛0 𝛿 𝑛 ՞ 𝑍 = 1 Exemplo 10.12 Opp. Obtenha a T.Z inversa de 𝑋 𝑧 = 4𝑧2 + 2 + 3𝑧−1, 0 < 𝑧 < ∞ Usando o par de T.Z acima: 𝑥 𝑛 = 4𝛿 𝑛 + 2 + 2𝛿 𝑛 + 3𝛿[𝑛 − 1] Transformada Z Inversa EL36F Transmissão de Dados 30 Tópicos • Transformada Z • Propriedades da região de convergência (RDC) • Transforma Z inversa • Cálculo geométrico da transforma de Fourier • Propriedades da transformada Z • Análise de Sistemas LIT usando transformada Z • Diagrama de blocos EL36F Transmissão de Dados 31 A resposta em frequência de ℎ[𝑛] pode ser calculada fazendo a relação dos vetores de polos e zeros 𝑣1 𝑣2 ao redor do círculo unitário 0 < 𝜔 < 2𝜋. ℎ 𝑛 = 𝑎𝑛𝑢 𝑛 𝐻 𝑧 = 1 1 − 𝑎𝑧−1 , 𝑧 > 𝑎 𝐻 𝑒𝑗𝜔 = 1 1 − 𝑎𝑒−𝑗𝜔 Cálculo Geométrico da T.F. 𝐻 𝑒𝑗𝜔 = 𝑣1 𝑣2 = 1 𝑣2 EL36F Transmissão de Dados 32 A resposta em frequência de ℎ[𝑛] pode ser calculada fazendo a relação dos vetores de polos e zeros 𝑣1 𝑣2 + 𝑣1 𝑣3 ao redor do círculo unitário 0 < 𝜔 < 2𝜋. ℎ 𝑛 = 𝑟𝑛 sin 𝑗 + 1 sin 𝜃 𝑢[𝑛] 𝐻 𝑒𝑗𝜔 = 1 1−2𝑟 cos 𝜃 𝑒−𝑗𝜔+𝑟2𝑒−𝑗2𝜔 𝐻 𝑧 = 1 1−2𝑟 cos 𝜃 𝑧−1+𝑟2𝑧−2 → polos 𝑧1 = 𝑟𝑒𝑗𝜃e 𝑧2 = 𝑟𝑒−𝑗𝜃, dois zeros em 0. Cálculo Geométrico da T.F. 𝐻 𝑒𝑗𝜔 = 𝑣1𝑣1 𝑣2𝑣3 𝐻 𝑒𝑗𝜔 = 1 𝑣2𝑣3 EL36F Transmissão de Dados 33 Tópicos • Transformada Z • Propriedades da região de convergência (RDC) • Transforma Z inversa • Cálculo geométrico da transforma de Fourier • Propriedades da transformada Z • Análise de Sistemas LIT usando transformada Z • Diagrama de blocos EL36F Transmissão de Dados 34 Deslocamento no tempo 𝑥 𝑛 ՞ 𝑍 𝑋 𝑧 , com RDC = 𝑅 𝑥 𝑛 − 𝑛0 ՞ 𝑍 𝑧−𝑛0𝑋(𝑧) 𝑧−𝑛0 pode adicionar polos, se 𝑛0 for positivo, ou zeros, se 𝑛0 for negativo. Mudança de escala no domínio Z 𝑧0 𝑛𝑥 𝑛 ՞ 𝑍 𝑋 𝑧 𝑧0 Se temos polo em 𝑧 = 𝑎, novo polo será 𝑧 = 𝑧0𝑎. A região de convergência 𝑅 de 𝑋(𝑧) será agora |𝑧0|𝑅. Se 𝑧0 𝑛 = 𝑒𝑗𝜔0𝑛 temos o deslocamento em frequência. Os polos são deslocados em frequência. 𝑒𝑗𝜔0𝑛𝑥 𝑛 ՞ 𝑍 𝑋 𝑒−𝑗𝜔0𝑧 Propriedades da Transformada Z EL36F Transmissão de Dados 35 Reflexão no tempo 𝑥 𝑛 ՞ 𝑍 𝑋 𝑧 , com RDC = 𝑅 𝑥 −𝑛 ՞ 𝑍 𝑋 1/𝑧 , com RDC = 1 𝑅 Expansão no tempo 𝑥(𝑘)[𝑛] possui 𝑘 − 1 zeros inseridos entre amostras de 𝑥[𝑛]. 𝑥(𝑘) 𝑛 ՞ 𝑍 𝑋 𝑧𝑘 , com RDC = 𝑅1/𝑘 Conjugação 𝑥∗ 𝑛 ՞ 𝑍 𝑋∗ 𝑧∗ , com RDC = 𝑅 Se 𝑥[𝑛] é real (um cosseno) 𝑋 𝑧 = 𝑋∗ 𝑧∗ , ou seja, os polos de 𝑥[𝑛] real possuem complexo conjugado. Propriedades da Transformada Z EL36F Transmissão de Dados 36 Convolução 𝑥1 𝑛 ՞ 𝑍 𝑋1 𝑧 , com RDC = 𝑅1 𝑥2 𝑛 ՞ 𝑍 𝑋2 𝑧 , com RDC = R2 𝑥1 𝑛 ∗ 𝑥2 𝑛 ՞ 𝑍 𝑋1 𝑧 𝑋2 𝑧 com RDC = 𝑅1 ∩ 𝑅2 Com o plus da RDC poder ser maior por ter alguns polos cancelados por zeros. Diferenciação 𝑛𝑥 𝑛 ՞ 𝑍 − 𝑧 𝑑𝑋 𝑧 𝑑𝑧 , com RDC = 𝑅 Propriedades da Transformada Z EL36F Transmissão de Dados 37 Propriedades da Transformada Z EL36F Transmissão de Dados 38 Propriedades da Transformada Z EL36F Transmissão de Dados 39 Propriedades da Transformada Z Alguns pares de transformada Z EL36F Transmissão de Dados 40 Propriedades da Transformada Z Alguns pares de transformada Z EL36F Transmissão de Dados 41 Tópicos • Transformada Z • Propriedades da região de convergência (RDC) • Transforma Z inversa • Cálculo geométrico da transforma de Fourier • Propriedades da transformada Z • Análise de Sistemas LIT usando transformada Z • Diagrama de blocos EL36F Transmissão de Dados 42 Causabilidade de sistemas LIT 𝑯(𝒛) Um sistema ℎ[𝑛] causal é nula para 𝑛 < 0, ou seja, ℎ[𝑛] é lateral direita. Se 𝐻(𝑧) possuir qualquer potência positiva de 𝒛, ele não é causal. Exemplo: ℎ 𝑛 = 𝛿 𝑛 + 1 ՞ 𝑍 z Análise de Sistemas LIT usando T.Z Um sistema LIT 𝑯(𝒛) é causal se e somente se a RDC for exterior de um círculo que inclui o polo de maior raio, caso seja racional, e se o grau do polinômio do numerador é menor que o grau do denominador. EL36F Transmissão de Dados 43 Causabilidade de sistemas LIT 𝑯(𝒛) Um sistema ℎ[𝑛] causal é nula para 𝑛 < 0, ou seja, ℎ[𝑛] é lateral direita. Se 𝐻(𝑧) possuir qualquer potência positiva de 𝒛, ele não é causal. Exemplo: ℎ 𝑛 = 𝛿 𝑛 + 1 ՞ 𝑍 z O sistema abaixo também não é causal por que o polinômio do numerador tem ordem mais alta (𝑧3) que do denominador (𝑧2): 𝐻 𝑧 = 𝒛𝟑−3𝑧2+𝑧 𝑧2+1 4𝑧+1 8 Este possui mesma ordem. É causal se a RDC for maior que maior polo. 𝐻 𝑧 = 3𝑧2+𝑧 𝒛−𝟏 𝟑 𝒛−𝟏 𝟐 Análise de Sistemas LIT usando T.Z Um sistema LIT 𝑯(𝒛) é causal se e somente se a RDC for exterior de um círculo que inclui o polo de maior raio, caso seja racional, e se o grau do polinômio do numerador é menor que o grau do denominador. EL36F Transmissão de Dados 44 Estabilidade de sistemas LIT 𝑯(𝒛) Um sistema ℎ[𝑛] é estável se sua resposta ao impulso é absolutamente somável, e, em consequência, a T.F 𝐻(𝑒𝑗𝜔) converge. Logo, um sistema LIT é estável se e somente se a RDC incluir a circunferência unitária. Análise de Sistemas LIT usando T.Z Um sistema pode ser estável e não causal, como o sistema do plano z ao lado, pois é a soma de dois sistemas laterais esquerdo e direito. → EL36F Transmissão de Dados 45 Estabilidade de sistemas LIT 𝑯(𝒛) Um sistema ℎ[𝑛] é estável se sua resposta ao impulso é absolutamente somável, e, em consequência, a T.F 𝐻(𝑒𝑗𝜔) converge. Logo, um sistema LIT é estável se e somente se a RDC incluir a circunferência unitária. Análise de Sistemas LIT usando T.Z Um sistema pode ser estável e não causal, como o sistema do plano z ao lado, pois é a soma de dois sistemas laterais esquerdo e direito. → Um sistema LIT causal é estável se e somente se todos os polos estiverem dentro do círculo unitário. Exemplo de sistema causal e estável → EL36F Transmissão de Dados 46 Equações de diferenças em sistemas LIT Exemplo 10.25 Opp 𝑦 𝑛 − 1 2 𝑦 𝑛 − 1 = 𝑥 𝑛 + 1 3 𝑥 𝑛 − 1 𝑌 𝑧 − 1 2 𝑧−1𝑌 𝑧 = 𝑋 𝑧 + 1 3 𝑧−1𝑋 𝑧 1 − 1 2 𝑧−1 𝑌 𝑧 = 𝑋 𝑧 1 + 1 3 𝑧−1 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = 1 + 1 3 𝑧−1 1 − 1 2 𝑧−1 = 1 1 − 1 2 𝑧−1 + 1 3 z−1 1 − 1 2 𝑧−1 Porém, equações de diferenças não possuem informação de RDC. Informação de causabilidade e estabilidade ajudam a identificar a RDC: • Se o sistema for causal: RDC está fora do polo mais externo. • Se o sistema for estável: RDC inclui circunferência unitária. Análise de Sistemas LIT usando T.Z EL36F Transmissão de Dados 47 Equações de diferenças em sistemas LIT Exemplo 10.25 Opp 𝑦 𝑛 − 1 2 𝑦 𝑛 − 1 = 𝑥 𝑛 + 1 3 𝑥 𝑛 − 1 𝑌 𝑧 − 1 2 𝑧−1𝑌 𝑧 = 𝑋 𝑧 + 1 3 𝑧−1𝑋 𝑧 1 − 1 2 𝑧−1 𝑌 𝑧 = 𝑋 𝑧 1 + 1 3 𝑧−1 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = 1 + 1 3 𝑧−1 1 − 1 2 𝑧−1 = 1 1 − 1 2 𝑧−1 + 1 3 𝒛−𝟏 1 1 − 1 2 𝑧−1 Vamos supor que ℎ[𝑛] é causal: ℎ 𝑛 = 1 2 𝑛 𝑢 𝑛 + 1 3 1 2 𝑛−1 𝑢 𝑛 − 1 , 𝑧 > 1/2 Análise de Sistemas LIT usando T.Z EL36F Transmissão de Dados 48 Equações de diferenças em sistemas LIT Logo, a T.Z genérica para equações de diferenças é: ෍ 𝑘=0 𝑁 𝑎𝑘𝑦[𝑛 − 𝑘] = ෍ 𝑘=0 𝑀 𝑏𝑘𝑥[𝑛 − 𝑘] ෍ 𝑘=0 𝑁 𝑎𝑘𝑧−𝑘𝑌(𝑧) = ෍ 𝑘=0 𝑀 𝑏𝑘𝑧−𝑘𝑋(𝑧) 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 Análise de Sistemas LIT usando T.Z EL36F Transmissão de Dados 49 Tópicos • Transformada Z • Propriedades da região de convergência (RDC) • Transforma Z inversa • Propriedades da transformada Z • Análise de Sistemas LIT usando transformada Z • Diagrama de blocos EL36F Transmissão de Dados 50 Vamos analisar um exemplo de conversão de um sistema causal 𝐻(𝑧) em um diagrama de blocos. Exemplo 10.28: 𝐻 𝑧 = 1 1−1 4𝑧−1, usando 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 obtemos 𝑏0 = 1, 𝑎0 = 1, 𝑎1 = − 1 4, logo 𝑎0𝑦 𝑛 + 𝑎1𝑦 𝑛 − 1 = 𝑏0𝑥[𝑛] 𝑦 𝑛 − 1 4 𝑦 𝑛 − 1 = 𝑥[𝑛] Diagrama de Blocos de T.Z EL36F Transmissão de Dados 51 Vamos analisar um exemplo de conversão de um sistema causal 𝐻(𝑧) em um diagrama de blocos. Exemplo 10.28: 𝐻 𝑧 = 1 1−1 4𝑧−1, usando 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 obtemos 𝑏0 = 1, 𝑎0 = 1, 𝑎1 = − 1 4, logo 𝑎0𝑦 𝑛 + 𝑎1𝑦 𝑛 − 1 = 𝑏0𝑥[𝑛] 𝑦 𝑛 − 1 4 𝑦 𝑛 − 1 = 𝑥[𝑛] 𝑦 𝑛 = 𝑥 𝑛 + 1 4 𝑦 𝑛 − 1 Diagrama de Blocos de T.Z 𝑦 𝑛 − 1 EL36F Transmissão de Dados 52 Exemplo 10.31: 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 𝐻 𝑧 = 1 − 7 4 𝑧−1 − 1 2 𝑧−2 1 + 1 4 𝑧−1 − 1 8 𝑧−2 = 1 1 + 1 4 𝑧−1 − 1 8 𝑧−2 1 − 7 4 𝑧−1 − 1 2 𝑧−2 𝑎0𝑦 𝑛 + 𝑎1𝑦 𝑛 − 1 + 𝑎2𝑦 𝑛 − 1 = 𝑏0𝑥 𝑛 + 𝑏1𝑥 𝑛 − 1 + 𝑏2𝑥[𝑛 − 2] 1𝑦 𝑛 = − 1 4 𝑦 𝑛 − 1 + 1 8 𝑦 𝑛 − 2 + 1𝑥 𝑛 − 7 4 𝑥 𝑛 − 1 − 1 2 𝑥 𝑛 − 2 Diagrama de Blocos de T.Z EL36F Transmissão de Dados 53 Exemplo 10.31: 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 𝐻 𝑧 = 1 − 7 4 𝑧−1 − 1 2 𝑧−2 1 + 1 4 𝑧−1 − 1 8 𝑧−2 = 1 1 + 1 4 𝑧−1 − 1 8 𝑧−2 1 − 7 4 𝑧−1 − 1 2 𝑧−2 𝑎0𝑦 𝑛 + 𝑎1𝑦 𝑛 − 1 + 𝑎2𝑦 𝑛 − 1 = 𝑏0𝑥 𝑛 + 𝑏1𝑥 𝑛 − 1 + 𝑏2𝑥[𝑛 − 2] 1𝑦 𝑛 = − 1 4 𝑦 𝑛 − 1 + 1 8 𝑦 𝑛 − 2 + 1𝑥 𝑛 − 7 4 𝑥 𝑛 − 1 − 1 2 𝑥 𝑛 − 2 Diagrama de Blocos de T.Z EL36F Transmissão de Dados 54 Exemplo 10.31: 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 𝐻 𝑧 = 1 − 7 4 𝑧−1 − 1 2 𝑧−2 1 + 1 4 𝑧−1 − 1 8 𝑧−2 = 1 1 + 1 4 𝑧−1 − 1 8 𝑧−2 1 − 7 4 𝑧−1 − 1 2 𝑧−2 𝑎0𝑦 𝑛 + 𝑎1𝑦 𝑛 − 1 + 𝑎2𝑦 𝑛 − 1 = 𝑏0𝑥 𝑛 + 𝑏1𝑥 𝑛 − 1 + 𝑏2𝑥[𝑛 − 2] 1𝑦 𝑛 = − 1 4 𝑦 𝑛 − 1 + 1 8 𝑦 𝑛 − 2 + 1𝑥 𝑛 − 7 4 𝑥 𝑛 − 1 − 1 2 𝑥 𝑛 − 2 Diagrama de Blocos de T.Z 𝑥 𝑛 − 1 𝑦 𝑛 − 1 𝑥 𝑛 − 2 𝑦 𝑛 − 2 Forma direta 1 EL36F Transmissão de Dados 55 Exemplo 10.31: 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 𝐻 𝑧 = 1 − 7 4 𝑧−1 − 1 2 𝑧−2 1 + 1 4 𝑧−1 − 1 8 𝑧−2 = 1 1 + 1 4 𝑧−1 − 1 8 𝑧−2 1 − 7 4 𝑧−1 − 1 2 𝑧−2 𝑎0𝑦 𝑛 + 𝑎1𝑦 𝑛 − 1 + 𝑎2𝑦 𝑛 − 1 = 𝑏0𝑥 𝑛 + 𝑏1𝑥 𝑛 − 1 + 𝑏2𝑥[𝑛 − 2] 1𝑦 𝑛 = − 1 4 𝑦 𝑛 − 1 + 1 8 𝑦 𝑛 − 2 + 1𝑥 𝑛 − 7 4 𝑥 𝑛 − 1 − 1 2 𝑥 𝑛 − 2 Diagrama de Blocos de T.Z Forma direta 2 EL36F Transmissão de Dados 56 Exemplo 10.31: 𝐻 𝑧 = 𝑌 𝑧 𝑋 𝑧 = σ𝑘=0 𝑀 𝑏𝑘𝑧−𝑘 σ𝑘=0 𝑁 𝑎𝑘𝑧−𝑘 𝐻 𝑧 = 1 − 7 4 𝑧−1 − 1 2 𝑧−2 1 + 1 4 𝑧−1 − 1 8 𝑧−2 = 1 1 + 1 4 𝑧−1 − 1 8 𝑧−2 1 − 7 4 𝑧−1 − 1 2 𝑧−2 𝑎0𝑦 𝑛 + 𝑎1𝑦 𝑛 − 1 + 𝑎2𝑦 𝑛 − 1 = 𝑏0𝑥 𝑛 + 𝑏1𝑥 𝑛 − 1 + 𝑏2𝑥[𝑛 − 2] 1𝑦 𝑛 = − 1 4 𝑦 𝑛 − 1 + 1 8 𝑦 𝑛 − 2 + 1𝑥 𝑛 − 7 4 𝑥 𝑛 − 1 − 1 2 𝑥 𝑛 − 2 Diagrama de Blocos de T.Z Forma direta 2 2022-1 EL36F – Processamento Digital de Sinais Prof. Eduardo Alves Hodgson hodgson@utfpr.edu.br Transformada de Fourier Discreta DFT e FFT UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ Câmpus Cornélio Procópio EL36F Transmissão de Dados 2 Vamos mudar para o livro: V. K. Ingle; J.G. Proakis, Digital Signal Processing Using MATLAB, 3rd Edition, Cengage, 2012. Texto mais simplificado e bem resumido para aulas mais específicas de PDS, como DFT e filtros digitais. Referências EL36F Transmissão de Dados 3 Tópicos • Série de Fourier Discreta - DFS • Transformada de Fourier Discreta - DFT • Propriedades da DFT • Transformada de Fourier Rápida - FFT • FFT com decimação no tempo Radix-2 EL36F Transmissão de Dados 4 Introdução • Transformada de Fourier discreta no tempo (DTFT) e transformada Z analisam sinais de tamanho infinito. • Análise de sinais periódicos em sistemas discretos práticos, como Matlab, DSP, etc., precisam ser truncadas e analisadas como sequências finitas. • Objetivo: serem numericamente computáveis. • Solução: transformada discreta no tempo, DFT e FFT. EL36F Transmissão de Dados 5 Série de Fourier discreta - DFS Considere que ෤𝑥 𝑛 é uma sequência periódica com período fundamental N: ෤𝑥 𝑛 = ෤𝑥[𝑛 + 𝑘𝑁] Já vimos antes que podemos representar ෤𝑥 𝑛 em uma série de Fourier discreta: ෤𝑥 𝑛 = ෍ 𝑘=<𝑁> 𝑎𝑘𝑒𝑗𝑘2𝜋 𝑁 𝑛 onde os coeficientes são obtidos com: 𝑎𝑘 = 1 𝑁 ෍ 𝑛=<𝑁> ෤𝑥 𝑛 𝑒−𝑗𝑘2𝜋 𝑁 𝑛 EL36F Transmissão de Dados 6 Série de Fourier discreta - DFS Considere que ෤𝑥 𝑛 é uma sequência periódica com período fundamental N: ෤𝑥 𝑛 = ෤𝑥[𝑛 + 𝑘𝑁] A representação de ෤𝑥 𝑛 em Série de Fourier Discreta (DFS) é: ෤𝑥 𝑛 = 1 𝑁 ෍ 𝑘=0 𝑁−1 ෨𝑋[𝑘]𝑒𝑗2𝜋 𝑁 𝑘𝑛 onde os coeficientes da DFS são: ෨𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 ෤𝑥 𝑛 𝑒−𝑗2𝜋 𝑁 𝑘𝑛 ෨𝑋 𝑘 também é periódico: ෨𝑋 𝑘 = ෨𝑋 𝑘 + 𝑁 EL36F Transmissão de Dados 7 Série de Fourier discreta - DFS Vamos utilizar 𝑊𝑁 = 𝑒−𝑗2𝜋 𝑁 para representar a exponencial complexa: Equação de análise da DFS: ෨𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 ෤𝑥 𝑛 𝑒−𝑗2𝜋 𝑁 𝑘𝑛 → ෨𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 ෤𝑥 𝑛 𝑊𝑁 𝑘𝑛 Equação de síntese da DFS ou DFS inversa: ෤𝑥 𝑛 = 1 𝑁 ෍ 𝑘=0 𝑁−1 ෨𝑋[𝑘]𝑒𝑗2𝜋 𝑁 𝑘𝑛 → ෤𝑥 𝑛 = 1 𝑁 ෍ 𝑘=0 𝑁−1 ෨𝑋 𝑘 𝑊𝑁 −𝑘𝑛 As operações de DFS e IDFS serão simplificadas para: ෨𝑋 𝑘 = DFS ෤𝑥 𝑛 ෤𝑥 𝑛 = IDFS[ ෨𝑋 𝑘 ] EL36F Transmissão de Dados 8 Série de Fourier discreta - DFS Exemplo Ingle 5.1: Encontre a DFS do sinal periódico: ෤𝑥 𝑛 = … , 0,1,2,3,0,1,2,3,0,1,2, … Vemos que 𝑁 = 4 e 𝑊𝑁 = 𝑒−𝑗2𝜋 4 = 𝑒−𝑗𝜋 2 = −𝑗 ෨𝑋 0 = ෍ 𝑛=0 3 ෤𝑥 𝑛 𝑊𝑁 0𝑛 = ෤𝑥 0 + ෤𝑥 1 + ෤𝑥 2 + ෤𝑥 3 = 0 + 1 + 2 + 3 = 6 ෨𝑋 1 = ෍ 𝑛=0 3 ෤𝑥 𝑛 𝑊𝑁 1𝑛 = ෍ 𝑛=0 3 ෤𝑥 𝑛 −𝑗 𝑛 = ෤𝑥 0 −𝑗 0 + ෤𝑥 1 −𝑗 1 + ෤𝑥 2 −𝑗 2 + ෤𝑥 3 −𝑗 3 ෨𝑋 1 = 0 − 1𝑗 − 2 + 3𝑗 = −2 + 2𝑗 EL36F Transmissão de Dados 9 Série de Fourier discreta - DFS Exemplo Ingle 5.1: Encontre a DFS do sinal periódico: ෤𝑥 𝑛 = … , 0,1,2,3,0,1,2,3,0,1,2, … Vemos que 𝑁 = 4 e 𝑊𝑁 = 𝑒−𝑗2𝜋 4 = 𝑒−𝑗𝜋 2 = −𝑗 ෨𝑋 0 = ෍ 𝑛=0 3 ෤𝑥 𝑛 𝑊𝑁 0𝑛 = ෤𝑥 0 + ෤𝑥 1 + ෤𝑥 2 + ෤𝑥 3 = 0 + 1 + 2 + 3 = 6 ෨𝑋 1 = ෍ 𝑛=0 3 ෤𝑥 𝑛 𝑊𝑁 1𝑛 = ෍ 𝑛=0 3 ෤𝑥 𝑛 −𝑗 𝑛 = ෤𝑥 0 −𝑗 0 + ෤𝑥 1 −𝑗 1 + ෤𝑥 2 −𝑗 2 + ෤𝑥 3 −𝑗 3 ෨𝑋 1 = 0 − 1𝑗 − 2 + 3𝑗 = −2 + 2𝑗 ෨𝑋 2 = ෍ 𝑛=0 3 ෤𝑥 𝑛 𝑊𝑁 2𝑛 = ෍ 𝑛=0 3 ෤𝑥 𝑛 −𝑗 2𝑛 = 0 −𝑗 0 + 1 −𝑗 2 + 2 −𝑗 4 + 3 −𝑗 6 = 2 ෨𝑋 3 = ෍ 𝑛=0 3 ෤𝑥 𝑛 𝑊𝑁 3𝑛 = ෍ 𝑛=0 3 ෤𝑥 𝑛 −𝑗 3𝑛 = −2 − 2𝑗 EL36F Transmissão de Dados 10 Série de Fourier discreta - DFS Livro do Ingle tem funções para calcular DFS usando vetores e matrizes. function [Xk] = dfs(xn,N) % Computes Discrete Fourier Series Coefficients % --------------------------------------------- % [Xk] = dfs(xn,N) % Xk = DFS coeff. array over 0 <= k <= N-1 % xn = One period of periodic signal over 0 <= n <= N-1 % N = Fundamental period of xn % n = [0:1:N-1]; % row vector for n k = [0:1:N-1]; % row vecor for k WN = exp(-j*2*pi/N); % Wn factor nk = n’*k; % creates a N by N matrix of nk values WNnk = WN .^ nk; % DFS matrix Xk = xn * WNnk; % row vector for DFS coefficients ෤𝐱 é um vetor, 𝐖𝑁 uma matriz e ෩𝐗 um vetor. ෩𝐗 = 𝐖𝑁 ෤𝐱 EL36F Transmissão de Dados 11 Série de Fourier discreta - DFS Exemplo 5.2 Ingle. Com ajuda do Matlab, foi obtido as DFS da onda quadrada de duração 𝐿 = 5 com período 𝑁 = 20. EL36F Transmissão de Dados 12 Série de Fourier discreta - DFS Exemplo 5.2 Ingle. Com ajuda do Matlab, foi obtido as DFS da onda quadrada de duração 𝐿 = 5 com período 𝑁 = 20. | ෨𝑋 𝑘 = 𝐿, 𝑘 = 0, ±𝑁, ±2𝑁 | ෨𝑋 𝑘 = sin 𝜋𝑘𝐿 𝑁 sin 𝜋𝑘 𝑁 , 𝑘 ≠ 0, ±𝑁, ±2𝑁 Aumentando 𝑁 de 20 para 40 e 60 vemos um pulso sinc com nulos em 𝑁/𝐿. EL36F Transmissão de Dados 13 Série de Fourier discreta - DFS Relação entre DFS e DTFT (T.F de tempo discreto) Considere a DTFT de um sinal 𝑥[𝑛] limitado em 0 ≤ 𝑛 ≤ 𝑁 − 1: 𝑋 𝑒𝑗𝜔 = ෍ 𝑛=0 𝑁−1 𝑥 𝑛 𝑒−𝑗𝜔𝑛 ෨𝑋 𝑘 = 𝑋 𝑒𝑗𝜔 |𝜔=2𝜋 𝑁 𝑘 = ෍ 𝑛=0 𝑁−1 ǁ𝑥 𝑛 𝑒−𝑗2𝜋 𝑁 𝑘𝑛 Ou seja, a DFS é uma versão amostrada da DTFT contínua nas frequências 𝜔𝑘 = 2𝜋 𝑁 𝑘. EL36F Transmissão de Dados 14 Série de Fourier discreta - DFS Relação entre DFS e DTFT (T.F de tempo discreto) Exemplo 5.3: Obtenha a DTFT de 𝑥 𝑛 = {0, 1, 2, 3}. Amostre em 𝜔𝑘 = 2𝜋 4 𝑘 e mostre que é igual a DFS. 𝑋 𝑒𝑗𝜔 = ෍ 𝑛=−∞ ∞ 𝑥 𝑛 𝑒−𝑗𝜔𝑛 = 𝑒−𝑗𝜔 + 2𝑒−𝑗2𝜔 + 3𝑒−𝑗3𝜔 Amostramos em 𝜔𝑘 = 2𝜋 4 𝑘 𝑋 𝑒𝑗0 = 1 + 2 + 3 = 6 = ෨𝑋 0 𝑋 𝑒𝑗2𝜋 4 = 𝑒−𝑗2𝜋 4 + 2𝑒−𝑗22𝜋 4 + 3𝑒−𝑗32𝜋 4 = −2 + 2𝑗 = ෨𝑋 1 𝑋 𝑒𝑗4𝜋 4 = 𝑒−𝑗4𝜋 4 + 2𝑒−𝑗24𝜋 4 + 3𝑒−𝑗34𝜋 4 = 2 = ෨𝑋 2 𝑋 𝑒𝑗6𝜋 4 = 𝑒−𝑗6𝜋 4 + 2𝑒−𝑗26𝜋 4 + 3𝑒−𝑗36𝜋 4 = −2 − 2𝑗 = ෨𝑋 3 EL36F Transmissão de Dados 15 Tópicos • Série de Fourier Discreta - DFS • Transformada de Fourier Discreta - DFT • Propriedades da DFT • Transformada de Fourier Rápida - FFT • FFT com decimação no tempo Radix-2 EL36F Transmissão de Dados 16 Transformada de Fourier discreta - DFT • DFS é utilizada para sinais periódicos. • A DFT é utilizada para uma sequência de 𝑁 amostras finitas não periódicas de 0 ≤ 𝑛 ≤ 𝑁 − 1, sendo nula para outros valores de 𝑛. Para calcular a DFT, usamos a DFS. Primeiro obtemos uma versão periódica de 𝑥 𝑛 , dado por ෤𝑥[𝑛]: ෤𝑥 𝑛 = ෍ 𝑟=∞ ∞ 𝑥[𝑛 − 𝑟𝑁] = 𝑥 𝑛 mod 𝑁 EL36F Transmissão de Dados 17 Transformada de Fourier discreta - DFT • DFS é utilizada para sinais periódicos. • A DFT é utilizada para uma sequência de 𝑁 amostras finitas não periódicas de 0 ≤ 𝑛 ≤ 𝑁 − 1, sendo nula para outros valores de 𝑛. Para calcular a DFT, usamos a DFS. Primeiro obtemos uma versão periódica de 𝑥 𝑛 , dado por ෤𝑥[𝑛]: ෤𝑥 𝑛 = ෍ 𝑟=∞ ∞ 𝑥[𝑛 − 𝑟𝑁] = 𝑥 𝑛 mod 𝑁 ෤𝑥 𝑛 = 𝑥 𝑛 mod 𝑁 = 𝑥 𝑛 𝑁 A operação módulo-N (𝑛 mod 𝑁) retorna um valor de 𝑛 entre 0 ≤ 𝑛 ≤ 𝑁 − 1. Logo: • ෤𝑥 𝑛 = 𝑥 𝑛 𝑁 : extensão periódica de 𝑥 𝑛 de período 𝑁 • 𝑥 𝑛 = ෤𝑥 𝑛 ℛ𝑁[𝑛]: janelamento de tamanho 𝑵 ou seja, zera amplitudes fora de 0 ≤ 𝑛 ≤ 𝑁 − 1. EL36F Transmissão de Dados 18 Transformada de Fourier discreta - DFT A DFT 𝑋 𝑘 de 𝑥 𝑛 é definida por 𝑋 𝑘 = DFT 𝑥 𝑛 = ෨𝑋 𝑘 ℛ𝑁 𝑛 = ቊ ෨𝑋 𝑘 , 0 ≤ 𝑘 ≤ 𝑁 − 1 0, outros valores • Ou seja, a DFT 𝑋 𝑘 só existe para 0 ≤ 𝑘 ≤ 𝑁 − 1, sendo 𝑊𝑁 = 𝑒−𝑗2𝜋 𝑁 : 𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 𝑥 𝑛 𝑊𝑁 𝑘𝑛 , 0 ≤ 𝑘 ≤ 𝑁 − 1 • A IDFT 𝑥 𝑘 𝑥 𝑘 = 1 𝑁 ෍ 𝑘=0 𝑁−1 𝑋 𝑘 𝑊𝑁 −𝑘𝑛 = ǁ𝑥 𝑛 ℛ𝑁 𝑛 , 0 ≤ 𝑛 ≤ 𝑁 − 1 EL36F Transmissão de Dados 19 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1 (a) Obtenha a DTFT 𝑋(𝑒𝑗𝜔) (b) Obtenha 𝑋[𝑘] de 4 amostras. 𝑋 𝑒𝑗𝜔 = ෍ 𝑛=0 3 𝑥[𝑛] 𝑒−𝑗𝜔𝑛 = 1 + 𝑒−𝑗𝜔 + 𝑒−𝑗2𝜔 + 𝑒−𝑗3𝜔 EL36F Transmissão de Dados 20 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1 (a) Obtenha a DTFT 𝑋(𝑒𝑗𝜔) (b) Obtenha 𝑋[𝑘] de 4 amostras. 𝑋 𝑒𝑗𝜔 = ෍ 𝑛=0 3 𝑥[𝑛] 𝑒−𝑗𝜔𝑛 = 1 + 𝑒−𝑗𝜔 + 𝑒−𝑗2𝜔 + 𝑒−𝑗3𝜔 ⋅ 1 − 𝑒−𝑗𝜔 1 − 𝑒−𝑗𝜔 = 1 − 𝑒−4𝑗𝜔 1 − 𝑒−𝑗𝜔 𝑋 𝑒𝑗𝜔 = sin 2𝜔 sin 𝜔/2 𝑒−𝑗3𝜔/2; 𝑋 𝑒𝑗𝜔 = sin 2𝜔 sin 𝜔 2 ; ∠𝑋 𝑒𝑗𝜔 = − 3𝜔 2 ±𝜋 𝑠𝑒 sin 2𝜔 sin 𝜔 2 < 0 EL36F Transmissão de Dados 21 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1 (b) Obtenha 𝑋[𝑘] de 4 amostras. 𝑋 𝑘 = ෍ 𝑛=0 3 𝑥 𝑛 𝑊4 𝑘𝑛 , 𝑊4 = 𝑒−𝑗2𝜋 4 = −𝑗 EL36F Transmissão de Dados 22 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1 (b) Obtenha 𝑋[𝑘] de 4 amostras. 𝑋 𝑘 = ෍ 𝑛=0 3 𝑥 𝑛 𝑊4 𝑘𝑛 , 𝑊4 = 𝑒−𝑗2𝜋 4 = −𝑗 𝑋 0 = ෍ 𝑛=0 3 𝑥 𝑛 𝑊4 0𝑛 = 𝑥 0 + 𝑥 1 + 𝑥 2 + 𝑥 3 = 4 𝑋 1 = ෍ 𝑛=0 𝑁−1 1 −𝑗 𝑛 = −𝑗 0 + −𝑗 1 + −𝑗 2 + −𝑗 3 = 1 − 𝑗 − 1 + 𝑗 = 0 𝑋 2 = ෍ 𝑛=0 𝑁−1 1 −𝑗 2𝑛 = −𝑗 0 + −𝑗 2 + −𝑗 4 + −𝑗 6 = 1 − 1 + 1 − 1 = 0 𝑋 3 = ෍ 𝑛=0 𝑁−1 1 −𝑗 2𝑛 = 0 EL36F Transmissão de Dados 23 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1 (b) Obtenha 𝑋[𝑘] de 4 amostras. 𝑋 𝑘 = ෍ 𝑛=0 3 𝑥 𝑛 𝑊4 𝑘𝑛 , 𝑊4 = 𝑒−𝑗2𝜋 4 = −𝑗 𝑋 𝑘 = {4, 0, 0, 0} |𝑋 𝑒𝑗𝜔 | -- |𝑋 𝑘 | o EL36F Transmissão de Dados 24 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1, 0, 0,0, 0 (b) Obtenha 𝑋[𝑘] de 8 amostras. 𝑋 𝑘 = ෍ 𝑛=0 8 𝑥 𝑛 𝑊8 𝑘𝑛 , 𝑊8 = 𝑒−𝑗2𝜋 8 Operação zero-padding: Preenchimento de zeros em uma sequência 𝑥[𝑛] aumenta o número de amostras da DFT 𝑋[𝑘], ficando cada vez mais similar à DTFT 𝑋(𝑒𝑗𝜔). EL36F Transmissão de Dados 25 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1, 0, 0,0, 0 (b) Obtenha 𝑋[𝑘] de 8 amostras. 𝑋 𝑘 = ෍ 𝑛=0 8 𝑥 𝑛 𝑊8 𝑘𝑛 , 𝑊8 = 𝑒−𝑗2𝜋 8 >>abs(fft([1 1 1 1 0 0 0 0])) ans = 4.00000 2.61313 0.00000 1.08239 0.00000 1.08239 0.00000 2.61313 >>angle(fft([1 1 1 1 0 0 0 0]))*180/pi ans = 0.00000 -67.50000 0.00000 -22.5000 0.00000 22.50000 -0.00000 67.5000 EL36F Transmissão de Dados 26 Transformada de Fourier discreta - DFT Exemplo 5.6 Considere a sequência 𝑥 𝑛 = 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0 (b) Obtenha 𝑋[𝑘] de 16 amostras. 𝑋 𝑘 = ෍ 𝑛=0 16 𝑥 𝑛 𝑊16 𝑘𝑛 , Operação zero-padding: Preenchimento de zeros em uma sequência 𝑥[𝑛] aumenta o número de amostras da DFT 𝑋[𝑘], ficando cada vez mais similar à DTFT 𝑋(𝑒𝑗𝜔). EL36F Transmissão de Dados 27 Transformada de Fourier discreta - DFT Exemplo 5.8 𝑥 𝑛 = cos(0,48𝜋𝑛) + cos(0,52𝜋𝑛) (a) Obtenha a DFT para 0 ≤ 𝑛 ≤ 10; (b) Obtenha a DFT para 0 ≤ 𝑛 ≤ 100. a) 𝑋[𝑘] possui apenas 10 amostras. Vamos preencher zero para ver se melhora essa DFT. EL36F Transmissão de Dados 28 Transformada de Fourier discreta - DFT Exemplo 5.8 𝑥 𝑛 = cos(0,48𝜋𝑛) + cos(0,52𝜋𝑛) (a) Obtenha a DFT para 0 ≤ 𝑛 ≤ 10; (b) Obtenha a DFT para 0 ≤ 𝑛 ≤ 100. Preencher zeros aumenta o número de amostras na DFT, mas não vemos as frequências de 0,48𝜋 e 0,52𝜋 rad. Ou seja, não vemos dois impulsos nestas frequências. EL36F Transmissão de Dados 29 Transformada de Fourier discreta - DFT Solução: aumentar o número de amostras de 𝑥 𝑛 de 10 para 100 amostras. • Conclusões: 1) Zero-padding só aumenta a densidade da DFT, ou seja, apenas melhora o plot da DFT. 2) Para aumentar a resolução da DFT temos que aumentar o tamanho da sequência 𝑥[𝑛]. Exemplo 5.8 𝑥 𝑛 = cos(0,48𝜋𝑛) + cos(0,52𝜋𝑛) (a) Obtenha a DFT para 0 ≤ 𝑛 ≤ 10; (b) Obtenha a DFT para 0 ≤ 𝑛 ≤ 100. EL36F Transmissão de Dados 30 Tópicos • Série de Fourier Discreta - DFS • Transformada de Fourier Discreta - DFT • Propriedades da DFT • Transformada de Fourier Rápida - FFT • FFT com decimação no tempo Radix-2 EL36F Transmissão de Dados 31 Propriedades da DFT Linearidade: DFT 𝛼𝑥1[𝑛] + 𝛽𝑥2[𝑛] = 𝛼DFT 𝑥1[𝑛] + 𝛽DFT[𝑥2[𝑛]] Dobramento circular: Usamos a operação módulo-𝑁 para obter 𝑥 −𝑛 𝑁 𝑥 −𝑛 𝑁 ቊ 𝑥 0 , 𝑛 = 0 𝑥[𝑁 − 𝑛], 1 ≤ 𝑛 ≤ 𝑁 − 1 Ex: 𝑥 −𝑛 11 𝑥 −𝑛 𝑁 𝑥[𝑛] EL36F Transmissão de Dados 32 Propriedades da DFT Conjugação: DFT 𝑥∗ 𝑛 = 𝑋∗ −𝑘 𝑁 Logo, se 𝑥[𝑛] é real temos a simetria circular conjugada 𝑋 𝑘 𝑁 = 𝑋∗ −𝑘 𝑁 Ver exemplo 5.6 Re 𝑋 𝑘 = Re[𝑋 −𝑘 𝑁] sequência circular par Im 𝑋 𝑘 = −Im[𝑋 𝑁 − 𝑘 𝑁] sequência circular ímpar |𝑋 𝑘 | = |𝑋 −𝑘 𝑁| sequência circular par ∠𝑋 𝑘 = −∠𝑋 −𝑘 𝑁 sequência circular ímpar EL36F Transmissão de Dados 33 Propriedades da DFT Deslocamento circular: (1) Converter a sequência 𝑥[𝑛] DFT em ෤𝑥[𝑛] DFS: 𝑥 𝑛 = ෤𝑥 𝑛 ℛ𝑁[𝑛] (2) deslocar a sequência ෤𝑥 𝑛 : ෤𝑥 𝑛 − 𝑚 = 𝑥 𝑛 − 𝑚 𝑁 (3) converter ෤𝑥 𝑛 em 𝑥 𝑛 : 𝑥 𝑛 = ෤𝑥 𝑛 ℛ𝑁[𝑛] Exemplo 5.11 𝑥 𝑛 = 10 0,8 𝑛, 0 ≤ 𝑛 ≤ 10 (a) Obtenha 𝑥 𝑛 + 4 11ℛ11[𝑛] EL36F Transmissão de Dados 34 Propriedades da DFT Deslocamento circular: (1) Converter a sequência 𝑥[𝑛] DFT em ෤𝑥[𝑛] DFS: 𝑥 𝑛 = ෤𝑥 𝑛 ℛ𝑁[𝑛] (2) deslocar a sequência ෤𝑥 𝑛 : ෤𝑥 𝑛 − 𝑚 = 𝑥 𝑛 − 𝑚 𝑁 (3) converter ෤𝑥 𝑛 em 𝑥 𝑛 : 𝑥 𝑛 = ෤𝑥 𝑛 ℛ𝑁[𝑛] Exemplo 5.11 𝑥 𝑛 = 10 0,8 𝑛, 0 ≤ 𝑛 ≤ 10 (b) Obtenha 𝑥 𝑛 − 3 15ℛ15[𝑛] EL36F Transmissão de Dados 35 Propriedades da DFT Deslocamento circular na frequência: Dual do deslocamento circular no tempo DFT[𝑊𝑁 −𝑙𝑛 𝑥[𝑛]] = 𝑋 𝑘 − 𝑙 𝑁ℛ𝑁[𝑛] Convolução circular: A multiplicação das sequências na frequência é igual a DFT da convolução circular no tempo: DFT 𝑥1 𝑛 ◯𝑥2 𝑛 = 𝑋1 𝑘 𝑋2[𝑘] 𝑥1 𝑛 ◯𝑥2 𝑛 = ෍ 𝑚=0 𝑁−1 𝑥1 𝑚 𝑥2 𝑛 − 𝑚 𝑁 , 0 ≤ 𝑛 ≤ 𝑁 − 1 𝑁 𝑁 EL36F Transmissão de Dados 36 Propriedades da DFT Exemplo 5.13 Obtenha a convolução circular de 𝑁 = 4 pontos entre 𝑥1 𝑛 = {1, 2, 2} e 𝑥2 𝑛 = {1, 2, 3, 4}. R: Primeiro fazemos 𝑥1 𝑛 = {1, 2, 2, 0} 𝑥1 𝑛 ◯𝑥2 𝑛 = ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 𝑛 − 𝑚 4 ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 0 − 𝑚 4 = ෍ 𝑚=0 3 1, 2, 2, 0 ⋅ 𝟏, 𝟒, 𝟑, 𝟐 = ෍ 𝑚=0 3 1, 8, 6, 0 = 15 4 𝑥2 −𝑚 4 EL36F Transmissão de Dados 37 Propriedades da DFT Exemplo 5.13 Obtenha a convolução circular de 𝑁 = 4 pontos entre 𝑥1 𝑛 = {1, 2, 2} e 𝑥2 𝑛 = {1, 2, 3, 4}. R: Primeiro fazemos 𝑥1 𝑛 = {1, 2, 2, 0} 𝑥1 𝑛 ◯𝑥2 𝑛 = ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 𝑛 − 𝑚 4 ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 0 − 𝑚 4 = ෍ 𝑚=0 3 1, 2, 2, 0 ⋅ 𝟏, 𝟒, 𝟑, 𝟐 = ෍ 𝑚=0 3 1, 8, 6, 0 = 15 ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 𝟏 − 𝑚 4 = ෍ 𝑚=0 3 1, 2, 2, 0 ⋅ 𝟐, 𝟏, 𝟒, 𝟑 = ෍ 𝑚=0 3 2, 2, 8, 0 = 12 ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 𝟐 − 𝑚 4 = ෍ 𝑚=0 3 1, 2, 2, 0 ⋅ 𝟑, 𝟐, 𝟏, 𝟒 = ෍ 𝑚=0 3 3, 4, 2, 0 = 9 ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 𝟑 − 𝑚 4 = ෍ 𝑚=0 3 1, 2, 2, 0 ⋅ 𝟒, 𝟑, 𝟐, 𝟏 = ෍ 𝑚=0 3 4, 6,4, 0 = 14 4 𝑥2 −𝑚 4 EL36F Transmissão de Dados 38 Propriedades da DFT Exemplo 5.13 Obtenha a convolução circular de 𝑁 = 4 pontos entre 𝑥1 𝑛 = {1, 2, 2} e 𝑥2 𝑛 = {1, 2, 3, 4}. R: Primeiro fazemos 𝑥1 𝑛 = {1, 2, 2, 0} 𝑥1 𝑛 ◯𝑥2 𝑛 = ෍ 𝑚=0 3 𝑥1 𝑚 𝑥2 𝑛 − 𝑚 4 𝑥1 𝑛 ◯𝑥2 𝑛 = {15, 12, 9, 14} • No Matlab se usa a função circular convolution: cconv(x1,x2,N) cconv([1,2,2],[1,2,3,4],4) ans = 15 12 9 14 • Obtemos o mesmo resultado multiplicando os sinais na frequência: > ifft(fft([1,2,2]).*fft([1,2,3,4])) ans = 15 12 9 14 4 4 EL36F Transmissão de Dados 39 Propriedades da DFT Exemplo 5.15 Vamos aumentar o valor de 𝑁 do mesmo exemplo para 5, 6 e 7. cconv([1,2,2],[1,2,3,4],4); ans = 15 12 9 14 cconv([1,2,2],[1,2,3,4],5); ans = 9 4 9 14 14 cconv([1,2,2],[1,2,3,4],6); ans = 1 4 9 14 14 8 cconv([1,2,2],[1,2,3,4],7); ans = 1 4 9 14 14 8 0 Note que a primeira amostra 9 do 𝑁 = 5 é a soma de 1 + 8 do 𝑁 = 6. É como se houvesse um aliasing circular das amostras do 𝑁 = 6. No 𝑁 = 4, obtemos também 12 = 4 + 8 e 15 = 14 + 1. EL36F Transmissão de Dados 40 Propriedades da DFT Exemplo 5.15 Vamos aumentar o valor de 𝑁 do mesmo exemplo para 5, 6 e 7. cconv([1,2,2],[1,2,3,4],4); ans = 15 12 9 14 cconv([1,2,2],[1,2,3,4],6); ans = 1 4 9 14 14 8 Note que 𝑥1 𝑛 ∗ 𝑥2 𝑛 = 1, 4, 9, 14, 14, 8 é igual a 𝑥1 𝑛 ◯𝑥2 𝑛 . Considere que 𝑥1 𝑛 tem tamanho 𝑁1 e 𝑥2 𝑛 tem tamanho 𝑁2. A convolução circular de 𝑥1 𝑛 e 𝑥2 𝑛 terá o tamanho mínimo 𝑁𝑐 = 𝑚á𝑥 𝑁1, 𝑁2 . Neste exemplo, 𝑁𝑐 = 𝑚á𝑥 3,4 = 4. • A saída da convolução circular será igual a 𝑁𝑐 = 4 amostras da convolução linear das versões periódicas de 𝑥1[𝑛] e 𝑥2[𝑛], que são ෤𝑥1 𝑛 e ෤𝑥2 𝑛 . 𝑥1 𝑛 ◯𝑥2 𝑛 = (෤𝑥1 𝑛 ∗ ෤𝑥2 𝑛 )ℛ𝑁𝑐[𝑛] • Se aumentarmos 𝑁 na convolução circular para 𝑁𝐿 = 𝑁1 + 𝑁2 − 1, (ou 𝑁 = 6 neste exemplo), preenchemos zeros em 𝑥1[𝑛] e 𝑥2[𝑛] e o resultado será o mesmo da convolução linear: 𝑥1 𝑛 ◯𝑥2 𝑛 = 𝑥1 𝑛 ∗ 𝑥2 𝑛 6 𝑁𝑐 𝑁𝐿 EL36F Transmissão de Dados 41 Propriedades da DFT Multiplicação: Dual da convolução. DFT 𝑥1 𝑛 ⋅ 𝑥2 𝑛 = 1 𝑁 𝑋1 𝑘 ◯𝑋2[𝑘] Relação de Parseval: 𝐸𝑥 = ෍ 𝑛=0 𝑁−1 𝑥 𝑛 2 = 1 𝑁 ෍ 𝑘=0 𝑁−1 𝑋 𝑘 2 𝑁 EL36F Transmissão de Dados 42 Tópicos • Série de Fourier Discreta - DFS • Transformada de Fourier Discreta - DFT • Propriedades da DFT • Transformada de Fourier Rápida - FFT • FFT com decimação no tempo Radix-2 EL36F Transmissão de Dados 43 Transformada de Fourier rápida FFT Considere a DFT de uma sequência de 𝑁 pontos abaixo, onde 𝑊𝑁 = 𝑒−𝑗2𝜋 𝑁 𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 𝑥 𝑛 𝑊𝑁 𝑘𝑛 A DFT requer 𝑁 multiplicações complexas e 𝑁 − 1 somas complexas para cada amostra de 𝑋 𝑘 . Além de armazenar (ou calcular) 𝑁2 coeficientes 𝑊𝑁 𝑘𝑛. A complexidade computacional será focada nas multiplicações. Para a DFT, é representada por: 𝐶𝑁 = 𝑜 𝑁2 EL36F Transmissão de Dados 44 Transformada de Fourier rápida FFT Algoritmos de FFT exploram as seguintes propriedades de 𝑊𝑁 = 𝑒−𝑗2𝜋 𝑁 : • Propriedade da periodicidade 𝑊𝑁 𝑘𝑛 = 𝑊𝑁 𝑘(𝑛+𝑁) = 𝑊𝑁 (𝑘+𝑁)𝑛 • Propriedade da simetria 𝑊𝑁 𝑘𝑛+𝑁/2 = −𝑊𝑁 𝑘𝑛 Alguns algoritmos de FFT: • Goertzel (1958): bem simples. • Decimação no tempo Radix-2 • Decimação no frequência Radix-2 EL36F Transmissão de Dados 45 Tópicos • Série de Fourier Discreta - DFS • Transformada de Fourier Discreta - DFT • Propriedades da DFT • Transformada de Fourier Rápida - FFT • FFT com decimação no tempo Radix-2 EL36F Transmissão de Dados 46 A. V. Oppenheim, R. W. Schafer and J. R. Buck, Discrete-Time Signal Processing, 2nd Edition, Prentice-Hall, 1998. Para o algoritmo de decimação no tempo Radix-2 usei também o livro de PDS do Oppenheim, capítulo 9.3. FFT com decimação no tempo Radix-2 EL36F Transmissão de Dados 47 FFT com decimação no tempo Radix-2 Considere que 𝑁 = 2𝑣. Dividimos 𝑥[𝑛] em duas sequências de tamanho 𝑀 = 𝑁/2. Objetivo: dividir DFT em duas DFTs de tamanho 𝑁/2. 𝑔 𝑛 = 𝑥 2𝑛 ℎ 𝑛 = 𝑥 2𝑛 + 1 ; 0 ≤ 𝑛 ≤ 𝑁 2 − 1 𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 𝑥 𝑛 𝑊𝑁 𝑘𝑛 = ෍ 𝑛=0 𝑁 2−1 𝑥 2𝑛 𝑊𝑁 2𝑛𝑘 + ෍ 𝑛=0 𝑁 2−1 𝑥 2𝑛 + 1 𝑊𝑁 (2𝑛+1)𝑘 EL36F Transmissão de Dados 48 FFT com decimação no tempo Radix-2 Considere que 𝑁 = 2𝑣. Dividimos 𝑥[𝑛] em duas sequências de tamanho 𝑀 = 𝑁/2. Objetivo: dividir DFT em duas DFTs de tamanho 𝑁/2. 𝑔 𝑛 = 𝑥 2𝑛 ℎ 𝑛 = 𝑥 2𝑛 + 1 ; 0 ≤ 𝑛 ≤ 𝑁 2 − 1 𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 𝑥 𝑛 𝑊𝑁 𝑘𝑛 = ෍ 𝑛=0 𝑁 2−1 𝑥 2𝑛 𝑊𝑁 2𝑛𝑘 + ෍ 𝑛=0 𝑁 2−1 𝑥 2𝑛 + 1 𝑊𝑁 (2𝑛+1)𝑘 • 𝑊𝑁 2 = 𝑒−𝑗22𝜋 𝑁 = 𝑒 −𝑗 2𝜋 𝑁/2 = 𝑊𝑁/2. 𝑋 𝑘 = ෍ 𝑛=0 𝑁 2−1 𝑔 𝑛 𝑊𝑁/2 𝑛𝑘 + 𝑊𝑁 𝑘 ෍ 𝑛=0 𝑁 2−1 ℎ 𝑛 𝑊𝑁/2 𝑛𝑘 EL36F Transmissão de Dados 49 FFT com decimação no tempo Radix-2 Considere que 𝑁 = 2𝑣. Dividimos 𝑥[𝑛] em duas sequências de tamanho 𝑀 = 𝑁/2. Objetivo: dividir DFT em duas DFTs de tamanho 𝑁/2. 𝑔 𝑛 = 𝑥 2𝑛 ℎ 𝑛 = 𝑥 2𝑛 + 1 ; 0 ≤ 𝑛 ≤ 𝑁 2 − 1 𝑋 𝑘 = ෍ 𝑛=0 𝑁−1 𝑥 𝑛 𝑊𝑁 𝑘𝑛 = ෍ 𝑛=0 𝑁 2−1 𝑥 2𝑛 𝑊𝑁 2𝑛𝑘 + ෍ 𝑛=0 𝑁 2−1 𝑥 2𝑛 + 1 𝑊𝑁 (2𝑛+1)𝑘 • 𝑊𝑁 2 = 𝑒−𝑗22𝜋 𝑁 = 𝑒 −𝑗 2𝜋 𝑁/2 = 𝑊𝑁/2. 𝑋 𝑘 = ෍ 𝑛=0 𝑁 2−1 𝑔 𝑛 𝑊𝑁/2 𝑛𝑘 + 𝑊𝑁 𝑘 ෍ 𝑛=0 𝑁 2−1 ℎ 𝑛 𝑊𝑁/2 𝑛𝑘 • 𝐺 𝑘 = FFT[𝑔[𝑛]] e 𝐻 𝑘 = FFT[ℎ[𝑛]], 𝑘 = 0,1, … , 𝑁/2 − 1 𝑋 𝑘 = 𝐺 𝑘 𝑁/2 + 𝑊𝑁 𝑘𝐻 𝑘 𝑁/2 , 𝑘 = 0,1, … , 𝑁 − 1 EL36F Transmissão de Dados 50 FFT com decimação no tempo Radix-2 Considere que 𝑁 = 2𝑣. Dividimos 𝑥[𝑛] em duas sequências de tamanho 𝑀 = 𝑁/2. Objetivo: dividir DFT em duas DFTs de tamanho 𝑁/2. 𝑋 𝑘 = 𝐺 𝑘 𝑁/2 + 𝑊𝑁 𝑘𝐻 𝑘 𝑁/2 DFT de 𝑁 pontos 𝐶𝑁 = 𝑜 𝑁2 • Duas DFTs de 𝑁/2 pontos 𝐶𝑁 = 𝑁2 2 + 𝑁 = 𝑜 𝑁2/2 EL36F Transmissão de Dados 51 FFT com decimação no tempo Radix-2 Considere que 𝑁 = 2𝑣. Dividimos 𝑥[𝑛] em duas sequências de tamanho 𝑀 = 𝑁/2. Objetivo: dividir DFT em duas DFTs de tamanho 𝑁/2. 𝑋 𝑘 = 𝐺 𝑘 𝑁/2 + 𝑊𝑁 𝑘𝐻 𝑘 𝑁/2 DFT de 𝑁 pontos 𝐶𝑁 = 𝑜 𝑁2 • Duas DFTs de 𝑁/2 pontos 𝐶𝑁 = 𝑁2 2 + 𝑁 = 𝑜 𝑁2/2 Esta decimação em 𝑁/2 pode ser repetida 𝑣 vezes até obtermos DFTs de 𝑁 = 1 ponto. No total teremos 𝑣 = log2𝑁 estágios de decomposição e 𝑁/2 multiplicações. A ordem da complexidade será: 𝐶𝑁 = 𝑁 2 𝑣 = 𝑜 𝑁 2 log2𝑁 Para 𝑁 muito grande, 𝑜 𝑁2 é inviável. Já 𝑜 𝑁 2 log2𝑁 é praticamente linear. EL36F Transmissão de Dados 52 FFT com decimação no tempo Radix-2 Fluxograma 𝑵 = 𝟖 𝑋 𝑘 = 𝐺 𝑘 𝑁/2 + 𝑊𝑁 𝑘𝐻 𝑘 𝑁/2 𝑋[0] = 𝐺 0 + 𝑊𝑁 0𝐻 0 𝑋 4 = 𝐺 4 4 + 𝑊𝑁 4𝐻 4 4 𝑋[4] = 𝐺 0 + 𝑊𝑁 4𝐻 0 EL36F Transmissão de Dados 53 FFT com decimação no tempo Radix-2 Fluxograma 𝑵 = 𝟖. Os blocos “𝑁/2 DFT” são divididos em blocos “𝑁/4 DFT” 𝐺 𝑘 = 𝐺1 𝑘 𝑁/4 + 𝑊𝑁/2 𝑘 𝐻1 𝑘 𝑁/4 𝐺1 0 𝐺1 1 𝐻1 0 𝐻1 1 EL36F Transmissão de Dados 54 FFT com decimação no tempo Radix-2 Fluxograma 𝑵 = 𝟖. Substituindo os blocos “𝑁/2 DFT”: Lembrando que 𝑊𝑁/2 = 𝑊𝑁 2, 𝑊𝑁/2 2 = 𝑊𝑁 4, etc. EL36F Transmissão de Dados 55 FFT com decimação no tempo Radix-2 Fluxograma 𝑵 = 𝟖. Bloco “𝑁/4 DFT” é representado pela fluxograma conhecido como borboleta (à esquerda). Usando a simplificação abaixo 𝑊𝑁 𝑟+𝑁/2 = 𝑒−𝑗2𝜋 𝑁 𝑟+𝑁 2 = 𝑒−𝑗𝜋𝑒−𝑗2𝜋 𝑁 𝑟 = −𝑊𝑁 𝑟 reduzimos duas multiplicações em apenas uma. A troca de sinal muitas vezes é só trocar um bit de polaridade. EL36F Transmissão de Dados 56 FFT com decimação no tempo Radix-2 Fluxograma 𝑵 = 𝟖. Com 𝑊𝑁 𝑟+𝑁/2 = −𝑊𝑁 𝑟 obtemos o bloco “𝑁/4 DFT”. EL36F Transmissão de Dados 57 FFT com decimação na frequência Radix-2 É possível fazer também a decimação na frequência, quebrando 𝑋[𝑘] e duas equações 𝑋[2𝑟] e 𝑋 2𝑟 + 1 (cap. 9.4 Opp. DSP). As equações mudam, mas o conceito é basicamente o mesmo da decimação no tempo. EL36F Transmissão de Dados 58 FFT com decimação na frequência Radix-2 É possível fazer também a decimação na frequência, quebrando 𝑋[𝑘] e duas equações 𝑋[2𝑟] e 𝑋 2𝑟 + 1 (cap. 9.4 Opp. DSP). As equações mudam, mas o conceito é basicamente o mesmo da decimação no tempo. EL36F Transmissão de Dados 59 FFT com decimação na frequência Radix-2 É possível fazer também a decimação na frequência, quebrando 𝑋[𝑘] e duas equações 𝑋[2𝑟] e 𝑋 2𝑟 + 1 (cap. 9.4 Opp. DSP). As equações mudam, mas o conceito é basicamente o mesmo da decimação no tempo.