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

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.
Nội dung trích xuất từ tài liệu:
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-zKhoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 2Bài Giảng Môn: Xử Lý Tín Hiệu SốDFT & IDFTz 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 IDFTz 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 = WNkKhoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 3Bà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 FFTz 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 + qLKhoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Slide 4Bà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 =0Vớ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 = WLplX ( 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ộn ...