基于fpga的大分数二维ff方法

基于fpga的大分数二维ff方法

0伪随机序列换能力fft是信号分析和处理中的一个重要变化。随着通信、雷达技术的发展,特别是CDMA技术的兴起,伪随机序列的捕获问题对系统的FFT变换能力要求越来越高。对于较短的伪随机序列,普通的一维FFT方法在pipeline、多通道等技术的改进下可以实现实时处理,然而对于超长序列,如GPS的P码,不仅周期长而且速率高,如此一来这些方法便显得无能为力了。在这种情况下二维FFT被重视起来,并被一些设计者成功地用于解决长序列的实时处理问题,然而如果能像一维FFT的多通道技术一样,将二维FFT加上并行算法,必然可以大大提高其处理能力。1由n点的fft转换为二维分解长度为N的有限长序列x(n)的DFT为:X(k)=Ν-1∑n=0x(n)WknΝ‚k=0‚1‚⋯‚Ν-1(1)式中:WknΝ=exp{j2πkn/N}为旋转因子。令N=N1N2,将x(n)分解为N2个长度为N1序列,令n和k的序号映射定义为:n=N2n1+n20≤n1≤N1-1,0≤n2≤N2-1(2)k=k1+N1k20≤k1≤N1-1,0≤k2≤N2-1(3)则N点DFT可表示为:X(k)=X(k1+Ν1k2)=Ν2-1∑n2=0Ν1-1∑n1=0x(Ν2n1+n2)×W(Ν2-k1n1)ΝWk1n2ΝWΝ1k2n2ΝWΝ1Ν2k2n1n=Ν2-1∑n2=0{[Ν1-1∑n1=0x(Ν2n1+n2)Wn1k1Ν1Wk1n2Ν}Wn2k2Ν2(4)设G(n2,k1)=Ν1-1∑n1=0x(Ν2n1+n2)Wn1k1Ν1,则可以看出,大点数N点FFT被转换为二维处理,由两个N1和N2点的一维FFT先后完成,可以大大节省内部存储器。如果对大点数N经过一次分解得到的N1和N2仍然较大,则可以继续进行二维分解,然而这样使得控制部分的逻辑变得非常复杂,不利于FPGA的有效实现。但N1和N2的快速计算仍然需要解决,此时可以考虑使用并行的FFT算法。2xk评分观察如图1所示的标准的16点DIF。第一级是由间隔8行的两行计算而成,第二级是由间隔4行计算而成,可以发现每一级的相关项在靠近。在第二级处可以看到数据已经成为相互独立的4项,因此可以考虑相互独立的计算单元来并行的计算它们,这就是并行FFT的思想。在计算通信领域关于并行FFT已经提出了很多算法,其中一种方法就是将要计算的数值分组用不同的处理器来计算(如对于16点的情况可以分成4组),但是由于第一级各组之间并不是独立的,所以需要特别的模块来控制这种通信。也有一些方法不需要第一级的数据交换,但是在计算完第一级后需要对其结果进行适当的处理才能开始第二级的计算。考虑将输出X(k)分为4个部分,那么N点的DFT可以分解为:X(4k)=Ν-1∑n=0x[n]W(4k)nΝ(5)X(4k+1)=Ν-1∑n=0x[n]W(4k+1)nΝ(6)X(4k+2)=Ν-1∑n=0x[n]W(4k+2)nΝ(7)X(4k+3)=Ν-1∑n=0x[n]W(4k+3)nΝ(8)因为FFT的4个输出各自需要4个输入,因此式(5)～(8)需要相互独立的输入数据组。所以再对X(4k)进行分解:X(4k)=Ν-1∑n=0x[n]W(4k)nΝ=Ν/4-1∑n=0x[n]W4knΝ+Ν/2-1∑n=Ν/4x[n]W4knΝ+3Ν/4-1∑n=Ν/2x[n]W4knΝ+Ν-1∑n=3Ν/4x[n]W4knΝ(9)变量代换后有:X(4k)=Ν/4-1∑n=0x[n]W4knΝ+Ν/4-1∑n=0x[n+Ν/4]W4knΝWkΝΝ+Ν/4-1∑n=0x[n+Ν/2]W4knΝW2kΝΝ+Ν/4-1∑n=0x[n+3Ν/4]W4knΝW3kΝΝ(10)因为WΖkΝΝ=1,WΖknΝ=WknΝ/Ζ,其中Z为整数,则式(10)变为:X(4k)=Ν/4-1∑n=0(x[n]+x[n+Ν/4]+x[n+Ν/2]+x[n+3Ν/4])WknΝ/4(11)同理其余3个输出可以变为:X(4k+1)=Ν/4-1∑n=0(x[n]-jx[n+Ν/4]+x[n+Ν/2]+jx[n+3Ν/4])WknΝ/4WnΝ(12)X(4k+2)=Ν/4-1∑n=0(x[n]-x[n+Ν/4]+x[n+Ν/2]-x[n+3Ν/4])WknΝ/4W2nΝ(13)X(4k+3)=Ν/4-1∑n=0(x[n]+jx[n+Ν/4]-x[n+Ν/2]-jx[n+3Ν/4])WknΝ/4W3nΝ(14)令:a0[n]=x[n]+x[n+N/4]+x[n+N/2]+x[n+3N/4])(15)a1[n]=(x[n]-jx[n+N/4]+x[n+N/2]+jx[n+3N/4])WknΝ/4WnΝ(16)a2[n]=(x[n]-x[n+N/4]+x[n+N/2]-x[n+3N/4])WknΝ/4W2nΝ(17)a3[n]=(x[n]+jx[n+N/4]-x[n+N/2]-jx[n+3N/4])WknΝ/4W3nΝ(18)代入上面的结果则得到:X(4k)=Ν/4-1∑n=0a0[n]WknΝ/4(19)X(4k+1)=Ν/4-1∑n=0a1[n]WknΝ/4(20)X(4k+2)=Ν/4-1∑n=0a2[n]WknΝ/4(21)X(4k+3)=Ν/4-1∑n=0a3[n]WknΝ/4(22)观察式(18)～(22)发现这时的结果即是各组的DFT的结果,并且它们的旋转因子相同,故它们可以各自独立的从并行的FFT模块计算得出。唯一需要另外计算的就是{a0[n],a1[n],a2[n],a3[n]},它们其实可以通过修正过旋转因子传统4点的蝶形运算单元计算,如图2,它的旋转因子可以从a的表达式获得。这个结果和混合基FFT方法是相当的。采用并行方法实现FFT的最大好处便在于能够获得比传统方法更大的吞吐量,同时,因为并行通道公用了逻辑和内存单元从而获得了超线性的加速(吞吐量提高K倍而使用的硬件资源却小于原先的K倍)。本文讨论的是4通道并行FFT,实际上在具体实现中可以实现任意通道数目。很明显此种并行的思想可以在硬件资源允许的情况下极大的提高吞吐量,它提供了在硬件资源和处理速度之间取舍的途径。本文的4并行FFT算法用VHDL实现写入ALTERA公司的StratixEP1S80并将结果与单通道的FFT对比,结果见表1。所有计算采用固定点数18位精度。吞吐量即每秒钟的采样数,可以由时钟速率乘以并行通道数目获得。由表可见4并行的FFT用的硬件资源仅仅是单通道的2～3倍但却在基本相同的时钟速率下运算时间缩短为原先的1/4。3并行fft算法与单通道算法的比较针对VLSI的多片联合并行多通道技术及针对FPGA的单片并行多通道技术已经被一些有实力的公司研究出来,相关的使用文档也公开发行,然而它们很少涉及到详细的内部结构。本文从FFT的理论公式出发,推导