利用FFT IP Core实现FFT算法

摘要:结合工程实践，介绍了一种利用FFT IP Core实现FFT的方法，设计能同时对两路实数序列进行256点FFT运算，并对转换结果进行求模平方运算，且对数据具有连续处理的能力。设计采用低成本的FPGA实现，具有成本低、性能高、灵活性强、速度快等特点，而且通过工程应用证明了设计是正确可行的。

    由于FFT(快速傅里叶变换)的问世，促进了数字信号处理这门学科的成熟，它可应用于傅里叶变换理论所能涉及的任何领域。FFT传统实现
方法无非是软件(软件编程)和硬件(专用芯片ASIC)两种，FPGA的出现使人们在FFT的实现方面又多了一种选择。FPGA同时具有软件编程的灵活性和ASIC电路的快速性等优点，适合高速数字信号处理。大多数FPGA厂商都提供了可配置的逻辑核(Core)实现各种算法功能，其中包括FFT IP Core(知识产权核)。使用这些资源允许设计师将更多的时间和精力放在改善增加系统功能上，这无疑将大大减少设计风险及缩短开发周期。
    本设计采用了Altera公司的FFT IP Core实现FFT功能，可同时实现两路256点实数数据的FFT转换，并对转换结果进行求模平方运算，设计对数据具有连续处理的能力。FPGA芯片选用的是有史以来成本最低的Altera公司的Cyclone系列的芯片，FFT内核是Altera MegaCore FFT-V2.0.0，整个设计成本低、性能好，已经成功地应用到雷达产品中。

2  算法原理和FFT Core介绍
    设计用到的算法包括同时计算两个实函数的FFT算法和CORDIC算法。
2.1  同时计算两个实函数的FFT算法
    DFT(离散傅里叶变换)的定义为：
 
式(1)中，都假定时间函数x(n)是一个复函数。但是在许多FFT的实际应用中，时间函数往往是实函数。下面介绍的算法可以有效地减少实数序列FFT的计算工作量，从而提高计算速度。该方法可归纳为如下几个步骤：
①函数h(n)和g(n)是两个实函数，n=0，1，…，N-1；
②将其中的一个作为实部而另一个作为虚部，构成复函数z(n)为：
  z(n)=h(n)+jg(n)，  n=0，1，…，N-1；
③计算z(n)的N点DFT得：
 
式中，Zr(k)和Zi(k)分别是Z(k)的实部和虚部；
④从z(k)中分析出H(k)和G(k)：
 
式中，H(k)和G(k)分别是h(n)和g(n)的DFT。
    详细的推导过程参见文献[2]。

2.2 CORDIC算法原理
  CORDIC(The Coordinate Rotational Digital Computer)算法是一种循环迭代算法，其基本思想是用一系列与运算基数相关角度的不断偏摆从而逼近所需旋转的角度。从广义上讲它是一个数值性计算逼近的方法，由于这些固定的角度与计算基数有关，运算只有移位和加减。可用该算法来计算的函数包括乘、除、平方根、正弦、余弦正切、向量旋转(即复数乘法)以及指数运算等。CORDIC的基本原理如下。
    向量x+jy，旋转角度θ到向量x\'+jy\'，假设的方向用δ表示，旋转的角度为θi，并且θi满足关系：tanθi=2ⁱ。则由文献[3]的推导可知:
 
假设x[0]=b,y[0]=a,z[0]=0,则有：
 
式中， 为畸变因子，对于字长一定的运算，它为一常数，如字长为16位时，K=1.6667。δi表示每一次旋转的方向，当y[i]≥0时，其值为1；当y[i]≤0时，其值为-1。

2.3 FFT Core简介
    FFT-V2.0.0是Altera公司2004年2月新发布的FFT知识产权核，它是一个高性能、高度参数化的快速傅里叶变换(FFT)处理器，支持Cyclone、
Stratix II、Stratix GX、Stratix系列FPGA器件。该FFT Core功能是执行高性能的正向复数FFT或反向的FFT(IFFT)，采用基2/4频域抽取(DIF)的FFT算法，其转换长度为2m，这里6≤m≤14。在其内部，FFT采用块浮点结构，以在最大信噪比(SNR)和最小资源需求之间获得最大的收益。FFT Core接收一个长度为N的、二进制补码格式、顺序输入的复数序列作为输入，输出转换域的、顺序的复数数据序列。同时，一个累加块指数被输出，表示块浮点的量化因子。FFT Core的转换方向事先由一个输入端口为每个数据转换块指定。
   FFT Core可以设置两种不同的引擎结构：四输出(Quad-output FFT engine)和单输出(Single-output FFT engine)。对于要求转换时间尽量小的
应用，四输出引擎结构是最佳的选择；对于要求资源尽量少的应用，单输出引擎结构比较合适。为了增加整个FFT Core的吞吐量，可以采用多并行引擎结构。
    FFT Core支持3种I/O数据流结构：连续(streaming)、缓冲突发(Buffered Burst)、突发(Burst)。连续I/O数据流结构允许处理连续输入数据，输出连续复数数据流，而不中断输入和输出数据；缓冲突发I/O数据流结构与连续结构相比，需要更少的存储资源，但是，这是以减少平均吞吐
量为代价的；突发数据流结构的操作与缓冲突发方式基本上一致，但突发方式则需要更少的存储资源，这也是以降低吞吐量为代价的。

3  硬件设计
 
图1整体原理图
    设计的整体原理图如图1所示。输入和输出缓冲器分别存储预处理数据和FFT转换结果；FFT运算器负责FFT运算；控制器为输入和输出缓冲器提供读写地址，并控制FFT运算的时序和缓冲器的读写操作；后处理单元从单路复数输入频谱数据中分离出两路实数输入频谱数据；求模运算器实现CORDIC算法，求取转换结果的平方根。设计的输入为两路实数序列，一路作为实部，另一路作为虚部，由连续的256点的数据段组成；输出是间断的256点数据段，各数据段的前128点为第一路的频谱数据，后128点是第二路的频谱数据。根据FFT频谱关于中心点对称的结果，只截取前半段频谱数据并不会丢失任何信息。
    整个系统的工作时序为：
①数据以5MHz的速率输入到输入缓冲器；
②FFT运算器以40MHz的速率从输入缓冲器中取数进行运算；
③FFT运算结束时，将转换结果存入到输出缓冲器中；
④输出缓冲器数据以20MHz的速率被送到后处理单元进行转变；
⑤数据被送到求模运算器，进行CORDIC运算，输出；
⑥当③结束时，FFT运算器又回到起始状态，等待处理下一组数据，从而使运算周而复始地进行。整个设计由控制器严格控制。
    输入和输出缓冲器由FPGA内部的RAM实现，这些都相对简单。下面重点介绍。FFT运算器、控制器、后处理单元和求模运算器。[page]
 
3.1  FFT 运算器
    FFT运算器采用FFT Core实现，其引擎结构为双Single-output，I/O数据流采用突发(Burst)方式。FFT Core采用Atlantic Interface协议，输入
接口视为主接收器，输出接口视为主发送器。具体接口定义如表1所示。

     具体的工作流程：系统复位后，数据源将master_sink_dav置位，表示有采样数据等待输入；作为回应，FFT Core将master_sink_ena置位，表示可以接收输入数据；数据源加载第一个复数数据，同时master_sink_sop置位，表示输入数据块的起始；下一个时钟，master_sink_sop被清零，输入数据按照自然顺序被加入。输入数据达到256点时，系统自然启动FFT运算。通过inv_i信号的置位/清零可以改变单个数据块的FFT转换方向，inv_i信号必须和master_sink_sop信号严格同步。当FFT转换结束时，子接收器已经将master_source_dav信号置位，表示子接收器可以接收FFT的转换结果；同时，master_source_ena信号置位，FFTCore按照自然顺序输出运算结果；在输出过程中，
master_source_sop和master_source_eop信号被置位，表示输出数据块的起始和结束。详细的描述参见文献[4]。

3.2 控制器与后处理单元
    控制器大体可分为三个部分：输入缓冲控制(c_i)、FFT运算控制(c_f)、输出缓冲控制(c_o)。c_i为输入缓冲器提供读/写地址和相应的读/写
控制信号；c_f为FFT运算器提供控制信号，严格控制FFT Core的工作时序;c_o为输出缓冲器提供读/写地址及读/写控制信号。控制器通过VHDL语言编程的状态机方式可以轻易实现。
    后处理单元其实是式(2)和式(3)的硬件实现，具体的原理如图2所示。
 
图2后处理单元原理图
    图中标识“mux”、“+”、“-”、“1/2”分别表示选择器、加法器、减法器和除法器，dr、di、dnr、dni分别与式(1)和式(2)中的Zr(k)、
Zi(k)、Zr(N-k)、Zi(N-k)相对应。当sel等于0时，提取第一路实序列的频谱数据G(k)，实现式(1)功能；当sel等于1时，提取第二路实序列的频谱数据，实现式(2)功能。

3.3 求模运算器
    由于工程只要求求平方根，不涉及角度的计算，因此，CORDIC的角度计算部分没有给出，但这并不会影响到幅度的计算。整个CORDIC采用全流水线结构，设计总共有16级流水线单元，各流水线单元结构相似。CORDIC流水线结构如图3所示。
 
图3 CORDIC流水线原理图
    该结果并不是最终结果，还要加一级幅度校正，以去除畸变因子的影响。

4  结束语
    设计的输入和输出工作频率相对较低，因而很容易满足，关键是FFT Core的性能指标。根据工程需要，输入数据速率采用5MHz，FFT Core工作在40MHz，输出转换结果采用20MHz时钟，在此条件下对设计进行硬件测试，结果证明设计功能正确、工作稳定、性能优越。另外，经软件时序仿真可知，FFT Core最高工作频率可达到117.52MHz，通过提高运算时钟，还可获得更快的运算能力。
    设计选用Altera公司的FFT Core，成功地在FPGA中实现了两路连续256点实数序列FFT的算法，其设计成本低、性能好，已经成功地应用到
雷达产品中。由于FFT Core的可塑性很强，通过改动参数设置，就可轻易地使设计适应于不同的产品。