11 - Transformada Discreta de Fourier

Prévia do material em texto

Universidade Federal do Amazonas (UFAM)
Faculdade de Tecnologia (FT)
Departamento de Eletrônica e Computação (DTEC)
Sinais e Sistemas
Transformada de Fourier no Tempo Discreto
Prof. Francisco Januário
2Prof. Francisco Januário
Sinais e Sistemas 
Referências
Oppenheim, Alan. V., Signals and Systems, Prentice-Hall, NJ, 2002.
Haykin, Simon. Sistemas de Comunicação: analógicas e digitais. 4 ed.
São Paulo: Bookman, 2004.
Oppenheim, Alan V.; Schafer, Ronald W. Processamento em tempo
discreto de sinais. 3 ed. Pearson, 2010
Lathi, B. P. Sinais e Sistemas Lineares. 2 ed. Porto Alegre: Bookman,
2007.
Haykin, Simon; Barry, Van Veen. Sinais e sistemas. Porto Alegre:
Bookman, 2001.
DINIZ, Paulo S.; SILVA, Eduardo A. B.; NETTO Sergio L. Processamento
digital de sinais: projeto e análise de sistemas. 2. ed. Porto Alegre:
Bookman, 2014.
3
A transformada de Fourier no Tempo Discreto (DTFT –
Discrete Time Fourier Transform) é a decomposição de um
sinal no tempo discreto como uma soma infinita de
senoides complexas no tempo discreto.
A DTFT converte uma sequência no tempo discreto para o
domínio contínuo da frequência em 𝜔
𝑋 𝑗𝜔 = 𝑋 𝑒𝑗𝜔 = ෍
𝑛=−∞
∞
𝑥[𝑛]𝑒−𝑗𝜔𝑛
Sinais e Sistemas
Transformada de Fourier no Tempo Discreto
Prof. Francisco Januário
4
Um sinal 𝑥[𝑛] no tempo discreto pode ser representado
por um somatório infinito de senoides de frequências 𝜔
ponderadas por fatores proporcionais a 𝑋(𝑗𝜔)
𝑥[𝑛] =
1
2𝜋𝑗
න
−𝜋
𝜋
𝑋(𝑗𝜔)𝑒𝑗𝜔𝑛𝑑𝜔
Lembrando que 𝑒𝑗𝜔 = cos 𝜔 + 𝑗sen(𝜔) (Fórmula de
Euler), então 𝑥[𝑛] pode ser representada como
𝑥[𝑛] =
1
2𝜋𝑗
න
−𝜋
𝜋
𝑋(𝑗𝜔) cos 𝜔𝑛 + 𝑗sen(𝜔𝑛) 𝑑𝜔
Sinais e Sistemas
Transformada Inversa de Fourier no Tempo Discreto
Prof. Francisco Januário
5
Linearidade
𝑥[𝑛] = 𝑎𝑥1[𝑛] + 𝑏𝑥2[𝑛]
𝑋(𝑒𝑗𝜔) = 𝑎𝑋1(𝑒
𝑗𝜔) + 𝑏𝑋2(𝑒
𝑗𝜔)
Reversão no Tempo
𝑥[−𝑛] = 𝑋(𝑒−𝑗𝜔)
Deslocamento no Tempo
𝑥[𝑛 + 𝑛0] ⟷ 𝑒
𝑗𝜔𝑛0𝑋(𝑒𝑗𝜔), ∀𝑛0 ∈ ℤ
Sinais e Sistemas
Propriedades da DTFT
Prof. Francisco Januário
6
Multiplicação por uma Exponencial Complexa
𝑒𝑗𝜔0𝑛𝑥[𝑛] ⟷ 𝑋 𝑒𝑗(𝜔−𝜔0)
Corresponde ao deslocamento da frequência, ou,
modulação.
Diferenciação Complexa
𝑛𝑥[𝑛] ⟷ 𝑗
𝑑𝑋(𝑒𝑗𝜔)
𝑑𝜔
Sinais e Sistemas
Propriedades da DTFT
Prof. Francisco Januário
7
Teorema de Convolução
𝑥1 𝑛 ∗ 𝑥2[𝑛] ⟷ 𝑋1 𝑒
𝑗𝜔 𝑋2 𝑒
𝑗𝜔
A convolução no domínio do tempo é igual ao produto no
domínio da frequência.
Teorema de Parseval
෍
𝑛=−∞
∞
𝑥[𝑛] 2 =
1
2𝜋
න
−𝜋
𝜋
𝑋(𝑒𝑗𝜔)
2
𝑑𝜔
A energia do sinal no domínio do tempo é igual à energia
do sinal no domínio da frequência dividida por 2𝜋.
Sinais e Sistemas
Propriedades da DTFT
Prof. Francisco Januário
8
Considerando um sinal periódico 𝑥[𝑛] = 𝑥[𝑛 + 𝑘𝑁] de
período 𝑁 composto por versões deslocadas do sinal 𝑥𝑓[𝑛],
que corresponde a um período de 𝑥[𝑛], tal que
𝑥𝑓[𝑛] = 0 para 𝑛 < 0 e 𝑛 ≥ 𝑁
Pode-se então escrever 𝑥[𝑛] como
𝑥[𝑛] = ෍
𝑛=−∞
∞
𝑥𝑓[𝑛 + 𝑘𝑁] , ∀𝑘 ∈ ℤ
Onde 𝑥𝑓[𝑛] é deslocada para as posições 𝑘𝑁.
Sinais e Sistemas
DTFT para Sinais Periódicos
Prof. Francisco Januário
9
Usando a propriedade do deslocamento no tempo a DTFT
periódica pode ser obtida como
𝑋 𝑒𝑗𝜔 = ෍
𝑘=−∞
∞
𝑒𝑗𝜔𝑘𝑁𝑋𝑓 𝑒
𝑗𝜔
Podendo também ser escrito como
𝑋 𝑒𝑗𝜔 =
2𝜋
𝑁
෍
𝑘=−∞
∞
𝑋(𝑘)𝛿 𝜔 −
2𝜋
𝑁
𝑘
Sendo que
𝑋 𝑘 = ෍
𝑛=0
𝑁−1
𝑥[𝑛]𝑒−𝑗(2𝜋/𝑁)𝑘
Sinais e Sistemas
DTFT para Sinais Periódicos
Prof. Francisco Januário
10
Percebe-se que, para sinais periódicos, a DTFT se
transforma numa soma discreta de senoides com
frequências múltiplas de 2𝜋/𝑁.
A transformada inversa, então, pode ser descrita como
𝑥[𝑛] =
1
2𝜋
න
−𝜋
𝜋
𝑋(𝑒𝑗𝜔)𝑒𝑗𝜔𝑛𝑑𝜔
ou
𝑥[𝑛] =
1
𝑁
෍
𝑘=0
𝑁−1
𝑋(𝑘)𝑒𝑗 2𝜋/𝑁 𝑘𝑛
Sinais e Sistemas
DTFT para Sinais Periódicos
Prof. Francisco Januário
Transformadas Discretas
11Prof. Francisco Januário
Sinais e Sistemas
12
As transformadas estudadas ate aqui convertem um sinal
no tempo discreto para o domínio da frequência com
variável contínua 𝜔 , não sendo adequadas para
processamento em sistemas digitais.
Algumas transformadas que realizam mapeamentos para
domínios discretos de frequências:
▪ Transformada Discreta de Fourier (DFT – Discrete
Fourier Transform);
▪ Transformada Discreta de Cossenos (DCT – Discrete
Cosine Transform)
Sinais e Sistemas
Transformadas Discretas
Prof. Francisco Januário
13
A transformada discreta de Fourier (DFT – Discrete Fourier
Transform) converte uma sequência 𝑥[𝑛] no tempo
discreto para o domínio de frequência discreta 𝑘.
𝑋 𝑒𝑗 2𝜋/𝑁 𝑘 = 𝑋 𝑘 = ෍
𝑛=0
𝑁−1
𝑥[𝑛]𝑊𝑁
𝑘𝑛, 0 ≤ 𝑘 ≤ 𝑁 − 1
A transformada inversa (IDFT) é
𝑥[𝑛] =
1
𝑁
෍
𝑘=0
𝑁−1
𝑋(𝑘)𝑊𝑁
−𝑘𝑛, 0 ≤ 𝑛 ≤ 𝑁 − 1
Sendo que 𝑊𝑁 = 𝑒
−𝑗2𝜋/𝑁
Sinais e Sistemas
Transformada Discreta de Fourier (DFT)
Prof. Francisco Januário
14
A DFT fornece uma representação discreta na frequência
para um sinal de comprimento finito 𝐿 no tempo discreto.
Essa representação só é útil se o número 𝑁 de amostras da
DFT é maior ou igual a 𝐿 do sinal original.
A quantidade de amostras da transformada de Fourier é
igual a 𝑁 (número de amostras do sinal no domínio do
tempo).
Quanto maior 𝑁, melhor a resolução da representação no
domínio da frequência.
Sinais e Sistemas
Transformada Discreta de Fourier (DFT)
Prof. Francisco Januário
15
As equações que definem a DFT e a IDFT podem ser modificadas
para a forma matricial, fazendo inicialmente
𝑋 𝑘 = 𝑊𝑁
0 𝑊𝑁
𝑘 𝑊𝑁
2𝑘 ⋯ 𝑊𝑁
𝑁−1 𝑘
𝑥[0]
𝑥[1]
𝑥[2]
⋮
𝑥[𝑁 − 1]
𝑥[𝑛] =
1
𝑁
𝑊𝑁
0 𝑊𝑁
−𝑘 𝑊𝑁
−2𝑘 ⋯ 𝑊𝑁
− 𝑁−1 𝑘
𝑋(0)
𝑋(1)
𝑋(2)
⋮
𝑋(𝑁 − 1)
Sinais e Sistemas
Representação da DFT na Forma Matricial
Prof. Francisco Januário
16
As transformadas DFT e IDFT na forma matricial
𝑋(0)
𝑋(1)
𝑋(2)
⋮
𝑋(𝑁 − 1)
=
𝑊𝑁
0 𝑊𝑁
0 ⋯ 𝑊𝑁
0
𝑊𝑁
0 𝑊𝑁
1 ⋯ 𝑊𝑁
𝑁−1
𝑊𝑁
0
⋮
𝑊𝑁
0
𝑊𝑁
2
⋮
𝑊𝑁
𝑁−1
⋯
⋱
⋯
𝑊𝑁
2 𝑁−1
⋮
𝑊𝑁
𝑁−1 2
𝑥[0]
𝑥[1]
𝑥[2]
⋮
𝑥[𝑁 − 1]
𝑥[0]
𝑥[1]
𝑥[2]
⋮
𝑥[𝑁 − 1]
=
1
𝑁
𝑊𝑁
0 𝑊𝑁
0 ⋯ 𝑊𝑁
0
𝑊𝑁
0 𝑊𝑁
−1 ⋯ 𝑊𝑁
− 𝑁−1
𝑊𝑁
0
⋮
𝑊𝑁
0
𝑊𝑁
−2
⋮
𝑊𝑁
− 𝑁−1
⋯
⋱
⋯
𝑊𝑁
−2 𝑁−1
⋮
𝑊𝑁
− 𝑁−1 2
𝑋(0)
𝑋(1)
𝑋(2)
⋮
𝑋(𝑁 − 1)
Sinais e Sistemas
Representação da DFT na Forma Matricial
Prof. Francisco Januário
17
Definindo-se
𝒙 =
𝑥[0]
𝑥[1]
𝑥[2]
⋮
𝑥[𝑁 − 1]
, 𝑿 =
𝑋(0)
𝑋(1)
𝑋(2)
⋮
𝑋(𝑁 − 1)
E uma matriz 𝑾𝑵 tal que 𝑾𝑵 𝒊𝒋 = 𝑾𝑵
𝒊𝒋
, para 0 ≤ 𝑖, 𝑗 ≤
𝑁 − 1, as equações anteriores podem ser reescritas como
𝑿 = 𝑾𝑵𝒙
𝒙 =
𝟏
𝑵
𝑾𝑵
∗ 𝑿
Sinais e Sistemas
Representação da DFT na Forma Matricial
Prof. Francisco Januário
Matriz Conjugada 
Transposta
18
É interessante notar que a matriz 𝑾𝑵 tem propriedades
especiais como
▪ É simétrica: 𝑾𝑵
𝑻 = 𝑾𝑵
▪ A equações são diretas e inversas: 𝑾𝑵
−𝟏 =
𝟏
𝑵
𝑾𝑵
∗
Considerando o custo computacional do cálculo da DFT,
pode-se verificar que, para uma DFT de comprimento 𝑁
são necessárias:
▪ 𝑁2 multiplicações complexas
▪ 𝑁 𝑁 − 1 adições
Sinais e Sistemas
Representação da DFT na Forma Matricial
Prof. Francisco Januário
19
Linearidade
𝑥[𝑛] = 𝑎1𝑥1[𝑛] + 𝑎2𝑥2[𝑛]
𝑋(𝑘) = 𝑎1𝑋1(𝑘) + 𝑎2𝑋2(𝑘)
Reversão no Tempo
𝑥[−𝑛] = 𝑋(−𝑘)
Deslocamento no Tempo
𝑥[𝑛 + 𝑛0] ⟷ 𝑊𝑁
−𝑛0𝑘𝑋(𝑘), ∀𝑛0 ∈ ℤ
Sinais e Sistemas
Propriedades da DFT
Prof. Francisco Januário
20
Deslocamento na Frequência
𝑊𝑁
𝑛0𝑛𝑥[𝑛] ⟷ 𝑋 𝑘 + 𝑛0 , ∀𝑛0 ∈ ℤ
Convolução Circular no Tempo
Se 𝑥[𝑛] e ℎ[𝑛] são periódicas no período 𝑁, então
𝑥 𝑛 ∗ ℎ 𝑛 = ෍
𝑙=0
𝑁−1
𝑥 𝑙 ℎ[𝑛 − 𝑙] ⟷ 𝑋 𝑘 𝐻(𝑘)
onde 𝑋(𝑘) e 𝐻(𝑘) são as DFTs dos sinais de comprimento
𝑁 correspondentes a um período de 𝑥[𝑛] e ℎ[𝑛],
respectivamente.
Sinais e Sistemas
Propriedades da DFT
Prof. Francisco Januário
21
Teorema de Parseval
෍
𝑛=0
𝑁−1
𝑥[𝑛] 2 =
1
𝑁
෍
𝑛=0
𝑁−1
𝑋(𝑘) 2
A energia do sinal no domínio do tempo é igual à energia
do sinal no domínio da frequência dividida por 𝑁.
Sinais e Sistemas
Propriedades daDFT
Prof. Francisco Januário
22
Conforme mostrado anteriormente, o cálculo da DFT pela
definição, requer 𝑁2 multiplicações complexas (ou seja,
cresce com o quadrado do comprimento do sinal).
Isso limita sua aplicação prática a sinais de pequeno
comprimento.
Visando contornar essa limitação, foram desenvolvidos
algoritmos rápidos para a estimação da DFT, conhecidos
genericamente como FFT (Fast Fourier Transform).
Sinais e Sistemas
Estimação Computacional da DFT
Prof. Francisco Januário
23
A transformada discreta de cossenos (DCT – Discrete Cosine
Transform) de comprimento 𝑁 de um sinal 𝑥[𝑛] pode ser
definida como
𝐶 𝑘 = 𝛼(𝑘)෍
𝑛=0
𝑁−1
𝑥[𝑛]cos
𝜋 𝑛 + Τ1 2 𝑘
𝑁
, para 0 ≤ 𝑘 ≤ 𝑁 − 1
sendo
𝛼 𝑘 = ቐ
Τ1 𝑁 , para 𝑘 = 0
Τ2 𝑁 , para 1 ≤ 𝑘 ≤ 𝑁 − 1
É interessante observar que a DCT é uma transformada
real, pois mapeia um sinal real em coeficientes reais.
Sinais e Sistemas
Transformada Discreta de Cossenos
Prof. Francisco Januário
24
A DCT inversa é dada por
𝑥[𝑛] = ෍
𝑘=0
𝑁−1
𝛼(𝑘)𝐶 𝑘 cos
𝜋 𝑛 + Τ1 2 𝑘
𝑁
, para 0 ≤ 𝑛 ≤ 𝑁 − 1
Definindo a matriz 𝐶𝑁
𝐶𝑁 𝑘𝑛 = 𝛼(𝑘) cos
𝜋 𝑛 + Τ1 2 𝑘
𝑁
Então, a forma matricial da DCT é representada por
𝒄 = 𝑪𝑵𝒙 e 𝒙 = 𝑪𝑵
𝑻𝒄
Sinais e Sistemas
Transformada Discreta de Cossenos
Prof. Francisco Januário
25
Um sistema de compressão de imagem ou vídeo
genérico pode ser representado por
Sinais e Sistemas
Aplicações com DCT
Prof. Francisco Januário
26
(a) 100%, (b) 75%, (c) 50% e (d) 25% de retenção de coeficientes
após a DCT.
Sinais e Sistemas
Reconstrução após Compactação via DCT
Prof. Francisco Januário
27
A DCT é amplamente utilizada em sistemas
modernos de compressão de vídeo e áudio.
Para sua implementação computacional pode-se:
▪ utilizar a relação da DCT com a DFT (a partir da
formula de Euler) e em seguida um algoritmo
eficiente FFT para a DFT.
▪ utilizar implementações rápidas e otimizadas
para o calculo da DCT.
Sinais e Sistemas
Implementação Computacional da DCT
Prof. Francisco Januário
28
O Matlab possui funções que podem ser utilizadas para
cálculo das transformadas discretas.
Entre elas podemos destacar:
fft: calcula os coeficientes da DFT de um sinal usando um
algoritmo FFT.
ifft: calcula a IDFT a partir dos coeficientes da DFT.
dct e idct: respectivamente a DCT e a inversa da DCT
Sinais e Sistemas
Transformadas Discretas no Matlab
Prof. Francisco Januário
29
Para o sinal 𝑥 𝑡 = 2sen 2𝜋10𝑡 + sen(2𝜋50𝑡)
amostrado a 1 kHz, calcular a DFT usando o Matlab
>> fs=1000;
>> t=0:1/fs:1;
>> x=2*sin(2*pi*10*t)+sin(2*pi*50*t);
>> X=fft(x); %% DFT utilizando FFT
%% Visualizando o gráfico da DFT
>> F=linspace(0,fs/2,length(X)/2);
>> stem(F,abs(X(1:length(X)/2))/500);
>> set(gca, 'fontsize',14);
>> xlabel('Frequencia (Hz)', 'fontsize',14);
>> ylabel('Amplitude', 'fontsize',14);
>> grid;
Sinais e Sistemas
Transformadas Discretas no Matlab
Prof. Francisco Januário
30
Gráfico da DFT do slide anterior
Sinais e Sistemas
Transformadas Discretas no Matlab
Prof. Francisco Januário