一种FFT逆序输出整序的时间优化方法

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

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

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

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

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

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

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

2 基于查找表整序算法

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

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

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

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

3 试验

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

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

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

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

4 结论

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

参考文献

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

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

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

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

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

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

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

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

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

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

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

电子工程师必读：FFT和示波器实用指南

快速傅里叶变换(FFT)是20世纪70年代微处理器进入商业设计时首次出现的。从昂贵的实验室型号到最便宜的业余型号,现在几乎每一台示波器都能提供FFT分析功能。FFT是一种功能强大的工具，高效使用FFT要求人们对FFT有一定的研究。本文将介绍如何设置FFT和高效使用FFT，FFT的技术原理这里不再赘述。

FFT是一种能够缩短离散傅里叶变换(DFT)计算时间的算法，也是一种用于在频域(幅度和相位与频率的关系)中查看所采集的时域(幅度与时间)数据的分析工具。FFT给数字示波器增加了频谱分析功能。

观察图1中的上半部分曲线，你看到的是一个经过幅度调制的载波，它使用梯形脉冲作为调制函数。在看图1中的这个时域图时，如果让你告诉我信号的带宽，你可能一时答不上来。但如果你对这个信号进行FFT处理，就能得到另外一个视角。这个信号有一个线性扫描的频率，带宽用光标标记出来了，是4.7MHz。这正是示波器中增加FFT功能的原理，它是从另外一个角度来看同样的数据。

图1：上面的时域图显示了脉冲调制的射频载波，下方的频域图显示了在997MHz和1002MHz之间均匀

FFT频带宽度和分辨率带宽

在最早的电路课程中，你应该学过周期信号的频率(频域)是周期(时域)的倒数。同样，这个关系贯穿在整个FFT设置过程中。

设置FFT最好从选择分辨率带宽(RBW)开始，因为它与单参调整有关。RBW (Δf)是显示FFT频率轴的增量步距。在时域中，采样周期决定了样本之间的时间间隔。而在频域中，RBW是频谱图中相邻“单元”之间的频率差值。RBW是时域记录长度(也称为采集时间)的倒数，如图2所示。你可以用示波器的水平刻度或时间/格参数设置来控制RBW。图1中的采集时长是20μs，频谱图中的RBW是它的倒数，即50kHz。

图2：频谱的分辨率带宽是时域记录长度或采集时间的倒数

设置FFT的下一步是确定频域图的宽度——FFT中最高频率和最低频率之差。注意，FFT通常从0 Hz开始，一直到整个频带宽度。这与射频频谱分析仪有很大的区别，马上我会讲到。

FFT的频带宽度是示波器有效采样率的一半(图3)。时域中的最短时间增量——采样周期——决定了频域中的最大分量。同样，频域中的最小增量是时间记录中最长持续时间的函数。这符合时域和频域之间的倒数关系。

图3：频谱宽度是示波器有效采样率的一半

为了在频域中取得更高的分辨率，必须增加采集的数据量，方法是增加时间/格设置值。这与在示波器的时域图中增加时间分辨率的做法刚好是相反的。

从实用的角度看，时域记录长度是由示波器的时间/格参数值控制的。一旦你选择了时间/格参数值来达到想要的分辨率带宽，那么控制采样率达到所需频带宽度的唯一方法是修改示波器的采集内存长度。现在事情似乎复杂起来了，确实是这样。

最近，大多数高端示波器制造商都修改了FFT用户界面，使它更类似于标准的射频频谱分析仪，设置中心频率和频带宽度时将分辨率带宽作为一个参数。虽然这类界面使得FFT使用起来更容易，但确实隐藏了FFT的基本功能，导致必须接受示波器设置的时间/格、采样率和内存长度组合。根据这部分讨论的一些规则，你可以手工设置FFT，并在设置中获得更多的自由度。

垂直缩放

根据示波器的不同，FFT也许可以选择垂直刻度，也许只能是固定的单一垂直格式。最常见的垂直格式是功率谱，它以功率为单位显示垂直幅度，常用相对于1毫瓦的分贝表示(dBm)，并在对数垂直刻度上显示。这种选择也是射频频谱分析仪功能的保留。实验室级别的示波器可以提供更多的数据，包括功率谱密度(PSD)、线性幅度、平方幅度、相位或实数/虚数分量。

