基于FPGA的高速分裂基FFT算法实现

1、年第期（总第期）中国高新技术企业（CumulativetyNO.136）基于FPGA 的高速分裂基FFT 算法实现刘星（电子科技大学自动化工程学院，四川成都610054）摘要：快速傅里叶变换（FFT ）是离散傅里叶变换（DFT ）的快速算法，而分裂基FFT 算法是所有FFT 算法中一种效率较高的在高速的系统要求下，文章选择分裂基FFT 算法作为实现高速FFT 处理器的基本算法。文中一种算法，有着广泛的应用。流水线技术等有效的实现方法，在Virtex-5FPGA 平台上有着很好的效果，并且满足了高速的系统设计采用了并行处理、系统延时只有13个周期，并且在资源利用上面有很高的效率。要求。结果显示，

2、关键词：FFT ；分裂基算法；FPGA ；Virtex-5；并行处理；流水线中图分类号：TN791文献标识码：A 文章编号：1009-2374（2010）01-0011-03离散傅里叶变换（）和卷积运算是两种基本和常用的很多其他的算法比如滤波、频谱分析信号处理方法。实际上，等，都能够通过来实现。但是由于算法过于复杂，和在年最先提出了快速傅里叶变换（）算法来代替。作为一个快速版本的，以及它的反变换，是数字信号频谱分析领域中的重要分析方法。现场可编程门阵列（）比普通的数字信号处理器（）在实现算法时有着很大的速度优势以及更高的效率。因此在实时信号处理领域，用做运算比用处理器有着更多的好处。文章介绍了

3、一种基于的高速定点分裂基算法的实现，此设计有较小的均方误差，并且当等于点时，系统时钟可以达到，而数据延时只有个周期。第一节介绍了算法的选择，分裂基算法的原理以及数据流图。第二节介绍了处理器的设计。第三节介绍了设计的仿真、综合以及实现结果。最后第四节给出了此设计的结论。于的基数没有多大实际意义。因此，实用中多采用基本形式的基或基算法。年，和将基和基分解柔和在一起，提出了一种分裂基算法。其运算量比前几种算法都有所减少，运算流图却与基很接近，程序也很容易实现，因此分裂基是一种实用、高效的算法。文章将以分裂基算法为研究对象，完成基于的高速引擎的实现。（二）分裂基算法原理分裂基算法的基本思路就是队偶序号

4、序列实用基算法，队基序号序列实用基算法，这样就可将基分解同基分解组合在一起。算法的推导如下：设，且，则可表示为，（）（）（）（一、算法选择及原理（一）选择算法（自从和提出（按时间抽取）算法后，已经有很多种新的算法被人们研究出来，包括上面推导中运用了的结果。这些算法可以分为两类：（按频率抽取）算法等。总的来说，将表示为，）；另外一类是不第一类是点数等于（为任意自然数则（）可表示为：等于。由于当不等于时，我们可以在后面加上若干个，使（）（）（）（等于，从而转化为第一种情况。所以我们常用的都是属于第一类的。在第一类算法中，包括基、基（）（）和基（）等。从理论上讲，用较大的基数可以进一步减少运算次数，

5、但程序（或硬件）都将变得复杂，因此大在，时用表示，表示，可得出：的执证上岗考核氰化物项目时，显色时未放入水浴，只放置在实验室中显色，盲样考核合格。三、结论试验结果表明，直接放置于室温显色，避免了水浴显色时将比色管放入与取出等步骤，且不需要恒温水浴锅，方法简单；直接显色温色范围宽，一般实验室四季均可在直接显色法精密度好，准确度高。温度范围内；参考文献1水质氰化物的测定异烟酸吡唑啉酮光度法（GB7487-87）S2国家环境保护总局水和废水监测分析方法编委会水和废水监测分析方法（第4版）M北京：中国环境科学出版社，2002作者简介：张莉（1973），女，湖南洪江人，湖南省怀化市洪江区环境监测站工程师

