基于FPGA的64点FFT处理器设计

采用FPGA实现FFT算法随着数字技术的快速发展，数字信号处理已深入到各个学科领域。

在数字信号处理中，许多算法如相关、滤波、谱估计、卷积等都可通过转化为离散傅立叶变换(DFT)实现，从而为离散信号分析从理论上提供了变换工具。

但DFT计算量大，实现困难。

快速傅立叶(FFT)的提出，大大减少了计算量，从根本上改变了傅立叶变换的地位，成为数字信号处理中的核心技术之一，广泛应用于雷达、观测、跟踪、高速图像处理、保密无线通信和数字通信等领域。

目前，硬件实现FFT算法的方案主要有：通用数字信号处理器(DSP)、FFT专用器件和现场可编程门阵列(FPGA)。

DSP具有纯软件实现的灵活性，适用于流程复杂的算法，如通信系统中信道的编译码、QAM映射等算法。

DSP完成FFT运算需占用大量DSP的运算时间，使整个系统的数据吞吐率降低，同时也无法发挥DSP软件实现的灵活性。

采用FFT专用器件，速度虽能够达到要求。

但其外围电路复杂，可扩展性差，成本昂贵。

随着FPGA发展，其资源丰富，易于组织流水和并行结构，将FFT实时性要求与FPGA器件设计的灵活性相结合，实现并行算法与硬件结构的优化配置，不仅可以提高处理速度，并且具有灵活性高。

开发费用低、开发周期短、升级简单的特点。

针对某OFDM系统中FFT运算的实际需要，提出了基于FPGA的设计来实现FFT算法，并以16位长数据，64点FFT为例，在Quartus Ⅱ软件上通过综合和仿真。

2 FFT原理及算法结构FFT是离散傅立叶变换(DFT)的快速算法。

对于N点离散的有限长时问序列x(n)，其傅里叶变换为：完成N点的DFT需要N2次复数乘法和N(N-1)次复数加法。

点数大时，计算量也大，所以难以实现信号的实时处理。

FFT的基本思想是利用旋转因子WN的周期性、对称性、特殊性以及周期N的可互换性，将长度为N点的序列DFT运算逐次分为较短序列的DFT运算，合并相同项，大大减少了计算量。

FFT算法的一种FPGA实现摘要：FFT运算在OFDM系统中起调制和解调的作用。

针对OFDM系统中FF T运算的要求，研究了一种易于FPGA实现的FFT处理器的硬件结构。

接收单元采用乒乓RAM结构，扩大了数据吞吐量。

中间数据缓存单元采用双口RAM，减少了访问RAM的时钟消耗。

计算单元采用基2算法，流水线结构，可在4个时钟后连续输出运算结果。

各个单元协调一致的并行工作，提高了系统时钟频率，达到了高速处理。

采用块浮点机制，动态扩大数据范围，在速度和精度之间得到折衷。

模块化设计，易于实现更多点数的FFT运算。

关键词：FFT；FPGA；蝶型运算；乒乓RAM结构1引言OFDM（正交频分复用）是一种多载波数字调制技术，被公认为是一种实现高速双向无线数据通信的良好方法。

在OFDM系统中，各子载波上数据的调制和解调是采用FFT（快速傅里叶变换）算法来实现的。

因此在OFDM系统中，FFT的实现方案是一个关键因素。

其运算精度和速度必须能够达到系统指标。

对于一个有512个子载波，子载波带宽20 kHz的OFDM系统中，要求在50 μs内完成512点的FFT运算。

硬件实现FFT算法的主要方案有：DSP（通用数字信号处理器）；FFT专用芯片；FPGA（现场可编程门阵列）。

DSP具有纯软件实现的灵活性，适合用于流程复杂的算法，例如在通信系统中的信道编、解码，QAM映射等算法。

如果在DSP中完成FFT运算，不仅要占用大量D SP的运算时间，使整个系统的数据吞吐率降低，也无法发挥DSP软件实现的灵活性。

因此，前端的FFT运算应由ASIC或FPGA完成。

采用专用的FFT处理芯片，虽然速度能达到要求，但其可扩展性差。

FPGA具有硬件结构可重构的特点。

适合于算法结构固定、运算量大的前端数字信号处理。

新近推出的FPGA产品都采用多层布线结构，更低的核心电压，更丰富的IO管脚，容量可达到100 k个逻辑单元（LES），内置嵌入式RAM资源，内部集成多个数字锁相环，多个嵌入的硬件乘法器，所有这一切都使得FPGA在数字信号处理领域显示出自己特有的优势。

