基于FPGA的高速定点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运算，合并相同项，大大减少了计算量。

基于FPGA的高速定点FFT算法的实现迅速傅里叶变换(FFT)作为计算和分析工具，在众多学科领域(如信号处理、图像处理、生物信息学、计算物理、应用数学等)有着广泛的应用。

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

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

近年来现场可编程门阵列()以其高性能、高灵便性、友好的开发环境、在线可编程等特点，使得基于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算法的实现第1页共4页。

用FPGA实现FFT算法引言DFT(Discrete Fourier Transformation)是数字信号分析与处理如图形、语音及图像等领域的重要变换工具，直接计算DFT的计算量与变换区间长度N的平方成正比。

当N较大时，因计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。

快速傅立叶变换(Fast Fourier Transformation，简称FFT)使DFT运算效率提高1～2个数量级。

其原因是当N较大时，对DFT进行了基4和基2分解运算。

FFT算法除了必需的数据存储器ram和旋转因子rom外，仍需较复杂的运算和控制电路单元，即使现在,实现长点数的FFT仍然是很困难。

本文提出的FFT 实现算法是基于FPGA之上的，算法完成对一个序列的FFT计算，完全由脉冲触发，外部只输入一脉冲头和输入数据，便可以得到该脉冲头作为起始标志的N点FFT输出结果。

由于使用了双ram，该算法是流型(Pipelined)的，可以连续计算N点复数输入FFT，即输入可以是分段N点连续复数数据流。

采用DIF(Decimation In Frequency)-FFT和DIT(Decimation In Time)-FFT对于算法本身来说是无关紧要的，因为两种情况下只是存储器的读写地址有所变动而已，不影响算法的结构和流程，也不会对算法复杂度有何影响。

算法实现的可以是基2/4混合基FFT，也可以是纯基4FFT和纯基2FFT运算。

傅立叶变换和逆变换对于变换长度为N的序列x(n)其傅立叶变换可以表示如下：N nkX(k)=DFT[x(n)] =Σ x(n)Wn=0式（１）其中，W=exp(-2π/N)。

当点数N较大时，必须对式(1)进行基4/基2分解，以短点数实现长点数的变换。

而IDFT的实现在DFT的基础上就显得较为简单了：式（２）由式(2)可以看出，在FFT运算模块的基础上，只需将输入序列进行取共轭后再进行FFT运算，输出结果再取一次共轭便实现了对输入序列的IDFT运算，因子1/N对于不同的数据表示格式具体实现时的处理方式是不一样的。

基于FPGA的高速基4FFT设计与实现王金川;高强;高光辉【摘要】针对实时高速信号处理要求,设计并实现了一种基于FPGA的高速流水线结构的基4FFT处理器。

根据各种不同基算法的运算量、硬件面积和控制复杂度,选定按时间抽取的基4算法,同时采用单路延时反馈(Single-path Delay Feedback,SDF)流水线结构,提高了处理速度。

通过Verilog HDL语言进行模块化描述和验证,结果表明,该FFT处理器具有较高性能。

% A high-speed FFT processor based on FPGA is designed and realized to meet the demand of real time and high speed signal processing. Based on the analysis of the FFT algorithm, hardware area and complexity of control, the proposed processor adopts radix-4 DIT algorithm and a Single-path Delay Feedback (SDF) pipelined architecture, which speeds up the signal processing. The entire design is described, verified and implemented in Verilog HDL language. The results show that this FFT processor has higher performance.【期刊名称】《物联网技术》【年(卷),期】2012(000)007【总页数】4页(P38-40,44)【关键词】FFT;流水线;基4;蝶形运算【作者】王金川;高强;高光辉【作者单位】电子科技大学微电子与固体电子学院,四川成都 610054;电子科技大学微电子与固体电子学院,四川成都 610054;电子科技大学微电子与固体电子学院,四川成都 610054【正文语种】中文【中图分类】TN791快速傅里叶变换(Fast Fourier Transformation，FFT)作为时域和频域转化的基本运算，是数字谱分析的必要前提。

基于FPGA的FFT算法的实现摘要：信号处理在电力系统工作中应用广泛，其中快速傅里叶变换（FFT）在信号处理中是一种采用较多的方式。

现提出一种基于FPGA的快速傅里叶变化算法的实现方式，同时给出基于Modelsim的仿真结果与Matlab的计算结果进行对比。

关键词：FFT；FPGA；信号处理0 引言FFT是DFT的一种快速计算方式，能够将DFT运算的计算效率提高1~2个数量级[1]。

传统的快速傅里叶变化多采用单片机或者DSP进行实现，而单片机都采用循环的串行计算，当碰到高频信号需要较高的采样频率时，其计算结果的实时性无法得到保证。

FPGA（现场可编程门阵列）其并行运算的特性，能够进一步提高FFT计算的速度，拥有较高的实时性。

本文提出了一种基于FPGA的256点的FFT算法的实现。

1 FFT算法的原理对于一个N点有限长度的序列的，其DFT计算方式为：完成一次N点序列的DFT计算需要N2次复数乘法即N(N-1)次复数加法[2]，最终需要经历4N2次实数乘法，2N(2N-1)次实数加法才能得到其计算结果，其计算量十分庞大。

