Tham khảo tài liệu 'biến đổi foudier nhanh (fft) - chương 6', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương 6 BIẾN ĐỔI FOURIER NHANH FFT . Đinh Đức Anh Vũ Nội dung A Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Bài Giảng Môn Xử Lý Tín Hiệu Số Slide 2 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 DFT X k ĩ-1 x nW 0 k N -1 n 0 IDFT x n T ĩ-1 X k WNk 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 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 Tuân hoàn N-1 Xr k ĩ xR n cos 2 Nn x n sin T n 0 N-1 X k -ĩ xR n sin Nn - x n cos y 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 Wkr N 2 N Wk N N Đôi xúng -Wk -N Wkk N Slide 3 L Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Bài Giảng Môn Xử Lý Tín Hiệu Sô 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 PP - Giả sử N - 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 V 0 01 x 0 0 x 0 1 1 - Cách lưu trữ 2 Theo dòng n Ml m Theo cột n l mL L-1 x 1 0 x 1 1 x 2 0 x 2 1 x L-1 0 x L-1 1 M-1 x 0 M-1 x 1 M-1 x 2 M-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 L Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Bài Giảng Môn Xử Lý Tín Hiệu Sô Slide 4 Phương pháp chia-trị X k x n WN 0 k N -1 n 0 Với x n theo cột X k theo hàng M -1 L-1 X p q x l m WNip q m 0 l 0 W p q mL l WMLmPWmLqWMPlWlq WNNmp 1 WmqL Wmq N N L M L-1 X p q l 0 M-1 WỊN x l m Wmq i p WMpl Wpi Wpl N N M L m 0 DFT M điểm F l q G l q DFT L điểm X p q A Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Bài Giảng Môn Xử Lý Tín Hiệu Số 1 Tính L DFT M điểm - Nhân phức LM2 - Cộng phức LM M-1 2 Tính G l q - Nhân phức LM 3 Tính X p q - Nhân phức ML2 - Cộng phức ML L-1 Độ .
