Bài giảng Xử lý số tín hiệu (Digital signal processing) - Chương 8: Biến đổi DFT và FFT cung cấp cho người học các kiến thức: Lấy mẫu tần số, biến đổi Fourier rời rạc (DFT), biến đổi DFT, biến đổi FFT, biến đổi IFFT,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung Text: Bài giảng Xử lý số tín hiệu (Digital signal processing) - Chương 8: Biến đổi DFT và FFT
Xử lý số tín hiệu
Chương 8: Biến đổi DFT và FFT
Các phép biến đổi Fourier
2.5
Miền thời gian Miền tần số
2
1.5
1
T
1
Periodic s(t) e j k ω t dt
0.5
0
0 1 2 3 4 5 6 7 8
FS Discrete ck
time, t T
(period T) 0
2.5 Continuous j2 π f t
2
1.5
1
Aperiodic FT Continuous S(f) s(t) e dt
0.5
0
0 2 4 6 8 10 12
time, t
N 1 2πkn
j
2.5
2
~ 1 N
ck s[n] e
Periodic DFS Discrete
1.5
1
N
0.5
n 0
0
0 1 2 3
time, tk
4 5 6 7 8
(period T)
Discrete S(f) s[n] e j 2 π f n
DTFT Continuous
n
2.5
2
Aperiodic
2πkn
1.5
1N 1 j
1
DFT ~
0.5
ck s[n] e N
Discrete
0
time, tk
0 2 4 6 8 10 12
N
n 0
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
x (t ) ck e j 2 kF0 t
k
1 j 2 kF0 t
ck x (t )e dt
Tp Tp
X(f)
x(t)
τ
f
0 Tp t -F0 F0
-Tp
Biến đổi Fourier (Fourier transform-FT)
Tín hiệu x(t) không tuần hoàn
j 2 ft
x (t ) X F e df
j 2 ft
X f xt e dt
X(ω)
x(t)
ω
-τ/2 τ/2 t
-2π/τ 2π/τ
Biến đổi Fourier của một số tín hiệu cơ bản
Biến đổi Fourier thời gian rời rạc
Discrete – Time Fourier Transform (DTFT)
Tín hiệu x(n) rời rạc, không tuần hoàn
1
x ( n) X e j nd
2 2
j n
X x ne
n
Chuỗi Fourier rời rạc
Discrete Fourier Sequence (DFS)
Tín hiệu x(n) rời rạc, tuần hoàn với chu kỳ N
N 1
x ( n) ck e j 2 kn / N
k 0
N 1
1 j 2 kn / N
ck x ne
N n 0
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
Tín hiệu x(n) rời rạc, không tuần hoàn, chiều dài L hữu
hạn Biến đổi DTFT cho phổ liên tục X(ω)
|X(ω)|
x(n)
0 L-1 n -π π ω
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
Lặp lại tín hiệu x(n) với chu kỳ N ≥ L Tín hiệu xp(n)
tuần hoàn chu kỳ N
xp(n)
0 L-1 N-1 N n n
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
xp(n) tuần hoàn chu kỳ N Tính DFS của xp(n) Xp(k)
xp(n)
0 L-1 N-1 N n n
|Xp(k)|
-N 0 N k
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
Xp(k) tuần hoàn chu kỳ N Đặt X(k) = Xp(k), k = 0,..,N-1
x(n)
0 L-1 n
|X(k)| DFT
0 N-1 k
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
Công thức biến đổi DFT N-điểm cho chuỗi chiều dài L:
DFT L 1
j 2 kn / N
X (k ) xne , k 0,1,2,..., N 1
n 0
1 N 1
IDFT xn X k e j2 kn / N
, n 0,1,2,..., N 1
N k 0
Giải thuật biến đổi Fourier nhanh
Fast Fourier Transform (FFT)
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:
N 1
2 kn 2 kn
XR k xR n cos xI n sin
n 0 N N
N 1
2 kn 2 kn
XI k xR n sin xI n cos
n 0 N N
Tính trực tiếp cần:
• 2N2 phép tính hàm lượng giác Chi phí tính
• 4N2 phép nhân thực toán lớn
• 4N(N-1) phép cộng thực
Giải thuật biến đổi Fourier nhanh
Fast Fourier Transform (FFT)
j2 / N
Đặt WN e
N 1
X k x(n)WNnk
n 0
k N /2 k
Tính đối xứng: W M W N
k N k
Tính tuần hoàn:
W M W N
Giải thuật biến đổi Fourier nhanh
Fast Fourier Transform (FFT)
Xét chuỗi x(n) = {x(0), x(1)}
FFT 2 điểm của x(n):
0 0
X (0) x(0)W 2 x(1)W 2 x(0) x(1)
0 1
X (1) x(0)W2 x(1)W
2 x(0) x(1)
(Lưu ý: W2 = 1)
x(0) X(0)
1 Bướm
(Butterfly)
x(1) X(1)
-1
Giải thuật FFT phân chia theo thời gian
(Decimation in time – DIT)
Xét chuỗi x(n) có chiều dài N = 2K
Đặt g(n) = x(2n) g(n) = {x(0), x(2), … }
Đặt h(n) = x(2n + 1) h(n) = {x(1), x(3), …}
DFT N điểm của x(n):
k N
X (k ) G (k ) W H (k ) , k
N 0,1,..., 1
2
N
N k N N
X (k ) G (k ) W 2
N H ( k ) , k ,..., N 1
2 2 2
G(k), H(k) : DFT N/2 điểm của g(n), h(n)
Giải thuật FFT phân chia theo thời gian
g(0) G(0)
X(0)
0
g(1) G(1) W N
X(1)
W 1 k =0
FFT
FFTN/2
N/2 N
điểm
điểm N/2 -1
g(N/2 -1) G(N/2 -1)
N /2 1
X(N/2-1)
W N
h(0) H(0) WN0
X(N/2)
h(1) H(1) WN1
X(N/2 + 1) k = N/2
FFT
FFTN/2
N/2
điểm
điểm N-1
h(N/2 -1) H(N/2 -1) WNN / 2 1
X(N – 1)
Chi phí tính toán
So với tính trực tiếp: chi phí tính toán thấp hơn
2000
1500
DFT N2
Number of Operations
1000
FFT N log2N
500
0
0 10 20 30 40
Num b e r o f s a m ple s , N
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
