现代测控技术中的FFT算法探析

罗焕然

摘 要 本文阐述了频率域抽取基2FFT算法。内容包括公式推导、蝶形运算单元、

快速傅立叶变换算法的信号流程图。

关键词 FFT 频率抽取 蝶形单元 运算量

中图分类号：TN919 文献标识码：A

1概述

在测控技术中，传感器采集到的数字信号一般是时间序列，需要对这样的数字信号进行处理，通过离散傅立叶变换（Discrete Fourier Transform，簡称DFT），可以将时域信号转化为频域信号。快速傅立叶变换（Fast Fourier Transform，简称FFT）是一种提高离散傅立叶运算速度的快速算法，它使N点DFT的乘法计算量由N2次降为log2N次。以N=1024为例，计算量降为5120次，仅为原来的4.88%。人们公认这一重要发现的问世是数字信号处理发展史上的一个转折点，也可以称之为一个里程碑。

基于FFT变换的不言而喻的重要性以及对其产生的浓厚兴趣，深入学习了FFT变换的机理。所用教材给出了时间抽取（DIF）基2 FFT算法的详细的推导过程，而对于频率抽取（DIF）基2 FFT算法只是简略的提及，并没有做详细的探讨。为了深化对于FFT的认识，本文尝试详细给出频率抽取（DIF）基2 FFT算法的推导过程，并作出相应的讨论。

2频率抽取（DIF）基2 FFT算法

2.1算法的推导

对N点序列x（n），它的DFT变换定义为：

X（K）=x（n） k=0，1，…，N-1，WN= （4—a）

于是我们将一个N点DFT分成了两个N/2点的DFT，分的办法是将X（k）按序号k的奇、偶性分开。

对（4—a）式的DFT，继续将x（2r）按序列号分成上、下两部分，得：

（4—b）

（5—a）

同理，对于（4—b）的DFT，可以得到：

（5—b）

分别令r=2l，r=2l+1，l=0，1，…，N/4-1，则（5—a）和（5—b）可以化为：

（6—a）

（6—b）

（6—c）

（6—d）

令 （7—a）

（7—b）

（7—c）

（7—d）

则 （8—a）

（8—b）

（8—c）

（8—d）

这样，我们通过将X（2r）和X（2r+1）按r的奇、偶分开，把两个N/2点的DFT分成了四个N/4点的DFT。通过几个中间变量的代换，算出了时间序列x（n）的8点DFT。

若N=16，32或2的更高的幂，可按照前述的方法继续分下去，直到化成两点计算为止。以上算法是将频率下标k按奇、偶分开，故称频率抽取算法（Decimation in Frequency，DIF）。现将上述过程表示于图1。其基本运算单元如图2所示。

2.2算法的讨论

（1）“级”的概念

上述过程，每进行一次奇偶分离，就成为一“级”运算，一共有M=Log2N级，如图1所示。图中从左至右，依次为m=0级，m=1级，…，m=M-1级。

图2 第m级蝶形单位

（2）蝶形单元

在图1中有大量的如图2的蝶形运算单元，由于该运算结构的几何形状类似蝴蝶，所以有“蝶形运算单元”的名称，在第m级，有

（9）

p，q是参与本蝶形单元运算的上、下节点的序号。显然，第m级序号为p，q的两点只参与该蝶形单元的运算，并在第m+1级输出。该蝶形单元不会再涉及别的点。这个特点使得我们在计算机编程的时候，可以将蝶形单元的输出仍然放在输入数组里。这一特点称为“同址运算”。

由于每一级都含有N/2个蝶形单元，每一个蝶形单元需要一次复数乘法，两次复数加法，所以完成M=Nlog2N级共需要复数乘法次数m1和复数加法次数m2分别是：

（10）

由图2，在第m级，上下节点p，q之间的距离为

（11）

（3）码位倒置

由图1可以看出，输入序列x（n）依照正序排列，但变换后的输出序列X（k）的次序却似乎被打乱了，这是由于对X（k）作奇、偶分开所产生的。对于N=8，自然序号为0，1，2，3，4，5，6，7。第一次按奇、偶分开，可得X（k）的序号为：

0，2，4，6， | 1，3，5，7

对每组再作奇、偶分开，这时应该把每一组仍看作按自然顺序排列，故抽取后得四组，每组的序号为：

0，4 ， | 2，6，| 1，5，| 3，7

这一顺序正是图1输出端序列X（k）的排列次序，掌握这一规律，对N为2的更高次幂，我们都可以得到正确的抽取次序。

如果我们将X（k）的序号k=0，1，…，N-1写成二进制，如N=8，X（0），…，X（7）对应是

X（000），X（001），X（010），X（011），X（100），X（101），X（110），X（111）

将二进制数码翻转，得

X（000），X（100），X（010），X（110），X（001），X（101），X（011），X（111）

它们对应的十进制序号分别是

X（0），X（4），X（2），X（6），X（1），X（5），X（3），X（7）

也正是输出端所得到的顺序。掌握了这一规律，我们就可以做到正确的编程，FFT的软件已经是通用程序，所以我们只要了解排序的规律就可以了。

参考文献

[1] 周耀华，汪凯仁.数字信号处理.上海：复旦大学出版社，1992.

[2] 胡广书.数字信号处理——理论、算法与实现.北京：清华大学出版社，2002.