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 ≤

Không thể tạo bản xem trước, hãy bấm tải xuống
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.