FFT的计算机实现

快速傅立叶变换（FFT ）的计算机实现

邓凯 电气0706

1.FFT 运算的原理

DFT 运算过程中如果有限长序列的长度很长时，即N 很大时，在运算过程中所做的乘法和加法运算将很多。即便是采用高速的计算机进行运算，也很难达到信息实时处理的要求。由库利、图基等科学家提出的快速傅里叶变换FFT 算法大大减少了运算过程中的乘法和加法次数，适合信息处理对实时性的要求，从而得到广泛应用。

按时间抽取的FFT 算法的基本思想是将输入的有限长序列首先分成奇数序列和偶数序列，分别计算出奇、偶序列的DFT ，然后根据DFT 的周期性和对称性质，将其化简，接着将已分成的奇、偶序列再次分别划分成奇、偶序列，即前面的奇序列按其长度再划分成奇数序列和偶数序列；前面的偶序列按其长度再划分成奇数序列和偶数序列。分别计算其DFT 后，再按上述方法进行化简。如此反复，直至被划分成的奇、偶序列长度为1为止。 1.1基二FFT 算法原理

若设X(k)=DFT[x(n)]，且0≤n, k ≤N-1，N 为偶数（如果N 为奇数，则添上

一个零值点使长度N 为偶数）。把它分为奇序列和偶序列： 21i) x((i) x = )i x((i) x 122+= )12

0(-≤

≤N

i 又 (i )] D F T [x (k ) (i )] X D F T [x (k )X 2211==

)12

0(-≤≤N

i

则有 ⎪⎩

⎪

⎨⎧-=++=k

k

N

N

W k X k X N k X W k X k X k X )()()2()()()(2121 )120(-≤≤N i 其中，][1k X ][2k X 分别是][1i x 和][2i x 的

2

N

点DFT 即要求][k X 的值仅仅只需要求][1k X ][2k X 在)12

0(-≤

≤N

i 部分的值即可。 这样，我们就可以将][k X n 一直分为奇序列和偶序列来求其值，直到奇偶序列长度为1为止。 1.2蝶形图

对于FFT 运算，我们通常用蝶形图来表示

比如⎪⎩

⎪⎨⎧-=++=k

k

N N W k X k X N k X W k X k X k X )()()2()()()(2121 我们表示为

[1X (2X k

N W k X k X k )()()(21+=k N W k X k X N

k X )()(2

(21-=+

图1.21

下面以N=8为例，运用FFT 算法原理计算DFT ，如图 1.22、图1.23、图1.24所示。

图1.22 按时间抽取，将一个N=8点DFT分解为两个 4 点DFT

X(0)图1.23 按时间抽取，将一个N=8点DFT分解为四个 2点DFT

X(0)-1

4图1.23 按时间抽取，将一个N=8点DFT 分解为8个 1点DFT

2

1.3 FFT 算法特点

（1）原位运算。从图2.9的FFT 运算流图中我们可以看出，这种运算是很有规律可循的。其中的每级（每列）运算都是由N/2个蝶形运算所构成，如式（1.31）所示。

⎩⎨⎧-=+=----k

N

m m m N

m m m W j X k X j X W j X k X k X )()()()()()(11110

(式1.31) 其中，m 表示第m 列迭代，k, j 表示数据所在的行数，该式所对应的蝶形运算结构如图1.31所示。

图1.31

x x r

N

m m m W j x k x k )()()(11--+=r

N

m m m W j x k x j )()()(11---=

由图1.31的流程图我们可以看出，对于任一个蝶形中的任何两个节点k 和j ，经过运算后所得的结果作为下一列（级）k, j 两个节点的节点变量，同其他节点变量无关，这样就可以采用原位运算方法。即某一列的N 个数据送入存储器经蝶形运算后，结果为另一级（列）数据，而这些数据结果可以以蝶形为单位仍然存储在这同一组存储器中，直到最后输出，中间无需另加存储器。也就是说，蝶形运算的两个输出值仍放回到蝶形的两个输入所在的存储器中（即将原先的输入值覆盖掉）。前一级蝶形运算完成后才进行下一级蝶形原位运算，因而整个运算结

构由于采用这种原位运算而大大减少了存储单元的个数，有效地降低了成本。 （2）倒位序规律。由图2.9我们还可看出，由于采用了原位计算方法，FFT 的输出X(k)是按k 值的自然顺序排列在存储单元中的，即排列序列为X(0), X(1), …, X(7)，而输入的时间序列都不是按照自然顺序排列，而是按x(0), x(4), x(2), …, x(7)，输入到存储单元中。这种排列初看起来像是“混乱无序”的，但实质是有序的。如果我们用二进制数来表示0～7个数，设为n(n2 n1 n0)2，然后再来观察n (n0 n1 n2)2，如表1.1所示。

由表我们可以看出，只要将2)(012n n n n 转换成22)(10n n n n ，即将二进制的最高位与最低位相交换、次高位与次低位相交换……所得的n 就是以自然顺序排列的，故通常n 的这种排列规律我们称之为倒位序。

这两条性质给我们编程带来了极大的方便。

2．C 语言实现FFT 算法

2.1算法基本原理

如上所述，FFT 算法给编程带来了极大大方便，对比于DFT 不仅运算次数大

大降低，就连所需的内存空间在运算中也不会增加。主要算法有两部分，一个是倒二进制排序，还有最重要的蝶形算法。 倒二进制算法

对数组下标进行倒二进制运算，把输入数组按倒二进制排序即可，算法很简单，具体可参见代码