2023-11-08 19:06:04

大家好，我是小典，我来为大家解答以上问题。fft算法流程图，fft算法原理，很多人还不知道，现在让我们一起来看看吧！

1、二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：

2、先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：

3、for (int i=0; i<M; i++)

4、FFT_1D(ROW[i]，N);

5、for (int j=0; j<N; j++)

6、FFT_1D(COL[j]，M);

7、其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。

8、所以，关键是一维FFT算法的实现。下面讨论一维FFT的算法原理。

9、【1D-FFT的算法实现】

10、设序列h(n)长度为N，将其按下标的奇偶性分成两组，即he和ho序列，它们的长度都是N/2。这样，可以将h(n)的FFT计算公式改写如下 ：

11、 (A)

12、由于

13、所以，(A)式可以改写成下面的形式：

14、按照FFT的定义，上面的式子实际上是：

15、其中，k的取值范围是 0~N-1。

16、我们注意到He(k)和Ho(k)是N/2点的DFT，其周期是N/2。因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示

本文到此讲解完毕了，希望对大家有帮助。