一种FFT逆序输出整序的时间优化方法2016年2月14日

摘 要： 在数字信号处理中，FFT运算具有非常重要的作用。传统FFT算法具有原位计算的特点，原位FFT算法在自然序输入时输出呈逆序状态，因此为了得到自然序的结果数据，就必须对全部FFT输出数据进行整序。使用查找表整序是从FFT的逆序输出结果中直接读取自然序结果数据。试验证明，在获取全部FFT结果数据时，查找表整序相比传统整序在时间效率上可以提高一倍，并且在连续FFT分析的情况下，优势会更明显。

由表1可见，原位FFT的输入数据为自然序，输出数据为逆序，并且将自然序索引二进制表示的比特排列顺序完全逆过来，就得到逆序索引的二进制表示[5]。因此为了得到自然序的FFT结果，就需要对FFT的逆序输出结果进行整序。传统的整序算法是在原位FFT计算完毕后依自然序遍历每一个输出数据，先通过“比特倒序”运算计算自然序索引的逆序数，此逆序数就是输出数据的正确索引值，再以逆序数为索引调整这个FFT数据的，最后得到全部自然序的FFT结果数据。在DSP内只能使用高级语言编码实现位逆序时，传统做法是利用产生逆序数的十进制运算规律，采用循环迭代计算逆序数[4-5]。

[10] 林水生，黄顺吉.改进的任意基FFT整序算法[J].信号处理，1999，15（2）：163-165.

0 引言

[7] 乔春明，朱冰莲.快速傅里叶变换中逆序数计算的一种快速算法[J].信息技术，2011（8）：164-165.

对于N点原位FFT运算，传统整序需要计算N点索引的逆序数。使用查找表进行整序，假设目标数据长度为M（M≤N），则查找表内索引个数为M，索引数据类型设为32 bit整型，那么所需分配的空间为M×32 bit。计算查找表时可以在FFT分析前进行，这部分时间不占用FFT分析时间。对于单次FFT分析，增加M（M≤N）点数据空间可以为FFT计算节省N次逆序数的计算时间；对于连续FFT分析，不妨设连续分析n次，可以节省n×N次逆电子科技大学学报序数的计算时间。

图2中，iSourceIndex是待逆序的索引值，iBitNum是FFT计算点数的二进制位数，iDesIndex是BitReverse函数返回的逆序数。构造FFT结果的数据查找表的流程图如图3所示。

一次传统的N点原位FFT分析需要计算N个索引值的逆序数才能得到全部的自然序结果，进而才能获取自然序结果中的某一段目标FFT数据。对于需要连续进行FFT分析的情况，无论是获取全部FFT数据还是一段FFT数据，每一次N点FFT分析都需要重新计算一遍N个索引值的逆序数。对于重复计算，可以只计算一次，因此可以优化FFT分析中的整序过程。

[11] 贾渊，王俊波，姬长英.FFT快速整序算法的对比、改进及实现[J].电子科技大学学报，2009，38（2）：292-295.

1 FFT算法的原位计算的特点

4 结论

[2] 刘卫新.实现FFT整序方法的研究[D].南京：南京理工大学，2003.

[5] 姚天任.数字信号处理[M].：大学出版社，2011.

在实际应用中，所感兴趣的目标FFT数据，无论是全部FFT数据还是部分数据，都可看作全部自然序的FFT结果中的一段，那么可以设法从FFT逆序输出中直接获取这一段目标数据。即首先明确目标数据段在整序后的FFT结果中的，计算这些索引值的逆序数并存储在一个查找表中，然后根据此查找表就可以在FFT的逆序输出数据中直接提取目标数据。采用此算法将逆序数的计算从整序过程中剥离，简化整序过程，提高整序效率。使用查找表整序的方式易于理解，操作简单，并且在需要进行连续FFT分析的情况下会体现出很大的优势。

设N点原位FFT运算，对目标数据在全部自然序的FFT结果中的索引进行逆序操作，由于自然序和逆序索引的二进制表示之间是比特倒置关系，于是需要将每个自然序索引值二进制表示的最低位移向最高位，次低位移向次高位直到完成这个自然序索引值的位逆序过程。将一个索引值的位逆序函数设为BitReverse（intiSourceIndex，intiBitNum），其返回值为一个逆序数；所获取的查找表设为IndexArray。位逆序的计算流程图如图2所示。

[3] 高丽，刘卫新，张学智.FFT标准移序算法的优化[J].探测与控制学报，2004，26（2）：62-64.

[8] 张学智，毛俊.无须逆序数的FFT整序的一个新方法[J].探测与控制学报，2002，24（2）：61-63.

3 试验

