一种节省硬件资源的DFT实现算法研究

廖晓慧 彭永健 曹森

摘要：工程项目中DFT算法实现需使用大量FPGA资源。文章设计一种非2n点数的DFT算法，通过算法流程的改进、旋转因子的周期性，该算法可大量减少DFT的运算量，并在FPGA芯片上予以实现。实验仿真表明该算法优化了硬件资源，减少了存储资源和DSP资源。文章算法解决了工程DFT应用使用资源多的问题。

关键词：DFT；资源；FPGA

中图分类号：中图分类号  文献标志码：A文献标志码

0 引言

FPGA处理DFT运算，FPGA有内置高速乘法和加法器，高速性能好，处理速度快。基2或基4FFT算法［1］，可计算得到时域序列长度N=2nDFT运算结果。N≠2n时，DFT直接进行运算，将使用大量乘法器，运算量较大，占用FPGA资源较多。工程应用，运算量大，布局布线困难，同时增加系统成本和功耗［2］。

为减少DFT算法使用FPGA资源，降低布局布线难度，本文介绍一种节省硬件资源的DFT实现算法。该算法从DFT原理出发，在已知频率的系统当中进行定点DFT运算，通过算法流程的优化，节省FPGA资源，解决工程DFT应用使用资源多、不易实现的问题。

1 DFT原理

X（k）=∑N-1n=0x（n）exp（-2πnk/N），k取0，1，2…N-1，x（n）为时域信号，X（k）为频域信号［3］。exp（-2πnk/N）=cos（2πnk/N）+j×sin（2πnk/N） X（k）=∑N-1n=0x（n）cos（2πnk/N）+j×∑N-1n=0x（n）sin （2πnk/N），FPGA计算cos（2πnk/N）、sin（2πnk/N）会使用乘法器和逻辑资源［4］。k从0到N-1全部计算，将消耗大量的逻辑资源。本文算法通过已知k值，计算出频域值，节省资源。

2 算法分析以及实现

从DFT原理分析可知，旋转因子、并行处理都将使用大量处理资源。本文算法优化旋转因子模块同时优化算法流程解决处理资源问题。

旋转因子模块设计。FPGA直接计算cos（2πnk/N）、sin（2πnk/N）消耗大量的资源，不易实现［5］。Matlab直接计算出旋转因子的实部和虚部，然后乘以一个整数将浮点变化成为定点，将定点数以二进制补码形式存储在FPGA内部ROM中。定点数采用有符号位，在进行加减运算时不会溢出，其包含一位符号位、一位整数位、多个小数位，误差的大小决定于表示小数的位数。硬件设计简单、易于控制。

n取值范围0到N-1，k取值范围0到N-1， nk最大值（N-1）×（N-1）。nk值从0到（N-1）×（N-1）全部存储，控制电路简单但需要消耗大量的存储资源。利用cos（2πnk/N）、sin（2πnk/N）的周期性，ROM当中只存储nk从0到N-1的值。用较小的控制资源，节省大量的存储资源。

串行运算设计。x（n）串行采样数据输入。并行计算X（k）值，需将x（n）先存储，消耗大量存储资源、同时消耗大量乘法器。以串行不断累加的方式计算X（k）的值，不占用存储资源存储x（n）的值，同时复用乘法器，降低存储资源，同时降低乘法器资源。

3 FPGA实现流程

旋转因子实现流程。每个Clk更新n、nk。n累加1，从0到N-1。

如流程图1所示：DFT数据初始化，输入k，Qn、n赋初值0。具体步骤如下：

（1）k与Qn相加，累加得到Qn。

（2）利用旋转因子周期性。比较Qn和N，若Qn大于N，则Qn=Qn-N；否则Qn=Qn。

（3）将Qn作为下一个Qn累加的输入。

（4）同时将Qn作为存储模块地址的索引值，得到cos（2πnk/N）、sin（2πnk/N）。

（5）断时域输入序号n是否小于N-1。若n小于N-1，则继续计算nk的值；若大于等于N-1，则Qn赋值为0。

