Lesson 10 — FFT: Fast Fourier Transform (Cooley-Tukey)

Ba module tương tác: sơ đồ butterfly cho N=8 chạy từng tầng, so sánh độ phức tạp O(N²) vs O(N log N), và bộ chạy FFT đối chiếu với DFT trực tiếp.

1. Sơ đồ Butterfly — FFT radix-2 DIT, N = 8

Đầu vào đã sắp theo bit-reversal (trái). Có log₂8 = 3 tầng, mỗi tầng 4 butterfly. Bấm "Tầng tiếp" để tô từng tầng; cạnh hồng = butterfly đang hoạt động, nhãn hồng = twiddle Wₙᵏ.

2. So sánh độ phức tạp — O(N²) vs O(N log N)

Kéo slider chọn N (luôn là lũy thừa của 2). Cột đỏ = số phép DFT trực tiếp (N²), cột xanh = FFT (½·N·log₂N). Chú ý trục cao theo log để cột FFT không biến mất.

3. FFT Runner — chạy thật, đối chiếu DFT

Nhập tín hiệu (các số cách nhau bằng dấu phẩy; độ dài tự cắt/đệm 0 về lũy thừa 2). Bấm "Chạy FFT" để xem phổ |X[k]| và so khớp với DFT trực tiếp.