在原位FFT运算过程中，当输入数据为自然序时，由于FFT算法过程对输入数据的多次“奇偶抽取”，使得输出数据呈逆序状态，即输出数据的索引和自然序索引的二进制表示呈相互位逆序状态[1]。因此必须对输出数据进行整序，才能得到自然序的结果。即一次FFT分析包括FFT计算和对FFT逆序输出的整序。FFT分析几乎都在DSP处理器中完成，DSP处理器通过内部CPU逐条执行软件指令来完成各种运算和逻辑功能[2]。因此，在DSP内执行一次FFT算法，必须顺序执行FFT计算和整序操作[3-5]。研究者为提升整序效率进行了多种改进，有的是对整序过程中的逆序数计算进行了多种改进，比如逆序数生成法[6-7]和分组数据交换法[8]，但这些改进只关注了整序过程中的逆序数计算这一个方面；有的将逆序数计算与整序结合在一起，比如任意基的快速整序算法[9-10]，但这种方解起来很困难[11]。

[4] 丁玉美，高西全.数字信号处理[M].西安：西安电子科技大学出版社，1995.

对图1中FFT的输入数据和输出数据的索引变化在表1中予以反映。

本文在充分理解原位FFT的计算特点后，在FFT分析前，对目标数据在全部FFT结果中的索引计算逆序数，并将计算结果存储为一个查找表，然后通过此查找表从FFT的逆序输出中获得自然序结果。试验结果证明，相比于传统的整序，使用查找表整序时间高效并且简单实用，具有普遍的实用价值。比如，在软件无线电领域，一般的无线电信号带宽比较窄，频率范围比较宽，通常使用带通采样，因此对无线电信号进行FFT计算时，只关心某一段结果数据；并且在需要对无线电信号进行连续监测的中，系统希望快速获取每一次的FFT分析结果，在这种情况下，使用查找表整序处理FFT的逆序输出就具有很大的优势。于是，使用查找表整序节省了FFT分析的整序时间，从而提高了FFT分析的时间效率。

[9] 林水生，黄顺吉.一种实现任意基的快速整序算法[J].电子科技大学学报，1998，27（4）：343-346.

图1是8点的时域抽取基-2的原位FFT算法流程，输入数据是自然序的，输出数据为逆序状态[4]。

由表2可见，单独就整序过程而言，使用查找表整序比传统的整序在时间效率上可以提高一倍多。如果仅需要得到某一段FFT结果数据，传统整序首先要对N点FFT的全部逆序输出进行整序，然后再截取目标数据，而使用查找表整序则可以从FFT逆序输出数据中直接获取任意长度的目标数据，并且目标数据的长度越短，查找表长度越短，获取目标数据的时间效率就越高。

图3中，iStart为目标数据在整个FFT自然序结果中的起始，iDataLen为目标数据的长度，由BitReverse函数的返回值iDesIndex构成一个查找表IndexArray。于是，通过查找表从索引为iDesIndex的FFT逆序输出中获取自然序的目标结果数据。相比于传统的整序方式，使用查找表整序可以省去FFT分析过程中逆序数的计算过程。下面的试验在FFT计算完毕后，统计了传统整序和使用查找表整序所消耗的时钟周期个数，进而比较两种整序方式的时间效率。

[1] 方志红，张长耀，俞根苗.利用逆序循环实现FFT运算中倒序算法的优化[J].信号处理，2004，20（5）：533-535.

[6] 张学智，蔡晖.快速实现FFT的逆序方法[J]．探测与控制学报，2001，23（2）：62-64.

2 基于查找表整序算法

试验是TI公司提供的高效C编译器和集成开发Code Composer Studio，选择C67xx CPU Cycle Accurate Simulator处理器。在获得相同整序结果的前提下，比较传统整序和使用查找表整序的耗时情况。试验中，N点自然序数据作为FFT的输入，目标数据为全部FFT结果数据。在FFT计算完毕后，对FFT的逆序输出数据采用不同的整序方式得到自然序结果数据，统计两种整序方式所消耗的时钟周期数，并通过对比时钟周期数得到两种整序过程在时间效率上的差别。

参考文献

无论所需要的目标数据是全部FFT结果还是部分FFT结果，都可以事先计算目标数据在整个FFT结果中索引的逆序数，并将这些逆序数存储在一个查找表中，然后根据此查找表在FFT逆序输出数据中直接提取自然序的目标数据。在需要对信号进行连续FFT分析的中，查找表的计算可以在FFT分析前完成，并且只需计算一次。这种整序方式可以省去FFT分析过程中计算逆序数的时间，缩短单次FFT分析时间，提高单位时间内的FFT分析次数，提高信号分析效率。

记录N点FFT中传统整序和查找表整序所消耗的时钟周期个数，并计算后者与前者的百分比以观察时间效率的改善情况。运行情况记录如表2所示。