Cap5-slides

Prévia do material em texto

Transformada Discreta de Fourier (DFT) 
 A DFT de uma sequência 𝑥 𝑛 de comprimento finito 𝑁 é 
definida como: 
 
𝑋 𝑘 = 𝑥 𝑛 𝑒−𝑗
2𝜋
𝑁 𝑘𝑛
𝑁−1
𝑛=0
, 0 ≤ 𝑘 ≤ 𝑁 − 1 
 
 
 A DFT mapeia uma sequência de comprimento 𝑁, 𝑥 𝑛 , em outra 
sequência, 𝑋 𝑘 , também de comprimento 𝑁, cujas componentes 
correspondem a amostras igualmente espaçadas no eixo 𝜔 da DTFT 
desta sequência, ou seja: 
 
𝑋 𝑘 = 𝑋 𝑒𝑗𝜔 
𝜔=2𝜋𝑘 𝑁 
, 0 ≤ 𝑘 ≤ 𝑁 − 1 
 
 
Transformada Discreta de Fourier (DFT) 
 
 Em geral, as amostras igualmente espaçadas da DTFT não 
representam unicamente uma sequência 𝑥 𝑛 quando 𝑥 𝑛 tem 
duração infinita. As amostras 𝑋 𝑒𝑗𝜔 
𝜔=2𝜋𝑘 𝑁 
 representam a DFT de 
um período (0 ≤ 𝑛 ≤ 𝑁 − 1) da sequência periódica: 
 
𝑥𝑝(𝑛) = 𝑥 𝑛 − 𝑙𝑁 , 
∞
𝑙=−∞
 
 
Transformada Discreta de Fourier (DFT) 
 
 Definindo 𝑊𝑁 = 𝑒
−𝑗
2𝜋
𝑁 , a DFT pode ser escrita como: 
 
𝑋 𝑘 = 𝑥 𝑛 𝑊𝑁
𝑘𝑛, 
𝑁−1
𝑛=0
0 ≤ 𝑘 ≤ 𝑁 − 1 
 
 
 Complexidade da DFT: 
 
• O cálculo de cada componente da DFT pela expressão acima requer 
𝑁 multiplicações complexas e 𝑁 − 1 somas complexas. 
• O cálculo de todos componentes (0 ≤ 𝑘 ≤ 𝑁 − 1) requer 𝑁2 
multiplicações e 𝑁(𝑁 − 1) somas. 
• O algoritmo FFT, que será visto mais adiante, requer apenas 
𝑁 log2 𝑁 multiplicações e somas complexas quando 𝑁 = 2
𝑟 , 𝑟 inteiro. 
Transformada Discreta de Fourier (DFT) 
 Exemplo 1: A DFT de 
 
 𝑥 𝑛 = 
1, 𝑛 = 0 
0, 𝑛 = 1,2, ⋯ , 𝑁 − 1
 
 é 
 
 
 
 
 
 Exemplo 2: A DFT de 
 
𝑥 𝑛 = 1, 𝑛 = 0,1, ⋯ , 𝑁 − 1 
 é 
𝑋 𝑘 = 𝑊𝑁
𝑛𝑘 
𝑁−1
𝑛=0
=
1 − 𝑊𝑁
𝑁𝑘
1 − 𝑊𝑁
𝑘 = 
𝑁, 𝑘 = 0
0, 𝑘 ≠ 0 
 
𝑋 𝑘 = δ(𝑛)𝑊𝑁
𝑛𝑘 
𝑁−1
𝑛=0
= 1, 𝑘 = 0,1, ⋯ , 𝑁 − 1 
Transformada Discreta de Fourier (DFT) 
 Exemplo 3: A DFT de 
 
𝑥 𝑛 = cos 
2𝜋𝑟𝑛
𝑁
, 𝑛 = 0,1, ⋯ , 𝑁 − 1 
 
 sendo 𝑟 um inteiro com 0 ≤ 𝑟 ≤ 𝑁 − 1, é 
 
𝑋 𝑘 = 
1
2
𝑊𝑁
−𝑟𝑛 + 𝑊𝑁
𝑟𝑛 𝑊𝑁
𝑛𝑘 
𝑁−1
𝑛=0
=
1
2
 𝑊𝑁