PSD是归一化为FFT分辨率带宽的功率谱值。它的测量单位是dBm/Hz，代表单位带宽上的功率。PSD在测量宽带现象(如噪声)时非常有用。幅度格式显示示波器测量的线性单位的频谱幅度，如伏特(V)或安培(A)。

幅度平方显示顾名思义是将频谱幅值显示为幅度的平方值，单位可以是V²、A²等等，并且在归一化为仪器输入阻抗(通常是50Ω)时为功率测量提供线性缩放。归一化是利用示波器的再缩放函数实现的，它允许乘以一个常数。对于50Ω来说，幅度平方谱乘以0.02(即1/50)，即对于50Ω输入阻抗而言将单位改为瓦(V²/50)。

从数学的角度来看FFT频谱是一个复杂函数，幅值的显示只是全貌的一半。FFT输出由实数和虚数部分组成，一些示波器可以同时显示这两部分。作为实数分量和虚数分量的替代，许多示波器显示FFT相位和幅值。这两个成对的输出格式(实数/虚数和幅值/相位)构成了完整的FFT。计算反向FFT时要求实数/虚数分量，在机械应用(如振动测量)中它们更常用，幅度/相位格式在电气测量中也常见到。图4显示了一个方波的功率谱幅值/相位和实数/虚数分量的例子。

图4：一个方波的FFT的功率谱幅值、相位、实数和虚数分量

相位谱使用垂直单位度，实数和虚数格式使用与源通道相同的垂直单位，在本例中是mV。对于类似这种方波的周期性波形，相位、实数和虚数格式只在基频和谐波频率点有有效值。

加权函数

示波器中实现的FFT具有有限的记录长度，这将在频谱显示中引起问题，原因是获取的波形的起点和终点的连续性问题。图5显示了起点和终点是如何影响频谱形状的。

图5：起点和终点的边界条件将影响信号经FFT处理之后的频谱形状

图5的上面两个波形中，所采集的信号频率是采样率的因数，获取的波形中存在整数的周期性，起点和终点处于相同的幅度，结果生成的频谱非常窄。在下面两个波形中，所采集的信号的频率不是采样速率的因数，起点和终点位于不同的电平。

这将导致时间记录的不连续性。生成的频谱变得更宽，峰值电平更低，原因是频谱扩展(也称为泄漏)，即采集信号的能量被扩展到了相邻频率单元。更低的、与频率有关的峰值响应被称为“尖桩篱栅”效率或扇形损耗。加权(开窗)有助于最大限度地减小这些效应。

加权是将获取的波形乘以一个窗口函数，通过调制将端点变为零。窗口函数的形状决定了频谱响应，包括频谱线的形状和任何边带的幅度。常用加权函数的特征如表1所示。

表1 常见FFT加权(窗口)函数的特征

这张表对每个窗口最大限度减小旁瓣和扇形损耗的能力进行了总结。图6显示了在相同输入信号条件下窗口函数对谱线的影响。

图6：这个屏幕图像比较了在相同输入信号条件下不同加权函数对频谱响应的影响

谱线变宽可以减小扇形损耗，这是有意义的，因为相邻单元中的信号会在更高幅度点重合，以获得更宽的响应，并最大限度地减小扇形损耗。

窗口函数的选择取决于具体需求。如果你要测量比采集窗口小的瞬变，那么不要使用窗口函数，因为频谱峰值的幅度将根据采集窗口中的瞬态位置发生改变。在这种情况下，矩形窗口(无加权)是最好的选择。越窄的窗口响应可以提供越好的频率分辨率和更宽的响应——Blackman Harris或平顶窗口——产生更为精确的幅度测量结果。如果你要两者兼顾，一个好的折衷方案是Von Hann或Hamming窗口。

频域平均

平均操作可以用来改善采集信号的信噪比，并且通常要求多次采集。平均可以在时域完成，也可以在频域完成。与触发事件不同步的信号，比如噪声，将与平均次数呈正比衰减。图7是频域平均的一个例子。

图7：频域平均可以改善信噪比，并提供更大的动态测量范围。有噪信号FFT在经过许多次采集的平均后可以消

频域中的平均是将多次采集的每个频率单元的内容累加起来然后除以采集次数实现的。那些与采集不同步的信号将被平均为零，而同步信号则连续累加。在图7中，有噪信号的FFT包含频谱被扩展的噪声分量，这些噪声隐藏了低电平的谐波。平均有助于提高信噪比，减少噪声，使得谐波分量可见。以同样的方式，那些与采集不同步的信号幅度也将降低。

