实数二维FFT及其改进算法的FPGA实现

刘冀川

（中国电子科技集团公司第五十四研究所，河北石家庄050081）

0 引言

快速傅里叶变换（FFT）是最常用的信号处理方法之一，在通信对抗领域得到广泛的应用[1]。随着高速跳频通信和突发通信技术的发展，对信号的快速检测能力有了更高的要求，对FFT处理速度要求也越来越高[2]。

目前，FPGA设计都是使用厂商提供的FPGA软核，处理速度无法进一步提高。为了实现更快的处理速度，需要利用一些计算技巧，自主开发新的FFT处理模块。对多个快速算法及其工程可实现性进行评估后，选择了基于二维处理的FFT快速实现算法，并结合FPGA芯片的编程特性对算法进行了改进，在FPGA内实现并在试验平台上进行了功能测试和验证工作。

1 二维FFT的实现原理

设序列x（n）的长度为N，且N为2的自然数次幂，其DFT为X（k）[3]。则，

若N=M×L，将x（n）进行重新排序为L行M列的矩阵。假设，

将n、k代入X（k）的表达式，整理后得到:

由上式可以看出，方括号内是L点的FFT，一共M个。而最外层的求和项是M点的FFT，一共L个。这样就把一个基于一维处理的FFT运算转换为基于二维处理的FFT运算。

二维FFT的算法流程图如图1所示。

图1 二维FFT算法流程图

具体实现步骤如下[4]:①数据重排，将N点数据排成L×M点格式;②做M个L点的一维FFT变换;③将L点数据输出乘以旋转因子得到中间数据矩阵;④做L个M点一维FFT变换;⑤整序输出。

由上可知，即使两次FFT的IP核复用，FPGA完成二维FFT计算也需要至少个IP核，所以当M=L时，最省资源。例如，1024点FFT最少需要32个IP核，需要大量的硬件逻辑资源，给FPGA实现带来的难度。

2 算法改进

针对上述的硬件资源消耗太大的问题，对实数二维FFT算法进行了改进，以节省硬件资源，从而降低硬件成本。在许多情况下，时域中的时间序列信号都是实数值，对于实值信号，可以利用实数信号FFT结果的对称性，以及通过复值FFT（CFFT）计算实值FFT（RFFT）的方法来提高运算效率[5]。

FPGA的FFT IP核是针对复数来进行计算的，对于实数，以前的做法是把虚部全部设为0，这样，计算出来的结果就是实数的FFT结果。但是，现在要减少IP核数量，所以要想办法把虚部也利用上。

利用复值FFT计算实值FFT，当N=2m时，对于实值信号x（n）和y（n），其中（n=0，1，…，N－1），设置一个z（n）=x（n）+jy（n），并设{z（n）}的FFT（即CFFT）为{Z（k）}。下面分析用Z（k）求X（k）和Y（k）的方法[6]。

设

则下式成立:

于是X（k）和Y（k），（k=0，1，…，N－1）可表示为:

而且，有ZR（N）=ZR（0），ZI（N）=ZI（0）。

经过上述计算以后，还原出了两路FFT结果X（k）和Y（k），这样，通过M/2个IP核就能实现M列变换。根据上面提到的二维FFT的具体实现步骤可知，得到的列变换的FFT结果X（k）和Y（k）后，乘以旋转因子，再进行行变换，根据实数FFT结果的对称性[7]，那么只需要（L/2）+1行数据进行行变换，需要的IP核数量也为（L/2）+1，这样，2次FFT计算所使用的IP核复用，实际使用的IP核数量为max{M/2，L/2+1}，当M=L时，使用的IP核最少，即（L/2）+1。

3 算法的仿真与性能分析

3.1 算法仿真

针对上述二维FFT及其改进算法，对1024点正弦数进行了MATLAB仿真[8]，结果如图2所示。与一维FFT相比，结果完全相同，从而证明了算法的正确性。

图2 二维FFT及其改进算法仿真结果

3.2 用时比较

在工作时钟为150MHz时钟下，速度最快的IP核算法和二维改进算法用时的比较如表1所示[9]。

表1 FFT用时比较

从表中可以看出，二维FFT并行算法的用时相对于最快的IP核速度的10倍多。

3.3 资源耗用率

此算法在Xilinx公司的XC4VSX55芯片上实现，其主要资源耗用率如表2所示[10]。

表2 FFT主要资源耗用率

与之相比，改进后算法的硬件资源DSP48S为78%，如果用未进行改进的二维FFT算法，1024点的FFT所需要的DSP48S已超出XC4VSX55的资源上限，由此可见，改进的二维FFT算法大大节省了硬件资源，从而降低了硬件成本。

4 结束语

在分析二维FFT算法的基础上，利用实数FFT结果具有对称性的特性，结合FPGA的优势，提出并实现了流水结构的FFT算法。该算法采用并行的组织结构，进一步的减少了处理时间和硬件资源，更好地满足了FFT处理数据时间的需要。该算法已应用于工程实践当中，解决了关键性技术，取得了很好的效果。

[1]王旭东，刘渝.全并行结构FFT的FPGA实现[J].南京航空航天大学学报，2006，38（1）:96－100.

[2]黄宁，朱恩，荣黄宁.高速FFT芯片设计及结构研究[J].电子器件，2008，31（2）:511－515.

[3]张丽君.大点数FFT的二维算法FPGA并行实现[J].无线电通信技术，2013，39（3）:86－88.

[4]张傲华.基于FPGA的高速实时信号处理技术研究[D].成都:电子科技大学，2005:22－27.

[5]李伯全，胥保文，潘海彬，等.基于FPGA的FFT高速运算器设计[J].仪器仪表学报，2008，29（4）:51－53.

[6]谷荻隆嗣.快速算法与并行信号处理[M].北京:科学出版社，2003.

[7]邓波，戎蒙恬，汤晓峰.可配置高速高精度FFT的硬件实现[J].计算机工程，2006，32（17）:254－256.

[8]李伟.1024点基4FFT处理芯片及接口设计研究[D].南京:东南大学，2009:39－40.

[9]Xilinx.LogiCORE IP Fast Fourier Transform v7.1[M].USA:Xllinx，2010.

[10]Xilinx.Virtex4 User Guide[M].USA:Xllinx，2005.