基于FPGA架构的可变点FFT处理器设计与实现才华;陈广秋;刘广文;耿振野;杜兆圣【摘要】通过对传统的基-4快速Fourier变换(FFT)算法进行优化,降低基-4算法的复杂度,使其具有基-2算法的蝶形结构.采用优化后的基-4/2混合基算法及流水线基-22单路延时反馈(R22 SDF)结构设计可变点FFT处理器,并对输出结果进行功能和信号仿真验证.结果表明,该处理器的有效性和执行效率均表现良好.%The complexity of radix-4 algorithm was reduced by optimizing the traditional radix-4 fast Fourier transform (FFT) algorithm ,which retained the butterfly structure of radix-2 algorithm .The optimized mixed radix-4/2 and pipeline radix-22 single-path delay feedback (R22 SDF) structure were adopted to design the variable points FFT processor ,and the output results were verified by the function and signal simulation .The results show that the FFT processor is excellent in validity and efficiency .【期刊名称】《吉林大学学报（理学版）》【年(卷),期】2018(056)001【总页数】8页(P151-158)【关键词】正交频分多址技术;快速Fourier变换;蝶形运算;流水线;基-22单路延时反馈【作者】才华;陈广秋;刘广文;耿振野;杜兆圣【作者单位】长春理工大学电子信息工程学院 ,长春130022;长春理工大学电子信息工程学院 ,长春130022;长春理工大学电子信息工程学院 ,长春130022;长春理工大学电子信息工程学院 ,长春130022;长春理工大学电子信息工程学院 ,长春130022【正文语种】中文【中图分类】TN47快速Fourier变换(FFT)作为一种有效计算离散Fourier变换(DFT)的方法, 在通信、滤波及数字谱分析等领域应用广泛. 利用现场可编程门阵列(FPGA)可设计FFT处理器的硬件架构[1].随着FFT算法的不断完善, 在基-2FFT算法[2]的基础上, 文献[3-6]又提出了基-4、基-8和基-16固定基以及分裂基等算法. 随着基数r的增加, 算法分解级数逐渐减少, 所需运算量(乘法和加法)也逐渐减少, 但其算法控制的复杂度增大. 由于可实现的点数受到限制, 因此需引进混合基算法兼顾FFT的运算量和复杂度[7].常用的FFT处理器硬件结构有4种[8]：顺序结构、流水线结构、并行结构和阵列结构. 其中顺序结构运算速度慢, 实时性差；流水线结构比顺序结构的运算速度提高了logrN倍(其中： N为序列点数； r为基数), 所需的硬件资源有所增加；阵列结构的运算速度最快, 但所需硬件资源和功耗也最大. 由于流水线结构包含多个独立的蝶形运算单元, 每个单元负责一级蝶形运算, 各级蝶形运算单元间采用流水线方式进行工作, 通过增减结构中蝶形运算单元可实现不同点数序列的FFT, 此外流水线结构还具有芯片面积小、功耗低以及高数据吞吐量等优点, 因此可采用流水线结构处理硬件资源与处理速度间的关系.正交频分多址技术(OFDMA)是基于正交频分复用技术(OFDM)的新一代无线接入技术, 在IEEE802.16e物理层标准中, 不同带宽的OFDMA系统采用的FFT点数不同, 如3 M带宽采用256点, 10 M带宽采用1 024点, 20 M带宽采用2 048点等[9-10]. 本文利用FPGA硬件架构, 采用优化的基-4/2混合基分解算法及流水线硬件结构实现可变点FFT处理器的设计, 并将其应用于OFMDA系统中.1 按频率抽取基-2/4混合基算法原理1.1 按频率抽取基-2FFT算法原理设序列点数N=2L(L为整数), 按频率抽取(DIF)基-2FFT算法将输入x(n)按n的顺序分为前后两部分, 将结果X(k)按k的奇偶进行分组[11-12]. 其中(1)按k的奇偶性, 将X(k)划分为(2)图1 DIF基-2蝶形运算单元Fig.1 Radix-2 DIF butterfly operation unit由式(2)可得DIF基-2蝶形运算单元, 如图1所示.1.2 按频率抽取基-4FFT算法原理设序列点数N=4L(L为整数), DIF基-4FFT算法将输入x(n)按n的顺序分为前后4组, 将运算结果X(k)按k=4r, k=4r+1, k=4r+2和进行分组. 其中(3)对X(k)进行分组(4)由式(4)可得DIF基-4蝶形运算单元, 如图2所示. 由图2可见, 基-4比基-2蝶形运算复杂, 结构差别较大, 规律性较差, 不适合硬件实现混合基运算, 因此需对上述算法进行优化. 将式(4)中的序列重新分组, 可得优化的DIF基-4FFT算法为(5)由式(5)可得优化后的DIF基-4蝶形计算单元, 如图3所示.图2 传统DIF基-4蝶形运算单元Fig.2 Traditional radix-4 DIF butterfly operation unit图3 优化后的DIF基-4蝶形运算单元Fig.3 Optimized radix-4 DIF butterfly operation unit通过计算可知, 优化后的DIF基-4蝶形运算比传统的DIF基-4蝶形运算可减少4个复数加法运算, 其结构与DIF基-2蝶形结构相同, 信号流图具有较强的规律性, 适合硬件实现混合基运算. 图4为优化后N=16的DIF基-4FFT流图.图4 优化后的DIF基-4FFT流图(N=16)Fig.4 Flow graph of optimized radix-4 DIF FFT (N=16)由图4可见, 优化后DIF基-4FFT与DIF基-2FFT的各级流图在结构形式上一致, 仅旋转因子不同.2 混合基FFT算法原理N点DFT的计算表达式为(6)其中N=r1r2…rL为复合数, 按整数的多基多进制表示形式, 式(6)中的n和k可分别表示为(7)其中: ni=0,1,…,rL-i-1; ki=0,1,…,ri+1-1, i=0,1,…,L-1. 将式(7)中n和k的值代入式(6)可得(8)由式(8)可知, 当满足r1=r2=…=rL-1=rc时, 可将N点DFT分解为(L-1)个基-rcFFT及一个基-rLFFT级联的形式, 从而缩短完成DFT运算所需时间, 并解决基-rcFFT算法无法实现rc非整数次幂DFT算法的问题, 因此本文提出的可变点FFT 算法可将DIF基-4和基-2进行级联计算, 且优化后的DIF基-4与基-2算法具有相同蝶形单元结构, 更适合硬件实现混合基运算[13-14].3 可变点FFT处理器的硬件架构设计及仿真和验证3.1 FFT处理器流水线结构基-2或基-4FFT处理器主要有4种流水线结构[15-16], 分别为基-2多路延时转换(R2MDC)结构、基-2单路延时反馈(R2SDF)结构、基-4单路延时反馈(R4SDF)结构与基4多路延时转换(R4MDC)结构. R2SDF和R4SDF比R2MDC和R4MDC 能更有效利用存储器, R4SDF比R2SDF能更有效利用乘法器, 但R2SDF比R4SDF具有更简单的蝶形结构及更低的控制复杂度. 在混合基算法中, 基-2FFT流水线结构采用R2SDF结构, 优化后的基-4FFT流水线结构采用改进的R2SDF结构, 称为基-22单路延时反馈(R22SDF)结构. 以16点FFT为例, R2SDF结构如图5所示.图5 R2SDF结构(N=16)Fig.5 Structure of R2SDF (N=16)首先将输入数据分成上下两部分, 上半部分数据串行输入第一级延时缓存器中, 下半部分第一个数据与缓存单元中的第一个数据送入第一级基-2蝶形单元(数据点间距为N/2)进行运算, 将二者之和送到下一级运算单元, 二者之差送到本级的延时缓存器中, 覆盖第一个数据, 对所有数据依次进行上述处理, 可得第一级蝶形运算的全部结果, 结果的上半部分依次送入下一级继续计算, 下半部分依次存入本级的延时缓存单元；对进入第二级基-2蝶形运算单元的数据也分为上下两部分, 上半部分数据串行输入第二级延时缓存器中, 下半部分第一个数据与缓存单元中的第一个数据送入第二级基-2蝶形单元进行运算(数据点间距为N/4), 各级基-2蝶形运算单元均采用相同的处理机制, 从而保证各级数据流的连续性, 最后得到计算结果.由图1和图2可知, 优化后的基-4蝶形单元与基-2蝶形单元具有相同结构, 仅在BF2Ⅰ阶段需乘以一个-j, 对R2SDF结构进行改进得到优化后的基-4FFT流水线单路延时反馈结构, 其数据流的计算过程与R2SDF结构相同, 如图6所示.图6 R22SDF结构(N=256)Fig.6 Structure of R22SDF (N=256)在图6的BF2Ⅰ单元中, t为控制输出与-j相乘的时钟, 可实现实部与虚部位置互换. 不同流水线结构所需硬件资源及控制复杂性的比较列于表1. 由表1可见, R22SDF 流水线结构在乘法器和存储器所需数量均最少, 因此本文采用R22SDF结构.表1 不同流水线结构所需硬件资源及控制复杂性的比较Table 1 Comparisons of hardware requirement and control complexity in different pipeline structures结构乘法器加法器存储器控制复杂性R2MDC2(log4N-1)4log4N3N/2-2简单R2SDF2(log4N-1)4log4NN-1简单R4SDFlog4N-18log4NN-1中等R4MDC3(log4N-1)8log4N5N/2-4简单R22SDClog4N-14log4NN-1简单3.2 可变点FFT处理器的硬件架构设计采用基-4/2混合基算法和流水线R22SDF结构设计可变点FFT处理器的硬件架构, 如图7所示. 由图7可见, 可通过增减蝶形单元实现不同点数的FFT, 从而实现OFDMA系统的核心功能. 各级运算模块结构类似, 均包括控制单元、蝶形运算数据存储单元、旋转因子存储单元、复数乘法运算单元和蝶形运算单元五部分. 其中蝶形运算单元为核心部分, 该单元完成BF2,BF2Ⅰ和BF2Ⅱ的复数加法运算, 其运算单元结构如图8所示.3.3 功能仿真验证采用Matlab软件产生一个64=43点的序列, 作为仿真软件Modelsim和FFT处理器的输入, Modelsim仿真结果如图9(A)所示, 通过Quartus中的Signaltap逻辑分析仪采样得到FFT处理器运行结果, 如图9(B)所示. 由图9可见, (A)和(B)的结果一致, 表明设计的FFT处理器各功能模块及整个系统满足设计要求, 功能与时序正确.图7 可变点FFT处理器的硬件架构Fig.7 Hardware architecture of variable points FFT processor图8 BF2Ⅰ(A)和BF2/BF2Ⅱ(B)的运算单元结构Fig.8 Operation unit structure of BF2Ⅰ (A) and BF2/BF2Ⅱ (B)图9 Modelsim仿真结果(A)与FFT处理器运行结果(B)Fig.9 Simulation results of modelsim (A) and operation results of FFT processor (B)3.4 信号仿真验证利用Matlab软件对正弦波和锯齿波进行采样, 得到输入序列, 将FFT处理器运算结果通过Matlab做ifft和生成频谱, 并与Matlab中fft( )函数产生的频谱进行比较.3.4.1 正弦波信号仿真利用Matlab函数产生一组1 024=45点正弦波序列点, 信号的采样频率为500 Hz, 为显示方便, 幅值放大104倍.x(t)=sin(2π×10×t).(10)通过Matlab中fft( )函数产生的频谱和FFT处理器运行结果如图10所示. 由图10可见, FFT处理器输出的结果通过函数ifft( )得到的时域信号与输入正弦波信号相同, 输出的频谱与Matlab所得频谱一致, 时域误差与频域误差极小.(A) 正弦信号时域信号(N=1 024); (B) 利用IFFT得到的时域信号; (C) 时域信号误差;(D) Matlab FFT运算结果; (E) 本文FFT运算结果; (F) 频域信号误差.图10 1024点正弦波运算结果Fig.10 Operation results for 1 024 points sine wave 3.4.2 锯齿波信号仿真与验证利用Matlab软件产生一组2 048=2×45点锯齿波序列点, 作为输入信号, 信号的采样频率为50 Hz, 为显示方便, 幅值放大104倍, 通过Matlab中fft( )函数产生的频谱和FFT处理器运行结果如图11所示. 由图11可见, FFT处理器输出的结果通过函数ifft( )得到的时域信号与输入三角波信号相同, 输出的频谱数据与Matlab所得频谱一致, 时域误差与频域误差较小.(A) 锯齿波信号时域信号(N=2 048); (B) 通过IFFT得到的时域信号; (C) 时域信号误差;(D) Matlab FFT运算结果; (E) 本文FFT运算结果; (F) 频域信号误差.图11 2 048点锯齿波信号运算结果Fig.11 Operation results for 2 048 points sawtooth wave综上, 本文设计了一种基于FPGA的可变点FFT处理器, 采用DIF基-4/2混合基算法, 通过优化使得基-4算法流图中具有基-2蝶形结构, 有效减少了蝶形迭代的次数, 降低了运算的复杂度, 采用流水线R22SDF结构, 可减少所需存储器和乘法器的数量, 提高各级间的运算速度, 每级蝶形运算可在部分数据完成计算和存储后即开始新一级运算, 实现多级运算交叉进行, 进一步提高了FFT运算速度, 降低控制难度. 最后通过实验对FFT处理器进行功能和信号的仿真验证, 实验结果表明, FFT处理器的有效性和执行效率均满足OFDMA系统应用的需求.参考文献【相关文献】[1] CHEN Jiyang, LEI Yuanwu, PENG Yuanxi, et al. Configurable Floating-Point FFT Accelerator on FPGA Based Multiple-Rotation CORDIC [J]. Chinese Journal of Electronics, 2016, 25(6): 1063-1070.[2] 刘宝军, 王中训, 钟强, 等. 基于FPGA的FFT算法设计与实现 [J]. 光电技术应用, 2016, 31(3): 46-49. (LIU Baojun, WANG Zhongxun, ZHONG Qiang, et al. Design and Implementation of FFT Algorithm Based on FPGA [J]. Electro-Optic Technology Application, 2016, 31(3): 46-49.)[3] Prabhu E, Mangalam H, Karthick S. Design of Area and Power Efficient Radix-4 DIT FFT Butterfly Unit Using Floating Point Fused Arithmetic [J]. Journal of Central South University, 2016, 23(7): 1669-1681.[4] 樊恩辰, 姚馨, 何书专, 等. 基于SystemC的可配置FFT周期精确模型 [J]. 微电子学与计算机, 2014, 31(11): 83-87. (FAN Enchen, YAO Xin, HE Shuzhuan, et al. Cycle-Accurate Configurable FFT Modeling with System C [J]. Microelectronics & Computer, 2014, 31(11): 83-87.)[5] Huang S J, Chen S G. A High-Throughput Radix-16 FFT Processor with Parallel and Normal Input/Output Ordering for IEEE 802.15.3c Systems [J]. IEEE Transactions on Circuits & Systems Ⅰ: Regular Papers, 2012, 59(8): 1752-1765.[6] Joshi S P, Paily R. Distributed Arithmetic Based Split-Radix FFT [J]. Journal of Signal Processing Systems, 2014, 75(1): 85-92.[7] Kim E J, Lee J H, Sunwoo M H. Novel Shared Multiplier Scheduling Scheme for Area-Efficient FFT/IFFT Processors [J]. IEEE Transactions on Very Large Scale Integration Systems, 2015, 23(9): 1689-1699.[8] 王英喆, 杜蓉. 基于FPGA流水线结构并行FFT的设计与实现 [J]. 电子设计工程, 2015, 23(4): 47-50. (WANG Yingzhe, DU Rong. A Pipelining Architecture Design of Parallel FFT Based on FPGA [J]. Electronic Design Engineering, 2015, 23(4): 47-50.)[9] Harikrishna K, Rama R T, Labay V A. FPGA Implementation of FFT Algorithm for IEEE 802.16e (Mobile WiMAX) [J]. International Journal of Computer Theory and Engineering, 2011, 3(2): 197-203.[10] Yang K J, Tsai S H, Chuang G C H. MDC FFT/IFFT Processor with Variable Length for MIMO-OFDM Systems [J]. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(4): 720-731.[11] 许朋, 周立青, 刘宇航, 等. 基于FPGA的高性能浮点型FFT处理器设计 [J]. 武汉大学学报(工学版), 2015, 48(1): 120-124. (XU Peng, ZHOU Liqing, LIU Yuhang, et al. Design of a High-Performance Floating-Point Fast Fourier Transform Processor Based on FPGA [J]. Engineering Journal of Wuhan University, 2015, 48(1): 120-124.)[12] 苏斌, 刘畅, 潘志刚. 基于FPGA的高速浮点FFT/IFFT处理器设计与实现 [J]. 中国科学院大学学报, 2015, 32(2): 259-263. (SU Bin, LIU Chang, PAN Zhigang. Design and Implementation of High-Speed Floating Points FFT Processor Based on FPGA [J]. Journal of University of Chinese Academy of Sciences, 2015, 32(2): 259-263.)[13] 周景龙. 基于高速FFT结构的频域抗干扰算法的FPGA实现 [J]. 微电子学与计算机, 2014,31(5): 32-35. (ZHOU Jinglong. An FPGA Implementation of Frequency-Domain Anti-jamming Algorithm Based on a Structure of High-Speed FFT [J]. Microelectronics & Computer, 2014, 31(5): 32-35.)[14] Lakshmi D V V, Satya N C, Anil K R. Butterfly Design for RADIX-4K DIF FFT [J]. International Journal of Research in Computer and Communication Technology, 2014,3(10): 1348-1353.[15] WANG Zeke, LIU Xue, HE Bingsheng, et al. A Combined SDC-SDF Architecture for Normal I/O Pipelined Radix-2 FFT [J]. IEEE Transactions on Very Large Scale Integration Systems, 2015, 23(5): 973-977.[16] 王天. 基于混合基算法的快速傅立叶变换和反变换在VDSL2中的应用与实现 [D]. 西安：西安电子科技大学, 2009. (WANG Tian. Application and Implementation of FFT/IFFT Based on Mixed Radix in VDSL2 System [D]. Xi’an: Xidian University, 2009.)。

