频分分路中高速FFT的实现

摘    要：本文介绍了多相阵列FFT在星上多载波数字化分路中的应用，并针对星上处理的实时高速处理要求，提出了一种FFT的实现方案，并用一片FPGA芯片验证了其正确性和可行性。
关键词：FFT；FPGA；频分分路

多载波信号的数字化分路是卫星通信星上处理技术的关键技术之一，数字化分路技术主要有并行滤波器组分路、树形滤波器组分路和多相阵列FFT分路三种。在通道数较多时，多相阵列FFT有效地使用了抽取技术，且FFT算法具有很高的计算效率，本文所讨论的就是该方法中FFT的实现。

FFT方案的确定
本文所实现的是32点复数FFT，FFT运算输入为含有32路合路信号信息的连续串行数据流，数据率为40M波特，每32个数据为一组，每隔32个时钟周期又是一组新的数据，FFT运算的输出也是32个数据为一组的连续串行数据流，对应频分分路后的32路信号的数据信息。输入/输出数据的数据率和FFT内部的时钟计算频率数值是相等的，这要求FFT的前端部分必须在32个时钟周期内完成对一组数据的处理，以保证不造成其后一组数据的“丢失”。星上多载波数字化分路是实时超高速、大规模运算场合，所以FFT运算的处理时间是首要因素，结合这些要求，本设计采用时域抽取的基2算法，在硬件结构上采用级联结构来实现。

硬件实现
运算架构
总体运算框图如图1所示。
输入的串行数据流(复数数据)经过倒序模块输出两路并行数据，经过五级蝶形运算后，输出一路串行的复数数据。每级的蝶形运算由一个蝶形运算单元完成，前一级蝶形运算的输出直接送给后一级运算，这样对整个FFT模块来说，当进行第一轮数据运算时，前一级的运算开始后，后一级要等待一段时间才能开始运算。从第二轮数据运算开始，每级蝶形运算都有数据在进行运算，一直处于“忙”状态，资源得到了充分利用。倒序模块较为简单，这里不作叙述。
各级蝶形运算的实现
蝶形运算单元是每级运算的核心单元，如图2所示，其信号关系如下：
X＝A+B*                              (1)
 Y＝A-B*                      (2)
式中为旋转因子，第一级运算的旋转因子只有一种形式，为=1，第二级运算的旋转因子有两种形式，为、，后者等于－j，容易推知这两级蝶形运算主要是完成复数加减运算。实现框图如图3所示。
下面分析第一级运算的时序(见图4)，这里着重分析从第一组数据输入到第一组数据输出的时序操作，后面各级的分析类同。计数模块主要用于表示时钟的次序，让一个信号量sel从0到31循环计数。第一个时钟(sel=0)将第一组输入数据din1、din2映射到底层模块进行运算，可得到结果dout1、dout2，第二个时钟(sel=1)负责运算第二组数据din3、din4，可得到结果dout3、dout4，同时顶层模块将底层模块送上来的第一组结果dout1、dout2保存。依此类推，在第四个(sel=3)时钟，顶层模块已经保存了前两组运算结果dout1、dout2、dout3、dout4，正是第二级第一次蝶形运算的两个输入数据(dout1、dout3)的来源，这时候即可输出第一级的第一组输出dout1、dout3。
与第一级不同的是，第二级运算模块虽然也是只进行加减运算，但是根据前面的分析，这一级旋转因子有1和-j两种形式，所以相应加减运算也有两种。对应地，在这一级的底层模块运算分两种不同的方式，故在顶层模块加一个控制字，底层模块根据该控制字来判断进行哪种运算，这一点实现简单，这里不再赘述。
第二级的计数模块和第一级是一样的，所以对于第二级来说，在sel=4时才有第一组输入数据，第二级运算的时序分析类似于第一级，从第五个时钟(sel=4)将本级第一组输入数据din1、din2映射到底层模块运算，得到结果dout1和dout2，sel=5将第一组运算结果dout1、dout2映射给顶层保存。依此类推，sel=8时，顶层模块已保存了三组运算结果dout1、dout2、dout3、dout4、dout5、dout6，从此时钟开始输出本级的第一组输出数据dout1、dout5(第三级的第一次蝶形运算的两个输入数据)。
从第三级开始，旋转因子中有复数形式出现，如第三级的旋转因子为、、、，其中、是复数数据，所以后三级蝶形运算涉及到复数乘法，其实现框图如图5所示。                            
第三级运算的时序分析：由第二级的时序分析可知，sel=9时本级即可开始运算，所以第一组旋转因子应该在sel=8时代入，由于有复数乘法，所以要在顶层模块就得到蝶形运算的第一组结果，与前面两级相比需要多几个时钟周期。在sel=15时，顶层模块得到第一组蝶形运算结果。同样地，为了使本级的输出适合下一级蝶形运算，需要等待好几组运算结果后才能输出本级的第一组输出数据。sel=20时，第三级输出第一组数据。
第四级和第五级的时序分析类似第三级，只是第五级的输出是一路数据(整个FFT运算的最终结果)，这里不再赘述。
数据精度控制
由(1)、(2)两式容易得出如下不等式：
                  
