使用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。