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

Tài Liệu: Biến Đổi Fourier

Chia sẻ: Trần Trong Nghia | Ngày: | Loại File: PDF | Số trang:0

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

Biến đổi Fourier có rất nhiều ứng dụng khoa học, ví dụ như trong vật lý, số học, xử lý tín hiệu, xác suất, thống kê, mật mã, âm học, hải dương học, quang học, hình học và rất nhiều lĩnh vực khác. Trong xử lý tín hiệu và các ngành liên quan, biến đổi Fourier thường được nghĩ đến như sự chuyển đổi tín hiệu thành các thành phần biên độ và tần số. Sự ứng dụng rộng rãi của biến đổi Fourier bắt nguồn từ những tính chất hữu dụng của biến đổi này:...

Chủ đề:

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

Lưu

Nội dung Text: Tài Liệu: Biến Đổi Fourier

  1. Chương 6 BK BIẾN ĐỔI FOURIER TP.HCM NHANH (FFT) T.S. Đinh Đức Anh Vũ Faculty of Computer Science and Engineering HCMC University of Technology 268, av. Ly Thuong Kiet, 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 å x ( n )W X (k ) = 0 £ k £ N -1 kn DFT N p - j 2N WN = e n=0 N -1 1 å - x(n) = 0 £ n £ N -1 X (k )WN kn IDFT N k =0 ª 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 ï X ( k ) = - [ x ( n ) sin( 2 p kn ) - x ( n ) cos( 2 p kn )] → Độ phức tạp : O(N2) å0 R ïI I N N § Biến đổi WN î n= 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 4N2 phép nhân số thực ª theo những cách khác nhau 4N(N-1) phép cộng số thực ª Một số phép toán chỉ số ª WN + N / 2 = -WNk k Ñoái xöùng và địa chỉ để nạp x(n) WN + N = WN k k Tuaàn hoaøn 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ữ 2 x(2,0) x(2,1) … x(2,M-1) • Theo dòng n = Ml + m • 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 ( n )W X (k ) = 0 £ k £ N -1 kn N n=0 Với: M -1 L -1 X ( p, q ) = åå x(l , m)WN Mp + q )( mL +l ) x(n) : theo cột ( X(k) : theo hàng m =0 l =0 WNNmp = 1 WNMp+q)(mL+l ) = WN WN WN WN ( MLmp mLq Mpl lq W N = W N / L = WM mqL mq mq WNMpl = WNpl/ M = WLpl ì lq é M -1 mq ù ü lp L -1 X ( p, q) = å íWN ê å x(l , m)WM ú ýWL (1): Tính L DFT M điểm ë m =0 ûþ l =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) è Độ phức tạp DFT L điểm 3 ª Nhân phức : N(M+L+1) X(p,q) ª 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 chia-trị PP tính trực tiếp • Nhân phức : N(M+L+1) • Nhân phức : N2 • Cộng phức : N(M+L-2) • Cộng phức : N(N-1) 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 2 Giải thuật 1 1. Lưu trữ t/h theo hàng 1. Lưu trữ t/h theo cột 2. Tính DFT L điểm của mỗi cột 2. Tính DFT M điểm của mỗi hàng 3. Nhân ma trận kết quả với hệ số pha WNpm 3. Nhân ma trận kết quả với hệ số pha WNlq 4. Tính DFT M điểm của mỗi hàng 4. Tính DFT L điểm của mỗi cột 5. Đọc ma trận kết quả theo cột 5. Đọc ma trận kết quả theo hàng 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(5) x(2) X(1) T3 DFT 2 điểm DF x(3) X(4) x(0) 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(N-1) x(0) x(1) x(2) … … … … Giải thuật m=0 m=1 m=M-1 chia theo thời gian f1(2n) l=0 x(N-2) x(0) x(2) … n= 0,1, …, N/2-1 f2(2n+1) l=1 x(N-1) x(1) x(3) … DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 7
  8. FFT cơ số 2 N -1 å x ( n )W = k = 0 ,1,..., N - 1 kn X (k ) N n=0 å å = x ( n )W Nkn + x ( n )W Nkn n even n old ( N / 2 ) -1 ( N / 2 ) -1 å å x ( 2 m + 1)W Nk ( 2 m +1 ) = + 2 mk x ( 2 m )W N WN = WN / 2 2 m =0 m =0 ( N / 2 ) -1 ( N / 2 ) -1 å å X (k ) = +W km k km f1 ( m)W f 2 (m)WN / 2 N /2 N m =0 m =0 = F1 (k ) + WN F2 (k ) k = 0,1,..., N - 1 k F1(k), F2(k) tuần hoàn f1 ( m) ¬¾ ¾2 ® F1 (k ) ¾ k = 0,1,..., N / 2 chu kỳ N/2 DFTN / f 2 ( m) ¬¾ ¾2 ® F2 ( k ) ¾ k = 0,1,..., N / 2 F1(k+ N/2) = F1(k) DFTN / F2(k+ N/2) = F2(k) ì X (k ) = F1 (k ) + WN F2 (k ) k = 0,1,.., N - 1 k ï WN + N / 2 = -WN k k 2 í ï X (k + N ) = F1 (k ) - WN F2 (k ) k = 0,1,.., N - 1 k î 2 2 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 8
  9. FFT cơ số 2 ìG1 (k ) = F1 (k ) k = 0,1,.., N - 1 ï 2 í ïG2 (k ) = WN F2 (k ) k = 0,1,.., N - 1 k î 2 G1(k) X(k) DFT2 G2(k) X(k+ N/2) ì X (k ) = G1 (k ) + G2 (k ) k = 0,1,..., N - 1 k=0,1,…,(N/2-1) 2 í X (k + N ) = G1 (k ) - G2 (k ) k = 0,1,..., N - 1 î 2 2 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 ) DFT iểm 2đ 0) (2 D ) (0 ) /2 (0 0 4 X( 2 x( )F x( 1 1 G F DFT iểm 2đ N (1 N1 ) (3 1) FT 2 F 2 đi ể m W )x 2+ ) ) N0 D (0 (0 1 ) N/ x( W 2 2 G /2 ( F NX DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 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 ) = n = 0 ,1,..., -1 f1 ( 2 n ) N 4 ï ï v12 ( n ) = f 1 ( 2 n + 1) n = 0 ,1,..., -1 N DFT 4 í Vij(k) vij(n) ï v 21 ( n ) = n = 0 ,1,..., -1 N/4 điểm f 2 (2n) N 4 ïv ( n ) = f 2 ( 2 n + 1) n = 0 ,1,..., -1 N î 22 4 ì F1 ( k ) = V11 ( k ) + W Nk / 2V12 ( k ) k = 0 ,1,..., -1 N 4 ï F1 ( k + N ) = V11 ( k ) - W Nk / 2V12 ( k ) k = 0 ,1,..., -1 N ï 4 4 í ï 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,..., -1 N î2 21 N / 2 22 4 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) [0,4] [2,6] [1,5] [3,7] x(3) x(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) -1 0 W 8 x(2) X(2) -1 0 W 8 x(6) X(3) -1 0 -1 2 W W 8 8 x(1) X(4) -1 0 W8 x(5) X(5) -1 -1 W80 W81 x(3) X(6) -1 -1 2 W 0 W 8 8 x(7) X(7) -1 -1 -1 2 0 3 W W W 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 Địa Phân Địa Phân Địa Bộ Bộ Bộ chỉ chia chỉ chia chỉ nhớ nhớ nhớ 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 4 điểm x(2) X(4) b B = (a–b)WN’ –1 W N’ x(3) X(6) x(4) X(1) 0 W -1 8 x(5) X(3) DFT 1 W -1 4 điểm 8 X(5) x(6) 2 W -1 8 x(7) X(7) 3 W -1 8 DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 15
  16. FFT cơ số 4 N = 4v x(0) x(2) x(4) … … … x(N-1) 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(4n) x(0) x(4) … … x(N-4) l=1 x(1) x(5) … … x(N-3) x(4n+1) n = 0,1,…,N/4-1 x(2) x(6) … … x(N-2) l=2 x(4n+2) x(3) x(7) … … x(N-1) l=3 x(4n+3) DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 16
  17. FFT cơ số 4 ì lq é M -1 mq ù ü L -1 X ( p , q ) = å íW N ê å x ( l , m )W M ú ýW Llp ë m =0 ûþ l =0 î [ ] 3 X ( p, q) = å WN F (l , q) W4lp p = 0,1,2,3 lq l =0 DFT N/4 điểm ìl = 0,1,2,3 N /4 F (l , q) = å x(l , m)W mq í N /4 q = 0,1,.., ( N - 1) î m=0 4 ì x(l , m) = x(4m + l ) í X ( p, q ) = X ( N p + q ) î 4 1 ù é W N F ( 0, q ) ù é X (0, q ) ù é1 1 0 1 ê ú ê X (1, q ) ú ê1 - j - 1 j ú ê W Nq F (1, q ) ú ê ú=ê ú 1 - 1 ú êW N2 q F ( 2, q ) ú ê X ( 2, q ) ú ê1 - 1 ú ê 3q ú ê úê - 1 - j û êW N F (3, q ) ú ë X (3, q ) û ë1 j ë û DSP – Lecture 6, © 2007, Dr. Dinh-Duc Anh-Vu – CSE 17
  18. FFT cơ số 4 0 WN -j -1 q WN j -1 1 WN q 2 -1 j 0 -1 -j WN q 3 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 0 ù é W N0 F ( 0 , q ) ù é X (0, q ) ù é1 0 ù é1 0 1 0 1 ê ú ê X (1, q ) ú ê 0 0 - j ú ê1 0 ú ê W Nq F ( 0 , q ) ú -1 1 0 ê ú=ê úê ú 1 ú êW N2 q F ( 0 , q ) ú ê X ( 2, q ) ú ê1 - 1 0 ú ê0 0 1 0 ú ê 3q ú ê úê úê - 1û êW N F ( 0 , q ) ú X ( 3, q ) û ë 0 1 0 j û ë0 1 0 ë ë û (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 N -1 1 å - x(n) = 0 £ n £ N -1 X (k )WN kn N k =0 ª 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

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2432 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.

 

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