(3)
从(3)式可以看出，各级蝶形运算后输出的值一般是逐级增大的，所以在运算中需要扩位。如前所述，第一级和第二级的蝶形运算主要是加减运算，其输出数据只需扩展一位。而从第三级开始，旋转因子开始有复数出现，而且其实部和虚部都是小数，在硬件实现中是不能表示小数的，在计算代入的时候都是放大若干倍后的整数，运算完要缩小一定的倍数，即某些运算环节的数据需要进行一定的截位处理(缩小)。显然，进行截位处理会给运算带来误差，截位处理的原则是前面级的运算作较少的截位处理，尽量将较长的截位处理放在最后一级进行，保证整个FFT运算的精度达到要求。
设计优化
在FPGA设计中，首先要保证指标达到要求，在此前提下，尽可能优化设计，减少设计占用资源。在旋转因子的量化上，在尽可能少的数据位数和使运算保持尽可能高的精度这两点上做一下权衡，尽可能节省硬件资源。
在蝶形运算中，对于输入数据与旋转因子，要在某一个时钟得到其运算结果，需要4个实数乘法器和2个实数加法器，做一下变换得到如下结果：
                             
(4)
                             
(5)
即可以用3个实数乘法器和5个实数加法器实现复乘，在FPGA的硬件实现中，一个阵列乘法器所需要的资源远远大于加法器，所以用(4)、(5)来实现复乘以节省资源。
因为Quartus II软件本身对VHDL语言的综合能力不强，所以设计完成后，可以先用Synplify软件对设计进行编译综合，然后将相应的vqm文件在Quartus II 软件下编译综合和适配，可以达到占用较少的芯片资源和较高的最高时钟频率fmax。

仿真验证及结论
本设计选用一片Altera公司的Stratix系列EP1S20芯片实现，它内嵌大量的DSP块(包括硬件乘法器/硬件累加器和流水线结构)，适合于高速数字信号处理和各类算法的实现。本设计的编译结果为：逻辑资源(LEs)占用32％，DSP块资源占用65％，最高时钟频率fmax=85.3MHz。图6为Quartus II软件环境下的时序仿真结果，输入是经过倒序处理的两路12bit的复数数据data1re、data1im和data2re、data2im，输出为16bit的一路复数数据doutputre、doutputim，第一轮运算从第一组数据输入到第五级输出第一组FFT运算结果只延时了44个时钟周期，此后便是连续输出的串行数据流。由仿真可知该设计达到了实时高速处理要求，实现了预期目标。■

 参考文献
1 褚振勇,翁木云．FPGA设计及应用. 西安：西安电子科技大学出版社，2002
2 戴明桢．数字信号处理的硬件实现. 北京：航空工业出版社，1998
3 侯伯亨，顾新．VHDL硬件描述语言与数字逻辑电路设计.西安：西安电子科技大学出版社，2000
4 丁玉美，高西全．数字信号处理. 西安电子科技大学出版社, 2001

(收稿日期：2003-07-22)