intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Tín hiệu số - Xử lý dữ liệu - Chương 6

Chia sẻ: Nguyen Bac A. Châu | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
163
lượt xem 73
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tín hiệu số - Xử lý dữ liệu. Tiến sĩ: Đinh Đức Anh Vũ.Chương 6: 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: Tín hiệu số - Xử lý dữ liệu - Chương 6

  1. Chương 6 BK TP.HCM BIẾN ĐỔI FOURIER NHANH (FFT) Faculty of Computer Science and Engineering HCMC University of Technology 268, av. Ly Thuong Kiet, T.S. Đinh Đức Anh Vũ District 10, HoChiMinh city Telephone : (08) 864-7256 (ext. 5843) Fax : (08) 864-5137 Email : anhvu@hcmut.edu.vn http://www.cse.hcmut.edu.vn/~anhvu
  2. 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 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 2
  3. DFT & IDFT § 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 )W N kn 0 £ k £ N -1 - j 2Np n=0 N -1 WN = e 1 IDFT x(n) = N å X k =0 ( k )W - 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 § Tính trực tiếp ì N -1 ï X R ( k ) = å [ x R ( n ) cos( N ) + x I ( n ) sin( N )] 2 p kn 2 p kn ª N2 phép nhân phức ï n=0 ª N(N-1) phép cộng phức í N -1 → Độ phức tạp : O(N2) ï X ( k ) = - [ x ( n ) sin( 2 p kn ) - x ( n ) cos( 2 p kn )] § Biến đổi WN ïî I å n=0 R N I N ª 2N2 phép tính lượng giác ª 4N2 phép nhân số thực Giải thuật tính DFT tối ưu mỗi phép toán ª 4N(N-1) phép cộng số thực theo những cách khác nhau ª Một số phép toán chỉ số Ñoái xöùng WNk + N / 2 = -WNk và địa chỉ để nạp x(n) Tuaàn hoaøn WNk + N = WNk DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 3
  4. Phương pháp chia-trị § 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 § Phương pháp ª 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 0 1 … M-1 m 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ữ • Theo dòng n = Ml + m 2 x(2,0) x(2,1) … x(2,M-1) • 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) • Theo dòng k = Mp + q • Theo cột k = p + qL DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 4
  5. Phương pháp chia-trị N -1 X (k ) = å x ( n )W n=0 N kn 0 £ k £ N -1 Với: M -1 L -1 x(n) X(k) : theo cột : theo hàng X ( p, q ) = åå x(l , m)WN( Mp + q )( mL +l ) m =0 l =0 WNNmp = 1 WN( Mp+q)(mL+l ) = WNMLmpWNmLqWNMplWNlq WNmqL = WNmq/ L = WMmq ì lq é M -1 L -1 mq ù ü lp WNMpl = WNpl/ M = WLpl X ( p, q) = å íWN ê å x(l , m)WM ú ýWL (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) ªCộng phức : N(M+L-2) DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 5
  6. Phương pháp chia-trị § 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) § PP chia-trị rất hiệu quả khi N= r1r2r3…rv ª Phân rã nhỏ hơn đến (v-1) lần § 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 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 6
  7. Phương pháp chia-trị § 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) m điể x(5) x(2) X(5) X(1) T3 DFT 2 điểm x(3) x(0) DF X(4) X(0) x(1) X(3) § 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 1 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) DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 7
  8. FFT cơ số 2 N -1 X (k ) = å x ( n )W n=0 N kn k = 0 ,1,..., N - 1 = å n even x ( n )W Nkn + å n old x ( n )W Nkn ( N / 2 ) -1 ( N / 2 ) -1 = å x ( 2 m )W N 2 mk + å x ( 2 m + 1)W Nk ( 2 m +1 ) m =0 m =0 WN2 = WN / 2 ( N / 2 ) -1 ( N / 2 ) -1 X (k ) = å m =0 f1 ( m)W km N /2 +W k N å m =0 f 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 ) k = 0,1,..., N / 2 DFTN / 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 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 8
  9. 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) ì X (k ) = G1 (k ) + G2 (k ) k = 0,1,..., N2 - 1 k=0,1,…,(N/2-1) í î X ( k + 2 ) = G1 ( k ) - G2 ( k ) N k = 0,1,..., N2 - 1 1) 1) 1) - ) - - /2 -2 /2 /2 N N (N (N X( x( DFT 1 1 G F m 1) 2 điểm ) ể 1 - -2 2- /2 đi N N/ N (N ) ) -1 x( (2 /2 W ) 2 F N 4 1 )F x( X( m N ) (1 (1 1) ể DFT ) FT (2 X( đi 1 1 F )G )x ) 2 điểm 0) (2 DFT D ) (0 ) /2 (0 0 4 X( 2 x( )F x( 1 1 G F 2 điểm N DFT (1 N 1 ) (3 1) FT 2 F 2 điểm W )x 2+ ) ) N 0 D (0 (0 1 ) N/ x( W 2 2 G /2 ( F DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE N X 9 X(
  10. FFT cơ số 2 § Tiếp tục phân f1(n) và f2(n) thành các chuỗi N/4 điểm ì v11 ( n ) = f1 ( 2 n ) n = 0 ,1,..., N 4 -1 ï ï v12 ( n ) = f 1 ( 2 n + 1) n = 0 ,1,..., -1 N 4 DFT í vij(n) Vij(k) ï v 21 ( n ) = f 2 (2n) n = 0 ,1,..., -1 N/4 điểm N 4 ïv ( n ) = f 2 ( 2 n + 1) n = 0 ,1,..., N -1 î 22 4 ì F1 ( k ) = V11 ( k ) + W Nk / 2V12 ( k ) k = 0 ,1,..., N 4 -1 ï F ï 1 ( k + N 4 ) = V 11 ( k ) - W k N / 2V12 ( k ) k = 0 ,1,..., N 4 -1 í ï F2 ( k ) = V 21 ( k ) + W N / 2V 22 ( k ) k = 0 ,1,..., -1 k N 4 ï F (k + N ) = V (k ) - W k V (k ) k = 0 ,1,..., N -1 î 2 4 21 N / 2 22 4 § 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 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 10
  11. FFT cơ số 2 § 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] DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 11
  12. FFT cơ số 2 x(0) X(0) x(4) X(1) W 0 -1 8 x(2) X(2) W 0 -1 8 x(6) X(3) W 0 -1 W 2 -1 8 8 x(1) X(4) W 0 -1 8 x(5) X(5) W80 -1 W81 -1 x(3) X(6) W 0 -1 W 2 -1 8 8 x(7) X(7) W 0 -1 W 2 -1 W 3 -1 8 8 8 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 12
  13. FFT cơ số 2 § 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 • 2 cộng phức b B = a–WN’b 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ỗ DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 13
  14. FFT cơ số 2 § 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 Bộ Địa Phân Bộ Địa Phân Bộ Địa nhớ chỉ chia nhớ chỉ chia nhớ 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 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 14
  15. FFT cơ số 2 § 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) X(2) DFT x(2) 4 điểm X(4) b B = (a–b)WN’ –1 W N’ x(3) X(6) x(4) X(1) 0 -1 W 8 x(5) X(3) 1 DFT -1 W 8 4 điểm x(6) X(5) 2 -1 W 8 x(7) X(7) 3 -1 W 8 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 15
  16. 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) DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 16
  17. FFT cơ số 4 ì lq é M -1 L -1 mq ù ü X ( p , q ) = å íW N ê å x ( l , m )W M ú ýW Llp l =0 î ë m =0 ûþ [ ] 3 X ( p, q) = å WNlq F (l , q) W4lp p = 0,1,2,3 l =0 DFT N/4 điểm N /4 ìl = 0,1,2,3 F (l , q) = å x(l , m)W mq N /4 í m=0 î q = 0,1,.., ( 4 - 1) N ì x(l , m) = x(4m + l ) í î X ( p , q ) = X ( 4 p + q) N é X (0, q ) ù é1 1 1 1 ù é W N0 F (0, q ) ù ê X (1, q ) ú ê1 - j ê ú ê ú=ê - 1 j úú ê W Nq F (1, q ) ú ê X ( 2, q ) ú ê1 - 1 1 - 1 ú êW N2 q F ( 2, q ) ú ê ú ê ú ê 3q ú ë X (3, q ) û ë1 j - 1 - j û êëW N F (3, q ) úû DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 17
  18. FFT cơ số 4 WN0 -j -1 WNq j -1 1 WN2q -1 j -1 0 -j WN3q q 2q Dạng rút gọn 3q DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 18
  19. 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 1 0 ù é1 0 1 0 ù é W N0 F ( 0 , q ) ù ê X (1, q ) ú ê 0 ê ú ê ú=ê 1 0 - j úú êê 1 0 -1 0 úú ê W Nq F ( 0 , q ) ú ê X ( 2, q ) ú ê1 0 - 1 0 ú ê0 1 0 1 ú êW N2 q F ( 0 , q ) ú ê ú ê úê ú ê 3q ú ë X ( 3, q ) û ë0 1 0 j û ë0 1 0 - 1û êëW N F ( 0 , q ) úû (3N/8)log2N : Nhân phức (giảm 25% vs FFT2) Nlog2N : Cộng phức (bằng FFT2) DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 19
  20. Hiện thực các giải thuật FFT § 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ỗ • 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ự § IDFT 1 N -1 x(n) = N å X k =0 ( k )W - 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 • Đả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 § DFT với số điểm khác 2v hoặc 4v ® đệm thêm các số 0 § Độ 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ụ) DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

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.

 

Đồng bộ tài khoản
2=>2