Giáo trình Xử lý tín hiệu số - Chương 7: DFT và FFT - Nguyễn Thanh Tuấn

Chương 7: DFT & FFT
•DTFT
•DFT
•FFT
ThS. Nguyễn Thanh Tuấn
Khoa Điện-Điện tử, Đại học Bách Khoa TP.HCM
nttbk97@yahoo.com
Miền thời gian Miền tần số
dt
tfπj2
es(t)S(f)


 
dt
T
0
tωkjes(t)
T
1
kc 
Periodic 
(period T)
Discrete 
ContinuousFTAperiodic
FS
0
0.5
1
1.5
2
2.5
0 1 2 3 4 5 6 7 8
time, t
0
0.5
1
1.5
2
2.5
0 2 4 6 8 10 12
time, t





1N
0n
N
nkπ2
j
es[n]
N
1
kc
~
Discrete
DiscreteDFSPeriodic 
(period T)
ContinuousDTFT
Aperiodic 
DiscreteDFT
nfπ2je
n
s[n]S(f) 


 
0
0.5
1
1.5
2
2.5
0 2 4 6 8 10 12
time, tk
0
0.5
1
1.5
2
2.5
0 1 2 3 4 5 6 7 8
time, tk





1N
0n
N
nkπ2
j
es[n]
N
1
kc
~
Continuous
Chuỗi Fourier (Fourier series-FS)
• Tín hiệu x(t) tuần hoàn, chu kỳ Tp , tần số F0 = 1/Tp




k
tkFj
kectx
02)(



pT
tkFj
p
k dtetx
T
c 0
2
)(
1 
X(f)
f
-Tp Tp0
x(t)
τ
t F0-F0
Biến đổi Fourier (Fourier transform-FT)
• Tín hiệu x(t) không tuần hoàn
 


 dfeFXtx ftj 2)(
   


 dtetxfX ftj 2
X(ω)
ω
2π/τ-2π/τ
x(t)
-τ/2 tτ/2
Biến đổi Fourier của một số tín hiệu cơ bản
7.1 DTFT
• Định nghĩa
• Hạn chế tính toán
– Chiều dài x(n) vô hạn
– X(w) liên tục
• Cửa sổ hóa tín hiệu
– Hàm cửa sổ
– Ảnh hưởng
• Tính toán DTFT
– Tại 1 tần số
– Trong khoảng tần số  không thể
  



deXnx nj
2
2
1
)(
   



n
njenxX 
Cửa sổ hóa thời gian
• Giảm độ phân giải tần số  chiều dài cửa sổ
• Gây rò rỉ tần số  hình dạng cửa sổ
Cửa sổ chữ nhật
Tín hiệu tuần hoàn lấy mẫu
Ảnh hưởng của cửa sổ chữ nhật
Ảnh hưởng của cửa sổ chữ nhật (2)
Ảnh hưởng của cửa sổ chữ nhật (2)
Các cửa sổ khác
• Tăng độ phân giải tần số: búp chính rộng 
hơn (và thấp hơn)
Cửa sổ Hamming
Tính toán DTFT
7.2 DFT
• Định nghĩa: DFT N điểm
• Quan hệ của DFT với biến đổi Z
• Dạng ma trận
• Chèn zero
• Giảm modulo-N
• DFT ngược (IDFT)
• Điều kiện khôi phục đúng
  1,...,2,1,0 , )(
1
0
/2 


 NkenxkX
L
n
Nknj 
    1,...,2,1,0 , 
1 1
0
/2  


NnekX
N
nx
N
k
Nknj 
DFT N điểm
DFT và biến đổi Z
DFT dạng ma trận 
Ma trận DFT
Chèn zero
• Khi L < N
Giảm modulo-N
• Khi L > N
Ví dụ
Tính không duy nhất của DFT
IDFT
Ví dụ
• Tính trực tiếp DFT N – điểm của x(n):
Tổng quát: X(k) và x(n) là số phức:
Tính trực tiếp cần:
• 2N2 phép tính hàm lượng giác
• 4N2 phép nhân thực
• 4N(N-1) phép cộng thực
     









1
0
2
sin
2
cos
N
n
IRR
N
kn
nx
N
kn
nxkX

     









1
0
2
cos
2
sin
N
n
IRI
N
kn
nx
N
kn
nxkX

Chi phí tính toán lớn
7.3 FFT
• Lịch sử
• Phương pháp chia để trị
• Đánh giá hiệu quả
• FFT phân chia miền thời gian
– Công thức
– Sơ đồ hình bướm
• FFT phân chia miền tần số
– Công thức
– Sơ đồ hình bướm
• IFFT
– Quan hệ với FFT
kN
Nk
M WW 
 2/
k
N
Nk
M WW 

Sơ đồ hình bướm
x(0)
x(1)
X(0)
X(1)
-1
FFT phân chia miền thời gian
FFT phân chia miền thời gian (2)
Quá trình đảo bit
Ví dụ
FFT 8 điểm phân chia theo thời gian
FFT 8 điểm phân chia theo thời gian (2)
FFT 8 điểm phân chia theo thời gian (3)
FFT 8 điểm phân chia theo thời gian (4)
FFT 8 điểm phân chia theo tần số
FFT 8 điểm phân chia theo tần số (2)
FFT 8 điểm phân chia theo tần số (3)
Tóm tắt chương 7
• Ảnh hưởng của quá trình cửa sổ hóa tín hiệu?
• So sánh các hàm cửa sổ?
• Điều kiện của số điểm N khi thực hiện DFT?
• Điều kiện tối ưu của số điểm N khi thực hiện FFT?
• Đánh giá hiệu quả của FFT so với DFT?
• Xác định DFT N điểm?
• Xác định IDFT N điểm?
• Thực hiện FFT N điểm phân chia miền thời gian?
• Thực hiện FFT N điểm phân chia miền tần số?
• Thực hiện IFFT N điểm phân chia miền thời gian?
• Thực hiện IFFT N điểm phân chia miền tần số?