(𝑘−𝑟)𝑛
+ 𝑊𝑁
(𝑘+𝑟)𝑛
𝑁−1
𝑛=0
 
=
1
2
1 − 𝑊𝑁
𝑁(𝑘−𝑟)
1 − 𝑊𝑁
𝑘−𝑟
+
1 − 𝑊𝑁
𝑁(𝑘+𝑟)
1 − 𝑊𝑁
𝑘+𝑟
=
𝑁
2
, 𝑘 = 𝑟 
𝑁
2
, 𝑘 = 𝑁 − 𝑟
0, outro 𝑘 
 
Simetrias da DFT de Sequências Reais 
 Para uma sequência 𝑥 𝑛 real de comprimento 𝑁, temos: 
 
𝑋 𝑘 ∗ = 𝑥 𝑛 𝑒𝑗
2𝜋
𝑁 𝑘𝑛
𝑁−1
𝑛=0
 
 = 𝑥 𝑛 𝑒−𝑗
2𝜋
𝑁
(𝑁−𝑘)𝑛
𝑁−1
𝑛=0
= 𝑋 𝑁 − 𝑘 
 
 Portanto: 
𝑋𝑅 𝑘 = 𝑋𝑅 𝑁 − 𝑘 
 
𝑋𝐼 𝑘 = −𝑋𝐼 𝑁 − 𝑘 
 
𝑋 𝑘 = 𝑋 𝑁 − 𝑘 
 
∠𝑋 𝑘 = −∠𝑋 𝑁 − 𝑘 
 
DFT Inversa (IDFT) 
 As componentes de 𝑥 𝑛 podem ser obtidas da sua DFT pela 
expressão: 
 
𝑥 𝑛 =
1
𝑁
 𝑋 𝑘 𝑊𝑁
−𝑘𝑛, 
𝑁−1
𝑘=0
0 ≤ 𝑛 ≤ 𝑁 − 1 
 
Obtenção da DTFT por Interpolação da DFT 
 A DTFT de uma sequência de 𝑥 𝑛 de comprimento 𝑁 é: 
𝑋 𝑒𝑗𝜔 = 𝑥(𝑛)𝑒−𝑗𝜔𝑛 
𝑁−1
𝑛=0
 
 
 Substituindo 𝑥 𝑛 pela expressão da IDFT, obtemos: 
𝑋 𝑒𝑗𝜔 = 
1
𝑁
 𝑋 𝑘 𝑊𝑁
−𝑘𝑛
𝑁−1
𝑘=0
𝑒−𝑗𝜔𝑛 
𝑁−1
𝑛=0
 
 =
1
𝑁
 𝑋 𝑘
𝑁−1
𝑘=0
 𝑒
−𝑗 𝜔−
2𝜋𝑘
𝑁 𝑛 
𝑁−1
𝑛=0
 
 =
1
𝑁
 𝑋 𝑘
𝑁−1
𝑘=0
𝑠𝑒𝑛 (𝜔𝑁 − 2𝜋𝑘) 2 
𝑠𝑒𝑛 (𝜔𝑁 − 2𝜋𝑘) 2𝑁 
𝑒
−𝑗 𝜔−
2𝜋𝑘
𝑁
𝑁−1
2 
 
 Através da expressão acima, podemos reconstruir a DTFT 𝑋 𝑒𝑗𝜔 de uma 
sequência de comprimento 𝑁 a partir da sua DFT 𝑋 𝑘 . 
Cálculo Numérico da DTFT 
 A DTFT 𝑋 𝑒𝑗𝜔 de uma sequência 𝑥(n) de comprimento 𝑁 pode ser 
obtida em um grid denso de frequências 𝜔𝑘 = 2𝜋𝑘/𝑀, com M ≫ 𝑁, 
definindo: 
 
𝑥𝑒 𝑛 = 
𝑥 𝑛 , 0 ≤ 𝑛 ≤ 𝑁 − 1
0, 𝑁 ≤ 𝑛 ≤ 𝑀 − 1
 
 
 
 Observando que 𝑋𝑒 𝑒
𝑗𝜔 = 𝑋 𝑒𝑗𝜔 , a DFT de 𝑥𝑒 𝑛 corresponderá 
 à DTFT de 𝑥 n para 𝜔𝑘 =
