›
›

Bài giảng Xử lý tín hiệu số - Chương 6: Giải thuật cho biến đổi Fourier (FFT) - Đinh Đức Anh Vũ

pdf 30 trang ngocly 60
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xử lý tín hiệu số - Chương 6: Giải thuật cho biến đổi Fourier (FFT) - Đinh Đức Anh Vũ", để 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:

  • pdfbai_giang_xu_ly_tin_hieu_so_chuong_6_giai_thuat_cho_bien_doi.pdf

Nội dung text: Bài giảng Xử lý tín hiệu số - Chương 6: Giải thuật cho biến đổi Fourier (FFT) - Đinh Đức Anh Vũ

  1. dce 2011 Chương 6 Giải thuật cho biến đổi Fourier (FFT) BK TP.HCM ©2011, TS. Đinh Đức Anh Vũ
  2. dce 2011 Nội dung Tính DFT & IDFT Tính Biến đổi trực tiếp WN Lọc Chia-Trị tuyến tính Cơ số 2 Cơ số 4 Tách cơ số Goertzel Chirp-z DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 2
  3. dce 2011 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 kn DFT X (k) = ∑ x(n)WN 0 ≤ k ≤ N −1 n=0 N −1 1 −kn IDFT x(n) = ∑ X (k)WN 0 ≤ n ≤ N −1 N k =0 – Giải thuật tính DFT cũng được áp dụng cho việc tính IDFT  N −1 = 2πkn + 2πkn • Tính trực tiếp X R (k) ∑[xR (n)cos( N ) xI (n)sin( N )]  = 2 n 0 – N phép nhân phức  N −1 – N(N-1) phép cộng phức  2πkn 2πkn X I (k) = − [xR (n)sin( ) − xI (n)cos( )] 2  ∑ N N → Độ phức tạp : O(N )  n=0 • Biến đổi W N Giải thuật tính DFT tối ưu mỗi phép toán – 2N2 phép tính lượng giác – 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 kN+ /2 k Doi xung WWNN= − – Một số phép toán chỉ số kN+ k và địa chỉ để nạp x(n) Tuan hoan WWNN= DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 3
  4. dce 2011 Phương pháp chia-trị (1) • 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 L × M (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 L × M (p: chỉ số hàng, q: chỉ số cột) • Theo dòng k = Mp + q • Theo cột k = p + qL DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 4
  5. dce 2011 Phương pháp chia-trị (2) N −1 kn X (k) = ∑ x(n)WN 0 ≤ k ≤ N −1 n=0 Với: M −1 L−1 x(n) : theo cột (Mp+q)(mL+l) X ( p,q) = ∑∑ x(l,m)WN X(k) : theo hàng = = m 0 l 0 Nmp WN =1 (Mp+q)(mL+l) = MLmp mLq Mpl lq mqL mq mq WN WN WN WN WN WN = WN / L = WM Mpl pl pl L−1 M −1 WN = WN / M = WL  lq  mq  lp 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 Nhân phức: LM F(l,q) (3): Tính X(p,q)  2 2 G(l,q) Nhân phức: ML Cộng phức: ML(L-1) Độ phức tạp 3 DFT L điểm Nhân phức: N(M+L+1) X(p,q) Cộng phức: N(M+L-2) DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 5
  6. dce 2011 Phương pháp chia-trị (3) • 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 lq pm 3. Nhân ma trận kết quả với hệ số pha WN 3. Nhân ma trận kết quả với hệ số pha WN 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 – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 6
  7. dce 2011 Phương pháp chia-trị (4) • 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 lq W6 x(4) X(2) x(5) X(5) x(2) X(1) x(0)x(3) ểm X(0)X(4) x(1) X(3) DFT 2đi DFT • Giải thuật tính FFT cơ số 2 v – Nếu N = r1r2r3 rv = r → 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 – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 7
  8. dce 2011 FFT cơ số 2 (1) N −1 kn X (k) = ∑ x(n)WN k = 0,1, , N −1 n=0 kn kn = ∑ x(n)WN + ∑ x(n)WN n even n old ( N / 2)−1 (N / 2)−1 2mk k (2m+1) = ∑ x(2m)WN + ∑ x(2m +1)WN m=0 m=0 2 WN = WN / 2 (N / 2)−1 (N / 2)−1 km k km X (k) = ∑ f1(m)WN / 2 +WN ∑ f2 (m)WN / 2 m=0 m=0 k = F1(k) +WN 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 (m)←→ F (k) k = 0,1, , N / 2 F (k+ N/2) = F (k) 2 DFTN / 2 2 1 1 F2(k+ N/2) = F2(k) k N  = + = − k +N / 2 k X (k) F1(k) WN F2 (k) k 0,1, , 2 1 W = −W  N N N k N X (k + 2 ) = F1(k) −WN F2 (k) k = 0,1, , 2 −1 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 8
  9. dce 2011 FFT cơ số 2 (2) N G1(k) = F1(k) k = 0,1, , 2 −1  k N G2 (k) = WN F2 (k) k = 0,1, , 2 −1 G1(k) X(k) G2(k) DFT2 X(k+ N/2) N k=0,1, ,(N/2-1) X (k) = G1(k) + G2 (k) k = 0,1, , 2 −1  N N X (k + 2 ) = G1(k) − G2 (k) k = 0,1, , 2 −1 DFT 2 điểm DFT DFT2 đi ểm DFT2 đi ểm 2 điểm DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 9
  10. dce 2011 FFT cơ số 2 (3) • Tiếp tục phân f1(n) và f2(n) thành các chuỗi N/4 điểm N v11(n) = f1(2n) n = 0,1, , 4 −1  N v12 (n) = f1(2n +1) n = 0,1, , 4 −1  N DFT v21(n) = f2 (2n) n = 0,1, , −1  4 vij(n) Vij(k)  N N/4 điểm v22 (n) = f2 (2n +1) n = 0,1, , 4 −1 F (k) = V (k) +W k V (k) k = 0,1, , N −1  1 11 N / 2 12 4 N k N F1(k + 4 ) = V11(k) −WN / 2V12 (k) k = 0,1, , 4 −1  k N F2 (k) = V21(k) +WN / 2V22 (k) k = 0,1, , 4 −1  N k N F2 (k + 4 ) = V21(k) −WN / 2V22 (k) k = 0,1, , 4 −1 • Hiệu quả DFT trực tiếp N=2v điểm Các DFT 2 điểm FFT cơ số 2 2 Nhân phức: N Nhân phức: (N/2)log2N 2 Cộng phức: N – N Cộng phức: Nlog2N DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 10
  11. dce 2011 FFT cơ số 2 (4) • Ví dụ: tính DFT 8 điểm x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) ời gian ời th theo Phân 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 – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 11
  12. dce 2011 FFT cơ số 2 (5) • 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 – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 12
  13. dce 2011 FFT cơ số 2 (6) x(0) X(0) x(4) X(1) 0 -1 W8 x(2) X(2) 0 -1 W8 x(6) X(3) 0 -1 2 -1 W8 W8 x(1) X(4) 0 -1 W8 x(5) X(5) 0 -1 1 -1 W8 W8 x(3) X(6) 0 -1 2 -1 W8 W8 x(7) X(7) 0 -1 2 -1 3 -1 W8 W8 W8 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 13
  14. dce 2011 Baseline Parallel Architecture Size 16 8192 ∆ 1 1 1 1 Pins 448 229K 2 2 2 2 Fly 32 53K 3 3 3 3 Mult 4 4 4 4 Add 5 5 5 5 Shift 0 0 6 6 6 6 7 7 7 7 8 8 8 8 Parallel FFT 9 9 9 9 . Butterfly structure 10 10 10 10 . Removes redundant 11 11 11 11 calculation 12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 14
  15. dce 2011 Parallel-Pipelined Architecture Size 16 8192 ∆ 1 1 1 1 Pins 448 229K 2 2 2 2 Fly 32 53K 3 3 3 3 Mult 96 159K 4 4 4 4 Add 288 480K 5 5 5 5 Shift 0 0 6 6 6 6 7 7 7 7 8 8 8 8 A pipelined version 9 9 9 9 . IO Bound 10 10 10 10 . 100% Efficient 11 11 11 11 12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 15
  16. dce 2011 FFT cơ số 2 (7) • 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 – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 16
  17. dce 2011 FFT cơ số 2 (8) • 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’ –1 W N’ x(3) X(6) x(4) X(1) -1 W 0 x(5) 8 X(3) DFT -1 1 W8 x(6) 4 điểm X(5) -1 W 2 x(7) 8 X(7) -1 3 W8 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 17
  18. dce 2011 FFT cơ số 4 (1) 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 – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 18
  19. dce 2011 FFT cơ số 4 (2) L−1 M −1  lq  mq  lp X ( p,q) = ∑ WN ∑ x(l,m)WM WL l=0  m=0  3 lq lp X ( p,q) = ∑[WN F(l,q)]W4 p = 0,1,2,3 l=0 N / 4 l = 0,1,2,3 DFT N/4 điểm = mq F(l,q) ∑ x(l,m)WN / 4  N m=0 q = 0,1, ,( 4 −1) x(l,m) = x(4m + l)  N X ( p,q) = X ( 4 p + q) 0 X (0,q) 1 1 1 1 WN F(0,q)       X (1,q) 1 − j −1 j W q F(1,q)   =   N      2q  X (2,q) 1 −1 1 −1 WN F(2,q)     3q   X (3,q) 1 j −1 − jWN F(3,q) DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 19
  20. dce 2011 FFT cơ số 4 (3) 0 WN -j W q -1 N j -1 1 2q WN -1 j -1 0 3q -j WN q 2q Dạng rút gọn 3q DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 20
  21. dce 2011 FFT cơ số 4 (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 X (0,q) 1 0 1 0 1 0 1 0 WN F(0,q)        X (1,q) 0 1 0 − j 1 0 −1 0 W q F(0,q)   =    N       2q  X (2,q) 1 0 −1 0 0 1 0 1 WN F(0,q)      3q   X (3,q) 0 1 0 j 0 1 0 −1WN F(0,q) (3N/8)log2N : Nhân phức (giảm 25% vs FFT2) Nlog2N : Cộng phức (bằng FFT2) DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 21
  22. dce 2011 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 k – Hệ số quay WN : đượ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 −kn x(n) = ∑ X (k)WN 0 ≤ n ≤ N −1 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 – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 22
  23. dce 2011 Ứng dụng của các giải thuật FFT • 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) 1 * x1(n) = X (k) = {DFT[x(n)]+ DFT[x (n)]} 2 1 2 x(n) − x* (n) 1 x (n) = X (k) = {DFT[x(n)]− DFT[x* (n)]} 2 2 j 2 2 1 * X1(k) = 2 [X (k) + X (N − k)] x* (n)←DFTN → X * (N − k) 1 * X 2 (k) = 2 [X (k) − X (N − k)] DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 23
  24. dce 2011 Ứng dụng của các giải thuật FFT • 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) 1 * X1(k) = 2 [X (k) + X (N − k)] 1 * X 2 (k) = 2 [X (k) − X (N − k)] N −1 N −1 2nk (2n+1)k G(k) = ∑ g(2n)W2N + ∑ g(2n +1)W2N n=0 n=0 N −1 N −1 nk k nk = ∑ x1(n)WN +W2N ∑ x2 (n)WN n=0 n=0 k G(k) = X1(k) +W2N X 2 (k) k = 0,1,, N −1 k G(k + N) = X1(k) −W2N X 2 (k) k = 0,1,, N −1 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 24
  25. dce 2011 Ứng dụng của các giải thuật FFT • Lọc tuyến tính các chuỗi dữ liệu dài – Overlap-add DFT + FFT – Overlap-save • Phương pháp – h(n) – Đáp ứng xung đơn vị của bộ lọc (chiều dài M) • Được đệm thêm L-1 số không sao cho N = L + M – 1 = 2v • 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) • Được đệm thêm M–1 điểm (giá trị tùy theo PP lọc được dùng) • 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) • H(k) và Xm(k) cùng có thứ tự đảo → Ym(k) theo thứ tự đảo • 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 • Tính tương quan (tương tự) DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 25
  26. dce 2011 Phương pháp lọc tuyến tính • 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 • Giải thuật Goertzel k – Dựa vào tính chu kỳ của WN và biểu diễn việc tính toán DFT như lọc tuyến tính N −1 N −1 −kN km −k (N −m) X (k) = WN ∑ x(m)WN = ∑ x(m)WN m=0 m=0 1 N −1 H (z) = −k (n−m) k − −k −1 Đăt yk (n) = ∑ x(m)WN = x(n)*hk (n) 1 WN z m=0 −kn Một pole trên vòng tròn đơn vị vói hk (n) = WN u(n) tại tần số ω =2πk/N ⇒ = k X (k) yk (n) n=N Việc tính DFT tại một điểm k có thể Thay vì tính tổng chập trực tiếp, ta có thể dùng PTSP được thực hiện bằng cách cho t/h −k yk (n) = WN yk (n −1) + x(n) yk (−1) = 0 đi vào bộ cộng hưởng một pole tại tần số ωk=2πk/N DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 26
  27. dce 2011 Giải thuật Goertzel • Kết hợp từng cặp các bộ cộng hưởng có pole liên hợp phức 1−W −k z −1 H (z) = N k 1− 2cos(2πk / N)z −1 + z −2 • Hiện thực bằng dạng chuẩn tắc (dạng II) 2πk vk (n) = 2cos N vk (n −1) − vk (n − 2) + x(n) n = 0,1, , N k yk (n) = vk (n) −WN vk (n −1) n = N vk(n) – Với đ/k đầu + + x(n) y (n) v (−1) = v (−2) = 0 – k k k Z–1 • vk(n) được lặp lại cho n = 0, 1, , N 2πk k 2cos( N ) W – Mỗi vòng cần 1 phép nhân thực + n • yk(n) được tính duy nhất một lần cho n = N Z–1 –1 • 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} • Giải thuật Goertzel chỉ thích hợp khi số giá trị DFT cần tính khá nhỏ (≤ log2N) DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 27
  28. dce 2011 Giải thuật BĐ Chirp-z (1) j2πkn/N • DFT N điểm ~ X(zk) với zk = e , k=0,1, ,N-1 (các điểm cách đều trên vòng tròn đơn vị) N −1 = −n = − • BĐ Z của x(n) tại các điểm zk X (zk ) ∑ x(n)zk k 0,1, , L 1 n=0 j2πkn/N • Nếu zk = re (zk là N điểm cách đều nhau trên vòng tròn bk r) N −1 −n − j2πkn/ N X (zk ) = ∑[x(n)r ]e 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θ0 • Tổng quát, zk nằm trên cung xoắn ốc bắt đầu từ điểm z0 = r0e (đi vào hoặc jθ0 jφ0 k đi ra gốc toạ độ) zk = r0e (R0e ) k = 0,1,, L −1 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 Φ0 = θ0 = 0 Φ0 = θ0 = 0 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 28
  29. dce 2011 Giải thuật BĐ Chirp-z (2) y(k) X (z ) = k = 0,1,, L −1 BĐ chirp-z k h(k) jφ0 V = R0e 2 h(n) = V n / 2 2 jθ0 −n −n / 2 g(n) = x(n)(r0e ) V N −1 y(k) = ∑ g(n)h(k − n) k = 0,1,, L −1 n=0 2 jφ0n / 2 j(nφ0 / 2)n jωn R0 =1 ⇒ h(n) = e = e ≡ e Tần số của t/h mũ phức h(n), tăng tuyến tính theo thời gian ω = nφ0 / 2 → h(n): chirp signal DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 29
  30. dce 2011 Giải thuật BĐ Chirp-z (3) • 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,, L −1 n=0 • Giả sử M = L + (N–1) • M điểm của chuỗi h(n) được xác định –(N–1) ≤ n ≤ (L–1) • Định nghĩa chuỗi M điểm h1(n) = h(n–N+1) n = 0,1, ,M–1 • H1(k) = DFTM{h1(n)} • G(k) = DFTM{g(n)} (sau khi đã đệm thêm vào g(n) L-1 số 0) • Y1(k) = G(k)H(k) → y1(n) = IDFT{Y1(k)} n = 0,1, ,M–1 • N-1 điểm đầu tiên của y1(n) là các điểm lặp → loại bỏ chúng • 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 • X(zk)= y(k)/h(k) k = 0,1, ,L–1 DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ 30