高速64点FFT芯片设计技术引言FFT(快速傅里叶变换)广泛应用于现代数字信号处理的各个领域，如雷达信号处理、卫星通信、无线通信等，而专用FFT处理芯片已成为其中的关键部件之一，对系统性能影响较大。

本文针对64点FFT处理器，探讨和研究了采用标准CMOS 数字工艺库研制FFT处理ASIC(专用集成电路)芯片的若干问题，成果可引伸到更大点数的FFT处理芯片的设计中。

本文介绍了按照固定几何结构FFT算法，采用并行及流水线结构的FFT处理器的原理与电路实现。

FFT处理器主要包括I／O缓存、数据缓存、旋转因子存储器、蝶形运算单元、地址产生器、I／O控制器和系统控制器等模块。

内部数据采用IEEE754标准的单精度浮点格式，实现高精度数据处理。

为进一步提高系统数据吞吐率，FFT处理器采用双I／O缓存，可同步进行数据变换和I／O操作。

1 FFT原理及运算流图的改进DFT(离散傅里叶变换)满足以下关系式：式中：序列x(n)及X（k）均是复数表示。

Cooly和Tukey提出的的FFT算法利用系数WknN的对称性和周期性，大大减小了DFT的运算量。

G(k)仪包含x(n)中偶数点序列，而H(k)仅包含x(n)中奇数点序列，考虑G(k)、H(k)的周期性，得到：经典FFT运算流图的缺点是每级蝶形运算数据寻址方式都不同，FFT处理器寻址电路设计复杂。

