FFT — Giải thích đơn giản về biến đổi Fourier nhanh

FFT, hay fast Fourier transform, là một cách nhanh để tính biến đổi Fourier rời rạc (DFT). Nếu bạn bắt đầu với các mẫu cách đều, DFT cho biết mỗi mẫu tần số rời rạc xuất hiện nhiều đến mức nào trong các mẫu đó.

Điểm quan trọng là FFT không làm thay đổi kết quả. Nó cho ra đúng các giá trị DFT như công thức tính trực tiếp, nhưng đạt được điều đó với ít phép tính lặp lại hơn nhiều.

FFT Trong Một Câu

FFT là một thuật toán nhanh hơn để tính ra chính các giá trị trong miền tần số mà DFT đã định nghĩa.

DFT Đo Điều Gì

Giả sử bạn có các mẫu $x_0, x_1, \dots, x_{N-1}$. DFT tạo ra các số $X_0, X_1, \dots, X_{N-1}$ được định nghĩa bởi

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Mỗi $X_k$ đo mức độ dữ liệu khớp mạnh đến đâu với một mẫu tần số rời rạc.

Nếu các mẫu được lấy cách đều với tần số lấy mẫu $f_s$, thì khoảng cách giữa hai bin tần số liền kề là

$$\frac{f_s}{N}$$

Điều kiện đó rất quan trọng. Nếu không biết tần số lấy mẫu, bạn vẫn có các bin DFT, nhưng không thể gán cho chúng các tần số vật lý như hertz.

Vì Sao FFT Nhanh Hơn

FFT là một họ thuật toán dùng để tính DFT một cách hiệu quả. Mẹo chính là tái sử dụng cấu trúc trong các hệ số mũ phức thay vì tính lại từ đầu những tổng gần như giống hệt nhau.

Phiên bản dễ hình dung nhất là FFT radix-2. Nó hoạt động tự nhiên nhất khi $N$ là lũy thừa của $2$, và nó tách một phép biến đổi độ dài $N$ thành hai phép biến đổi độ dài $N/2$ trước khi ghép kết quả lại.

Với DFT tính trực tiếp, số phép toán tăng theo bậc $N^2$. Với các phương pháp FFT phổ biến, nó giảm xuống khoảng $N \log N$.

Khoảng cách đó là lý do FFT quan trọng trong thực tế. Với đầu vào nhỏ, cả hai cách đều có thể chấp nhận được. Với đầu vào lớn, FFT nhanh hơn rõ rệt.

FFT Chia Nhỏ Công Việc Như Thế Nào

Thay vì so sánh trực tiếp mọi mẫu với mọi mẫu tần số, FFT chia bài toán thành các phép biến đổi nhỏ hơn rồi ghép lại bằng các hệ số pha.

Một cách tách chuẩn là:

1. Đưa các mẫu có chỉ số chẵn vào một danh sách.
2. Đưa các mẫu có chỉ số lẻ vào một danh sách khác.
3. Tính các phép biến đổi nhỏ hơn trên các danh sách đó.
4. Ghép hai nửa lại với nhau.

Đó là chiến lược chia để trị áp dụng cho phân tích tần số.

Ví Dụ FFT 4 Điểm

Xét tín hiệu 4 điểm

$$x = [1, 0, 1, 0]$$

Mẫu này luân phiên giữa $1$ và $0$, nên ta kỳ vọng có một số cấu trúc tần số thay vì kết quả hoàn toàn phẳng.

Tách theo chỉ số chẵn và lẻ:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

DFT 2 điểm của phần chẵn là

$$E = [2, 0]$$

và DFT 2 điểm của phần lẻ là

$$O = [0, 0]$$

Với FFT 4 điểm, bước ghép là

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

trong đó

$$W_4 = e^{-i 2 \pi / 4}$$

Vì $O_k = 0$, bước ghép trở nên đặc biệt đơn giản:

$$X = [2, 0, 2, 0]$$

Bây giờ hãy diễn giải kết quả.

$X_0 = 2$ là thành phần tần số bằng không, nên nó phản ánh giá trị trung bình khác $0$ của các mẫu. Giá trị khác $0$ tại $X_2$ thể hiện phần luân phiên của mẫu trong trường hợp 4 điểm này. Nếu bạn trừ đi giá trị trung bình trước, thì hạng $X_0$ sẽ biến mất và thành phần luân phiên sẽ nổi bật rõ hơn.

Ví dụ này nhỏ, nhưng ý tưởng thì mở rộng được: giải các phép biến đổi nhỏ hơn, rồi ghép chúng lại thay vì xây dựng lại toàn bộ tổng mỗi lần.

Những Lỗi Thường Gặp Với FFT

Xem FFT Và DFT Là Hai Kết Quả Khác Nhau

Không phải vậy. FFT là một cách nhanh hơn để tính DFT.

Đọc Các Bin Như Tần Số Vật Lý Quá Sớm

Vị trí các bin chỉ trở thành tần số vật lý khi biết khoảng cách lấy mẫu. Nếu tần số lấy mẫu là $f_s$, thì khoảng cách giữa các bin là $f_s/N$ đối với các mẫu cách đều.

Cho Rằng Zero-Padding Thêm Thông Tin Mới

Zero-padding có thể làm phổ trông mượt hơn vì nó lấy mẫu phép biến đổi nền mịn hơn, nhưng nó không thêm dữ liệu đo mới.

Bỏ Qua Khâu Chuẩn Bị Tín Hiệu

Việc loại bỏ giá trị trung bình, dùng cửa sổ và chọn cách lấy mẫu cẩn thận có thể rất quan trọng. Nếu bỏ qua các điều kiện đó, đầu ra FFT vẫn có thể đúng về mặt toán học cho các mẫu đã cho nhưng lại dễ gây hiểu sai khi diễn giải.

FFT Được Dùng Ở Đâu

FFT xuất hiện ở mọi nơi cần thông tin miền tần số nhanh từ dữ liệu lấy mẫu. Các ví dụ phổ biến gồm phân tích phổ, lọc tín hiệu, xử lý ảnh, phân tích rung động, giải số phương trình vi phân và tính đa thức hoặc tích chập nhanh.

Lý do mang tính thực tế: nhiều phép toán trở nên dễ hơn hoặc nhanh hơn sau khi chuyển từ miền mẫu sang miền tần số.

Thử Một Trường Hợp Tương Tự

Lấy $8$ mẫu cách đều của một sóng sin trong đúng một chu kỳ đầy đủ và tính DFT bằng máy tính cầm tay hoặc script. Sau đó thêm một độ lệch hằng số và so sánh đầu ra mới. Giá trị mạnh hơn tại $X_0$ là một cách đơn giản để thấy FFT đã tách những gì.