6、，研究方向：环境监测。-11-l N N 3N ? X (4k x (n ?x (n ? ?x (n ? ?x (n ?W ?）（）（），l （l ?l ?424?N N 3N ?X (4k ?1 ?l x (n ?jx (n ? ?x (n ? ?jx (n ?W ?（l ）（）（），l 424l ?X (4k ?2 ?x (n ?x (n ?N ?x (n ?N ?x (n ?3N W 其中，424?N N 3N （）（）（），X (4k 3 x (n ?jx (n ? ?x (n ? ?jx (n ?W ?424（）（）（），?（）（）（），将偶数序号项（）和（）合并可得出偶数号输出项为

7、：（）（）（，（）（）（），（）（）（），经过分析计算，得到点分裂基数据流图如图所示：（）基数号输出项实用基算法如下：（）（）（）（）（）（）（）（）（）（）由此可见，一个点的可以分解为一个点的和两个点的，称其为形蝶形运算，其第一次形蝶形流图其余所示。一个形蝶形运算中只有两次乘旋转因子的运算，权威加减法运算。点的点的又可以继续进行形蝶形运算，因此循此进行，最好可以分解为点或点进行运算。图216点分裂基FFT 数据流图二、分裂基算法的设计与实现（一）总体实现结构设计分裂基算法以形蝶形运算为核心，其中既包括基所以分裂基算法并不是对称的。由图算法又包括基算法。可以看到，点复数中（）和（）只需经过级复

8、数加法运算就可以得到，但是（）和（）要经过级复数加减法运算，文章设计了一种并行流水线分裂基一级复数乘法运算。因此，算法处理器。其总体结构图如图所示：图1L 形算法结构下面以时，说明完整的分裂基运算流图。令（）（）（），（）（）（），（）（）（），（）（）（），（）（）（），由式（）（）（）可得：（）（），（）（）（）（），（）（）（），对式（）再进行分裂基蝶形运算，令（）（l ），第二次分l 解可得：（l ）（）（），l ll图316点分裂基FFT 处理器结构图输入数据为复数，包括的实部和的虚部。读入数据缓存后，开始进行形蝶形运算，第一级形蝶形运算得到的一个点的和两个点。点可以直接进行蝶形运算

9、得到结果。点数据再送入第二级形蝶形运算单元，得到一个点和两个点，然后直接进行蝶形运就完成了算，得到结果。最后再将后的数据重新排列，整个运算。（二）复数乘法器设计对于复数乘法单元的设计，常见的复数乘法方式为：（）（）（），其中为虚数单位。用这种方式，需要次乘法运算，次加减法运算。由于在-12-设计中乘法单元的引入，特别是高位数的乘法器单元的引入将会消耗大量的资源，并影响运行的速度。所以我们采取了一下的复数乘法器的设计：（）（）（）（）（）（）这种方式中，用到了次乘法运算，次加减法运算就完成了复数乘法运算，减少了乘法器的数量，增加了资源的利用率。（三）旋转因子查找表设计通过分析数据流图（图），我们

10、可以发现，某些蝶形运算可以简化为没有乘法器的运算，因为蝶形运算旋转因子，。有这些旋转因子的蝶形运算环节都可以，因此我们通过加减法运算，和改变符号，调换实部虚部来实现。只需要存储以下个蝶形运算旋转因子，这样就节约了大量的存储空间，同时也节约了大量的乘法。器单元。（四）错误分析浮点运算将会消耗很多的逻辑资源，相反的，尽管有限字长效应适当的存在，适当的数据转换可以防止数据的溢出，高效率的错误控制能够抑制圆周效应。在文章中采用了定点数运算。在定点数运算中，数据的错误由以下几个方面组成：乘法截取错误，两个的数相乘，得到的结果是，如果截取成，那么一定会出现错误。如果数据小于，那么结果就一定不会溢出。加减法

11、溢出错误，两个的数相加，得到的结果将会是一个的数，这样我们必须丢弃再进行下一级操只要将数据向低位移以为，就能够避免出现溢出。作。事实上，三、数据仿真与实现分析设计中采用了自顶向下的设计思路，各模块采用硬件描述语言在软件环境下在平台上进行设计，用仿真软件在系统时钟为的情况下结果显示消耗了进行仿真，系统综合在中进行。的单元，的资源，最快时钟达到。仿真图形如图所示。仿真结果与软件仿真的结果进行对比得出两者只有极其微小的差别，满足设计的要求。这说明系统若要扩展成点或点的，只需要增加蝶形运算的层级就能够实现 。图416点FFT 波形仿真图仿真图形显示，由于采用了有效的措施来抑制错误和溢系统延时为出，即便

12、是输入最大的数，也没有出现溢出的情况。个时钟周期。with practical algorithmsJIEEE Trans on ASSP ，1990，38（9）3王世一数字信号处理M北京：北京理工大学出版社，19974樊光辉，许茹，王德清基于FPGA 的高速流水线FFT 算法实现J电子工程师，2008，34（3）5ZhaoTao ，FU Feng -lin ，WANG Xiao -hui ，Design and implementation of FFT module based on the Stratix FPGA ，International Electronic Elements ，2006，（5）.Zhu En ，Design of high -performance FFT 6RongYu ，butterfly unit ，JOURNAL OF SOUTHEAST UNIVERSITY （Natural Science Edition ），2007，137（4）作者简介：刘星（1984），男，河南郑州人，电子科技大学自动化工程学院硕士研究生，研究方向：基于FPGA 的数字中频处理。四、结论经过验证，所采用的高速、并行、流水线、定点、分裂基所有的模算法设计，能达到设计要求，并且控制实现简单可行。块均经过