原创 【转】基于FPGA 的高速实时FFT处理器设计

离散傅里叶变换(DFT) 是数字谱分析必需的变换工具。完成N 点DFT 运算约需N² 次乘法和N^(N-1) 次加法,当N 较大时,运算量非常大,使其实际应用受到极大的限制。快速傅里叶变换(FFT) 采用递归型算法,利用旋转因子的周期性和对称性,将长序列DFT 分解为短序列DFT ,使总运算量减小1～2 个数量级,从而大大加快了运算速度。FFT 和快速傅里叶逆变换(IFFT) 在雷达信号处理、图像处理、谱估计等领域有广泛的应用。目前,高速FFT 的实现方案总体上分为基于专用集成电路(ASIC) 、现场可编程门阵列(FPGA) 、数字信号处理(DSP) 和通用处理机(GPP) 等几种。从FFT 的处理速度、面积和功耗方面比较,基于ASIC 实现的性能最好,基于FPGA 实现的次之。因此,在FFT 处理器的小规模应用场合,采用FPGA可以获得较高的性价比和灵活性。本设计主要应用于雷达系统的宽带信号处理和成像。

1 FFT算法分析
    从FFT 算法的复杂性来看,基4 算法比基2 算法减少约20 %的运算量。从硬件实现的难易程度来看,基4 算法具有比分裂基和更高基较易控制的特点。
    FFT 算法有按时间抽取(DIT) 和按频率抽取(DIF) 两种形式,其区别在于输入数据和旋转因子乘、加的顺序不同。在DIT 中,蝶形运算的输入数据和旋转因子是先乘后加,而在DIF 中,则是先加后乘,两者并没有实质区别。因此,本设计采用DIF 的基4 FFT 算法。
一个N 点序列x(n) 的DFT 定义为:
 
式中：
假定N = 4 ^m ,式(1) 先按时域前、后分开,可写成:
 
　式(2) 可进一步改写为:
 
　在频域X(k) 上将k 分解后进行抽取,分别令k 等于4r,4r+2,4r+1,4r+3(r=0,1,……,N/4-1) 。式(3) 可写为:
 
　分别令:
 
　式(4) 可进一步简化为:
 
　由式(5) 可见,完成一个基4 蝶形运算需要进行8个复数加和3 个复数乘,也就是22 个实数加和12 个实数乘。

2 高性能FPGA 的特点
    本设计采用Xilinx 公司2001 年推出的Virtex2 II系列FPGA ,它除了内含大量可配置逻辑模块(CLB) 、输入输出模块(IOB) 逻辑资源和布线资源外,还具有以下特点:
a) 内部时钟速度可达420 MHz ,且具有丰富的全局时钟资源和数字时钟管理模块(DCM) ,可以获得较小的时钟扭曲。
c) 具有为算术运算而特别设计的硬件结构,如18bit ×18 bit 嵌入式硬件乘法器、快速进位链等。
c) 包含丰富的模块化RAM。
    这些特点简化了逻辑设计,缩短了设计时间,为实现高速、实时FFT 处理提供了极大的便利。

3 FFT算法的硬件实现
3.1 系统设计
    从运算速度和硬件实现两方面综合考虑,本设计系统框架采用多级串行的同步流水结构,如图1 所示。
 
　与仅用1 个蝶算单元反复运算的处理方案相比,流水线处理方式可以获得更快的运算速度;与并行或阵列处理方式相比,这种结构可降低控制复杂度,节省硬件资源,获得较小的面积和功耗。
    串行级联的各级结构除了输入、输出级仅在溢出检测和移位控制上有所不同外,其余与中间各级的结构完全相同。图2 给出了中间单级的结构框图。
 
　
3.2 　运算数据的存取
    由于采用多级串行的流水线(pipeline) 结构,每级的数据输入、运算和数据输出是同时进行的。因此,数据的存取可采用单口或双口RAM ,实现乒乓操作,原理框图如图3 所示。
 
