手算二维FFT

发表于 分类于 ， Waline：
本文字数： 765 阅读时长 ≈ 1 分钟
介绍手工计算二维矩阵的FFT。

FFT原理

可以参照前面用C++实现的FFT算法

手算一维FFT

对于序列[1, 2, 3, 4]

  1. 将奇数项和偶数项分离

    注意：这里奇数偶数都是指在序列中的序号，而不是元素的值

    可以分为：[1, 3]和[2, 4]

  2. 计算只有两个数的FFT

    \(F_0=f_0+f_1W_2^0\)

    \(F_1=f_0-f_1W_2^0\)

    其中\(W_N^{ {\mu}x}=e^{\frac{-j2{\pi}{\mu}x}{N} }\)， \(W_N^0=1\)

    所以：\(F_0=f_0+f_1\)， \(F_0=f_0-f_1\)

  3. 计算四个数的FFT

    得到了两个数的FFT，就可以用来计算四个数的FFT。这可以看成是一个分治之后向上合并的过程，并且同样是交叉运算。这个交叉运算过程就是所谓的蝶形运算，而我们直接从分治到最后的两个数一组，并计算每组两个数的FFT的时候，原来的序列其实就是被重排序了。

详细计算过程如下：

因此序列[1, 2, 3, 4]的FFT结果就是[10, -2+2j, -2, -2-2j]

至此，可以手算一维的FFT了

手算二维FFT

二维的FFT就是先对矩阵每行进行一维FFT，得到新的矩阵之后再对每一列进行一维FFT

也就是说，对于一个4x4的矩阵，进行二维FFT，共需要计算8次一维的FFT

举个最简单的例子， \[ \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \] 用上面计算两个数的FFT时的结论：两个数一加一减就是一维的FFT结果。可以很快计算出这个矩阵的经过每行FFT之后： \[ \begin{bmatrix} 3 & -1 \\ 7 & -1 \end{bmatrix} \] 再经过每列FFT之后： \[ \begin{bmatrix} 10 & -2 \\ -4 & 0 \end{bmatrix} \] 这个结果可以用MATLAB进行验证：

相关文章