第三章 傅里叶分析

（将一个N点DFT分 由此可见，这种方法的每一步分解都是按输入序列在时间上的奇偶次序来分解为两个更短的子序列，所以称为“时间抽取算法”。

上述N=8点时间抽取法FFT的流图如下所示。

解为四个N/4点DFT）

2. 运算量

由上图可见，当N=2M时，共有M级（列）蝶形，每级都由N/2个蝶形运算组成，而每个蝶形运算都需要一次复数乘法和两次复数加法，因此每级运算都需N/2次复乘和N次复加，这样M级运算总共需要

复乘次数 mF?NNM?log2N 22 复加次数 aF?NM?Nlog2N

以乘法为例，由FFT算法、直接DFT算法的运算量与点数N的关系曲线图（P90图3.4.5）

可以直观地看出FFT算法的优越性，尤其是当点数N越大时，FFT的优点更突出，如图所示。

- 3-13 -

3. 算法的特点

由上面介绍的N=8点时间抽取法FFT流图，我们可以总结出N=2M点的时间抽取法的运算规律和特点。 （1） 蝶形运算

由8点FFT流图可见，FFT运算中的每一级（列）计算都是由N/2个蝶形运算组成，而N=2M时，共有M级（列）蝶形，因此N运算共需要/2·M个蝶形运算来完成。．点．FFT．．．．．．．．N．．．．．．．．．．．．其中，每个蝶形结构完成如下基本的迭代运算：

rXm(k)?Xm?1(k)?Xm?1(j)WNXm(j)?Xm?1(k)?Xm?1(j)WrN （3.4.8）

式中，m表示第m级（列）迭代，k，j为数据所在行数。其一般形式如图所示，它包括一

次复乘和两次复加。

在8点FFT流图中，第一级（列）每个蝶形的两节点间距为1=2，第二级每个蝶形的

M．两节点间距为2=21，第三级每个蝶形的两节点间距为4=22，由此类推得，对于N=2．．．．．点．FFT．．．

0

m-1．．．运算，其第m级每个蝶形的两节点间距为2．．．．．．．．．．．．．．．．．．．。

r另外，由推导可得，每一级（列）不同的WN因子分布情况为：

第1级，W2r，r?0第2级，W4r，r?0,1第3级，W8r，r?0,1,2,3(1种)(2种)(3种) (N/2种)?r第M级，WN，r?0,1,?,N/2?1r因此我们不难总结出WN因子分布的一般规律为： ．．．．．．．．．．

rN/2第m级，W2rm?WN，r?0,1,?,2m?1?1(2m?1种)

m（2） 同址运算

- 3-14 -

在计算机编程时，将蝶形的两个输出值仍放回到两个输入所在的存储器中，这种运算就称为“同址运算”。 ．．．．（3） 倒位序规律及实现

I. 倒位序的规律

这种顺序看似混乱无序，但实际上是有规律的，我们将其称为“倒位序”。 ．．．

倒位序的原因是输入(n)按时域变量的奇偶不断进行分组而造成的。 ．．．．．．．．．x．．．．．．．．．n．．．．．．．．．．．．．．．

II. 倒位序的实现

一般在实际运算中，我们总是先按自然顺序将输入序列存入存储单元中，再通过变址运算来实现倒位序的排列。其具体方法如下：

如果输入序列x(n)的序号n用二进制数（例如n2 n1 n0）表示，则其倒位序二进制数n就是（n0 n1 n2）。下表所示的是N=8时的自然顺序二进制数以及相应的倒位序二进制数对照表。

自然顺序n 0 1 2 3 4 5 6 7 自然顺序二进制数 000 001 010 011 100 101 110 111 倒位序二进制数 000 100 010 110 001 101 011 111 ^^

倒位序顺序n 0 4 2 6 1 5 3 7 ^

由此可知，只要在原来存放自然顺序序列x(n)的单元中，存入倒位序序列x(n)，即可实现倒位序的排列。这个变址过程如图所示。

由图可见，当n=n时，不必调换；只有当n≠n时，才需要将原来存放x(n)和x(n)的存储单元中的内容互换。为了节省调换时间，避免重复调换（保证只调换一次，否则又回到原状），我们只需检查n和n的相对大小，若n>n，则表明此x(n)在前面已经和x(n)调换过了，不必再

- 3-15 -

^

^

^

^

^

^

调换；否则，就必须进行互换。

综上所述，实现倒位序排列的具体方法为：若≥n时，不必调换；若

三、 按频率抽取（DIF）的基-2FFT算法（桑德-图基算法）

前面讨论的FFT算法是将输入序列x(n)按时间变量n的奇偶分解为越来越短的序列。类似地，如果我们将输出序列X(k)按频域变量k的奇偶分解为越来越短的序列，这种FFT算法就称为“频域抽取法”。 四、 IDFT的快速算法（IFFT）

利用FFT算法来计算IFFT的具体方法有以下两种： 1. 方法一

首先，比较IDFT公式

^

^

^

1N?1?kn x(n)?IDFT[X(k)]??X(k)WNNk?0和DFT 公式

kn X(k)?DFT[x(n)]??x(n)WNn?0N?1kn?kn可见，只要将DFT运算中的每一个系数WN换成WN，最后再乘以常数1/N，则前面所介

绍的按时间或按频率抽取的FFT算法都可用来计算IDFT。

kn?kn例如，我们可直接由8点频率抽取FFT流图出发，把WN换成WN，并在每级（列）MM．．

运算中都乘以1/2（注意：因为乘以1/N就等效于1/N =1/2=(1/2)．．．．．．．．．．．．．．．．．．．．．．．．，所以相当于每级都乘．．．．．．．．．．

以），这样即可得到相应的IFFT流图，如图所示。 ．1/2．．．

输入X(k) 顺序排列 输出x(n) 倒序排列

2. 方法二

首先，对IDFT公式取共轭，得

- 3-16 -