频率抽取基4ff的fpga设计

频率抽取基4ff的fpga设计

1fft实现方法随f原理的发展分散傅里叶变换dft广泛应用于通信、控制、处理器、数据处理、生物信息、计算物理、应用数学和其他许多领域。它在各种数字处理器中起着核心作用。快速傅里叶变换FFT的提出使傅里叶变换可运用到实时场合,各种FFT的实现方法也随之出现。FFT的FPGA实现同时具有软件编程的灵活性和ASIC电路的快速性等优点,随着集成电路技术的进步和制造工艺水平的提高,FPGA芯片具有的功能愈来愈强,成为快速实时实现FFT的一种重要手段。FFT算法在实现过程中其蝶形运算需要乘以许多旋转因子,以N点的FFT来讲,具有N/2个旋转因子。现有一般FPGA的实现方式是把所有的因子存在FPGA的内部或外部的存储器中,运算时通过地址的映射读出需要的旋转因子。这种方式需要较多的存储空间,同时也增加了蝶形运算的时间。本文在对此改进的基础上,提出了一种按频率抽取基4FFT的FPGA设计方案,以提高FFT的FPGA实现速度。2基4fft的基本运算长度为N的有限长序列x(n)的DFT为:X(k)=Ν-1∑n=0x(n)WknΝ‚k=0‚1‚⋯‚Ν-1(1)X(k)=∑n=0N−1x(n)WknN‚k=0‚1‚⋯‚N−1(1)式(1)中:WknΝ=exp{-j2πkn/N}为旋转因子。上述DFT的运算中存在大量重复的乘法,Cooley和Tukey提出的快速傅里叶变换算法即基2FFT有效地减少了乘法的次数。在基2FFT的基础上,发展出基4FFT,其基本结构是每一级的运算由N/4个蝶形运算构成,迭代计算公式如式(2)。在式(2)中r从0增加到N/4-1,W2nΝ,WnΝ,W3nΝ为旋转因子。可见蝶形运算可看作基4FFT的基本运算单元,参与蝶形运算的4节点是有规律的,分别为(n),(n+N/4),(n+2N/4)和(n+3N/4)。接着再将X(4r),X(4r+1),X(4r+2),X(4r+3)分别分解成4个长度为N/42的序列,经过迭代log4N次后完成计算,整个算法的复杂度减少为O(Nlog4N)。X(4r)=Ν4∑n=0((x(n)+x(n+Ν2))WnrΝ/4+(x(n+Ν4)+x(n+3Ν4))WnrΝ/4X(4r+2)=Ν4∑n=0((x(n)+x(n+Ν2))W2nΝWnrΝ/4-(x(n+Ν4)+x(n+3Ν4))W2nΝWnrΝ/4X(4r+1)=Ν4∑n=0((x(n)-x(n+Ν2))WnΝWnrΝ/4-j(x(n+Ν4)-x(n+3Ν4))WnΝWnrΝ/4X(4r+3)=Ν4∑n=0((x(n)-x(n+Ν2))W3nΝWnrΝ/4+j(x(n+Ν4)-x(n+3Ν4))W3nΝWnrΝ/4(2)3片内蝶形运算输出数据和旋转因子设计随着IC制造工艺的发展,片内集成的晶体管数量不断增加,FPGA内的资源也日趋增多,使得可以采用乒乓结构和流水线的方式实现FFT运算,加快运算速度。本结构也基于此,输入输出采用了乒乓RAM实现。对于输入部分,其中一组存储器用于寄存片外的输人数据,另一组向片内蝶形运算器输入数据。对于输出部分,其中一组存储器用于寄存片内蝶形运算器输出的数据,另一组向片外输出数据。设计时可利用片内的锁相环设计满足片内外不同的频率要求。基4蝶形运算作为基本的运算单元,分别完成FFT对应级上的蝶形运算。对于两个蝶形运算器之间的存储器,为了节省片内资源没有使用乒乓RAM而采用双端口的RAM。因为FFT的蝶形运算为同址运算,蝶形运算器可以在前一个时钟周期接受上一级的双端口RAM输入数据,后一个时钟周期向下一级RAM输出数据。地址生成器使蝶形运算器取得对应的输入数据,并使最后的乒乓RAM输出数据时按地址倒序输出。旋转因子实现向蝶形运算器输入所需的因子值,此处改进了因子产生方式,使因子存储数目减少,蝶形运算加快,这在下面蝶形运算和旋转因子设计中做详细介绍。整体系统结构框图如图1所示。4旋转因子复合乘法器3个蝶形运算是FFT实现的关键部分,决定了FFT的速度。根据FFT的迭代运算公式,可以看出每个蝶形运算单元计算4个值,信号流图如图2所示,其运算公式如式(3)所示。A′=(A+C)+(B+D)B′=[(A+C)-(B+D)]W2nΝC′=[(A-C)-j(B-D)]WnΝD′=[(A-C)+j(B-D)]W3nΝ(3)显然蝶形运算中最占时间的是乘于旋转因子时的3个复数乘,下面介绍其通过高效复数乘法器进行复数乘的设计思想。假设其中一条复数乘为:R+jI=(X1+jY1)*(X2+jY2)则:R=X1*X2-Y1*Y2=(X2-Y2)*Y1+X2*(X1-Y1)I=X1*Y2-Y1*X2=(X2+Y2)*X1-X2*(X1-Y1)这样把原来需要4次乘法才能完成的复数乘降为3次。由FFT算法可知,复数乘中X2+jY2代表的旋转因子在计算之前就可知道,这样旋转因子可以X2+Y2和X2-Y2的形式给出,而X2=((X2+Y2)+(X2-Y2))/2,这在硬件上可以与X1-Y1并行实现,硬件实现时只需从加法器数据输出端的次低位开始取值时就可以得到X2,从而使碟形运算速度加快。5地址生成系统的设计在FFT设计中,输入数据的寻址可以是十分灵活的。对于每个蝶形运算器需要的4个输入数据,在不同的级上是不同的,设计中可以利用RAM为每级蝶形运算生成地址查找表,也可以通过计数器的形式得到,本设计采用如下的方案:首先分析FFT算法的整体信号流图,可以看出每级运算中所有的蝶形运算器被分成若干组,每组中又包含若干个蝶形运算器,输入数据的地址跟蝶形运算器所在的位置有关。假设基4蝶形运算器输入数据地址为:ADDR=Cr…C1B2B1As…A1其中:r=log2P(P为蝶形运算器的分组数);s=log2Q(Q为每组包含蝶形运算器的个数)。所以Cr,…,C1由当前运算器所在的组号决定,B2B1表示为当前运算器输入的4个数中的第几个,As,…,A1的表示当前运算器所在组里的序号。下面以64点的FFT为例讲述其设计过程。当点数为64时,FFT运算共分3级每级所需的运算器个数为16个,表示地址的二进制位是log264,共6位,其Cr,…,C1,B2B1,As,…,A1在不同级中占的位数见表1。地址生成硬件实现结构如图3所示。其中蝶形运算器序号是表示第几个运算器,对于64点的FFT共需要16个蝶形运算器,其序号为0000到1111,数据序号是表示4个数中的第几个运算数,数值为00到11中的一个数。此结构无需数据的加减运算,也不用数据位的位移操作,结构的扩充也很方便,能实现多个蝶形运算器数据的同时输入。6第一下限内旋转因子的设计在FFT的蝶形中需要乘于WknΝ(0≤kn≤N-1)这样的旋转因子,对于N点的FFT需要N/2个旋转因子,所以无论在存储上还是在运算量上都是FFT设计的重点。本文在蝶形运算中讲述了复数乘的设计方法,在乘法的实现过程中没有采用传统的读取实部和虚部(分别设为X2和Y2)来计算复乘,而是读取X2+Y2和X2-Y2,即旋转因子是以X2+Y2和X2-Y2的形式来存储的,这样可以加快计算速度。其次通过分析旋转因子之间的关系,可以看到,在其他三个象限里的旋转因子都可以通过第一象限的变化得到,这样又可以使旋转因子减少到N/4个,具体的设计过程如下:设在第一象限的旋转因子为X2+jY2,其存储值为X2+Y2和X2-Y2。由坐标的对称关系(见图4)。可得到其他三个象限里的旋转因子与第一象限中旋转因子关系,只存在数据交换和正负号的差异,如表2所示。在蝶形运算时,当需要WknΝ(0≤kn≤N-1)时,根据kn的值,在已有的第一象限值的基础上生成对应的X2+Y2和X2-Y2。如64点的FFT,其kn是大于等于0到小于等于63,即用表示kn值的数据位共有6位(d5d4d3d2d1d0),可以分为第一象限存储地址和相位两部分,结合相应的硬件得到旋转因子值,图5给出其实现的结构。图5中,kn数据位的d5d4作为象限选择,00为第一象限,01为第二象限,10为第三象限,11为第4象限。d3d2d1d0作为地址,读取存储器中第一象限的X2+Y2和X2-Y2,进过转换后生成对应象限的X2+Y2和X2-Y2,输出给蝶形运算器。通过上面的设计,只需要读取第一象限的旋转因子就可以得到所有旋转因子的值,有效减少了旋转因子存储空间的大小。7fft算法的改进本文在分