2𝜋𝑘
𝑀
, 0 ≤ 𝑘 ≤ M − 1. 
 
 
Relações Matriciais 
 As 𝑁 componentes da DFT podem ser escritas, na forma matricial, 
em função das 𝑁 amostras de 𝑥 𝑛 , como: 
 
𝑋[0]
𝑋[1]
𝑋[2]
⋮
𝑋[𝑁 − 1]
=
1 1
1 𝑊𝑁
1 ⋯ 1
𝑊𝑁
2 ⋯ 𝑊𝑁
𝑁−1
1 𝑊𝑁
2
⋮ ⋮
1 𝑊𝑁
𝑁−1
𝑊𝑁
4 ⋯ 𝑊𝑁
2(𝑁−1)
⋮ ⋱ ⋮
𝑊𝑁
2(𝑁−1) ⋯ 𝑊𝑁
(𝑁−1)2
𝑥[0]
𝑥[1]
𝑥[2]
⋮
𝑥[𝑁 − 1]
 
 
 ou, na forma compacta: 
 
𝑿𝑁 = 𝑾𝑁𝒙𝑁 
 
 onde 𝑾𝑁 é chamada de matriz DFT. 
Relações Matriciais 
 A IDFT também pode ser expressa na forma matricial: 
 
𝑥[0]
𝑥[1]
𝑥[2]
⋮
𝑥[𝑁 − 1]
=
1
𝑁
1 1
1 𝑊𝑁
−1
1 ⋯ 1
𝑊𝑁
−2 ⋯ 𝑊𝑁
−(𝑁−1)
1 𝑊𝑁
−2
⋮ ⋮
1 𝑊𝑁
−(𝑁−1)
𝑊𝑁
−4 ⋯ 𝑊𝑁
−2(𝑁−1)
⋮ ⋱ ⋮
𝑊𝑁
−2(𝑁−1) ⋯ 𝑊𝑁
−(𝑁−1)2
𝑋[0]
𝑋[1]
𝑋[2]
⋮
𝑋[𝑁 − 1]
 
 
 ou, na forma compacta: 
 
𝒙𝑁 =
1
𝑁
𝑾𝑁
∗
𝑿𝑁 
 
 Comparando as expressões da DFT e da IDFT, concluímos que: 
 
𝑾𝑁
−𝟏 =
1
𝑁
𝑾𝑁
∗
 
Operações Circulares 
 Operação 𝑚 𝑚ó𝑑𝑢𝑙𝑜 𝑁 ou 𝑚 𝑁: 
 
 Dados dois números inteiros 𝑚 e 𝑁, seja 𝑖 o inteiro positivo ou 
 negativo tal que 
 
𝑚 = 𝑖𝑁 + 𝑟, com 0 ≤ 𝑟 ≤ 𝑁 − 1 
 
 Então: 
𝑚 𝑁 = 𝑟 
 
 
 Exemplos: 
13 5 = 3, pois 13 = 2 × 5 + 3 
 
27 5 = 2, pois 27 = 5 × 5 + 2 
 
−12 5 = 3, pois −12 = −3 × 5 + 3 
 
Operações Circulares 
 Deslocamento circular de 𝑛0 amostras de uma sequência x(n) de 
comprimento 𝑁: 
𝑥𝐶 𝑛 = 𝑥( 𝑛 − 𝑛0 𝑁) 
 
 
 Exemplo: 
 
 
 
 
 
 
Operações Circulares 
 Convolução circular de duas sequências g n e h(n) de 
comprimento 𝑁: 
𝑦 𝑛 = 𝑔(𝑚)
𝑁−1
𝑚=0
ℎ( 𝑛 − 𝑚 𝑁) 
 
 
 Exemplo: 
 
 
 
 
 
 
 𝑦 0 = 𝑔 0 ℎ 0 4 + 𝑔 1 ℎ −1 4 + 𝑔 2 ℎ −2 4 𝑔 3 ℎ −3 4 
= 𝑔 0 ℎ 0 + 𝑔 1 ℎ 3 + 𝑔 2 ℎ 2 + 𝑔 3 ℎ 1 
 = 1 + 4 + 3 + 2 
 = 10 
Operações Circulares 
 A convolução circular pode ser escrita na forma matricial como: 
 
