基于FPGA的高速基4FFT设计与实现

引言

快速傅里叶变换 (Fast Fourier Transformation，FFT) 作为时域和频域转化的基本运算，是数字谱分析的必要前提。FFT方法是信号处理领域的核心算法之一，它广泛应用于雷达信号处理、观测、数字通信、数据变换、定时定位处理、无线通讯、图像处理等领域。为便于硬件实现，FFT 算法常采用分级运算结构。如今的 FFT 大多采用并行结构，但其运算速度往往受到数据带宽的限制，因而需要增加成倍的存储单元才能满足速度要求。本文对 FFT 算法进行了分析，基于节省运算量、减少硬件面积和提高处理速率的考虑，给出了一个基于 FPGA的高速流水线结构的基 4FFT 处理器的设计方法。

1 基 4FFT 算法

FFT 算法的基本思想是 ：利用 DFT 系数的特性 ( 即周期性、对称性和可约性 ) 来合并 DFT 运算中的某些项，把长序列 DFT 变成短序列 DFT，从而减少其运算量，达到提高速度的目的。一般的 FFT 算法可以分为两类 ：第一类对时间，对时间序列 x(n) 进行逐次分解，称为时域抽取 FFT 法(Decima-tion-In-Time-FFT，DIT-FFT)；第二类对频率，主要对傅里叶变换序列 X(k) 进行分解，称为频域抽取 FFT 法 (Decimation-In-Frequency-FFT，DIF-FFT)。本设计采用 DIT-FFT 法进行设计。

1.1 基 4 DIT-FFT 算法

DFT 将时域信号变换成频域信号后，长度为 N 的有限长序列 x(n) 的离散傅里叶变换可以表示为 ：

基 4 DIT-FFT 算法的基本原理是 ：将一个 N 点的 FFT分解为 4 个 N/4 点的序列，再分别进行 DFT 计算 ；然后再将每个N/4点进一步分解为 4 个N/16点的计算，依此类推。同理，对于多点数还可以进行多级分解。其基 4 蝶形运算如下：

其中，X(K), X(k+N/4), X(k+2N/4), X(k+3N/4) 是蝶形运算后的结果。基 4 蝶形运算单元可以用图 1 表示。

1.2 算法比较与选择

一般常用乘法次数和加法次数来衡量一个算法的性能。例如，对于基 4FFT 算法的描述为 ：每个蝶形运算为 3 次复数乘法，每级共有 N/4 个基 4 蝶形单元，共有 m 级 ( 其中，N=4m)。表 1 所列是 4 种常用基数算法运算量的比较，表中，l=log2N。

一般情况下，基数越高，总计算量就越少，但是，控制复杂性也会相应提高。就复杂性而言，基 2 算法最容易控制，操作简单 ；基 4 算法控制稍许复杂，但与基 2 相差不大 ；基 8和基 16 算法的控制复杂度与基 4 相比，难度会增大很多。综合考虑运算量与控制复杂度，本文选择基 4 算法来实现设计。

2 基 4 FFT 算法的硬件实现

现今的 FFT 算法大多采用并行结构来实现。由于并行结构的数据输入大多是串行连续输入的，需要进入串并转换，这样会浪费大量时间，尤其是在一些实时高速处理的场合，并行结构难以适应。而流水线结构在实时性和连续性等方面具有天然的优势，所以，本设计采用流水线结构来完成设计。

FFT 算法的流水线结构一般分为 3 种：第一种是单路延时转接器结构 (Single-path Delay Commutator，SDC) ；第二种是多路延时转接器结构 (Multi-path Delay Commutator，MDC) ；第三种是单路延时反馈转接器结构 (Single-path Delay Feedback，SDF)。表 2 所列是流水线结构 FFT 各种指标的比较，其中，k=log4N。

从表 2 可以看出，在运算量上，SDC 占优势，但控制复杂度较高。综合考虑运算量、存储单元及控制复杂度，SDF是最优的选择。因此，本设计采用 SDF 结构。

本文设计实现的一个 1024 点流水线结构基 4-SDF FFT的结构框图如图 2 所示。

2.1 蝶形运算单元

可以将蝶形运算分割为下式 ：

其中，是蝶形运算后一状态的结果。经过分割后，可以看出，整个蝶形运算只有 a+b, a-b, a+jb, a-jb 四种计算，分别采用复数加法与减法器就可以完成蝶形运算，从而可大大简化设计和实现的复杂度。图 3 与图 4 分别是蝶形单元所用到的复数加法器与减法器的框图。

2.2高效乘法器

一般两个复数分别为A=a+jb, B=C+jd的复数相乘的计 算过程为：

AB=(a+j b)(c+j d)=(ac-bd)+j(ad+bc)=Fre+j Yim                      (4)

其中，Yre为 AB 结果的实部，Yim为 AB 的虚部。