　  通过输入和输出数据选择器按节拍相互配合的切换,将经过双端口RAM(DPRAM) 缓冲的数据流不停顿地送到数据流运算处理模块,可实现数据的无缝缓冲和处理。
    每级蝶形运算的输入数据,其地址按一定规律存放在该级ROM 中, 由地址发生器发送出来。每级DPRAM 有一个写地址和一个读地址,后一级RAM的写地址和前一级RAM 的读地址相同,使得每一级的输入数据均按自然顺序存储。另外,为节省存储资源,也可利用蝶形单元同址运算的特点,原址读出原址写入同一RAM 进行存储。
    由上述FFT 的算法分析可知,在点数N 确定后,一个基4 蝶形运算单元中3 个旋转因子Wⁿ_N、W²ⁿ_N 和W³ⁿ_N 的值均由n 值确定。n 值的大小由该蝶形运算单元所在的级数、该级的组数及其在该组蝶形运算单元中的具体位置决定。同样,各级旋转因子也采用对ROM 进行查表的方式得到。此外,基4 蝶形运算的输入和输出均为并行方式,所需的转换可用串/并和并/串转换模块来完成。

3.3 溢出检测和控制
    根据运算数据的不同表示形式,FFT 运算可分为浮点、块浮点和定点3 种类型。在定点运算中,需要对输入进行一定比例的衰减,以防止运算过程的溢出,结果显然影响到运算精度。采用浮点运算虽然不存在溢出问题,但是电路复杂性显著增加。
    本设计采用的块浮点FFT 处理,在每级的输入数据端,对符号位进行扩充;在每级的输出数据端,对最高几位进行检测,以确定是否存在溢出以及溢出的位数,再作出相应的移位处理。这样,既保证了运算过程的不溢出,又使得硬件结构和控制比浮点运算简单。
    在一个基4 蝶形运算单元中,由于旋转因子的实部和虚部的绝对值总是不大于1 ,故乘法运算不会引起输出数据位数的增加,而输入数据的加减也最多只有两次进位。因此,若输入数据的实部、虚部分别为N 位字长,为防止溢出, 输出数据要用N+2 位字长表示。溢出检测可采用状态机的描述形式对输出数据的高3 位进行比较,得到溢出控制位,以决定下一级作何种移位处理,移位输出的N 位字长的数据作为下一级蝶形运算的输入。同时,对各级的溢出控制位进行求和运算,得到一次N 点FFT 处理结果的块浮点指数。

3.4 运算数据的同步
    为了保证运算速度,在每级的蝶形运算中都插入了pipeline ,对乘法和加法的中间结果进行寄存。因此,存在数据同步的问题,包括每级蝶形运算的输入数据和旋转因子的对齐、蝶形运算中不含旋转因子的输出项和包含与旋转因子相乘的输出项的对齐,以及不同级之间输入数据的同步。解决办法是:前两种情况,可根据插入的pipeline 个数,插入同样数量的DFF 延迟对齐;后一种情况,则需通过地址控制发生器发送的地址作相应的延迟处理。

3.5 输出整序
    由于在设计中采用的是顺序输入、倒序输出,因此,必须对输出作整序操作。具体说来,最后一级输出到RAM 的写地址要按四进制数作倒序排列,而不再像中间级那样与前一级DPRAM 的读地址相同。

3.6 用FFT实现IFFT
    FFT 模块设计完成后,再要实现IFFT ,无论是在算法还是硬件实现上都相对比较容易。具体做法是:在输入端,对输入的频域数据取共轭后进行FFT 运算;在输出端,对输出数据也作共轭后再除以点数N ,即可得到需要的时域输出。

4 结束语
    本设计采用了多级串行的同步流水线处理结构,在对各功能模块进行明确的划分后,全部采用Verilog HDL 描述。在设计时例化了FPGA 内部的模块化RAM 和18 bit ×18 bit 的硬件乘法器。综合工具为Synplicity 公司的Synplify Pro ,仿真工具为Cadence 公司的NC2Sim ,布局布线为Xilinx 公司的ISE。在完成综合、布局布线和时序仿真后,将位流文件下载到Xilinx 公司的Virtex2 II器件中。经测试,在外部时钟为100 MHz 时, 完成1024 点、16 位复数点的块浮点FFT 处理时间为10.2 μs ,处理速度达到实时要求。实践证明,随着可编程器件性能的增强,用FPGA 高速、实时地实现复杂的DSP 算法是完全可行的。当然,在FFT 处理器的大规模应用场合,需要转向基于ASIC 实现时,本设计也有可借鉴之处。