作者 骆林依1，王英喆2，徐圆飞2，张华平3，梁星1(1.北华航天工业学院 电子与操控工程学院，河北 廊坊
065000;2.北京航星机器制作有限公司，北京 100013;3.郑州中兴智城实业有限公司，河南 郑州 450016)
摘要：跟着快速傅里叶改动(FFT)在信号处理使用领域的广泛使用，不同场合对硬件完结的 FFT
算法结构提出了多样化的要求，针对这种需求在硬件编程规划中将 FFT
分割成模块化的三部分：数据存储重排模块、旋转因子调用模块、蝶形运算模块。经过时序调用可组成不同结构的 FFT
处理器，完结流水结构与递归结构两种计划，别离偏重于处理速度与资源占用量两方面的优势。在FPGA硬件规划中运用 Verilog 言语完结代码编程，完结了两种结构的
512 点基 2 算法的快速傅里叶改换，运用 Modelsim 完结功用仿真。与 MATLAB 中 FFT
函数比照验证了成果的正确性。终究经过比较二者的处理速度和资源占用量，给出了计划功能剖析，及两种计划的最佳适用场合。
要害词：FFT;硬件完结;基 2 算法;模块化规划;流水线结构;递归结构
*基金项目：河北省北华航天工业学院硕士研讨生科研项目(YKY-2016-02)。
0 导言
快速傅里叶改换(FFT)作为信号处理的一种高效手法现已被广泛使用在许多工程中。但不同的使用场合对 FFT
算法的完结有不同的特性要求。研讨的首要热门在于硬件资源的占用量与运算速度[1-3]。而这两者又是相互制衡的联系。所以有必要比较完结 FFT 算法的多种计划。基
2 算法具有算法简略、时序明晰、在高速实时数据处理中不容易犯错的长处。所以本文扼要介绍了基 2 FFT 的算法化简原理，规划完结了将 FFT
处理器划分为通用化的三个模块。经过简略的时序调用就能够完结基 2 FFT
的两种功能偏重不同的计划。以习惯多种工程需求，并剖析了两种计划在不同场合的使用。
1 FFT算法原理
FFT(Fast Fourier Transformation)是离散傅氏改换(DFT)的快速算法
DFT 的运算公式为：
FFT 经过将离散序列逐级分解成为短序列，并使用旋转因子的周期性和对称性[4]简化了 DFT 的运算进程，进步了 DFT 的运算功率
[5-6]。
FFT算法的实质便是对数据逐级做蝶形运算。如图1所示是一个基2蝶形单元。蝶形运算为复数运算。每次运算由两个输入数据的实部虚部和相对应的复数旋转因子一起参加，运算成果成为下一级的输入数据。
由以下公式能够看出：一个基 2 蝶形运算单元中含有一个复数乘法和两个复数加法。在硬件完结中可将复数运算化简成实数运算[7-8]。
从上两式能够看出,(BrWr-BiWi)和(BrWi+BiWr)在上下两式中是重复呈现的，所以能够在蝶形模块中得到运算化简。
2 两种规划计划
递归结构处理速度较慢，但占用资源量少;流水线结构中量每一级运算都在一起进行着，输出数据除了刚开端的一段时刻延迟，之后会不间断地输出成果。因而，可进步运算速度。
榜首种规划计划是流水线[9-10]串行结构，体系框图如图2所示。流水线结构的特点是把全体规划分为几个次序的流程，这几个流程是单项串联的。数据在每一个流程中只运算一次，总是在将上一级的运算成果传递给下一级。直至一组数据经过一切流程完结运算。这种结构开端运算后的每一个流程都在一起高效的使用，处理来自上一级的接连数据流，所以在榜首组数据开端输出后，之后的成果数据就会不间断地输出。
流水结构中完结512点基 2 FFT 须重复调用9次三个通用模块，完结9级运算。数据次序逐级流入，依据级数计数信号来操控各模块的调整。
第二种规划计划是递归结构[11-12]，递归结构是指运算重复使用两组存储空间，每一级的运算都要用到上一级的运算成果。递归结构体系框图如图3所示。其要害部分是时序操控模块，效果是操控运算节奏，记载运算级数，然后操控排序模块在不同运算级的
RAM 读写规则以及旋转因子模块的地址选取。
在数据排序模块中，递归结构只占用两组 RAM 存储空间。数据穿插存储在两组 RAM 存储中。选用乒乓 RAM
结构交织写入读取数据，无需中间级的等候时刻，可减小体系的运算速度。
3 FPGA的硬件编程完结
FPGA完结的体系首要有三个通用模块构成：数据存储重排模块、旋转因子调用模块、蝶形运算模块。
本硬件规划中输入数据序列的长度为 512，输入数据的位宽为 30 位的有符号数，终究输出数据的位宽也是 30 位的有符号数。
以下来详细描述本规划中各个模块的硬件完结办法。
3.1 数据存储重排模块
FFT 中每级参加蝶形运算的两个数据是按规则挑取的。假定 L
级运算，每级中两个运管用据按原方位摆放会相差2(L-1)的距离。所以数据存储重排模块的效果便是将上一级的运算成果数据存储并按规则从头排序，使得输出的数据刚好是要进行下一级蝶形运算的两个数。
在本模块中，操控存储空间 RAM 的读写规则尤为要害。因为在 FFT 体系中，对 RAM 的读写速度直接影响到体系的运转速度。使用双口 RAM
对数据的读和写一起进行以进步体系运算功率，节省运算时刻。
每级数据调用方位不同，所以在编程时，要考虑每一级数据的排序规则，写入通用模块中，在 FFT 调用时依据运算级数操控数据的读取地址办法。本规划中 RAM
有两种存取办法：榜首级数据依照二进制码位倒叙写入，次序读出。2 到 9 级写入地址次序，读出地址距离为
1。经过验证这样的排序办法能够满意各级蝶形运管用的配对要求。
3.2旋转因子调用模块
旋转因子调用模块的效果是存储并按规则抽出旋转因子给蝶形运算模块。当参加 FFT
运算的点数确守时，所需的旋转因子值便是固定不变的。所以在硬件完结中，能够在体系运转之前将旋转因子数值表核算出来，并存储在 ROM 中。
旋转因子的调用跟运算级数有关，经过改动旋转因子的取数时刻距离和地址距离，生成9种不同的旋转因子调用规则。写入通用模块中。由时序操控模块中的运算级数计数器判别在程序运转中需求调用的旋转因子。
512 点的序列依据旋转因子的周期性和对称性共需求用到 256 个旋转因子。本规划共 9 级，假定第 L 级，则每级中会用到
2(L-1)个旋转因子。每级运算中会分为2(9-L)个运算组，同一级的每组用到的旋转因子都是相同的。每组中会用到本级一切的旋转因子。
依据 RAM
的取数规则，会按次序取完每组中的榜首个蝶形运算所需求的数据，他们所用到的旋转因子是同一个，运算完一切组的榜首个蝶形，再取每组的下一个蝶形运算所需求的数据，这样按次序把每组中所需求的数据取完，完结一级运算。
依照这种规则，运管用据与 ROM 读出的旋转因子相配合，能够削减 ROM 读地址的改动次数。这样 ROM
的取数更明晰简略，不同旋转因子取数的地址只用改动一次。如图 4，以 8 点 FFT 运算为例给出排序后的运管用据与旋转因子的对照表。
3.3 蝶形运算模块
因为本规划中只用到一种运算基，所以只用一个基 2 蝶形单元就能够完结对数据的流水线处理。
本规划中 512 点的 FFT 共有 9 级运算，蝶形运算模块内部选用流水结构，可将从 RAM 中输出的数据不间断地进行核算。每级次序进行 256
次蝶形运算。
本规划中的蝶形运算流程如图 5 所示。经过上述对公式的化简剖析可得，一次蝶形运算实质上可转化为 4 次实数乘法和 6
次实数加法运算。内部划分为三级流水结构，数据和旋转因子并行输入核算。进步了模块运算功率。
4 仿真成果
本规划选用 Verilog 硬件言语在quartus 16.0 渠道编写，在 modelsim 上经过仿真，验证成果与 matlab 中的 FFT
函数成果比较较，到达体系所要求精度。
流水结构的 modelsim 仿真成果如图6所示，仿真选用 50 M 时钟，在 105240 ns
时输出使能信号拉高有用，开端接连的输出运算成果数据。
流水线结构大幅度进步了处理器速度，一起不可避免的加大了资源占用量。本规划的资源占用状况见表 1.
递归结构的 modelsim 仿真成果如图7所示，仿真选用 50 M 时钟，在 10500 ns
时开端输出数据，由图中仿真成果能够看出，两种规划在运算一次 512
点FFT的时刻上十分挨近，仅仅流水结构在输出榜首组成果数据后可接连不断的输出下一组数据，递归结构则需求再等候一次完好运算时刻，才干输出下一组成果数据。
递归结构的资源占用量较流水结构比较削减许多。资源占用状况见表 2。
5 成果比较
FPGA完结中流水结构的资源占用量较大，但用流水线结构能够进步体系的作业频率和吞吐率。将处理器速度得到了大幅度的进步，可使用在实时性要求高的数据处理场合。进行实时的
FFT 运算。
从上面的剖析能够看出，递归结构两次运算输出成果所需时刻距离较长。但在硬件完结中需求的存储资源量很少。本规划经过选用乒乓 RAM
结构和下降蝶形运算单元中乘法数目的办法，节省了硬件资源，下降了规划本钱。适合于使用在对速度要求不高低本钱的处理体系中。
经过比较二者资源量和数据，能够发现资源与速度在硬件完结中是相互制约的。所以要参照 FFT
所运用的场合和用处来挑选最合适的算法。本规划中使用三个固定模块可快速灵敏的改动算法优势，满意资源和速度的两种需求。
参考文献
[1]刘智.根据FPGA完结的FFT速度与规划剖析[J].科技视界,2014(21):192-193.
[2]杜兆胜.根据FPGA的FFT硬件架构规划与完结[D].长春理工大学,2016.
[3]余雷.根据FPGA的32点FFT算法的规划与完结[D].西安电子科技大学,2014.
[4]钱辉,史瑶,龚敏,高博.结合频谱移位的二维傅里叶改换FPGA完结[J].电子器件,2017,40(05):1092-1096.
[5]顾美丽,周洪敏.根据FPGA的新式高速FFT算法研讨与完结[J].电子器件,2008(4):1249-1251.
[6]王晓君,龙腾,周希元.二维级联流水结构大点数FFT运算器完结研讨[J].无线电工程,2010,40(11):19-22.
[7]于洪松.根据FPGA的实时图画频域处理[D].中国科学院研讨生院(长春光学精密机械与物理研讨所),2014.
[8]唐英杰,钟凯.一种根据FPGA的高速FFT处理器完结[J].科技广场,2015(12):15-17.
[9]王英喆,杜蓉.根据FPGA流水线结构并行FFT的规划与完结[J].电子规划工程,2015,23(4):47-50.
[10]和玉梅.部分流水FFT处理器规划[J].兰州理工大学学报,2014,40(6):83-89.
[11]赵冬冬.根据FPGA的1024点FFT算法完结[D]. 苏州大学,2014.
[12]杨晶,康宁,王元庆.根据低本钱FPGA的FFT规划完结[J].电子器件,2013,36(4):506-509.
作者简介：
骆林依(1994-)，女，硕士生，首要研讨方向：信号收集与处理。
本文来源于科技期刊《电子产品世界》2019年第2期第31页，欢迎您写论文时引证，并注明出处