显然，一次复数乘法共需要4次实数乘法和3次实数加 法，但是，如果进行一定的变换，就可以减少实数乘法的次数。 即：

Yx=ac-bd=ac-ad+ad-bd=(c-d)a+(a-b)d                                      (5)

Yim=ad+bc=ad-bd+bd+bc=(c+d)b+(a-b)d                                 (6)

在计算前，将c-d,c+d,a-b的结果放在存储单元中，这样, 一次复数乘法就只需要3次实数乘法与5次实数加法，显然 会大大节约硬件开销，同时也提高了计算速度。

本设计采用有符号数BOOTH编码的乘法器，根据数据 量化，利用10位的被乘数和10位的乘数进行运算。其计算 结果乘积需要经过饱和，最后取10位结果保留。

2.3旋转因子存储

本设计需要将旋转因子向量= cos i +jsin i的实部和 虚部存储在寄存器中，并利用查找表方式实现向量旋转运算。 这样只需要取在1/8圆内，即［0，…，n/4］之间的旋转因子, 其他的旋转因子都是这1/8圆周区域内旋转因子的变换。按照 旋转因子的周期性和对称性，其他区域的旋转因子，可通过 交换实部虚部和改变正负号来得到。

例如：设点A为［0,…，”4］的一个旋转因子，假设它 写成矢量形式是A=cosx+jsinx,那么，映射到4个象限内的 另外7个投影则是：

sinx+jcosx, -cosx +jsinx, -sinx +jcosx, -cosx+j(-sinx), -sinx+j(-cosx), sinx+j(-cosx), cosx+j(-sinx)

旋转因子一共有8个数据。只需要将这样的一个数据的 实部和虚部的数值(不包括符号)分别存储在寄存器同一个地 址的数据存储单元里，就可以在取出这个数据后，通过变换 安排好它的实部和虚部，然后重新安排它的正负号，就可得到 其他在该级运算中所需要的另外7个旋转因子。

2.4控制单元

每级蝶形运算单元都有自己的控制单元，这主要是控制 蝶形运算单元的工作模式，判断是否进入流水操作，操作数 的选取，RAM的选通，复数乘法的选通，以及产生RAM和 旋转因子的地址。另外，控制单元还需要产生使能信号，以供 下一级的输入使用。

对于蝶形单元的控制，主要是控制其工作模式。在蝶形 单元中，输入数据先存储到第一个存储单元中，同时从第一个 存储单元的相同地址中取出上一次蝶形运算的结果，然后把第 二、三段数据存储到第二、三个存储单元中，同时读出相应的 结果；当最后的一段数据到来时，从存储单元中读取相应的 数据进行蝶形运算，同时输出第一个运算结果，并把其他3 个结果同址写回三个存储单元相对应的位置。

对于旋转因子的控制，由于在寄存器中的旋转因子都是 无符号数，因此在进行复数乘法之前，需要根据控制单元的 指示，重新安排它的正负号。

2.5输出数据地址转换

在系统中，FFT输出的数据也许是给下一级使用。特别是 在OFDM系统中，也需要找回原来的顺序。由于输出数据的 地址是乱序，所以需要有地址产生模块给数据产生地址，以 方便后级使用。输出数据地址转换应按照00、01、10、11输入, 并按照11、10、01、00顺序输出。

3仿真、综合及FPGA实现

本文设计实现了一个1 024点的基4 FFT处理器，数据 处理精度为10位。采用Verilog HDL语言描述整个设计，并 编写测试平台。笔者利用Modelsim SE 6.5对本文的设计进行 了功能仿真验证，运算结果与Matlab计算的结果一致，从而 证明了本文算法的正确性。

在FPGA实现方面，本文选用Xilinx的Spartan-3E-XC- 3S500E芯片,该器件的内部含有4个数字时钟管理器(DCM), 73 kB 的分布 RAM, 360 kB 的 block RAM, 4 个 18X18 的专 用乘法器(Dedicated Multipliers)单元，其中乘法器的工作频 率可达到300 MHz。综合布线工具均采用Xilinx的设计平台ISE9.1,表3所列是其该处理器与一些现有文献中的FFT处 理器核的性能比较，可见本设计具有一定的优势。

4结语

本文通过采用SDF流水线结构设计并实现了一个基于 FPGA的高速基4 FFT处理器，FPGA内部资源消耗明显减少, 并保持了比较高的工作频率，能满足信号处理系统实时处理的 要求。从实现结果可以看出，与并行结构的FFT处理器相比, 流水线结构的处理速度更快。该处理器可适用于超高速场合 以及需要密集型数字信号处理的领域，比如数字通信、数据 变换、定时定位处理、无线通讯、图像处理等。

20210915_6141736b491a4__基于FPGA的高速基4FFT设计与实现