本文采用了一种固定几何结构的FFT运算方法，每级运算采用相同寻址电路，简化了电路设计。

下面以16点FFT运算为例，分析固定几何结构FFT运算流图。

如图1所示，固定几何结构的FFT运算流图中，每级蝶形运算寻址结构相同，序列中每相隔N／2的两个数据送入一个蝶形运算单元进行处理，输出结果顺序排列。

由于该流图数据处理具有倒序的特点，所以旋转因子也采用倒序输入，并且，得到的变换结果也为倒序排列。

本文采用C语言对该流图算法进行模拟，证明该结构正确可行。

2 FFT处理器的结构与模块划分FFT处理器主要包括蝶形运算单元、数据缓存、I／O缓存、地址生成器、运算控制器，I／O控制器。

基于FPGA的64点FFT处理器设计的开题报告一、选题背景在数字信号处理中，FFT（快速傅里叶变换）是一种重要的算法，广泛应用于语音、图像、音频、雷达信号处理等领域。

FFT算法可以将时域信号转换为频域信号，以方便信号分析和处理。

随着科技的不断进步，现代信号处理要求FFT算法具有更高的运算速度和更低的能耗。

而FPGA（现场可编程门阵列）作为一种现代的可编程逻辑器件，可以充分利用硬件并行运算和高速存储器等优势，满足FFT 处理的高性能、低能耗需求，因此倍受研究者关注。

本课题旨在设计一种基于FPGA的64点FFT处理器，以满足应用于实际嵌入式系统的需求。

二、研究内容与意义本课题将从以下几个方面展开：1.基于蝶形运算的FFT算法优化设计，实现更高效的计算过程。

2.采用流水线技术，实现FFT处理器的并行计算，提高计算速度。

3.设计合适的存储器结构，提高数据读写速度，减少能耗。

4.利用FPGA资源和可编程能力，实现算法的灵活性和可扩展性。

本研究将能够在FPGA上实现高效的64点FFT处理器，并为实际应用提供了一种可靠的解决方案。

同时，该研究对于FFT算法优化、FPGA应用领域的研究，具有一定的学术研究价值与实际应用意义。

三、研究方法1.调研相关研究成果，深入了解FFT算法和FPGA相关知识。

2.采用Verilog语言，设计基于64点FFT算法的FFT处理器，并进行仿真调试。

3.对设计的不足之处进行改进，如加入流水线技术等。

4.在FPGA开发板上进行验证实验，对实验结果进行评估，探究算法的速度和能耗等性能指标。

四、拟解决的关键问题1.如何实现FFT算法的优化，提高计算效率和精度？2.如何设计合适的存储器结构，提高数据访问速度，减少能耗？3.例如如何采用流水线技术实现并行计算，并充分利用FPGA资源？五、预期目标1.成功设计一种基于FPGA的64点FFT处理器，并在实验中验证其功能。

2.对设计的处理器进行性能评估，提高其处理速度和性能指标。

基于FPGA的FFT处理器的设计郭宇，王建华（江苏科技大学电子信息学院，江苏镇江，212003） 摘要：本文主要研究基于FPGA的数据处理系统，内部包含一个1024点的FFT处理单元。

FFT部分采用基四算法，五级级联处理，并通过CORDIC流水线结构使硬件实现较慢的复乘运算转化为移位和加减运算。

