Bài giảng Xử lý tín hiệu số: Chương 4 - TS. Vũ Văn Sơn

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPT | Số trang:40

Thêm vào BST

Báo xấu

82
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 4 cung cấp cho người học các nội dung liên quan đến biểu diễn tín hiệu và hệ thống trong miền tần số rời rạc. Mục tiêu của chương này giúp người học hiểu được khái niệm DFT, hiểu được biến đổi Fourier rời rạc (DFT), các tính chất DFT và biến đổi fourier nhanh (FFT).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Xử lý tín hiệu số: Chương 4 - TS. Vũ Văn Sơn

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 j n Biến đổi Fourier dãy x(n): X( ) x ( n)e 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: N 1 2 j kn x ( n)e N :0 k N 1 X (k ) n 0 0 : k còn lạ i N 1 j 2 x ( n)W Nkn : 0 k N 1 WN e N 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 W N( r mN ) e N e N W Nr
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 X (k ) x ( n)W Nkn : 0 k N 1 n 0 1 N 1 x ( n) X ( k )W N kn : 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 X (k ) x(n)W kn j 1 2 3 n 0 4 W 4 e 4 j; W 4 1;W 4 j 3 X ( 0) x ( n)W40 x ( 0) x (1) x ( 2) x ( 3) 10 n 0 3 X (1) x ( n)W4n x ( 0) x (1)W41 x ( 2)W42 x ( 3)W43 2 j2 n 0 3 X ( 2) x ( n)W42 n x ( 0) x (1)W42 x ( 2)W44 x ( 3)W46 2 n 0 3 X ( 3) x ( n)W43 n x ( 0) x (1)W43 x ( 2)W46 x ( 3)W49 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 X 1 (k ) N x2 ( n)N X 2 (k ) N DFT Thì: a1 x1 ( n) N a2 x2 ( n) N a1 X 1 ( k ) N a2 X 2 ( k ) N Nếu: Lx1 N1 N2 Lx2 Chọn: N max{ N 1 , N 2 } b) Dịch vòng: DFT Nếu: x ( n) N X (k ) N DFT Thì: x ( n n0 ) N W Nkn0 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 rect N (n)
Ví dụ 1: Cho: x ( n) 1,2,3,4 a) Tìm dịch tuyến tính: x(n+3), x(n2) b)Tìm dịch vòng: x(n+3)4, x(n2)4 x(n) 4 3 2 1 n 0 1 2 3 x(n+3) x(n2) 4 4 3 3 a) 2 2 1 n 1 n 3 2 1 0 0 1 2 3 4 5
x(n) x(n1)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 3 2 1 n 0 1 2 3
c) Chập vòng: DFT DFT Nếu: x1 ( n) N X 1 (k ) N x2 ( n)N X 2 (k ) N DFT Thì: x1 ( n) N x2 ( n)N X 1 (k ) N X 2 (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 x1(n) & x2(n) m 0 Và: x2 ( n m ) N x~2 ( n m ) N rect 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: Lx1 N1 N2 Lx2 Chọn: N max{ N 1 , N 2 }
Ví dụ 1: Tìm chập vòng 2 dãy  Chọn độ dài N: N1 3, N 2 4 N max{ N 1 , 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:  Xác định x2(m)4:
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 ) x 2 ( m )4 x~2 ( 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(nm) là dịch vòng của x2(m) đi n đơn vị n>0: dịch vòng sang phải, n
 Nhân các mẫu 3 x1(m) & x2(nm) x3 ( n)4 x1 (m )4 x2 ( n m )4 : 0 n 3 m 0 và cộng lại: 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:
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  DFT của x(n) có độ dài N: X ( k ) x ( n)W Nkn : 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à (N1) 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 TOÁN FFT CƠ SỐ 2 a. THUẬT TOÁ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 X (k ) x ( n)W Nkn x ( n)W Nkn x ( n)W Nkn 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 X (k ) x ( 2r )W N2 kr x ( 2r 1)W Nk ( 2 r 1) r 0 r 0
2 2 j k 2r j kr Do: W Nk 2 r e N e N /2 W Nkr/ 2 ( N / 2) 1 ( N / 2) 1 X (k ) x ( 2r )W Nkr/ 2 W Nk . x ( 2r 1)W Nkr/ 2 r 0 r 0 ( N / 2) 1 ( N / 2) 1 Đặt: X 0 ( k ) x ( 2r )W Nkr/ 2 X1 (k ) x ( 2r 1)W Nkr/ 2 r 0 r 0 X (k ) X 0 ( k ) W Nk . X 1 ( 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 DFT X0(1) X(1) x(2) n chẵn N/2 W1 x(4) X0(2) X(2) điểm W2 x(6) X0(3) X(3) W3 X1(0) x(1) X(4) W4 x(3) DFT X1(1) X(5) n lẽ W5 N/2 X1(2) x(5) X(6) điểm W6 x(7) X1(3) 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 X 0 (k ) x ( 2r )W Nkr/ 2 g ( r )W Nkr/ 2 r 0 r 0 ( N / 2) 1 ( N / 2) 1 g ( r )W Nkr/ 2 g ( r )W Nkr/ 2 r 0 , 2 , 4... r 1, 3 , 5... ( N / 4) 1 ( N / 4) 1 g ( 2l )W Nkl/ 4 W Nk / 2 g ( 2l 1)W Nkl/ 4 l 0 l 0 X 00 ( k ) W Nk / 2 . X 01 ( k )
 Phân chia DFT N/2 điểm > 2 DFT N/4 điểm của X0(k) X00(0) x(0) DFT X0(0) N/4 X00(1) W0N/2 x(4) X0(1) X01(0) W1N/2 x(2) DFT X0(2) W N/2 2 N/4 X01(1) x(6) X0(3) W N/2 3  Phân chia X1(k) tương tự: X1 (k ) X 10 ( k ) W Nk / 2 . X 11 ( k ) X10(0) x(1) DFT X1(0) N/4 X10(1) W0N/2 x(5) X1(1) X11(0) W1N/2 x(3) DFT X1(2) W N/2 2 N/4 X11(1) x(7) X1(3) W N/2 3
 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) W0 W 0 N/4 X00(1) X(1) x(4) X01(0) W2 W 1 x(2) DFT X(2) W 4 W 2 N/4 X01(1) X(3) x(6) W6 W 3 X10(0) x(1) DFT X(4) W 0 W 4 N/4 X10(1) X(5) x(5) W 2 W 5 X11(0) x(3) DFT X(6) W 4 W 6 N/4 X11(1) X(7) x(7) W 6 W 7 x(0) X00(0)  Lưu đồ DFT 2 điểm: W0N = 1 x(4) X00(1) WN N/2 =1