Bài giảng môn học Xử lý tín hiệu số - Chương 4: Biểu diễn tín hiệu & hệ thống trong miền tần số rời rạc
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn học Xử lý tín hiệu số - Chương 4: Biểu diễn tín hiệu & hệ thống trong miền tần số rời rạc", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_mon_hoc_xu_ly_tin_hieu_so_chuong_4_bieu_dien_tin_h.ppt
Nội dung text: Bài giảng môn học Xử lý tín hiệu số - Chương 4: Biểu diễn tín hiệu & hệ thống trong miền tần số rời rạc
- Chương 4: BIỂU DIỄN TÍN HIỆU VÀ HỆ THỐNG TRONG MIỀN TẦN SỐ RỜI RẠC BÀI 1 KHÁI NiỆM DFT BÀI 2 BIẾN ĐỔI FOURIER RỜI RẠC (DFT) BÀI 3 CÁC TÍNH CHẤT DFT BÀI 4 BiẾN ĐỔI FOURIER NHANH (FFT)
- BÀI 1 KHÁI NIỆM DFT − Biến đổi Fourier dãy x(n): X() = x(n)e− jn n= X() cĩ các hạn chế khi xử lý trên thiết bị, máy tính: Tần số liên tục Độ dài x(n) là vơ hạn: n biến thiên -∞ đến ∞ Khi xử lý X() trên thiết bị, máy tính cần: Rời rạc tần số -> K Độ dài x(n) hữu hạn là N: n = 0 N -1 Biến đổi Fourier của dãy cĩ độ dài hữu hạn theo tần số rời rạc, gọi tắt là biến đổi Fourier rời rạc – DFT (Discrete Fourier Transform)
- BÀI 2 BIẾN ĐỔI FOURIER RỜI RẠC - DFT DFT của x(n) cĩ độ dài N định nghĩa: 2 N −1 − j kn x(n)e N : 0 k N − 1 X(k) = n=0 0 : k cịn lại N −1 2 kn − j x(n)W : 0 k N − 1 N N WN = e X (k) = n=0 0 : k cịn lại WN tuần hịan với độ dài N: 2 2 − j (r+mN) − j r (r+mN) N N r WN = e = e = WN
- X(k) biểu diễn dưới dạng modun & argument: X(k) = X(k) e j (k ) X(k) - phổ rời rạc biên độ Trong đĩ: (k) = arg[X(k)] - phổ rời rạc pha 2 1 N −1 j kn X (k)e N : 0 n N − 1 IDFT: x(n) = N k=0 0 : n cịn lại Cặp biến đổi Fourier rời rạc: N −1 kn X(k) = x(n)WN : 0 k N − 1 n=0 N −1 1 −kn x(n) = X(k)WN : 0 n N − 1 N k=0
- Ví dụ 1: Tìm DFT của dãy: x(n) = 1,2,3,4 3 2 kn − j X (k) = x(n)W4 1 4 2 3 n=0 W4 = e = − j;W4 = −1;W4 = j 3 0 X(0) = x(n)W4 = x(0) + x(1) + x(2) + x(3) = 10 n=0 3 n 1 2 3 X(1) = x(n)W4 = x(0) + x(1)W4 + x(2)W4 + x(3)W4 = −2 + j2 n=0 3 2n 2 4 6 X(2) = x(n)W4 = x(0) + x(1)W4 + x(2)W4 + x(3)W4 = −2 n=0 3 3n 3 6 9 X(3) = x(n)W4 = x(0) + x(1)W4 + x(2)W4 + x(3)W4 = −2 − j2 n=0
- BÀI 3. CÁC TÍNH CHẤT DFT a) Tuyến tính DFT DFT Nếu: x1 (n)N ⎯⎯ → X1(k)N x2 (n)N ⎯⎯ → X2(k)N DFT Thì: a1 x1 (n)N + a2 x2 (n)N ⎯⎯ →a1 X1(k)N + a2 X2(k)N Nếu: L = N N = L Chọn: x1 1 2 x2 N = max{ N1 , N 2 } b) Dịch vịng: DFT Nếu: x(n)N ⎯⎯ → X(k)N Thì: DFT kn0 x(n− n0 )N ⎯⎯ →WN X(k)N gọi là dịch vịng của ~ x(n)N đi n0 đơn vị Với: x(n − n0 )N = x(n − n0 )N rectN (n)
- Ví dụ 1: Cho: x(n) = 1,2,3,4 a) Tìm dịch tuyến tính: x(n+3), x(n-2) b)Tìm dịch vịng: x(n+3)4, x(n-2)4 x(n) 4 3 2 1 n 0 1 2 3 x(n+3) x(n-2) 4 4 3 3 a) 2 2 1 n 1 n -3 -2 -1 0 0 1 2 3 4 5
- x(n) x(n-1)4 b) 4 4 3 3 2 2 1 1 n n 0 1 2 3 0 1 2 3 N x(n+1)4 4 x(n − 2)4 = 3,4,1,2 3 2 1 n x(n + 3)4 = 4,1,2,3 0 1 2 3
- c) Chập vịng: DFT DFT Nếu: x1 (n)N ⎯⎯ → X1(k)N x2 (n)N ⎯⎯ → X2(k)N DFT Thì: x1 (n)N x2 (n)N ⎯⎯ → X1(k)N X2(k)N N −1 Chập vịng 2 dãy Với: x1 (n)N x2 (n)N = x1 (m)N x2 (n − m)N m=0 x1(n) & x2(n) Và: x (n − m) = x~ (n − m) rect (n) 2 N 2 N N Dịch vịng dãy x2(- m) đi n đ/vị Chập vịng cĩ tính giao hĩan: x1 (n)N x2 (n)N = x2 (n)N x1 (n)N Nếu: L = N N = L Chọn: x1 1 2 x2 N = max{ N1 , N 2 }
- Ví dụ 1: Tìm chập vịng 2 dãy x1(n) = 2,3,4 x2 (n) = 1,2,3,4 ▪ Chọn độ dài N: N1 = 3, N 2 = 4 N = max{ N1 , N 2 } = 4 3 x3 (n)4 = x1 (n)4 x2 (n)4 = x1 (m)4 x2 (n − m)4 : 0 n 3 m=0 ▪ Đổi biến n->m: x1(m) = 2,3,4,0 x2(m) = 1,2,3,4 ▪ Xác định x (-m) : ~ 2 4 x2 (−m)4 = x2 (−m)4 rect4(n) = 1,4,3,2
- x2(m) x2(-m) 4 4 3 3 2 2 1 m 1 m 0 1 2 3 -3 -2 -1 0 ~ ~ x 2(−m) x2 (−m)4 = x2 (−m)rect4 (n) 4 4 3 3 2 2 1 m 1 m -3 -2 -1 0 1 2 3 4 0 1 2 3
- ▪ Xác định x2(n-m) là dịch vịng của x2(-m) đi n đơn vị n>0: dịch vịng sang phải, n<0: dịch vịng sang trái x2(-m)4 x2(1-m)4 4 4 3 3 2 2 1 m 1 m 0 1 2 3 0 1 2 3 x2(2-m)4 x2(3-m)4 4 4 3 3 2 2 1 m 1 m 0 1 2 3 0 1 2 3
- ▪ Nhân các mẫu 3 x1(m) & x2(n-m) x3 (n)4 = x1 (m)4 x2 (n − m)4 : 0 n 3 và cộng lại: m=0 3 ▪ n=0: x3 (0)4 = x1 (m)4 x2 (0 − m)4 = 26 m=0 3 ▪ n=1: x3 (1)4 = x1 (m)4 x2 (1 − m)4 = 23 m=0 3 ▪ n=2: x3 (2)4 = x1 (m)4 x2 (2 − m)4 = 16 m=0 3 ▪ n=3: x3 (3)4 = x1 (m)4 x2 (3 − m)4 = 25 m=0 Vậy: x3 (n)4 = x1 (n)4 x2 (n)4 = 26,23,16,25
- BÀI 4. BiẾN ĐỔI FOURIER NHANH FFT 1. KHÁI NiỆM BiẾN ĐỔI FOURIER NHANH FFT ▪ Vào những năm thập kỷ 60, khi cơng nghệ vi xử lý phát triển chưa mạnh thì thời gian xử lý phép tĩan DFT trên máy tương đối chậm, do số phép nhân phức tương đối lớn. N −1 kn ▪ DFT của x(n) cĩ độ dài N: X(k) = x(n)WN : 0 k N − 1 n=0 ▪ Để tính X(k), với mỗi giá trị k cần cĩ N phép nhân và (N-1) phép cộng, vậy với N giá trị k thì cần cĩ N2 phép nhân và N(N-1) phép cộng. ▪ Để khắc phục về mặt tốc độ xử lý của phép tính DFT, nhiều tác giả đã đưa ra các thuật tĩan riêng dựa trên DFT gọi là FFT (Fast Fourier Transform).
- 2. THUẬT TỐN FFT CƠ SỐ 2 a. THUẬT TỐN FFT CƠ SỐ 2 PHÂN THEO THỜI GIAN Giả thiết dãy x(n) cĩ độ dài N=2M, nếu khơng cĩ dạng lũy thừa 2 thì thêm vài mẫu 0 vào sau dãy x(n). Thuật tĩan dựa trên sự phân chia dãy vào x(n) thành các dãy nhỏ, do biến n biểu thị cho trục thời gian nên gọi là phân chia theo thời gian. N −1 N −1 N −1 kn kn kn X (k) = x(n)WN = x(n)WN + x(n)WN n=0 n=0,2,4 n=1,3,5 Thay n=2r với n chẵn và n=2r+1 với n lẽ: ( N / 2)−1 ( N / 2)−1 2kr k(2r+1) X(k) = x(2r)WN + x(2r + 1)WN r=0 r=0
- 2 2 j k 2r j kr Do: k 2r N N / 2 kr WN = e = e = WN / 2 ( N / 2)−1 ( N / 2)−1 kr k kr X(k) = x(2r)WN / 2 + WN . x(2r + 1)WN / 2 r=0 r=0 ( N / 2)−1 ( N / 2)−1 Đặt: kr kr X 0 (k) = x(2r)WN / 2 X1(k) = x(2r + 1)WN / 2 r=0 r=0 k X(k) = X0(k) +WN .X1(k) X0(k) – DFT của N/2 điểm ứng với chỉ số n chẵn X1(k) – DFT của N/2 điểm ứng với chỉ số n lẽ Lấy ví dụ minh họa cho x(n) với N=8
- ▪ Phân chia DFT- N điểm -> 2 DFT- N/2 điểm; X0(0) x(0) X(0) W0 X0(1) x(2) DFT X(1) n chẵn W1 N/2 X0(2) x(4) X(2) W2 điểm X0(3) x(6) X(3) W3 X1(0) x(1) X(4) W4 X1(1) x(3) DFT X(5) n lẽ W5 N/2 X1(2) x(5) X(6) W6 điểm X1(3) x(7) X(7) W7 Qui ước cách tính X(k) theo lưu đồ: - Nhánh ra của 1 nút bằng tổng các nhánh vào nút đĩ - Giá trị mỗi nhánh bằng giá trị nút xuất phát nhân hệ số
- Sau đĩ đánh lại chỉ số theo thứ tự các mẫu x(n), tiếp tục phân chia DFT của N/2 điểm thành 2 DFT của N/4 điểm theo chỉ số n chẵn và lẽ và cứ thế tiếp tục phân chia cho đến khi nào cịn DFT 2 điểm thì dừng lại. Ví dụ X0(k) được phân chia: ( N / 2)−1 ( N / 2)−1 kr kr X 0 (k) = x(2r)WN / 2 = g(r)WN / 2 r=0 r=0 ( N / 2)−1 ( N / 2)−1 kr kr = g(r)WN / 2 + g(r)WN / 2 r=0,2,4 r=1,3,5 ( N / 4)−1 ( N / 4)−1 kl k kl = g(2l)WN / 4 + WN / 2 g(2l + 1)WN / 4 l=0 l=0 k = X00(k) +WN / 2 .X01(k)
- ▪ Phân chia DFT- N/2 điểm -> 2 DFT- N/4 điểm của X0(k) X (0) 00 X (0) x(0) DFT 0 0 X00(1) W N/2 x(4) N/4 X0(1) 1 W N/2 X01(0) x(2) X0(2) DFT 2 W N/2 X01(1) x(6) N/4 X0(3) 3 W N/2 k ▪ Phân chia X1(k) tương tự: X1(k) = X10(k) +WN / 2 .X11(k) X (0) 10 X (0) x(1) DFT 1 0 X10(1) W N/2 x(5) N/4 X1(1) 1 W N/2 X11(0) x(3) X1(2) DFT 2 W N/2 X11(1) x(7) N/4 X1(3) 3 W N/2
- ▪ Lưu đồ DFT dãy x(n) sau 2 lần phân chia với N=8 X00(0) x(0) DFT X(0) 0 W0 X00(1) W x(4) N/4 X(1) 1 X (0) W2 W x(2) 01 X(2) DFT 4 2 X (1) W W x(6) N/4 01 X(3) W6 W3 X10(0) x(1) DFT X(4) W0 W4 X10(1) x(5) N/4 X(5) W2 W5 X11(0) x(3) X(6) DFT W4 W6 X11(1) x(7) N/4 X(7) W6 W7 x(0) X (0) ▪ Lưu đồ DFT 2 00 W0 = 1 điểm: N x(4) N/2 X00(1) WN =-1
- ▪ Lưu đồ DFT dãy x(n) sau 3 lần phân chia với N=8 x(0) X(0) W0 W0 x(4) X(1) -1 W2 W1 x(2) X(2) W4 W2 x(6) X(3) -1 W6 W3 x(1) X(4) W0 W4 x(5) X(5) -1 W2 W5 x(3) X(6) W4 W6 x(7) X(7) -1 W6 W7 X (p) X (p) m m+1 Xm(p) Xm+1(p) r W N Wr X (q) X (q) N m m+1 Xm(q) X (q) (r+N/2) r m+1 WN = - WN -1
- ▪ Lưu đồ DFT dãy x(n) sau 3 lần phân chia với N=8 x(0) X(0) x(4) X(1) -1 W0 x(2) X(2) W2 -1 x(6) X(3) Đảo -1 -1 bít W0 x(1) X(4) -1 W1 x(5) X(5) -1 -1 W0 W2 x(3) X(6) -1 W2 -1 W3 x(7) X(7) -1 -1 -1 Với N=2M -> M lần phân chia Số phép nhân = số phép cộng = NM/2=(N/2)log2N
- ▪ Bảng mơ tả qui luật đảo bít: Chỉ số Số nhị phân chưa Số nhị phân đảo Chỉ số tự nhiên đảo (n2,n1,n0) (n0,n1,n2) đảo 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7
- Ví dụ 1: Hãy vẽ lưu đồ và tính FFT cơ số 2 phân theo t/g x(n) = 1,2,3,4 x(0) X(0) x(2) X(1) -1 W0 x(1) X(2) W1 -1 x(3) X(3) -1 -1 ▪ k=0:X(0) = [x(0) + x(2)] + W0[x(1) + x(3)] = 10. ▪ k=1:X(1) = [x(0) - x(2)] + W1[x(1) - x(3)] = - 2 + j2. ▪ k=2:X(2) = [x(0) + x(2)] - W0[x(1) + x(3)] = - 2. ▪ k=3:X(3) = [x(0) - x(2)] - W1[x(1) - x(3)] = - 2 - j2.
- b. THUẬT TỐN FFT CƠ SỐ 2 PHÂN THEO TẦN SỐ Thuật tĩan dựa trên sự phân chia dãy ra X(k) thành các dãy nhỏ, do biến k biểu thị cho trục tần số nên gọi là phân chia theo tần số. N −1 ( N / 2)−1 N −1 kn kn kn X (k) = x(n)WN = x(n)WN + x(n)WN n=0 n=0 n= N / 2 ( N / 2)−1 ( N / 2)−1 kn k(n+ N / 2) = x(n)WN + x(n + N / 2)WN n=0 n=0 ( N / 2)−1 ( N / 2)−1 kn kN / 2 kn = x(n)WN + WN x(n + N / 2)WN n=0 n=0 ( N / 2)−1 k kn = x(n) + (−1) x(n + N / 2)WN n=0
- Với k chẵn, thay k=2r: ( N / 2)−1 rn X(2r) = x(n) + x(n + N / 2)WN / 2 n=0 Với k lẽ, thay k=2r+1 ( N / 2)−1 n rn X(2r + 1) = x(n) − x(n + N / 2)WN WN / 2 n=0 Đặt: g(n) = x(n) + x(n + N / 2); h(n) = x(n) − x(n + N / 2) ( N / 2)−1 ( N / 2)−1 rn n rn X (2r) = g(n)WN / 2 X(2r + 1) = h(n)WN WN / 2 n=0 n=0 X(2r) – DFT của N/2 điểm ứng với chỉ số k chẵn X(2r+1) – DFT của N/2 điểm ứng với chỉ số k lẽ
- ▪ Phân chia DFT N=8 điểm -> 2 DFT N/2= 4 điểm g(0) x(0) X(0) g(1) x(1) DFT X(2) g(2) N/2 k chẵn x(2) X(4) g(3) điểm x(3) X(6) h(0) W0 x(4) X(1) -1 1 h(1) W x(5) DFT X(3) -1 2 h(2) W N/2 k lẻ x(6) X(5) -1 3 h(3) W điểm x(7) X(7) -1
- Sau đĩ đánh lại chỉ số theo thứ tự các mẫu X(k), tiếp tục phân chia DFT của N/2 điểm thành 2 DFT của N/4 điểm theo chỉ số k chẵn và lẽ. Tiếp tục phân chia cho đến khi nào cịn DFT 2 điểm thì dừng lại. Dữ liệu ra X(k) được sắp xếp theo thứ tự đảo bít, cịn dữ liệu vào được sắp theo thứ tự tự nhiên. Số phép nhân và phép cộng trong lưu đồ phân theo tần số bằng với số phép nhân và cộng trong lưu đồ phân theo thời gian.
- ▪ Lưu đồ DFT dãy x(n) sau 3 lần phân chia với N=8 x(0) X(0) x(1) X(4) W0 -1 x(2) X(2) -1 W2 x(3) X(6) -1 -1 Đảo W0 bít x(4) X(1) -1 W1 x(5) X(5) -1 -1 W2 W0 x(6) X(3) -1 W3 -1 W2 x(7) X(7) -1 -1 -1
- Ví dụ 2: Hãy vẽ lưu đồ và tính FFT cơ số 2 phân theo t/s x(n) = 1,2,3,4 x(0) X(0) x(1) X(2) -1 0 x(2) W X(1) -1 W1 x(3) X(3) -1 -1 k=0:X(0) = [x(0) + x(2)] + [x(1) + x(3)] = 10. k=2:X(2) = [x(0) + x(2)] - [x(1) + x(3)] = - 2. k=1:X(1) = [x(0) - x(2)] + W1[x(1) - x(3)] = - 2 + j2. k=3:X(3) = [x(0) - x(2)] - W1[x(1) - x(3)] = - 2 - j2.
- 3. THUẬT TỐN FFT VỚI N=N1N2 Giả thiết độ dài dãy x(n) cĩ thể phân tích N=N1N2, nếu độ dài khơng thể biểu diễn dưới dạng trên thì thêm vài mẫu 0 vào sau dãy x(n). Giả thiết dữ liệu vào được sắp xếp vào trong mảng theo thứ tự từng cột với số cột N1 và số hàng N2: n2 n1 0 1 N1-1 0 x(0) x(N2) x[N2(N1-1)] 1 x(1) x(N2+1) x[N2(N2-1)+1] N2-1 x(N2-1) x(2N2-1) x[N1N2-1]
- Lấy ví dụ sắp xếp dãy x(n) với N=12, chọn N1=3 và N2=4 n2 n1 0 1 2 0 x(0) x(4) x(8) 1 x(1) x(5) x(9) 2 x(2) x(6) x(10) 3 x(3) x(7) x(11) Các chỉ số n của x(n), k của X(k) xác định: 0 n1 N1 n = n1N2 + n2 0 n2 N2 0 n1 N1 k = k1 + k2N1 0 n2 N2
- DFT N điểm dãy x(n) được phân tích: N2 −1 N1 −1 (k1 +k2 N1 )(n2 +n1N2 ) X(k) = X(k1 + k2 N1 ) = x(n2 + n1 N 2 )WN n2=0 n1 =0 N2 −1 N1 −1 n2k1 n1k1N2 n2k2 N1 n1k2 N1N2 = x(n2 + n1 N 2 )WN WN WN WN n2=0 n1 =0 Do:W n1k1N2 = W n1k1 ;W n2k2N1 = W n2k2 ;W n1k2N1N2 = 1 N N1 N2 N N N2 −1 N1 −1 X(k) = x(n + n N )W n1k1 W n2k1 W n2k2 2 1 2 N1 N N2 n2=0 n1 =0
- N1 −1 F(n ,k ) = x(n + n N )W n1k1 2 1 2 1 2 N1 Đặt: n1 =0 n2k1 G(n2 ,k1 ) = F(n2 ,k1 ).WN N2 −1 X(k) = G(n ,k )W n2k2 2 1 N2 n2=0 Các bước tiến hành thuật tĩan: Sắp xếp dữ liệu vào theo thứ tự từng cột, mảng x Tính DFT theo từng hàng mảng x, được F(n2,k1) n2k1 Tính mảng hệ số WN n2k1 Nhân mảng F(n2,k1) với WN , được G(n2,k1) Tính DFT theo từng cột mảng G(n2,k1), được X(k) Đọc dữ liệu ra theo thứ tự từng hàng X(k).
- Ví dụ 1: Nêu các bước tính và vẽ lưu đồ thuật tĩan FFT dãy x(n) với N=N1N2=12, chọn N1=3 và N2=4 Sắp xếp dữ liệu vào theo thứ tự từng cột như bảng: n2 n1 0 1 2 0 x(0) x(4) x(8) 1 x(1) x(5) x(9) 2 x(2) x(6) x(10) 3 x(3) x(7) x(11)
- Tính DFT theo từng hàng mảng x, được F(n2,k1): N1 −1 F(n ,k ) = x(n + n N )W n1k1 2 1 2 1 2 N1 n1 =0 n2 k1 0 1 2 0 F(0,0) F(0,1) F(0,2) 1 F(1,0) F(1,1) F(1,2) 2 F(2,0) F(2,1) F(2,2) 3 F(3,0) F(3,1) F(3,2)
- n2k1 Tính mảng hệ số WN n2 k1 0 1 2 0 0 0 0 WN WN WN 0 1 2 1 WN WN WN 0 2 4 2 WN WN WN 0 3 6 3 WN WN WN
- Nhân các phần tử mảng F(n2,k1) với các hệ số của mảng n2k1 WN tương ứng, được G(n2,k1) : nikj Phần tử: G(ni,kj) = F(ni,kj). WN n2 k1 0 1 2 0 G(0,0) G(0,1) G(0,2) 1 G(1,0) G(1,1) G(1,2) 2 G(2,0) G(2,1) G(2,2) 3 G(3,0) G(3,1) G(3,2)
- Tính DFT theo từng cột mảng G(n2,k1), được X(k): N2 −1 X(k) = X(k + N k ) = G(n ,k )W n2k2 1 1 2 2 1 N2 n2 =0 k2 k1 0 1 2 0 X(0) X(1) X(2) 1 X(3) X(4) X(5) 2 X(6) X(7) X(8) 3 X(9) X(10) X(11) Đọc dữ liệu ra theo thứ tự từng hàng X(k)
- ▪ Lưu đồ FFT dãy x(n) N=N1N2, với N1=3, N2=4: X(0) x(0) DFT DFT x(4) N1 X(3) điểm N2 x(8) điểm X(6) 0 W X(9) x(1) DFT W1 x(5) N1 X(1) W2 x(9) điểm DFT X(4) 0 W N2 x(2) X(7) DFT W2 điểm x(6) N X(10) 1 W4 x(10) điểm X(2) W0 x(3) DFT X(5) DFT 3 W N2 x(7) N1 X(8) W6 điểm x(11) điểm X(11)