双端口RAM、只读ROM全部内置在FPGA芯片内部，使整个系统的数据交换和处理速度得以很大提高，合理地协调了资源和速度之间相互制约问题。

关键词：快速傅里叶变换（FFT）；蝶型运算；CORDIC；FPGA中图分类号：TN76 文献标识码：ADesign of FFT Processor Based on FPGAGUO YU ,WANG Jian-hua(College of Electrical and Information , Jiangsu University ofScience and Technology ,zhenjiang ,jiangsu 212003,China)Abstract:This thesis mainly studies data acquisition, controlling and FFT based on FPGA. FFT adopts the algorithm of radix-4, 5-step cascading processing. The whole system uses pipeline pattern, practicality. The multiplication unit is changed to shift and addition unit by CORDIC pipeline structure which is easier than multiplication for the hardware. Dual-port RAM and ROM are built inside the system. These methods accelerate the operating and reasonably resolve the mutually restriction of resources and speed.Key words:fast fourier transform(FFT);butterfly processing; CORDIC；FPGA1.引言数字信号处理领域中FFT作为时域和频域转换的基本运算，是数字谱分析的必要前提，超级的运算能力在雷达处理、高速图像处理等的应用上极为广泛，而实时系统对FFT的运算速度要求更高。

基于FPGA 的FFT 处理器的设计与实现胡其明,曹闹昌,刘东斌(空军工程大学工程学院　陕西西安　710038)摘　要:对FFT 处理器的实现算法2频域抽取基4算法做了介绍。

介绍一种以FP GA 作为设计载体,设计和实现一套集成于FP GA 内部的FF T 处理器的方法和设计过程。

FF T 处理器的硬件试验结果表明该处理器的运算结果正确,并且具有较高运算速度。

该方法具有设计简单灵活,体积小等优点,可用于雷达处理、高速图像处理和数字通信等应用场合。

关键词:FF T ;FP GA ;基4算法,硬件实验结果中图分类号:TP36811 文献标识码:B 文章编号:10042373X (2008)022074203Design and R ealization of FFT Processor B ased on FPG AHU Qiming ,CAO Naochang ,L IU Dongbin(Engineering College ,Air Force Engineering University ,Xi ′an ,710038,China )Abstract :The paper firstly introduces the arithmetic of FFT processor 2Radix 24,and introduces the method and process of design and realizes a FFT processor ,which is integrated in FP GA chip ,regarding FP GA as design carrier.The result of hard 2ware test of FFT processor shows that the processor works well and has high speed.The design has the advantages of simple ness ,agility and small bulk.It can be used in many application situations ,such as radar signals process ,high speed image process and digital communication.K eywords :FF T ;FP GA ;radix 24;algorithm ;hardware experiment result收稿日期:2007208223 数字信号处理领域中FF T 作为时域和频域转换的基本运算,是数字谱分析的必要前提。

基于FPGA的FFT处理器1 引言随着数字技术的快速发展，数字信号处理已深入到各个学科领域。

在数字信号处理中，许多算法如相关、滤波、谱估计、卷积等都可通过转化为离散傅立叶变换(DFT)实现，从而为离散信号分析从理论上提供了变换工具。

但DFT计算量大，实现困难。

快速傅立叶(FFT)的提出，大大减少了计算量，从根本上改变了傅立叶变换的地位，成为数字信号处理中的核心技术之一，广泛应用于雷达、观测、跟踪、高速图像处理、保密无线通信和数字通信等领域。

目前，硬件实现FFT算法的方案主要有：通用数字信号处理器(DSP)、FFT专用器件和现场可编程门阵列(FPGA)。

DSP具有纯软件实现的灵活性，适用于流程复杂的算法，如通信系统中信道的编译码、QAM映射等算法。

DSP完成FFT运算需占用大量DSP的运算时间，使整个系统的数据吞吐率降低，同时也无法发挥DSP软件实现的灵活性。

采用FFT专用器件，速度虽能够达到要求。

但其外围电路复杂，可扩展性差，成本昂贵。

随着FPGA发展，其资源丰富，易于组织流水和并行结构，将FFT实时性要求与FPGA器件设计的灵活性相结合，实现并行算法与硬件结构的优化配置，不仅可以提高处理速度，并且具有灵活性高。

开发费用低、开发周期短、升级简单的特点。

针对某OFDM系统中FFT运算的实际需要，提出了基于FPGA的设计来实现FFT算法，并以16位长数据，64点FFT为例，在QuartusⅡ软件上通过综合和仿真。

2 FFT原理及算法结构FFT是离散傅立叶变换(DFT)的快速算法。

对于N点离散的有限长时问序列x(n)，其傅里叶变换为：完成N点的DFT需要N2次复数乘法和N(N-1)次复数加法。

点数大时，计算量也大，所以难以实现信号的实时处理。

FFT的基本思想是利用旋转因子WN的周期性、对称性、特殊性以及周期N的可互换性，将长度为N点的序列DFT运算逐次分为较短序列的DFT运算，合并相同项，大大减少了计算量。

基于FPGA 的FFT 处理器设计1. 引言随着数字技术的快速发展，数字信号处理已深入到各个领域。

在数字信号处理中，许多算法如相关、滤波、谱估计、卷积等都可通过转化为离散傅立叶变换( DFT )实现，从而为离散信号分析从理论上提供了变换工具。

但DFT 计算量大，实现困难。

快速傅立叶( FFT )的提出，大大减少了计算量，从根本上改变了傅立叶变换的地位，成为数字信号处理中的核心技术之一，广泛应用于雷达、观测、跟踪、高速图像处理、保密无线通信和数字通信等领域。

目前，硬件实现FFT 算法的方案主要有：通用数字信号处理器( DSP )、FFT 专用器件和现场可编程门阵列( FPCA )。

DSP 具有纯软件实现的灵活性，适用于流程复杂的算法，如通信系统中信道的编译码、QA M 映射等算法。

DSP 完成FFT 运算需占用大量DSP 的运算时间，使整个系统的数据吞吐率降低，同时也无法发挥DSP 软件实现的灵活性。

采用FFT 专用器件，速度虽能够达到要求，但其外围电路复杂，可扩展性差，成本昂贵。

随着FPGA 发展，其资源丰富，易于组织流水和并行结构，将FFT 实时性要求与FPGA 器件设计的灵活性相结合，实现并行算法与硬件结构的优化配置，不仅可以提高处理速度，并且具有灵活性高，开发费用低、开发周期短、升级简单的特点。

针对某OFDM 系统中F FT 运算的实际需要，提出了基于FPGA 的设计来实现FFT 算法，并以16 位长数据，64点FFT 为例，在QuartusⅡ软件上通过综合和仿真。

2. FFT原理及算法结构FFT 是离散傅立叶变换( DFT )的快速算法。

对于N 点离散的有限长时间序列x(n)，其傅里叶变换为：完成N 点的DFT 需要N2 次复数乘法和N(N-1) 次复数加法。

