二维F F T算法在高速信号处理中的应用

吴海洲

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

在雷达、通信、测控等领域，FFT是信号分析与处理中常用的重要变换。为了便于工程实现，各大FPGA厂商都已推出了FFT的IP核，低速数据串行输入串行输出，应用简便，减小设计风险，缩短了开发周期。但是由于IP核的局限性很强，其处理速度、占用资源等不能满足高速信号处理的快速发展。尤其是FPGA中需高速处理的FFT算法，且数据通常是并行输入并行输出，针对这一问题，借鉴图像处理中的二维信号处理方法，将一维FFT算法转换成适用于矩阵运算的二维FFT算法，结合IP核的使用，在FPGA资源与算法复杂度中折中处理，解决了高速信号的FFT变换问题。

1 算法描述

FFT的表达式[1]如下所示，其中N为FFT的点数

上式内部为N2点的FFT，再乘以相位因子后再进行N1点的FFT即可得到N点的FFT。在并行信号处理中，N1通常选为4或8路，结合并行运算只需要简单的乘、加运算就可得到对应的4点或8点FFT。

2 实现步骤

根据算法描述，可知实现步骤[2]如下：

（1）将N点数据转换成N1行、N2列的矩阵。

（2）对数据矩阵的每行做N2点的FFT变换。

（3）对该矩阵的每个数据乘以对应的相位因子。

（4）对矩阵的每列做N1点的FFT变换。

（5）矩阵行列变换，数据整序输出。

由此可见，算法的实质就是将一个N点FFT分解为N1个N2点FFT和N2个N1点FFT以及N次与的乘积。

3 算法实现

在某信号处理算法中，需要对数据进行2048点FFT变换，但是该算法的处理速度较高，数据速率达到1.2Gbps以上，受限于FPGA的信号处理速度，数据以8路数据并行处理。

若直接调用2048点FFT的IP核，处理步骤需要：（1）2048*8=32768点数据进行行列转换；（2）调用8个2048点的FFT核；（3）32768点数据行列转换输出。这种方法实现结构简单，逻辑清晰，但是缺点是占用FPGA资源较大。以16bit数据位宽为例，仅两次行列转换所需的RAM资源就需1Mbps以上，8个2048点的FFT核所占的逻辑资源达58Kbps，而Xilinx的XC5VSX95T芯片逻辑资源一共也只有58Kbps，FPGA内不可实现该算法。

采用二维FFT的方法，将一维2048点FFT变换改为二维8*256点FFT变换，如图1所示。

图1 8*256点二维FFT实现示意图

FPGA内实现时可分为四个模块流水处理：

模块1：实现256点FFT功能，可直接调用8个相同配置参数的256点FFT的IP核；

模块2：实现与对应的旋转因子相乘的功能，2048个旋转因子存储在8个深度为256、位宽为16bit的ROM中，相位因子与对应的数据进行点对点复乘；

模块3：将256列数据分别做8点FFT，8路数据采用标准的基8蝶形运算实现数据的全并行输入与输出，如图2所示。

图2 基8蝶形运算

基8蝶形运算中只涉及数据的乘、加运算，而乘法运算是与固定乘数相乘，，其中，即可用数据移位、符号变换与加法代替乘法运算，至此，8点FFT转换为数据的移位与相加，且只需几个时钟周期就可完成。

模块4：实现矩阵的转置，可用片上RAM实现，控制RAM的读写地址，实现数据的整序输出。

4 结束语

本文将一个小点数的二维FFT代替大点数的FFT运算，信号处理时钟没有变化，虽然比直接调用8个2048点IP核的方法多两次运算，但是综合计算过程只相当于1个2048点FFT的运算量，缓存数据也只有2048个数据，FPGA逻辑资源与缓存资源占用均很少，处理时延也大大减小。根据本文算法实现结构可知，二维FFT将串入串出的一维低速FFT处理变为并入并出的高速信号处理，处理时钟没有显著变化，适用于高速信号并行处理，也适用于其它超大点数的FFT变换[3]等。

[1] 王晓君，龙腾，周希元.二维级联流水结构大点数FFT运算器实现研究[J].无线电工程，2010，40（11）：19-22.

[2] 张丽君.大点数FFT的二维算法FPGA并行实现[J].无线电工程，2013，39（3）：86-88.

[3] 于东，李丽，韩峰，王堃，丰帆，潘红兵.一种高精度的大点数二维FFT处理器设计[J].现代雷达，2016，38（5）16-21.