Biến đổi nhanh Fourier

Biến đổi nhanh Fourier (FFT) là một thuật toán rất hiệu quả để tính toán Biến đổi Fourier rời rạc (DFT) và Biến đổi ngược. Có nhiều loại thuật toán FFT khác nhau sử dụng các 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óm và lý 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(N) 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:

$X_k=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n{e}^{}$

− i 2 π k n N k = 0 , … , N − 1. {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{i2\pi k{\frac {n}{N}}}}\qquad k=0,\dots ,N-1.}

Tính trực tiếp từ định nghĩa trên đòi hỏi O(N) 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. Ko/l(mauio

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 Cooley-Tukey. Đâ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 N1 và N2, 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).

Phương pháp này, cùng với ý tưởng chung về FFT, được biết đến rộng rãi từ bài báo của J. W. Cooley và J. W. Tukey năm 1965, tuy nhiên đã được phát hiện lại độc lập từ thuật toán mà Carl Friedrich Gauss đã phát hiện vào khoảng năm 1805 (và sau đó được phát hiện lại nhiều lần trong các trường hợp đặc biệt).

Dạng phổ biến nhất của thuật toán Cooley-Tukey chia biến đổi thành hai nửa có 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), tuy nhiên, thuật toán này có thể áp dụng cho bất kỳ phân tích nào của thừa số (đ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, trong lập trình, người ta thường sắp xếp lại thuật toán để tránh sử dụng đệ quy. Ngoài ra, thuật toán Cooley-Tukey có thể kết hợp với các thuật toán khác cho DFT như những thuật toán mô tả dưới đây.

Các thuật toán FFT khác

Ngoài thuật toán Cooley-Tukey, còn có nhiều thuật toán FFT khác. Với N=N1N2 và N₁, N₂ là các số nguyên tố cùng nhau, có thể sử 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 một cách tương tự như Cooley-Tukey mà không cần sử dụng 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 đầu vào cho DFT là số thực. Kết quả thu được phải thỏa mãn điều kiện đối xứng sau đây

Công thức dưới đây biểu diễn điều kiện đối xứng của DFT: X_N-k = X_k*, trong đó X_N-k là phần tử ở vị trí N-k và X_k* là số phức liên hợp của X_k.

Có nhiều thuật toán FFT hiệu quả được phát triển đặc biệt cho dữ liệu số thực này. Một trong những phương pháp là cải tiến thuật toán Cooley-Tukey để tối ưu hóa thời gian tính toán và sử dụng bộ nhớ.

Các vấn đề liên quan đến tính toán được xem xét rộng rãi trong lĩnh vực này.

Một vấn đề lý thuyết quan trọng là chứng minh giới hạn dưới cho sự phức tạp tính toán và số lượng phép tính của biến đổi Fourier nhanh. Hiện tại, vẫn chưa có bằng chứng nào cho rằng DFT 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à mũ 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 mặc dù số lượng phép tính thường là vấn đề quan trọng trong lý thuyết, thực tế, tốc độ thực thi còn phụ thuộc nhiều yếu tố khác như tối ưu hóa bộ nhớ đệm và ống lệnh CPU (CPU Pipes).

Theo nghiên cứu của Winograd vào năm 1978, giới hạn dưới cứng cho số lượng phép nhân của FFT đã được biết là Θ(N).

• 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ú