考虑到旋转因子的对称性和周期性，有：若N=2M,M为整数，则可将N点序列按照N的奇偶性分为N/2长度的两个序列：根据旋转因子的特性，将上式改写为：如图1-1所示的蝶形运算形式：图1-12 256点基2DIT的FPGA实现2.1 FFT运算模块的结构FFT的设计采用并行迭代的结构，计算完上一级的蝶形运算后将计算结储存在RAM中，作为下一级蝶形运算的输入，继续调用蝶形运算模块，最总完成FFT的计算。

对于256点FFT需要进行8级蝶形运算，每级需要进行128次蝶形运算。

这里采用32位的定点数运算，在节约逻辑门资源的同时也保证了计算的精度。

FFT模块分为数据储存模块，蝶形运算模块，时钟模块，旋转因子储存模块，其整体结构如图2-1所示：图2-1蝶形运算模块的结构图如2-2：图2-22.2 FFT模块的工作过程1)当复位信rst_n（低电平有效）为高电平，发出一个启动信号FFT_START后，FFT模块开始工作，将输入的数据转存到RAM中去。

基于FPGA的高速流水线FFT算法实现樊光辉，许茹，王德清(厦门大学通信工程系水声通信与海洋信息技术教育部重点实验室，福建省厦门市361005)0 引言有限长序列的DFT(离散傅里叶变换)特点是能够将频域的数据离散化成有限长的序列。

但由于DYT本身运算量相当大，限制了它的实际应用。

FFT(快速傅里叶变换)算法是作为DFT的快速算法提出，它将长序列的DFT分解为短序列的DFT，大大减少了运算量，使得DFT算法在频谱分析、滤波器设计等领域得到了广泛的应用。

FPGA(现场可编程门阵列)是一种具有大规模可编程门阵列的器件，不仅具有专用集成电路(ASIC)快速的特点，更具有很好的系统实现的灵活性。

FPGA可通过开发工具实现在线编程。

与CPLD(复杂可编程逻辑器件)相比，FPGA属寄存器丰富型结构，更加适合于完成时序逻辑控制。

因此，FPGA为高速FFT算法的实现提供了一个很好的平台。

1 基4-FFT算法基本原理在FFT各类算法中，基2-FFT算法是最简单的一种，但其运算量与基4-FFT算法相比则大得多，分裂基算法综合了基4和基2算法的特点，虽然具有最少的复乘运算量，但其L蝶形运算控制的复杂性也限制了其在硬件上的实现，因此，本设计采用了基4-FFT 算法结构。

基4-FFT算法的基本运算是4点DFT。

一个4点的DFT运算的表达式为：式(1)对于输出变量进行了二进制倒序，便于在运算过程中进行同址运算，节省了运算过程中所需存储器单元的数量。

按DIT(时间抽取)的1 024点的基4-FFT共需5级蝶形运算，每级从RAM中读取的数据经过蝶形运算后原址存入存储单元准备下一级运算。

算法的第1级为一组N=1 024点的基4蝶形运算，共256个蝶形，每个蝶形的距离为256点；第2级为4组N=256点的基4蝶形运算，每组64个蝶形，每个蝶形的距离为64点。

后3级类推。

这种算法每一级的运算具有相对独立性，每级运算都采用同址运算，因此，本设计只使用了2个1 k×16 bits的RAM单元。

第一章绪论1.1 研究背景在现代通信中，提高频谱利用率一直是人们关注的焦点之一。

近几年来，随着通信业务需求的迅速增长，寻找频谱利用率更高的数字调制方式已成为数字通信系统设计、研究的主要目标之一。

为了实现这个目标，通信系统正采用比以前更加复杂的调制信号。

OFDM(正交频分复用)是一种高效的多载波调制技术，其最大的特点是传输速率高，具有很强的抗码间干扰和信道选择性衰落能力，具有非常高的频谱利用率。

OFDM最初用于高速MODEM、数字移动通信和无线调频信道上的宽带数据传输，随着IEEE802.11a协议和多媒体的发展，数字音频广播(DAB)、地面数字视频广播(DVB-T)和高清晰度电视(HDTV)都应用了OFDM技术。

OFDM利用离散傅立叶反变换/离散傅立叶变换(IDFT/DFT)代替多载波调制和解调，调制解调的核心是快速傅立叶运算单元，在进行蝴蝶运算时，不可避免的要进行大量的乘法运算。

由于FPGA具有强大的并行处理和计算能力，以及丰富的存储资源和逻辑运算资源，因此在FPGA器件上实现OFDM调制解调结构，具有很好的通用性和灵活性。

1.1.1无线通信的发展和现状现代无线通信技术的发展始于本世纪20年代，经历了早期专用移动通信系统的发展，公用移动通信业务的发展，到1978年底，美国贝尔试验室研制成功先进移动电话系统(AMPS)，建成了蜂窝状移动通信网，大大提高了系统容量。

随后投入商用，服务区域在美国逐渐扩大。

其它工业化国家也相继开发出蜂窝式公用移动通信网，这种模拟通信系统被称为第一代移动通信系统。

模拟蜂窝网虽然取得了很大成功，但也暴露了一些问题。

例如，频谱利用率低，移动设备复杂，费用较贵，业务种类受限制以及通话易被窃听等，最主要的问题是其容量已不能满足日益增长的移动用户需求。

解决这些问题的方法是开发新一代数字蜂窝移动通信系统。

数字无线传输的频谱利用率高，可大大提高系统容量。

另外，数字网能提供语音、数据多种业务服务，并与ISDN等兼容。