点数大时，计算量也大，所以难以实现信号的实时处理。

FFT 的基本思想是利用旋转因子WN 的周期性、对称性、特殊性以及剧期N 的可互换性，将长度为N 点的序列DFT 运算逐次分为较短序列的DFT 运算，合并相同项，大大减少了计算量。

基于FPGA的可扩展高速FFT处理器的设计与实现来源：电讯技术作者：刘晓明时间：2007-07-12 发布人:卢春妙本文提出了基于FPGA实现傅里叶变换点数可灵活扩展的流水线FFT处理器的结构设计以及各功能模块的算法实现，包括高组合数FFT算法的流水线实现结构、级间混序读/写RAM 地址规律、短点数FFT阵列处理结构以及补码实现CORDIC算法的流水线结构等。

利用FPGA 实现的各功能模块组装了64点FFT处理器。

从其计算性能可知，在输入数据速率为20 MHz 时，利用此结构实现的FFT处理器计算1024点FFT的运算时间约为52μs。

一、引言DFT(离散傅里叶变换)作为将信号从时域转换到频域的基本运算，在各种数字信号处理中起着核心作用，其快速算法FFT(快速傅里叶变换)在无线通信、语音识别、图像处理和频谱分析等领域有着广泛的应用。

用大规模集成电路FPGA(现场可编程门阵列)来实现FFT算法时，需要重点考虑的不再是算法运算量，而是算法的复杂性、规整性和模块化，因为算法的简单性和规整性将更适合大规模集成，更方便于版图设计，而算法的模块化更有利于FFT 处理器的灵活扩展。

组合数FFT算法和CORDIC(坐标旋转数字计算机)算法结合起来，在计算长点数、可扩展FFT时具有较大的优越性［1，2］。

而面向高速、大容量数据流的FFT的实时处理，可以通过VLSI(超大规模集成电路)器件的并行处理或多级流水线处理等来达到。

特别是多级流水线处理的FFT结构使得基于FPGA器件的FFT处理器完成不同点数的FFT计算时可以通过增减模块级数很容易地实现。

二、组合数N=r1r2点混合基FFT原理计算N点DFT：式中k=0，1，…，N-1。

若N=r1r2的组合数，可将n(n＜N)表示为式(2)的意义在于，计算组合数N=r1r2点DFT，等价于先求出r 2组r 1点的DFT，其结果经过对应旋转因子的相位旋转后，再计算r1组r2点的DFT。

基于FPGA的FFT高速运算器设计2009-11-15 18:40出处：中华电子网作者：仪器仪表学报【我要评论】[导读]本文依据基4FFT算法的基本原理，基于可编程逻辑器件FPGA通过硬件语言(VHDL)设计1024点基4FFT高速运算器，以满足高速数据处理要求。

1、引言在高速数字处理领域，快速傅立叶变换(FFT)一直是人们研究的重点。

硬件实现FFT算法的器件主要有：通用的数字处理器(DSP)芯片、专用的FFT芯片以及可编程逻辑器件FPGA。

FPGA是在专用ASIC的基础上发展出来的，它克服了专用ASIC不够灵活的缺点。

目前，90nm 的FPGA已经上市，其容量已经跨过了百万门级，不仅可以解决电子系统小型化、低功耗、高可靠性等问题，而且其开发周期短、开发软件投入少、芯片价格不断降低，这些因素促使FPGA越来越多地取代了ASIC甚至DSP、单片机的市场，成为解决系统级设计的重要选择方案之一。

本文依据基4FFT算法的基本原理，基于可编程逻辑器件FPGA通过硬件语言(VHDL)设计1024点基4FFT高速运算器，以满足高速数据处理要求。

2、基4FFT算法分析及实现方法FFT的算法主要有基2FFT算法、基4FFT算法、混合基FFT算法等。

在计算量上基4算法比基2算法减少约20%的运算量，从硬件实现上基4算法比混合基算法要容易。

FFT的算法有按时间抽取(DIT)和按频率抽取(DIF)两种形式，但两者并没有实质上的区别[1]。

所以，在本设计中采用基4FFT算法为对象的运算器设计。

基4碟形单元结构是基4FFT算法的核心部分，它将决定基4FFT控制器的内部结构。

基4碟形单元如图1所示。

在蝶形单元中，只有本蝶形单元的输入数据参与运算，不涉及其他数据，且运算结束数据点数也不变。

鉴于这个特点，在FPGA设计时，将每级蝶形单元的计算输出结果仍然存储在原输入数据的相同RAM单元中，这一点被称为“同址运算”。

从图1可以看出，四个数据(复数数据)并行输入，运算结果也是四个数据(复数数据)并行输出。

64点FFT硬件算法实现本文对FFT算法中的截位问题进行分析，并给出了硬件实现的基本流程。

1.截位分析以前的FFT算法中奇数级（1,3,5）蝶形运算输入数据均为12bit，输出数据均为13bit，只进行加减运算未进行截位；而偶数级（2,4,6）蝶形运算输入数据均为13bit，输出数据均为12bit，其中第二级和第四级均需乘以了12bit的旋转因子，并进行了11bit的截位，第六级截了1bit（最后一级的旋转因子是1）。

奇数级蝶形运算偶数级蝶形运算图—1 64点FFT各级截位方式下面对每级不同bit的截位进行比较分析（输入均为12bit）图—2 SNR 随每级增加位数的变化注：第二级，第四级和第六级的截位数从14.14.4~10.10.0~9.9.-1递减，从图中可以看出当第二级，第四级和第六级的截位数小于10.10.0时，即输出的比特数大于15bit 时，信噪比变化平缓。

图—3 输出为12bit 时SNR 随第二级增加位数的变化注：输出都是12bit 第二级的截位数从14bit 到9bit ，第四级截位数均为11bit ，第六级截位数从-2到3，从图中可以看出输出比特一定且第四级截位数不变的情况下，当第二级截位数小于等于10，第六级截位数大于等于2的时候，信噪比变化平缓。

每级增加位数S N R第二级增加位数S N R图—4 输出为12bit 时SNR 随第四级增加位数的变化注：输出都是12bit 第四级的截位数从14bit 到9bit ，第二级截位数均为11bit ，第六级截位数从-2到3，从图中可以看出输出比特一定且第二级截位数不变的情况下，当第四级截位数小于等于10，第六级截位数大于等于2的时候，信噪比变化平缓。

图—5 SNR 随第二级增加位数的变化注：第四级截位11bit ，第六级截位1bit ，只改变第二级的截位数，从图中可以看出，当x>=5，即第二级的截位数小于等于10时，系统的信噪比变换缓慢，因此我们可以选择此临界值。

基于FPGA的FFT设计与实现Abstract: In the design of FFT based on FPGA, in order to increase FFT processing speed, this paper brings forward a new method that use shift-register to store twiddle-factors, and validate on Stratix series FPGA of Altera company. Experimentation result indicates that this method can improve FFT processing speed of FFT observably than the method of store twiddle-factors with ROM generally, and can satisfy FFT real-time processing request better.Key words: FFT; FPGA; shift-register; twiddle-factors摘要:在基于FPGA的FFT设计中,为了提高速度,提出了用移位寄存器存储旋转因子的方法,并且在Altera公司的Stratix系列的FPGA上做了验证。

