Khác biệt giữa bản sửa đổi của “Biến đổi Fourier nhanh”
Nội dung được xóa Nội dung được thêm vào
Dòng 29:
Dạng phổ biến nhất của thuật toán Cooley-Tukey là chia biến đổi thành hai nửa kích thước ''N'' / 2 ở mỗi bước (vì vậy chỉ dùng được cho kích thước là lũy thừa của 2) nhưng bất kì cách phân tích ra thừa số nào cũng đều có thể dùng được (điều này cả Gauss và Cooley/Tukey đều nhận ra). Đây là dạng '''cơ số 2''' và dạng '''nhiều cơ số'''. Mặc dù ý tưởng cơ bản là đệ quy, khi lập trình, người ta thường sắp xếp lại thuật toán để tránh đệ quy. Ngoài ra, do thuật toán Cooley-Tukey chia một DFT thành các DFT nhỏ hơn, có thể phối hợp nó với các thuật toán khác cho DFT, chẳng hạn như những thuật toán mô tả dưới đây.
===Các thuật toán FFT khác===
Có nhiều thuật toán FFT khác ngoài Cooley-Tukey. Với ''N=N<sub>1</sub>N<sub>2</sub>'' và N<sub>1</sub>, N<sub>2</sub> [[nguyên tố cùng nhau]], có thể dùng [[thuật toán FFT thừa số nguyên tố]] (thuật toán Good-Thomas), dựa trên [[định lý số dư Trung Hoa]], để phân tích DFT tương tự như Cooley-Tukey nhưng không cần thừa số xoay.
===Thuật toán FFT cho số thực và dữ liệu đối xứng===
Trong nhiều ứng dụng, dữ liệu vào cho DFT là số thực. Khi đó kết quả thỏa mãn điều kiện đối xứng sau
:<math>X_{N-k} = X_k^*,</math>
và nhiều thuật toán FFT hiệu quả được thiết kế cho trường hợp này. Một phương pháp là lấy một thuật toán thông thường (chẳng hạn Cooley-Tukey) rồi bỏ đi phần tính toán không cần thiết, do đó tiết kiệm khoảng một nửa thời gian và bộ nhớ cần thiết.
==Các vấn đề tính toán==
| |||