TAILIEUCHUNG - Bài giảng Xử lý tín hiệu số: Chương 6 - TS. Đinh Đức Anh Vũ
Bài giảng "Xử lý tín hiệu số - Chương 6: Giải thuật cho biến đổi Fourier" cung cấp cho người học các kiến thức: DFT & IDFT, phương pháp chia -trị, FFT cơ số 2, Parallel-Pipelined architecture, hiện thực các giải thuật FFT,. . | dce 2011 Chương 6 Giải thuật cho biến đổi Fourier (FFT) BK ©2011, TS. Đinh Đ ức Anh Vũ dce 2011 Nội dung Tính DFT & IDFT Tính trực tiếp Biến đổi WN Lọc tuyến tính Chia-Trị Cơ số 2 Cơ số 4 DSP – Giải thuật cho Biến đổi Fourier Tách cơ số Goertzel Chirp-z ©2011, Đinh Đức Anh Vũ 2 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 DFT X (k ) = ∑ x(n)WNkn 0 ≤ k ≤ N −1 IDFT 1 x ( n) = N 0 ≤ n ≤ N −1 n =0 N −1 − kn X k W ( ) ∑ 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 – N2 phép nhân phức – N(N-1) phép cộng phức → Độ phức tạp : O(N2) • Biến đổi WN – – – – 2N2 phép tính lượng giác 4N2 phép nhân số thực 4N(N-1) phép cộng số thực Một số phép toán chỉ số và địa chỉ để nạp x(n) DSP – Giải thuật cho Biến đổi Fourier N −1 2πkn 2πkn X R (k ) = ∑ [ xR (n) cos( N ) + xI (n) sin( N )] n =0 N −1 X (k ) = − [ x (n) sin( 2πkn ) − x (n) cos( 2πkn )] ∑ R I N N I n =0 Giải thuật tính DFT tối ưu mỗi phép toán theo những cách khác nhau Doi xung WNk + N /2 = −WNk Tuan hoan WNk + N = WNk ©2011, Đinh Đức Anh Vũ 3 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ư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) – Cách lưu trữ • Theo dòng n = Ml + m • Theo cột n = l + mL 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) 2 x(2,0) x(2,1) x(2,M-1) x(L-1,0) x(L-1,1) x(L-1,M-1) L-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 dce 2011 Phương pháp chia-trị (2) N −1 X (k ) = ∑ x(n)WNkn 0 ≤ k ≤
đang nạp các trang xem trước
