zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Kỹ Thuật - Công Nghệ

» Kĩ thuật Viễn thông

Bài giảng Xử lý số tín hiệu: Chương 6 - TS. Đinh Đức Anh Vũ

Chia sẻ: Sơn Tùng | Ngày: | Loại File: PDF | Số trang:0

Báo xấu

114
lượt xem 5
download

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

Bài giảng "Xử lý số tín hiệu - Chương 6: Biến đổi Fourier nhanh" cung cấp cho người học các kiến thức: Tính DFT và IDFT, tính trực tiếp, phương pháp chia - trị, FFT cơ số 2, thực hiện các giải thuật FFT,... Mời các bạn cùng tham khảo nội dung chi tiết.

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ý số tín hiệu: Chương 6 - TS. Đinh Đức Anh Vũ

Chương 6 BIẾN ĐỔI FOURIER NHANH (FFT) T.S. Đinh Đức Anh Vũ Nội dung Tính DFT & IDFT Tính trực tiếp Biến đổi WN Chia-Trị Lọc tuyến tính Cơ số 2 Cơ số 4 Tách cơ số Goertzel Chirp-z Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 2 Bài Giảng Môn: Xử Lý Tín Hiệu Số
DFT & IDFT z Tính DFT: xác định chuỗi N giá trị phức {X(k)} khi biết trước chuỗi {x(n)} chiều dài N N −1 DFT X (k ) = ∑ x(n)WNkn 0 ≤ k ≤ N −1 n =0 −j2Nπ N −1 WN =e 1 IDFT x ( n) = N ∑ X (k )W k =0 − kn N 0 ≤ n ≤ N −1 – Giải thuật tính DFT cũng được áp dụng cho việc tính IDFT z Tính trực tiếp  N −1 – N2 phép nhân phức  n=0 ∑  X R ( k ) = [ xR ( n) cos( N ) + xI (n) sin( N )] 2πkn 2πkn – N(N-1) phép cộng phức  N −1  → Độ phức tạp: O(N )2  X I ( k ) = − n =0 ∑ [ xR (n) sin( 2πNkn ) − xI ( n) cos( 2πNkn )] z Biến đổi WN – 2N2 phép tính lượng giác Giải thuật tính DFT tối ưu mỗi phép toán theo những cách khác nhau – 4N2 phép nhân số thực – 4N(N-1) phép cộng số thực Đôi xúng WNk + N / 2 = −WNk – Một số phép toán chỉ số và địa chỉ để nạp x(n) Tuân hoàn WNk + N = WNk Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 3 Bài Giảng Môn: Xử Lý Tín Hiệu Số Phương pháp chia-trị z Nguyên tắc: phân rã nhỏ việc tính DFT N điểm thành việc tính các DFT kích thước nhỏ hơn → các giải thuật FFT z PP – Giả sử N=L.M – Lưu trữ x(n) vào mảng 2 chiều LxM (l: chỉ số hàng, m: chỉ số cột) n→ 0 1 2 … N-1 x(0) x(1) x(2) … x(N-1) l m 0 1 … M-1 0 x(0,0) x(0,1) … x(0,M-1) 1 x(1,0) x(1,1) … x(1,M-1) – Cách lưu trữ 2 x(2,0) x(2,1) … x(2,M-1) z Theo dòng n = Ml + m z Theo cột n = l + mL … … … … L-1 x(L-1,0) x(L-1,1) … x(L-1,M-1) – Tương tự, các giá trị DFT X(k) tính được cũng sẽ được lưu trữ trong ma trận LxM (p: chỉ số hàng, q: chỉ số cột) z Theo dòng k = Mp + q z Theo cột k = p + qL Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 4 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Phương pháp chia-trị N −1 X (k ) = ∑ x(n)WNkn 0 ≤ k ≤ N −1 n =0 Với: M −1 L −1 x(n) : theo cột X ( p, q) = ∑∑ x(l , m)WN( Mp+q )(mL+l ) X(k) : theo hàng m = 0 l =0 WNNmp = 1 WN( Mp+q )(mL+l ) = WNMLmpWNmLqWNMplWNlq WNmqL = WNmq/ L = WMmq  lq M −1 L −1  WNMpl = WNpl/ M = WLpl X ( p, q) = ∑ WN  ∑ x(l , m)WMmq  WLlp (1): Tính L DFT M điểm l =0   m=0  – Nhân phức: LM2 – Cộng phức: LM(M-1) DFT M điểm (2): Tính G(l,q) 1 F(l,q) – Nhân phức: LM (3): Tính X(p,q) 2 G(l,q) – Nhân phức: ML2 – Cộng phức: ML(L-1) 3 DFT L điểm Î Độ phức tạp X(p,q) – Nhân phức: N(M+L+1) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 5 – Cộng phức: N(M+L-2) Bài Giảng Môn: Xử Lý Tín Hiệu Số Phương pháp chia-trị z Hiệu quả PP tính trực tiếp PP chia-trị • Nhân phức : N2 • Nhân phức : N(M+L+1) • Cộng phức : N(N-1) • Cộng phức : N(M+L-2) N=1000 → L=2, M=500 106 nhân phức → 503,000 (~ N/2) z PP chia-trị rất hiệu quả khi N= r1r2r3…rv – Phân rã nhỏ hơn đến (v-1) lần – Hiệu quả hơn z Giải thuật n = l + mL n = Ml + m k = Mp + q k = qL + p Giải thuật 1 Giải thuật 2 1. Lưu trữ t/h theo cột 1. Lưu trữ t/h theo hàng 2. Tính DFT M điểm của mỗi hàng 2. Tính DFT L điểm của mỗi cột 3. Nhân ma trận kết quả với hệ số pha WNlq 3. Nhân ma trận kết quả với hệ số pha WNpm 4. Tính DFT L điểm của mỗi cột 4. Tính DFT M điểm của mỗi hàng 5. Đọc ma trận kết quả theo hàng 5. Đọc ma trận kết quả theo cột Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 6 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Phương pháp chia-trị z Mô hình tính toán DFT 6 điểm thông qua việc tính DFT 3 điểm và DFT 2 điểm W6lq x(4) X(2) iểm x(5) X(5) 3đ x(2) X(1) T DFT 2 điểm DF x(3) x(0) X(4) X(0) x(1) X(3) z Giải thuật tính FFT cơ số 2 – Nếu N = r1r2r3…rv = rv → mô hình tính DFT có cấu trúc đều (chỉ dùng một DFT r điểm) – r = 2 → FFT cơ số 2 – Chọn M = N/2 và L = 2 x(0) x(1) x(2) … … … … x(N-1) Giải thuật m=0 m=1 m=M-1 chia theo thời gian l=0 x(0) x(2) … x(N-2) f1(2n) n= 0,1, …, N/2-1 l=1 x(1) x(3) … x(N-1) f2(2n+1) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 7 Bài Giảng Môn: Xử Lý Tín Hiệu Số FFT cơ số 2 N −1 X (k ) = ∑ x(n)WNkn k = 0,1,..., N − 1 n =0 = ∑ x(n)W n even kn N + ∑ x(n)WNkn n old ( N / 2 ) −1 ( N / 2 ) −1 = ∑ x(2m)W m=0 2 mk N + ∑ x(2m + 1)W m =0 k ( 2 m +1) N ( N / 2 ) −1 ( N / 2 ) −1 WN2 = WN / 2 X (k ) = ∑ f (m)W m=0 1 km N /2 + WNk ∑f m=0 2 (m)WNkm/ 2 = F1 (k ) + WNk F2 (k ) k = 0,1,..., N − 1 F1(k), F2(k) tuần hoàn f1 (m) ← → F1 (k ) DFTN / 2 k = 0,1,..., N / 2 chu kỳ N/2 f 2 ( m) ← → F2 ( k ) DFTN / 2 k = 0,1,..., N / 2 F1(k+ N/2) = F1(k) F2(k+ N/2) = F2(k)  X (k ) = F1 (k ) + WNk F2 (k ) k = 0,1,.., N2 − 1 WNk + N / 2 = −WNk   X (k + N2 ) = F1 (k ) − WNk F2 (k ) k = 0,1,.., N2 − 1 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 8 Bài Giảng Môn: Xử Lý Tín Hiệu Số
FFT cơ số 2 G1 (k ) = F1 (k ) k = 0,1,.., N2 − 1  G2 (k ) = WNk F2 (k ) k = 0,1,.., N2 − 1 G1(k) X(k) G2(k) DFT2 X(k+ N/2) k=0,1,…,(N/2-1)  X (k ) = G1 (k ) + G2 (k ) k = 0,1,..., − 1 N 2   X (k + 2 ) = G1 (k ) − G2 (k ) k = 0,1,..., N2 − 1 N ) ) ) -1 -1 -1 ) /2 -2 /2 /2 N N (N (N X( x( DFT 1 G 1 F ểm iểm ) -1 2 điểm ) -1 -2 /2 2 N N/ đ N (N ) ) x( -1 (2 /2 W ) 2 F N 4 1 )F x( X( N ) (1 (1 1) DFT ) FT (2 X( đi 1 1 F G )x ) 2 điểm (2 0) DFT ) D ) (0 ) /2 (0 0 4 X( 2 )F x( x( 1 G 1 F 2 điểm N DFT (1 N 1 ) (3 ) FT +1 2 F W 2 điểm )x ) 2 ) D N 0 (0 (0 1 ) N/ x( W 2 G 2 /2 ( F N X X( Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 9 Bài Giảng Môn: Xử Lý Tín Hiệu Số FFT cơ số 2 z Tiếp tục phân f1(n) và f2(n) thành các chuỗi N/4 điểm v11 (n) = f1 ( 2n) n = 0,1,..., N4 − 1  v12 (n) = f1 (2n + 1) n = 0,1,..., N4 − 1  v21 (n) = f 2 ( 2n) n = 0,1,..., N4 − 1 vij(n) DFT Vij(k) v (n) = f 2 (2n + 1) n = 0,1,..., − 1 N N/4 điểm  22 4  F1 (k ) = V11 (k ) + WNk / 2V12 (k ) k = 0,1,..., N4 − 1   F1 (k + 4 ) = V11 ( k ) − WN / 2V12 (k ) k = 0,1,..., N4 − 1 N k   F2 (k ) = V21 ( k ) + WN / 2V22 (k ) k = 0,1,..., N4 − 1 k  F (k + N ) = V (k ) − W k V (k ) k = 0,1,..., N4 − 1  2 4 21 N / 2 22 z Hiệu quả DFT trực tiếp N=2v điểm Các DFT 2 điểm FFT cơ số 2 Nhân phức: N2 Nhân phức: (N/2)log2N Cộng phức: N2 – N Cộng phức: Nlog2N Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 10 Bài Giảng Môn: Xử Lý Tín Hiệu Số
FFT cơ số 2 z Ví dụ: tính DFT 8 điểm x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) Phân theo thời gian x(0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) [0,1,2,3,4,5,6,7] x(0) x(4) x(2) x(6) [0,2,4,6] [1,3,5,7] x(1) x(5) x(3) x(7) [0,4] [2,6] [1,5] [3,7] Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 11 Bài Giảng Môn: Xử Lý Tín Hiệu Số FFT cơ số 2 x(0) X(0) x(4) X(1) W80 -1 x(2) X(2) W 0 -1 8 x(6) X(3) W80 -1 W82 -1 x(1) X(4) W80 -1 x(5) X(5) W80 -1 W81 -1 x(3) X(6) W 0 -1 W82 -1 8 x(7) X(7) 0 -1 W 2 W -1 W 3 -1 8 8 8 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 12 Bài Giảng Môn: Xử Lý Tín Hiệu Số
FFT cơ số 2 z Khối tính toán cơ bản cho DFT 2 điểm (hình con bướm) a A = a+WN’b Độ phức tạp • 1 nhân phức b B = a-WN’b • 2 cộng phức W N’ -1 N= 2v: + Log2N : tầng tính toán + N/2 : khối tính toán cơ bản cho mỗi lớp Bộ nhớ: + Vào : (a,b) - số phức + Ra : (A,B) - số phức + Có thể lưu (A,B) đè lên (a,b) Î Chỉ cần N ô nhớ phức (2N ô nhớ thực) Î Tính toán tại chỗ Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 13 Bài Giảng Môn: Xử Lý Tín Hiệu Số FFT cơ số 2 z Thứ tự chuỗi dữ liệu vào sau khi phân (v-1) lần – Biểu diễn các chỉ số ở dạng nhị phân – Chuỗi sau khi phân chia sẽ là lấy theo thứ tự đảo các bit Địa Phân Địa Phân Địa Bộ nhớ Bộ nhớ Bộ nhớ chỉ chia chỉ chia chỉ x(0) 000 x(0) 000 x(0) 000 x(1) 001 x(2) 010 x(4) 100 x(2) 010 x(4) 100 x(2) 010 x(3) 011 x(6) 110 x(6) 110 x(4) 100 x(1) 001 x(1) 001 x(5) 101 x(3) 011 x(5) 101 x(6) 110 x(5) 101 x(3) 011 x(7) 111 x(7) 111 x(7) 111 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 14 Bài Giảng Môn: Xử Lý Tín Hiệu Số
FFT cơ số 2 z Phân chia theo tần số – Phương pháp chia và trị – M = 2, L = N/2 – Chuỗi dữ liệu nhập được sắp xếp theo cột – Phân chia X(k) thành X(2k) và X(2k+1) – Sau đó có thể phân chia tiếp tục mỗi X(k chẵn) và X(k lẻ) x(0) X(0) a A = (a+b) WN’ x(1) DFT X(2) x(2) 4 điểm X(4) b B = (a–b)WN’ x(3) X(6) -1 W N’ x(4) X(1) -1 W80 x(5) DFT X(3) -1 W81 4 điểm x(6) X(5) -1 W82 x(7) X(7) -1 W83 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 15 Bài Giảng Môn: Xử Lý Tín Hiệu Số FFT cơ số 4 x(0) x(2) x(4) … … … x(N-1) N = 4v l,p = 0,1,2,3 n = 4m + l L = 4, M = N/4 m,q = 0,1,…,N/4 – 1 k = (N/4)p + q m=0 m=1 m=(N/4)-1 l=0 x(0) x(4) … … x(N-4) x(4n) l=1 x(1) x(5) … … x(N-3) x(4n+1) n = 0,1,…,N/4-1 l=2 x(2) x(6) … … x(N-2) x(4n+2) l=3 x(3) x(7) … … x(N-1) x(4n+3) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 16 Bài Giảng Môn: Xử Lý Tín Hiệu Số
FFT cơ số 4  lq M −1 L −1  X ( p, q) = ∑ WN  ∑ x(l , m)WMmq  WLlp l =0   m =0  [ ] 3 X ( p, q ) = ∑ WNlq F (l , q ) W4lp p = 0,1,2,3 l =0 N /4 l = 0,1,2,3 F (l , q ) = ∑ x(l , m)WNmq/ 4  DFT N/4 điểm q = 0,1,.., ( 4 − 1) N m =0  x(l , m) = x(4m + l )   X ( p, q ) = X ( 4 p + q ) N  X (0, q) 1 1 1 1   WN0 F (0, q)   X (1, q)  1 − j − 1 j   q   =   WN F (1, q )   X (2, q) 1 − 1 1 − 1 WN F (2, q) 2 q      3q   X (3 , q )  1 j − 1 − j W  N F ( 3, q )  Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 17 Bài Giảng Môn: Xử Lý Tín Hiệu Số FFT cơ số 4 WN0 -j q -1 W N j -1 1 WN2q -1 j -1 0 3q -j W N q 2q Dạng rút gọn 3q Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 18 Bài Giảng Môn: Xử Lý Tín Hiệu Số
FFT cơ số 4 Độ phức tạp: 1 khối tính toán cần + 3 nhân phức + 12 cộng phức N=4v + Tầng tính toán : v = log4N + Mỗi tầng có : N/4 khối tính toán 3vN/4 = (3N/8)log2N : Nhân phức (giảm 25% vs FFT2) 12vN/4 = (3N/2)log2N : Cộng phức (tăng 50% vs FFT2) Biểu diễn lại nhân ma trận  X (0, q) 1 0 0  1 1 0 1 0   WN0 F (0, q)   X (1, q)  0    = 1 0 − j  1 0 − 1 0   WNq F (0, q)   X (2, q) 1 0 − 1 0  0 1 0 1  WN2q F (0, q)        X (3, q)  0 1 0 j  0 1 0 − 1 WN3q F (0, q)  (3N/8)log2N : Nhân phức (giảm 25% vs FFT2) Nlog2N : Cộng phức (bằng FFT2) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 19 Bài Giảng Môn: Xử Lý Tín Hiệu Số Hiện thực các giải thuật FFT z FFT cơ số 2 – Tính toán hình bướm: (N/2)log2N lần – Hệ số quay WNk: được tính một lần và lưu trong bảng – Bộ nhớ: 2N nếu muốn việc tính toán được thực hiện tại chỗ z 4N nếu muốn đơn giản hóa các tác vụ chỉ số và điều khiển; đồng thời cho phép chuỗi nhập và xuất theo đúng thứ tự z IDFT N −1 1 x ( n) = N ∑ X (k )W k =0 − kn N 0 ≤ n ≤ N −1 – Khác nhau cơ bản giữa việc tính DFT và IDFT là hệ số 1/N và dấu của hệ số pha WN z Đảo chiều sơ đồ tính DFT, đổi dấu hệ số pha, và chia kết quả cuối cùng cho N → IDFT z DFT với số điểm khác 2v hoặc 4v → đệm thêm các số 0 z Độ phức tạp – Tác vụ số học (nhân phức, cộng phức) – Cấu trúc hiện thực của giải thuật (qui tắc vs bất qui tắc) – Kiến trúc của các bộ DSPs (xử lý song song các tác vụ) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 21 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Ứng dụng của các giải thuật FFT z Tính DFT của 2 chuỗi thực – x1(n) và x2(n): chuỗi thực độ dài N cần tính DFT – Định nghĩa chuỗi x(n) = x1(n) + jx2(n) 0 ≤ n ≤ N-1 – X(k) = X1(k) + jX2(k) (tính tuyến tính của DFT) x ( n) + x * ( n) x1 (n) = 2 X 1 (k ) = 1 2 {DFT [x(n)] + DFT x* (n) }[ ] x2 ( n ) = x ( n) − x * ( n) 2j X 2 (k ) = {DFT [x(n)] − DFT x* (n) } 1 2 [ ] X 1 (k ) = 1 2 [X (k ) + X ( N − k )] * x (n) ←→ X ( N − k ) * DFTN * X 2 (k ) = 1 2 [X (k ) − X ( N − k )] * Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 22 Bài Giảng Môn: Xử Lý Tín Hiệu Số Ứng dụng của các giải thuật FFT z Tính DFT của chuỗi thực 2N điểm – g(n): chuỗi thực độ dài 2N cần tính DFT – Tách thành 2 chuỗi x1(n) = g(2n) và x2(n) = g(2n+1) 0 ≤ n ≤ N-1 – Định nghĩa chuỗi x(n) = x1(n) + jx2(n) 0 ≤ n ≤ N-1 – X(k) = X1(k) + jX2(k) (tính tuyến tính của DFT) X 1 (k ) = 1 2 [X (k ) + X ( N − k )] * X 2 (k ) = 1 2 [X (k ) − X ( N − k )] * N −1 N −1 G (k ) = ∑ g (2n)W 2 nk 2N + ∑ g (2n + 1)W2(N2 n +1) k n =0 n =0 N −1 N −1 = ∑ x1 (n)W nk N +W k 2N ∑ x (n)W 2 nk N n =0 n =0 G (k ) = X 1 (k ) + W2kN X 2 (k ) k = 0,1, K, N − 1 G (k + N ) = X 1 (k ) − W2kN X 2 (k ) k = 0,1, K, N − 1 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 23 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Ứng dụng của các giải thuật FFT z Lọc tuyến tính các chuỗi dữ liệu dài – Overlap-add DFT + FFT – Overlap-save z Phương pháp – h(n) – Đáp ứng xung đơn vị của bộ lọc (chiều dài M) z Được đệm thêm L-1 số không sao cho N = L + M – 1 = 2v z H(k): DFT N điểm của h(n), theo thứ tự đảo nếu h(n) được sắp theo thứ tự thuận (Giải thuật FFT suy giảm theo tần số) – xm(n) – khối dữ liệu chiều dài L (đã được phân cắt) z Được đệm thêm M–1 điểm (giá trị tùy theo PP lọc được dùng) z Xm(k): DFT N điểm của xm(n), cũng theo thứ tự đảo (Giải thuật FFT suy giảm theo tần số) – Ym(k) = H(k)Xm(k) z H(k) và Xm(k) cùng có thứ tự đảo → Ym(k) theo thứ tự đảo z ym(n) = IDFTN{Ym(k)} sẽ đúng theo thứ tự thuận nếu dùng giải thuật FFT suy giảm theo thời gian – Không cần thiết đảo vị trí các dữ liệu trong việc tính DFT và IDFT z Tính tương quan (tương tự) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 24 Bài Giảng Môn: Xử Lý Tín Hiệu Số Phương pháp lọc tuyến tính z FFT không hiệu quả khi tính DFT (IDFT) tại một số điểm (< log2N) → tính trực tiếp z Giải thuật Goertzel – Dựa vào tính chu kỳ của WNk và biểu diễn việc tính toán DFT như lọc tuyến tính N −1 N −1 X (k ) = W − kN N ∑ x(m)W m =0 km N = ∑ x(m)WN− k ( N − m ) m =0 N −1 Đăt yk (n) = ∑ x(m)WN− k ( n − m ) = x(n) * hk (n) H k ( z) = 1 m=0 1 − WN−k z −1 vói hk (n) = WN− knu (n) Một pole trên vòng tròn đơn vị ⇒ X ( k ) = y k ( n) n = N tại tần số ωk=2πk/N Việc tính DFT tại một điểm k có thể được thực hiện bằng cách cho t/h đi vào bộ cộng hưởng một pole tại tần số ωk=2πk/N Thay vì tính tổng chập trực tiếp, ta có thể dùng PTSP yk (n) = WN− k yk (n − 1) + x(n) yk (−1) = 0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 25 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Giải thuật Goertzel z Kết hợp từng cặp các bộ cộng hưởng có pole liên hợp phức 1 − WN− k z −1 H k ( z) = 1 − 2 cos(2πk / N ) z −1 + z − 2 z Hiện thực bằng dạng chuẩn tắc (dạng II) vk (n) = 2 cos 2Nπk vk (n − 1) − vk (n − 2) + x(n) n = 0,1,..., N yk (n) = vk (n) − WNk vk (n − 1) n=N vk(n) – Với đ/k đầu + + x(n) yk(n) vk (−1) = vk (−2) = 0 z-1 – z vk(n) được lặp lại cho n = 0, 1, …, N 2 cos( 2Nπk ) Wnk – Mỗi vòng cần 1 phép nhân thực + z yk(n) được tính duy nhất một lần cho n = N z-1 -1 z Nếu x(n) là t/h thực, cần N+1 phép nhân thực để tính X(k) và X(N-k) {do tính đối xứng} z Giải thuật Goertzel chỉ thích hợp khi số giá trị DFT cần tính khá nhỏ (≤ log2N) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 26 Bài Giảng Môn: Xử Lý Tín Hiệu Số Giải thuật BĐ Chirp-z z DFT N điểm ~ X(zk) với zk = ej2πkn/N , k=0,1,…,N-1 (các điểm cách đều trên vòng tròn đơn vị) N −1 z BĐ Z của x(n) tại các điểm zk X ( z k ) = x(n) zk− n ∑ k = 0,1,..., L − 1 n =0 z Nếu zk = rej2πkn/N (zk là N điểm cách đều nhau trên vòng tròn bk r) N −1 X ( z k ) = ∑ [ x(n)r − n ]e − j 2πkn / N k = 0,1,..., N − 1 n =0 – Việc tính DFT có thể được thực hiện bằng giải thuật FFT cho chuỗi x(n)r-n jθ z Tổng quát, zk nằm trên cung xoắn ốc bắt đầu từ điểm z0 = r0 e 0 (đi vào hoặc đi ra gốc tọa độ) z = r e jθ 0 ( R e jφ0 ) k k 0 k = 0,1, K, L − 1 0 Vòng tròn Im(z) Im(z) Im(z) Im(z) đơn vị r0 r0 θ0 Re(z) Re(z) Re(z) Re(z) R0 = r0 = 1 R0 = 1, r0 < 1 R0 < 1 R0 > 1 Φ0 = θ0 = 0 Φ 0 = θ0 = 0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 27 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Giải thuật BĐ Chirp-z y (k ) X ( zk ) = k = 0,1, K, L − 1 BĐ chirp-z h( k ) V = R0 e jφ0 2 h( n) = V n /2 g (n) = x(n)(r0 e jθ 0 ) − n V − n 2 /2 N −1 y ( k ) = ∑ g ( n) h( k − n) k = 0,1,K , L − 1 n =0 2 R0 = 1 ⇒ h(n) = e jφ0 n /2 = e j ( n φ 0 / 2 ) n ≡ e j ωn ω = nφ0 / 2 Tần số của t/h mũ phức h(n), tăng tuyến tính theo thời gian → h(n): chirp signal Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 28 Bài Giảng Môn: Xử Lý Tín Hiệu Số Giải thuật BĐ Chirp-z z Xác định tổng chập vòng của chuỗi g(n) N điểm và chuỗi h(n) M điểm (M > N) – N-1 điểm đầu là các điểm lặp lại – M-(N-1) điểm còn lại chứa kết quả N −1 y ( k ) = ∑ g ( n) h ( k − n ) k = 0,1, K, L − 1 n =0 z Giả sử M = L + (N-1) z M điểm của chuỗi h(n) được xác định –(N–1) ≤ n ≤ (L–1) z Định nghĩa chuỗi M điểm h1(n) = h(n–N+1) n = 0,1,…,M–1 z H1(k) = DFTM{h1(n)} z G(k) = DFTM{g(n)} (sau khi đã đệm thêm vào g(n) L-1 số 0) z Y1(k) = G(k)H(k) → y1(n) = IDFT{Y1(k)} n = 0,1,…,M–1 z N-1 điểm đầu tiên của y1(n) là các điểm lặp → loại bỏ chúng z Các điểm kết quả là giá trị của y1(n) khi N-1 ≤ n ≤ M–1 – y(n) = y1(n+N-1) n = 0,1,…,L-1 z X(zk)= y(k)/h(k) k = 0,1,…,L-1 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 29 Bài Giảng Môn: Xử Lý Tín Hiệu Số

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2397 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.