𝑦[0]
𝑦[1]
⋮
𝑦[𝑁 − 1]
=
ℎ[0] ℎ[𝑁 − 1]
ℎ[1] ℎ[0]
⋯ ℎ[1]
⋯ ℎ[2]
⋮ ⋮ 
ℎ[𝑁 − 1] ℎ 𝑁 − 2 
⋱ ⋮
⋯ ℎ[0]
𝑔[0]
𝑔[1]
⋮
𝑔[𝑁 − 1]
 
 
 
 No exemplo anterior: 
 
𝑦[0]
𝑦[1]
𝑦[2]
𝑦[3]
=
1 4
2 1
3 2
4 3
3 2
4 3
1 4
2 1
1
1
1
1
=
10
10
10
10
 
 
 
 
Propriedades da DFT 
 Sejam duas sequências de comprimento 𝑁, g n ⟷ 𝐺(𝑘) e 
h(n) ⟷ 𝐻 𝑘 . Então, as seguintes propriedades são válidas: 
 
 (i) Linearidade: 
 
αg n + 𝛽ℎ 𝑛 ⟷ 𝛼𝐺 𝑘 + 𝛽𝐻(𝑘) 
 
 
 (ii) Deslocamento circular no tempo: 
 
g 𝑛 − 𝑛0 𝑁 ⟷ 𝑊𝑁
𝑘𝑛0𝐺 𝑘 
 
 
 (iii) Deslocamento circular na frequência: 
 
𝑊𝑁
−𝑘0𝑛g(n) ⟷ 𝐺 𝑘 − 𝑘0 𝑁 
 
Propriedades da DFT 
 (iv) Convolução circular: 
 
 𝑔(𝑚)
𝑁−1
𝑚=0
ℎ( 𝑛 − 𝑚 𝑁) ⟷ 𝐺 𝑘 𝐻(𝑘) 
 
 ou seja, a DFT da convolução circular de 𝑁 amostras de duas 
 sequências é o produto de suas DFTs. 
 
 
 (v) Modulação: 
 
𝑔 𝑛 ℎ(𝑛) ⟷
1
𝑁
 𝐺(𝑙)
𝑁−1
𝑙=0
𝐻( 𝑘 − 𝑙 𝑁) 
 
 ou seja, a DFT do produto de duas sequências é igual à 
 convolução circular de suas DFTs. 
Computação de Convoluções Lineares Usando DFTs 
 Vimos que a resposta de um sistema LTI é a convolução linear da 
entrada com a resposta ao impulso. 
 
 Vimos também que a convolução linear pode ser computada usando 
DTFTs, ou seja: 
 
 
 
 
 
 
 
 A motivação para o uso da DFT é a redução da complexidade 
computacional. Mas, pela propriedade (iv) da DFT, a IDFT do 
produto de duas DFTs é igual à convolução circular das duas 
sequências no tempo. 
 
 
 
Computação de Convoluções Lineares Usando DFTs 
 A convolução linear de sequências de comprimento 𝑀 e 𝑁 é uma 
sequência de comprimento 𝐿 = 𝑀 + 𝑁 − 1. 
 
 A convolução circular entre duas sequências exige que elas tenham 
o mesmo comprimento. A sequência resultante terá o mesmo 
comprimento das sequências. 
 
 Os resultados das convoluções linear e circular serão idênticos se 
aumentarmos o comprimento de cada sequência com zeros de 
forma que cada uma delas tenha comprimento 𝐿 = 𝑀 + 𝑁 − 1. 
 
 Portanto, definimos as sequências estendidas: 
 
𝑥𝑒 𝑛 =𝑥 𝑛 , 0 ≤ 𝑛 ≤ 𝑁 − 1
0, 𝑁 ≤ 𝑛 ≤ 𝐿 − 1
 
 
ℎ𝑒 𝑛 = 
ℎ 𝑛 , 0 ≤ 𝑛 ≤ 𝑀 − 1
0, 𝑀 ≤ 𝑛 ≤ 𝐿 − 1
 
Computação de Convoluções Lineares Usando DFTs 
 A convolução linear pode ser então obtidas usando DFTs conforme 
ilustrado abaixo: 
 
 
 
 
 
 
 
 Exemplo: