利用FFT IP Core实现FFT算法

利用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数据流结构与连续结构相比，需要更少的存储资源，但是，这是以减少平均吞吐
量为代价的；突发数据流结构的操作与缓冲突发方式基本上一致，但突发方式则需要更少的存储资源，这也是以降低吞吐量为代价的。