2D FFT sử dụng 1D FFT

Question

Tôi đang cố triển khai FFT 2D bằng cách sử dụng FFT 1D. Tôi có một ma trận kích thước 4x4 (hàng lớn)

thuật toán của tôi là:

1. FFT trên tất cả 16 điểm
2. chút đảo ngược
3. transpose
4. FFT trên 16 điểm
5. chút đảo ngược
6. chuyển đổi

Điều này có đúng không?

Answer 1

Không - thuật toán là:

1. làm 1D FFT trên mỗi hàng (thực đến phức tạp)
2. làm 1D FFT trên mỗi cột phát sinh từ (1) (phức tạp đến phức tạp)

Vì vậy, nó là 4 x 1D (ngang) FFTs theo sau là 4 x 1D (theo chiều dọc) FFT, cho tổng số 8 x 1D FFT.