实验结果表明,该方法和普遍采用ROM做旋转因子存储器的方法相比,大幅提高了FFF的处理速度,能够更好地满足了FFT实时处理的要求。

关键词：FFT；FPGA；蝶型运算；旋转因子一、前言：FPGA是大规模可编程逻辑器件的另一大类PLD器件。

FFT运算在OFDM 系统中起调制和解调的作用。

针对OFDM系统中FF T运算的要求，研究了一种易于FPGA实现的FFT处理器的硬件结构。

接收单元采用乒乓RAM结构，扩大了数据吞吐量。

中间数据缓存单元采用双口RAM，减少了访问RAM的时钟消耗。

基于FPGA的FFT/IFFT处理器的实现浙江大学仪器系数字技术与仪器研究所（杭州310027）孙阳李然摘要：提出一种利用并行算法来实现FFT（快速傅里叶变换）及其逆变换IFFF（快速傅里叶逆变换）的设计方法。

该处理器可由用户动态配置成64、256、1024点复数FFT或其逆变换IFFT。

关键词：FPGA，FFT，IFFT1 引言高速实时数字信号处理对系统性能要求很高，因此，几乎所有的通用DSP都难以实现这一要求。

可编程逻辑器件允许设计人员利用并行处理技术实现高速信号处理算法，并且只需单个器件就能实现期望的性能。

在数据通信这样的应用中，常常需要进行高速、大规模的FFT及其逆变换IFFT运算。

当通用的DSP无法达到速度要求时，唯一的选择是增加处理器的数目，或采用定制门阵列产品。

现在，随着微电子技术的发展，采用现场可编程门阵列（FPGA）进行数字信号处理发展迅速。

采用现场可编程器件不仅加速了产品上市时间，还可满足现在和下一代便携式设计所需要的成本、性能、尺寸等方面的要求，并提供系统级支持。

本文研究了基于FPGA的FFT及其逆变换IFFT处理器的硬件电路实现方法。

在系统时钟频率为100MHz时，1024点复位FFT的计算时间只需要10μs左右。

2 基4 FFT/IFFT算法序列x(n),n=0,...,N-1的离散傅里叶变换为：这说明IFFT可以由FFT求出。

因此，FFT和IFFT处理器可以用统一的硬件结构来实现。

对于FFT，设序列x(n)的长度为N=4p(p为整数)，则基4频率抽取蝶菜运算单元方程为：3 FFT/IFFT的硬件实现我们采用Xilinx公司的Virtex-II系列FPGA来实现FFT/IFFT 处理器。

3.1 蝶形运算单元结构基4频率抽取FFT计算一共包括了log4(N)级运算，其中，在每一级中包含了N/4个基4蝶形运算，蝶形运算器如图1所示。

Virtex-II系列FPGA有内嵌18bit×18bit补码乘法器以及大容量用户可配置RAM，非常适合做大规模算术运算。

基于FPGA的FFT处理器设计任健;高晓蓉【摘要】在火车车轮的振动式擦伤检测系统中,经常需要对振动信号进行频谱分析,为实现振动频谱信号的及时输出,在此根据FFT算法中的一种变形运算流图,提出一种基于FPGA的FFT流水线结构,总结了利用流水线结构实现这种FFT运算流图的数据存取规律,并按此结构利用Verilog语言设计了64点数据的6级流水线运算结构.利用振动信号测试数据进行仿真实验,结果表明该设计方法的正确可靠.【期刊名称】《现代电子技术》【年(卷),期】2010(033)024【总页数】4页(P142-144,147)【关键词】FFT算法;FPGA;流水线结构;蝶形运算;流图【作者】任健;高晓蓉【作者单位】西南交通大学,物理科学与技术学院,四川,成都,610031;西南交通大学,物理科学与技术学院,四川,成都,610031【正文语种】中文【中图分类】TN911.72-34在火车车轮的振动式擦伤检测系统中，根据车轮与钢轨接触时产生的振动信号可以对车轮状态进行检测。

有擦伤的车轮与钢轨接触时产生的振动信号具有特定的频谱特征[1-2]，因此若将检测设备采集到的信号变换到频域进行分析，将有助于判断车轮是否有擦伤。

为实现信号的快速变换，采用FPGA实现的FFT处理器对信号进行变换。

FFT是离散傅里叶变换(DFT)的一种快速算法，当DFT的计算点数N很大时，FFT 算法相对于直接计算DFT时的运算量会显著减少，因此其在数字信号处理领域有着广泛的应用，大大推动了数字信号处理技术的发展[3]。

FFT算法可以通过计算机软件、DSP处理器、FPGA器件和ASIC等方式来实现，目前对各种方式的分析和比较，相关文献[4-6]已有介绍。

在此提出的FFT算法，其FPGA结构具有模块化、流水线、可扩展的特点，因此用它可以提高计算速度，在芯片容量允许的情况下进行多点数、多级流水线结构的FFT运算。

1 算法原理及分析1.1 FFT算法原理由DFT的定义可知，如果信号为x(n)，则对x(n)做N点DFT的计算表达式为：(1)式中：FFT算法即是对式(1)的一种快速算法。

信息与通信工程学院综合实验（1）设计报告基于FPGA的FFT设计与实现学号：S309080034专业：光学工程学生姓名：彭欢任课教师：钟志副教授2010年7月基于FPGA的FFT的设计与实现彭欢信息与通信工程学院摘要：本文主要研究如何利用FPGA实现FFT处理器，包括算法选取、算法验证、系统结构设计、各个模块设计、FPGA实现和测试整个流程。

设计采用基-2按时间抽取算法，以XILINX公司提供的ISE6.1为软件平台，利用V erilog HDL描述的方式实现了512点16bist复数块浮点结构的FFT系统，并以FPGA芯片场V irte x II XC2V1000为硬件平台，进行了仿真、综合等工作。

仿真结果表明其计算结果达到了一定的精度，运算速度可以满足一般实时信号处理的要求。

关键词：快速傅立叶变换，现场可编程门阵列，块浮点，V erilog HDL1引言目前，FFT己广泛应用在频谱分析、匹配滤波、数字通信、图像处理、语音识别、雷达处理、遥感遥测、地质勘探和无线保密通讯等众多领域。

在不同应用场合，需要不同性能要求的FFT处理器。

在很多应用领域都要求FFT处理器具有高速度、高精度、大容量和实时处理的性能。

因此，如何更快速、更灵活地实现FFT变得越来越重要。

在过去很长一段时间，DSP处理器是DSP应用系统核心器件的唯一选择。

尽管DSP处理器具有通过软件设计能适用于实现不同功能的灵活性，但面对当今速度变化的DSP应用市场，特别是面对现代通信技术的发展，DSP处理器在处理速度上早已力不从心。

