基于FPGA的高速fft运算.pdf

基于FPGA 的高速流水线FFT算法实现 0 引言 有限长序列的DFT(离散傅里叶变换)特点是能够将频域的数据离散化成有限长的序列。但由 于DYT本身运算量相当大，限制了它的实际应用。FFT(快速傅里叶变换)算法是作为DFT 的快速算法提出，它将长序列的DFT分解为短序列的DFT，大大减少了运算量，使得DFT 算法在频谱分析、滤波器设计等领域得到了广泛的应用。 FPGA(现场可编程门阵列)是一种具有大规模可编程门阵列的器件，不仅具有专用集成电路 (ASIC)快速的特点，更具有很好的系统实现的灵活性。FPGA可通过开发工具实现在线编程。 与CPLD(复杂可编程逻辑器件)相比，FPGA属寄存器丰富型结构，更加适合于完成时序逻辑 控制。因此，FPGA为高速FFT算法的实现提供了一个很好的平台。 1 基4-FFT算法基本原理 在FFT 各类算法中，基2-FFT算法是最简单的一种，但其运算量与基4-FFT算法相比则大得 多，分裂基算法综合了基4和基2算法的特点，虽然具有最少的复乘运算量，但其L蝶形运 算控制的复杂性也限制了其在硬件上的实现，因此，本设计采用了基4-FFT算法结构。 基4-FFT算法的基本运算是4点DFT。一个4点的DFT运算的表达式为： 式(1)对于输出变量进行了二进制倒序，便于在运算过程中进行同址运算，节省了运算过程 中所需存储器单元的数量。 按DIT(时间抽取)的1024点的基4-FFT 共需5级蝶形运算，每级从RAM中读取的数据经过蝶 形运算后原址存入存储单元准备下一级运算。算法的第1级为一组N=1 024点的基4蝶形运 算，共256个蝶形，每个蝶形的距离为256点；第2级为4组N=256点的基4蝶形运算，每组 64个蝶形，每个蝶形的距离为64点。后3级类推。这种算法每一级的运算具有相对独立性， 每级运算都采用同址运算，因此，本设计只使用了2个1k×16bits 的RAM单元。运算过程 中所需的旋转因子的值经过查询预设的正弦与余弦ROM表得到。 21024点FFT 算法模块的设计 本设计的总体框图如图1所示。整个模块的输入包括16位带符号实部和虚部数据输入、FFF 启动信号，输出包括16位带符号实部和虚部数据输出、输出有效数据区间标志。内部结构 包括2个1k×16bits的实部和虚部双口RAM存储单元、蝶形运算单元、旋转因子生成模块(包 括正弦因子查询表、余弦因子查询表和象限转换模块)、RAM和ROM存储器地址控制单元、 倒序模块以及时序总控制单元。 下面对主要单元进行分析。 2.1旋转因子产生模块 在整个FFT 运算过程中，需要存储一组旋转因子表用于蝶形运算，如第1级运算需要的旋转 因子有W01024，W11024，…，根据旋转因子的可约性，后几级运算所需的 旋转因子都可以在这一组数据中查到，因此无需另外存储。为了更节省存储资源，本设计只 在ROM单元中存储了前256个旋转因子数据，即第1象限因子W01024，W11024，…， W2551024，。其余象限的因子通过象限转换后得到。这样便可以节省3／4的ROM存储单元 的硬件资源。 2.2蝶形运算单元 2.2.1蝶形整体结构 蝶形运算单元包括输入输出寄存器、串／并转换、并／串转换和复数乘法器等。从基本的基 4蝶形运算表达式可以看出，每一级的输出数据在进入下一级运算之前都要首先与旋转因子 WnkN进行相乘。本设计采用如图2的蝶形运算器结构。 这种结构是经过优化的蝶形运算器结构，文献[3]给出了这一结构的具体分析，这样的结构 与传统的需要3个复乘单元的蝶形结果相比，因为采用了流水线控制，硬件上节省了2个复 乘单元，而输出同样只需4个时钟周期，工作效率并未降低。在FPGA设计中，一个乘法器 的引入，尤其是高位数的乘法器的引入，将很大程度地影响系统整体的运行速率，并且将占 用大量的资源。因此，这种改进方案更有利于FFT 算法的高效实现。 2.2.2复乘器设计 对于复乘单元的设计，常见的复乘方式为： 式中：i为虚数单位。 这种乘法表达式需要4个实数乘法运算和2个加减运算，设计中对表达式进行如下变换： 式(3)这种复乘方式只需要3个实数乘法运算和5个加减就可以完成复乘运算，减少了乘法器 数量。式中(c+s)值可以在进行象限转换的同时通过计算得到，而无需另外存储。 2.2.3数据溢出控制 为了防止数据计算过程中的溢出，上述蝶形单元中的加减法运算单元对于输入的4个有符号 复数数据采取了符号位扩展相加后再对计算结果进行1／4倍压缩的方法进行计算。而对于 乘法单元则采用了刻度(scaling)的方法，将复数数据