设置实例

考虑需要在一个4GHz带宽的示波器上设置FFT，其频带宽度是10MHz，中心频率是2.48GHz，分辨率带宽为10kHz，用于分析一个连续的周期性信号。根据上述讨论，只需简单地设置示波器的时间/格参数就能完成分辨率带宽的设置。10kHz的分辨率带宽要求采集或捕获时间为100μs，或者时间/格参数设为10μs /格。还应设置示波器的垂直灵敏度(电压/格)，以便信号占据至少90%的输入范围，尽量提高其动态范围。

FFT的频带宽度由采样率控制。由于这个宽度必须包含2.48GHz信号频率，因此必须大于这个频率的两倍。5GHz或更高的频率应该没问题。示波器的最大采样率是20 GS/s。利用示波器的时基设置来调整采集内存长度，可以获得想要的采样率。在本例使用的示波器中，将内存长度设为1MS，可以实现10GS/s的采样率和100μs的采集时间。详细的FFT设置见图8。

图8：适合本例使用的主要FFT参数设置

数学函数F1的FFT栏包含一些主要的FFT设置，并被设置为显示功率谱。由于信号被显示为连续的，因此加权函数类型可以选择Von Hann窗口，它可以在频率分辨率和幅度平坦度之间提供很好的折衷。

FFT栏显示分辨率带宽(Δf)为10kHz，宽度为5GHz。缩放栏可以让你将中心频率设为2.48GHz，水平刻度设为1MHz/格，如图8中的F1轨迹所示。

小结

本文讨论了一些重要的FFT特性，解释了如何利用这些特性设置FFT以实现高效的分析。等下次你要在示波器中使用FFT时希望能助你一臂之力。

相关问答

【数字信号处理】按时间抽取的FFT算法的运算量、按频率抽取...

[最佳回答]两个的运输量相同.

...一些离散的数字信号每N个一组进行FFT分解,它同样会得】作业帮

[最佳回答]FFT变换,输入数据应该是2^n个,因此,有N=2^n,输出的N个数中,前N/2个和后N/2相同,只需要前N/2个,记为M第一个数代表直流分量,也称零次谐波;第二个数代...

x[n]={8,10,12,12,16,12,16,10}求DFT和FFT急数字信号处理的...

[最佳回答]天空映记着你的彷徨眼泪始终是汗水永远蒙蔽的他们的双眼宣告的么你卑微的的?为么·我这一个静谧的午后天空映记着你的彷徨眼泪始终是汗水永远蒙蔽...

fft技术?

FFT是技术一种DFT的高效算法技术,称为快速傅立叶变换(fastFouriertransform)。傅里叶变换是时域一频域变换分析中最基本的方法之一。在数字处理领域应用的离...

fft什么结构?

FFT是一种DFT的高效算法,称为快速傅立叶变换(fastFouriertransform)。傅里叶变换是时域一频域变换分析中最基本的方法之一。在数字处理领域应用的离散傅里叶...

fft音频变换的原理?

FFT(FastFourierTransmit),快速傅里叶变换,可以将时域转化为频域。FFT是离散傅氏变换(DFT)的快速算法。在数字信号处理中常常需要用到离散傅立叶变换(DFT),...

【傅里叶变换补零的问题.看到这样一段话:FFT分析中常常要用...

[最佳回答]你说的没错,进行补零后,傅里叶变换的频率分辨率变小了,由2048/2000变为了2048/2048.

MATLAB实现信号频谱分析(以余弦信号的FFT为例)?

余弦信号y=cos(2π*f*t);信号频率为f=10Hz;时宽:1s采样率为fs=100Hz;MATLAB程序:f=10;fs=100;T=1;n=round(T*fs);%采样点个...

如何利用示波器的FFT功能查看信号频谱?

1、我们输入一个10MHZ的方波,接入示波器,打开Math按键。2、按下操作符菜单下的按键通过选择FFT,示波器就进入了频域显示窗口。3、对于不同的波形,我们可以...

FFTBo介绍?

FFTBo是一个基于快速傅里叶变换(FFT)算法的加速库,主要用于计算机视觉和数字信号处理领域。FFTBo使用了多种优化技术,如利用SSE指令集、AVX和FMA指令集、Open...