An Algorithm for the Machine Calculation of Complex Fourier Series

Thuật toán cho việc tính toán chuỗi Fourier phức bằng máy

Bởi James W. Cooley và John W. Tukey

Một phương pháp hiệu quả để tính toán các tương tác của một thí nghiệm giai thừa $2^m$ đã được Yates đưa ra và được biết rộng rãi theo tên ông. Sự tổng quát hóa cho $3^m$ được Box và cộng sự đưa ra [1]. Good [2] đã tổng quát hóa các phương pháp này và đưa ra các thuật toán thanh lịch, trong đó một lớp ứng dụng là tính toán chuỗi Fourier. Ở dạng tổng quát đầy đủ, các phương pháp của Good áp dụng cho một số bài toán trong đó cần nhân một vectơ $N$ với một ma trận $N \times N$ có thể được phân tích thành $m$ ma trận thưa, trong đó $m$ tỉ lệ với $\log N$. Điều này dẫn đến một thủ tục yêu cầu số phép toán tỉ lệ với $N \log N$ thay vì $N^2$. Các phương pháp này được áp dụng ở đây cho việc tính toán chuỗi Fourier phức. Chúng hữu ích trong các tình huống khi số điểm dữ liệu là, hoặc có thể được chọn là, một số có tính hợp thành cao. Thuật toán được suy ra và trình bày ở đây dưới một dạng khá khác biệt. Sự chú ý được dành cho việc lựa chọn $N$. Cũng chỉ ra rằng có thể thu được lợi thế đặc biệt khi sử dụng máy tính nhị phân với $N = 2^m$ và toàn bộ phép tính có thể được thực hiện bên trong mảng gồm $N$ vị trí lưu trữ dữ liệu được sử dụng cho các hệ số Fourier đã cho.

Xét bài toán tính toán chuỗi Fourier phức