使用1D FFT的2D FFT

Question

我正在嘗試使用1D FFT實現2D FFT。我有大小4×4的矩陣（行主要）

我的算法是：

1. FFT在所有16個點
2. 位反轉
3. 轉
4. FFT 16分
5. 位反轉
6. 轉置

這是正確的嗎？

Answer 1

否 - 該算法是：

1. 做1D FFT對每行（真實複雜）
2. 上從（1）（配合物複合物）所產生的每個列做1D FFT

因此，它是4 x 1D（水平）FFT，然後是4 x 1D（垂直）FFT，總共8 x 1D FFT。