与DSP相比，FPGA实现FFT的主要优越性有：(1)、FPGA实现数字信号处理最显著的特点就是高速性能好。

FPGA有内置的高速乘法器和加法器，尤其适合于乘法和累加等重复性的DSP任务。

(2)、FPGA的存储量大。

DSP内部一般没有大容量的存储器，但是FTF实时处理运算需要存储大量的数据，只能外接存储器，这样往往会使运算速度下降，同时电路也会更复杂和不稳定。

基于FPGA的FFT处理器设计杨伟才;侯洁;刘玉坤;包莉娜;郭立炜【摘要】针对现实生活中各种测试系统的需求,开发设计了能够分析多种系统特性的按时间抽取基2 FFT处理器,在传统的FFT算法以及硬件单元分析的基础上,提出了一种新型蝶形运算方法,通过减少乘法运算以及采用查表法,加快系统运算速度.设计中采用8位有符号数完成256点数据处理,提出新的数据处理方式,避免了浮点运算为数据处理造成的困难,采用自顶向下的设计方法,用Verilog HDL编程实现各模块功能,并详细介绍了数据从外部读取后,经由存储到数据处理再到输出的完整过程,最后在FPGA上实现设计功能.【期刊名称】《河北工业科技》【年(卷),期】2013(030)002【总页数】5页(P112-116)【关键词】现场可编程门阵列;快速傅里叶变换;硬件描述语言;基2蝶形算法【作者】杨伟才;侯洁;刘玉坤;包莉娜;郭立炜【作者单位】河北科技大学信息科学与工程学院,河北石家庄050018;河北科技大学信息科学与工程学院,河北石家庄050018;河北科技大学信息科学与工程学院,河北石家庄050018;河北科技大学信息科学与工程学院,河北石家庄050018;河北科技大学信息科学与工程学院,河北石家庄050018【正文语种】中文【中图分类】TN911高级信号处理算法和硬件的结合广泛应用于现实生活中的各个领域[1-3]。

1965年，COOLEY和TUKEY发表了一种计算DFT的快速算法，使得DFT的计算量大为减少，从而使DFT得以广泛应用。

利用FPGA灵活的实现方案，产品的低功耗、丰富的逻辑单元、大量的输入输出引脚、内置大量的RAM和乘法器资源等特点，在FFT算法的基础上提出了基于FPGA硬件平台的FFT处理器设计[4-8]，设计中采用8位有符号数完成256点数据处理，通过减少乘法运算以及采用查表法，加快系统运算速度，提出的数据处理方式避免了浮点运算为数据处理造成的困难，完成了信号处理算法与硬件结合的高速处理方案。

基于FPGA的高速定点FFT算法的设计方案基于FPGA的高速定点FFT算法的设计方案类别：电子综合引言快速傅里叶变换(FFT)作为计算和分析工具，在众多学科领域(如信号处理、图像处理、生物信息学、计算物理、应用数学等)有着广泛的应用。

在高速数字信号处理领域，如雷达信号处理，FFT的处理速度往往是整个系统设计性能的关键所在。

针对高速实时信号处理的要求，软件实现方法显然满足不了其需要。

近年来现场可编程门阵列(FPGA)以其高性能、高灵活性、友好的开发环境、在线可编程等特点，使得基于FPGA的设计可以满足实时数字信号处理的要求，在市场竞争中具有很大的优势。

在FFT算法中，数据的宽度通常都是固定的宽度。

然而，在FFT的运算过程中，特别是乘法运算中，运算的结果将不可避免地带来误差。

因此，为了保证结果的准确性，采用定点分析是非常必要的。

1 FFT算法原理FFT算法的基本思想就是利用权函数的周期性、对称性、特殊性及周期N的可互换性，将较长序列的DFT运算逐次分解为较短序列的DFT运算。

针对N=2的整数次幂，FFT算法有基-2算法、基-4算法、实因子算法和分裂基算法等。

这里，从处理速度和占用资源的角度考虑，选用基-4按时间抽取FFT算法 (DIT)。

对于N=4γ，基-4 DIT具有log4N=γ次迭代运算，每次迭代包含N／4个蝶形单元。

蝶形单元的运算表达式为：其信号流如图1。

式中：A，B，C，D和A′，B′，C′，D′均为复数据；W=e-j2π/N。

进行1次蝶形运算共需3次复乘和8次复加运算。

N=64 点的基-4DIT信号流其输入数据序列是按自然顺序排列的，输出结果需经过整序。

64点数据只需进行3次迭代运算，每次迭代运算含有N／4=16个蝶形单元。

2 FFT算法的硬件实现2．1 流水线方式FFT算法的实现为了提高FFT工作频率和节省FPGA资源，采用3级流水线结构实现64点的FFT运算。

流水线处理器的结构如图2所示。

基于FPGA的64点FFT处理器设计0 引言DFT 作为DSP 领域中时域和频域转换的基本运算，存在运算量太大的缺点，导致其应用受到局限。

DFT 快速算法FFT 的提出，简化了DFT 的运算过程，使其在实时信号处理领域中得到广泛应用。

FFT 实现的方法包括软件实现和硬件实现两种。

采用软件实现FFT 的方法存在计算慢，实现过程复杂等缺点，所以目前比较流行的方式是采用硬件实现FFT。

硬件实现的具体方法可以分为ASIC 方法、FPGA 方法、DSP 方法和通用处理机方法等。

FPGA 是20 世纪80 年代中期出现的一种新的电子设计自动化技术，具有集成度高，逻辑实现能力强，设计灵活等优势。

在FPGA 上实现数字信号处理，即用纯数字逻辑进行DSP 模块设计，为高速数字信号处理算法提供了实现途径。

在此，采用FPGA 方法设计64 点FFT 处理器。

现有的FFT 模块可以对多点数据进行运算，但是存在运算周期长。

结构复杂，硬件资源耗费大等缺陷。

采用64点FFT 可以通过优化结构来快速处理多点数数据。

目前设计的64 点FFT 处理器主要采用以专用处理单元取代常规FFT 处理单元的方法，或者按照固定几何结构设计FFT 处理器的方法。

这里所介绍的64 点FFT 处理器是在固定几何结构设计方法的基础上加以改进，将输入的64 点数据均匀分成8 组，并行输入给FFT 运算单元，进行FFT 运算。

通过对蝶形运算单元进行优化设计，所设计的64 点FFT 处理器模块较之以往的FFT 模块，节省了硬件资源，提高了运算效率。

通过ModelSim 仿真实验证明，在外部工作时钟频率为40 MHz 下，对随机生成的序列进行64 点FFT 运算处理，运算时间为10μs，缩短了现有FFT 模块的运算时间。

1 按频率抽取的基――4FFT算法原理对于序列长度为N(N 为2 的整数次幂)的FFT 算法主要有基-2 FFT 和基-4 FFT 两种。

计算一次基-2FFT 需要二次复乘和。