基于一维FFT的二维FFT

Question

我试图实现一个2D FFT使用一维FFT。我有一个大小为4x4 (行专业)的矩阵。

我的算法是：

1. 对所有16个点进行FFT
2. 位反转
3. 转座子
4. 16点FFT
5. 位反转
6. 转座子

这是正确的吗？

Answer 1

不-算法是：

1. 对每一行进行一维FFT (实数到复数)
2. 对(1)产生的每一列进行一维FFT (从复数到复数)

所以它是4x1D(水平)FFT，然后是4x1D(垂直)FFT，总共是8x1DFFT。