Matlab根据DFT点数N，计算旋转因子实部和虚部的值，存入FPGA的ROM中。Qn的计算值作为旋转因子ROM的索引地址，索引得到旋转因子的值。旋转因子模块接口如图2所示。

如图3所示，DFT算法实现流程如下：

（1）根据n，k的值生成旋转因子索引地址。

（2）将索引地址输入存储旋转因子ROM中，得到旋转因子的值。

（3）将时域序列x（n）与旋转因子相乘。

（4）将每一个相乘的值进行累加，得到DFT的计算结果Xk。

4 仿真结果及算法实现

本文分析算法使用乘法器个数，验证算法有效性。若DFT点数为N，并行4路时域数据输入，则DFT直接计算需要使用4N个乘法器。本文提出的DFT算法一路数据输入时，实部和虚部各需要一个乘法器。4路并行数据输入，本文提出的算法只需要8个乘法器，减少了硬件资源。两种算法乘法器使用个数对比如表1所示。

为进一步验证算法的有效性，在Xilinx公司的ISE软件上进行实际验证和调试。FPGA芯片是Virtex-5系列的XC6VLX240T。

整个系统算法仿真实现，DFT点数260，模块编译后进行综合，综合报告如图4所示。分析结果和用ISE软件实现结果相符。

验证算法的正确性和可实现性，在Matlab、ModelSim中对算法进行仿真，输入不同时域正弦波信号x（n）进行仿真。x（n）=cos（2πnf/fs），n=0，1…N-1。ModelSim进行仿真，x（n）乘以256进行量化，将浮点数转化为定点数。

设置N=260，采样率fs=520 MHz，f、k4组不同的变量，Matlab，ModelSim计算得到DFT的实部和虚部值。

图5和图6分别为f=12 MHz、k=6时Matlab计算DFT的结果，ModelSim仿真DFT的结果。FPGA当中时鐘采样率太高，时序不能满足要求。为满足时序要求，ModelSim输入4路并行260MHz的AD数据，idata_ch0、idata_ch1、idata_ch2、idata_ch3。同时通过旋转因子模块得到4路AD数据对应的旋转因子的值。计算处理得到DFT的结果。

表2為4组不同的f、k变量通过Matlab和ModelSim计算得到的结果。

由仿真结果可知当f=12、k=6时Matlab实部计算结果为33 267，ModelSim实部计算结果为33 266，  虚部计算结果都为0，误差3×10-5 。其他组的数据ModelSim仿真结果与Matlab计算结果相符，验证了算法的正确性。

5 结语

针对直接计算DFT使用FPGA存储和DSP资源较多的问题，本文提出一种简化的算法，能够减少存储和DSP资源，解决了工程应用中的问题。

参考文献

［1］刘顺杰.数字信号处理［M］.西安：西安电子科技大学出版社，2005.

［2］REDINBO G R.Tensor Product DFT Codes vs Standard DFT Codes［J］.IEEE Transactions on Computers，2019（11）：1678-1688.

［3］昌攀，钟诚.通过DFT变换提取DNA序列特征聚类物种［J］.小型微型计算机系统，2018（3）：463-467.

［4］RAO K R.Fast Fourier Transform：Algorithms And Applications［M］.北京：机械工业出版社，2010.

［5］HE Y Z，CUI G F，LI P X，et al.Timing Advanced Estimation Algorithm of Low Complexity Based on DFT Spectrum Analysis for Satellite System［J］.China Communications，2015（4）：140-150.

（编辑 王永超）

Research on a DFT implementation algorithm for saving hardware resources

Liao  Xiaohui， Peng  Yongjian， Cao  Sen

（The 29th Research Institute of China Electronics Technology Group Corporation， Chengdu 610036， China）

Abstract： The implementation of DFT algorithm in engineering projects uses a lot of FPGA resources. A non 2n points DFT implementation algorithm is designed， through the improvement of algorithm flow and periodicity of rotation factor， which can greatly reduce the computation of DFT and is implemented on FPGA chip. The simulation results show that the hardware resources can be optimized， and the storage resources and DSP resources are reduced. This algorithm solves the problem of using too many resources in engineering DFT applications.

Key words： DFT; resources; FPGA