Khác biệt giữa bản sửa đổi của “Biến đổi Fourier nhanh”

Bách khoa toàn thư mở Wikipedia
Nội dung được xóa Nội dung được thêm vào
Huynl (thảo luận | đóng góp)
Huynl (thảo luận | đóng góp)
Không có tóm lược sửa đổi
Dòng 25: Dòng 25:
|pages=297–301
|pages=297–301
}}</ref>. Đây là một [[thuật toán chia để trị]] dùng [[đệ quy]] để chia bài toán tính DFT có kích thước [[hợp số]] ''N=N<sub>1</sub>N<sub>2</sub>'', thành nhiều bài toán tính DFT nhỏ hơn có kích thước ''N<sub>1</sub>'' và ''N<sub>2</sub>'', cùng với O(''N'') phép nhân với [[căn của đơn vị]], thường được gọi là [[thừa số xoay]] (theo Gentleman và Sande, 1966)<ref>{{cite conference|author=W. M. Gentleman, G. Sande|year=1966|title=Fast Fourier Transforms: for fun and profit|booktitle=Proceedings of the November 7-10, 1966, fall joint computer conference (AFIPS '66 (Fall))|publisher=ACM, New York, NY, USA|pages=563-578|doi=10.1145/1464291.1464352|url=http://doi.acm.org/10.1145/1464291.1464352}}</ref>.
}}</ref>. Đây là một [[thuật toán chia để trị]] dùng [[đệ quy]] để chia bài toán tính DFT có kích thước [[hợp số]] ''N=N<sub>1</sub>N<sub>2</sub>'', thành nhiều bài toán tính DFT nhỏ hơn có kích thước ''N<sub>1</sub>'' và ''N<sub>2</sub>'', cùng với O(''N'') phép nhân với [[căn của đơn vị]], thường được gọi là [[thừa số xoay]] (theo Gentleman và Sande, 1966)<ref>{{cite conference|author=W. M. Gentleman, G. Sande|year=1966|title=Fast Fourier Transforms: for fun and profit|booktitle=Proceedings of the November 7-10, 1966, fall joint computer conference (AFIPS '66 (Fall))|publisher=ACM, New York, NY, USA|pages=563-578|doi=10.1145/1464291.1464352|url=http://doi.acm.org/10.1145/1464291.1464352}}</ref>.

==Các vấn đề tính toán==
==Các vấn đề tính toán==
{{Vấn đề mở|khoa học máy tính|Chặn dưới của độ phức tạp tính toán của biến đổi Fourier nhanh là gì? Liệu nó có thể nhanh hơn &Theta;(N log N) hay không?}}
{{Vấn đề mở|khoa học máy tính|Chặn dưới của độ phức tạp tính toán của biến đổi Fourier nhanh là gì? Liệu nó có thể nhanh hơn &Theta;(N log N) hay không?}}


Một bài toán mở quan trọng về mặt lý thuyết là chứng minh chặn dưới cho độ phức tạp tính toán và số phép tính của biến đổi Fourier nhanh.
Một bài toán mở quan trọng về mặt lý thuyết là chứng minh chặn dưới cho độ phức tạp tính toán và số phép tính của biến đổi Fourier nhanh. Hiện vẫn chưa có chứng minh nào cho việc DFT có thực sự đòi hỏi Ω(''N'' log ''N'') phép tính, ngay cả trong trường hợp kích thước ''N'' là lũy thừa của hai, mặc dù không có thuật toán nào có độ phức tạp thấp hơn. Chú ý rằng tuy số phép tính thường là quan tâm chính về mặt lý thuyết, trên thực tế, tốc độ thực thi phụ thuộc nhiều yếu tố khác như các tối ưu hóa cho [[bộ nhớ đệm]] và [[ống lệnh CPU]].


Theo công trình của Winograd năm 1978<ref>{{cite journal
|first1=S.
|last1=Winograd
|year=1978
|doi=10.1090/S0025-5718-1978-0468306-4
|title=On computing the discrete Fourier transform
|journal=Math. Computation
|volume=32
|issue=141
|pages=175&ndash;199
}} {{JSTOR|2006266}}</ref>, chặn dưới chặt cho số phép nhân của FFT đã được biết là &Theta;(''N'').
==Xem thêm==
* [[Thuật toán FFT Bruun]]
* [[Thuật toán FFT Rader]]
* [[Thuật toán FFT Bluestein]]
* [[Biểu đồ cánh bướm]] - một biểu đồ minh họa cho FFT.
* [[Thuật toán Odlyzko–Schönhage]] áp dụng FFT cho [[chuỗi Dirichlet]]
* [[FFTW]] "Fastest Fourier Transform in the West" - Thư viện viết bằng 'C' để tính biến đổi Fourier rời rạc (DFT) trong một hay nhiều chiều
* [[FFTPACK]] - một thư viện FFT khác cho C và Java
==Ghi chú==
==Ghi chú==
{{reflist}}
{{reflist}}

Phiên bản lúc 06:16, ngày 25 tháng 8 năm 2011

Một biến đổi Fourier nhanh (FFT) là một thuật toán hiệu quả để tính biến đổi Fourier rời rạc (DFT) và biến đổi ngược. Có nhiều thuật toán FFT khác nhau sử dụng kiến thức từ nhiều mảng khác nhau của toán học, từ số phức tới lý thuyết nhómlý thuyết số. Bài này chỉ giới thiệu tổng quan các kĩ thuật và một số tính chất tổng quát. Các thuật toán cụ thể được mô tả chi tiết hơn trong các bài khác được liên kết ở dưới.

Phép biến đổi DFT phân tích một dãy các số thành các thành phần ở các tần số khác nhau. Nó được sử dụng trong nhiều lĩnh vực khác nhau (xem các tính chất và ứng dụng ở biến đổi Fourier rời rạc) nhưng tính toán trực tiếp từ định nghĩa thường quá chậm trong thực tế. FFT là một cách để đạt được cùng kết quả đó nhưng nhanh hơn nhiều: tính DFT của N điểm trực tiếp theo định nghĩa đòi hỏi O(N2) phép tính, trong khi FFT tính ra cùng kết quả đó trong O(N log N) phép tính.

Định nghĩa và tốc độ

Giả sử x0, x1, ..., xn là các số phức. DFT được định nghĩa bởi công thức sau:

Tính trực tiếp từ định nghĩa trên đòi hỏi O(N2) phép tính: có N số Xk cần tính, để tính mỗi số cần tính một tổng N số hạng. Một FFT là một phương pháp để tính cùng kết quả đó trong O(N log N) phép tính.

Các thuật toán

Thuật toán Cooley–Tukey

Thuật toán FFT phổ biến nhất là thuật toán FFT Cooley-Tukey[1]. Đây là một thuật toán chia để trị dùng đệ quy để chia bài toán tính DFT có kích thước hợp số N=N1N2, thành nhiều bài toán tính DFT nhỏ hơn có kích thước N1N2, cùng với O(N) phép nhân với căn của đơn vị, thường được gọi là thừa số xoay (theo Gentleman và Sande, 1966)[2].

Các vấn đề tính toán

Vấn đề mở trong khoa học máy tính:
Chặn dưới của độ phức tạp tính toán của biến đổi Fourier nhanh là gì? Liệu nó có thể nhanh hơn Θ(N log N) hay không?
(các vấn đề mở khác trong khoa học máy tính)

Một bài toán mở quan trọng về mặt lý thuyết là chứng minh chặn dưới cho độ phức tạp tính toán và số phép tính của biến đổi Fourier nhanh. Hiện vẫn chưa có chứng minh nào cho việc DFT có thực sự đòi hỏi Ω(N log N) phép tính, ngay cả trong trường hợp kích thước N là lũy thừa của hai, mặc dù không có thuật toán nào có độ phức tạp thấp hơn. Chú ý rằng tuy số phép tính thường là quan tâm chính về mặt lý thuyết, trên thực tế, tốc độ thực thi phụ thuộc nhiều yếu tố khác như các tối ưu hóa cho bộ nhớ đệmống lệnh CPU.

Theo công trình của Winograd năm 1978[3], chặn dưới chặt cho số phép nhân của FFT đã được biết là Θ(N).

Xem thêm

Ghi chú

  1. ^ Cooley, James W.; Tukey, John W. (1965). “An algorithm for the machine calculation of complex Fourier series”. Math. Comput. 19 (90): 297–301. doi:10.1090/S0025-5718-1965-0178586-1.
  2. ^ W. M. Gentleman, G. Sande (1966). Fast Fourier Transforms: for fun and profit. ACM, New York, NY, USA. tr. 563–578. doi:10.1145/1464291.1464352. Đã bỏ qua tham số không rõ |booktitle= (trợ giúp)
  3. ^ Winograd, S. (1978). “On computing the discrete Fourier transform”. Math. Computation. 32 (141): 175–199. doi:10.1090/S0025-5718-1978-0468306-4. JSTOR 2006266