FPGA实现的基4FFT处理器高效排序算法研究

1、第37卷第2期2005年4月南京航空航天大学学报Jou rnal of N an jing U n iversity of A eronau tics &A stronau ticsA p r .2005FPGA 实现的基4FFT 处理器高效排序算法研究伍万棱,邵杰,冼楚华(南京航空航天大学信息科学与技术学院,南京,210016摘要:在FFT 处理器的设计中,蝶形处理部件是关系整个处理器运行速度与资源的核心部分。对于1024点的FFT 复数浮点运算,本文旨在提出一种高效的基4排序算法,该算法基于按时间抽取的基4FFT ,结合了流水线和并行方式的特点,利用4个循环序列进行时序控制,用3个实数乘法

2、器实现基4蝶形的3次复数乘法,相对于传统的基4FFT 算法可以节省75%的乘法器逻辑资源。实验结果表明,用该算法设计的1024点复数基4FFT 处理器在100M H z 的主时钟频率下运算速度为51129s ,满足了FFT 运算的高速实时性要求。由于该排序思想可以较方便地扩展到基8或基16,但不增加进行一次基本蝶算的时钟周期数,依然是4个,故对于高基数将具有更高的效率。关键词:FFT 处理器;基4排序算法;流水线方式;并行方式;基4蝶形中图分类号:TN 43112文献标识码:A 文章编号:100522615(2005022*基金项目:南京航空航天大学本科生科技创新基金资助项目。收稿日期:200

3、4206207;修订日期:2004211212作者简介:伍万棱,男,本科生,1982年5月生,E 2m ail :w uw anleng ho tm ail .com ;邵杰,男,高级工程师,1963年9月生;冼楚华,男,本科生,1982年8月生。Eff ic ien t Sorti ng Arch itecture for Rad ix -4FFT i n FPGAW U W an 2leng ,S H A O J ie ,X IA N Chu 2hua(Co llege of Info r m ati on Science and T echno logy ,N anjing U nive

4、rsity of A eronautics &A stronautics ,N anjing ,210016,Ch ina Abstract :T he novel so rting arch itectu re of the FFT p rocesso r is p resen ted based on radix 24deci m ati on 2in 2ti m e algo rithm .B y com b in ing bo th the p i peline and p arallel schem es ,the p ropo sed radix 24bu tterfly u se

5、s th ree real m u lti p liers and n ine real adders ,w h ich leads to reduce m u lti p liers of conven ti onal 75%.T he p rocesso r based on FPGA can op erate at 100M H z and calcu late the 1024floating 2po in t com p lex FFT in 51129s.So it satisfies the needs of bo th s m all area and h igh speed

6、.Fu rther m o re ,since the so rting arch itectu re can be easily upgraded fo r radix 28,radix 216FFT algo rithm ,and dono t increase the clock s requ ired fo r com pu ting a radix 2r bu tterfly ,it w ill be m o re efficien t fo r the h igh radix .Key words :FFT p rocesso r ;radix 24so rting arch it

7、ectu re ;p i peline schem e ;parallel schem e ;radix 24bu tterfly快速傅立叶变换(FFT 作为计算和分析工具,在众多学科领域(如信号处理、图像处理、生物信息学、计算物理、应用数学等有着广泛的应用1。在高速数字信号处理领域,如雷达信号处理,快速傅里叶变换的处理速度往往是整个系统设计性能的关键所在。硬件实现FFT 的方式主要有:(1通用数字信号处理器(D SP ;(2专用的FFT芯片;(3可编程逻辑器件(以FPGA 为代表。采用D SP 方案虽然灵活性强,但存在速度和精度之间的矛盾:若采用定点运算,舍入误差会降低最终处理结果的精度;若

8、采用浮点运算,可以消除动态范围局限的问题,但由于实现结构复杂使处理速度难以达到要求,而且系统造价较高。采用专用FFT 芯片虽然可以达到高的处理速度,但灵活性差,不易扩展。FPGA (现场可编程门阵列以高性能、高灵活性、友好的开发环境、在线可编程等特点可以使基于FPGA 的设计满足实时数字信号处理的要求2。在FFT 处理器的设计中,蝶形处理部件是关系整个处理器运行速度与资源的核心部分。在选择基4FFT 算法时,由于传统的基4蝶形处理部件需3个复数乘法器3,做一次复数乘法需4个实数乘法器,共需消耗12个实数乘法器的FPGA 片内资源,而乘法器是最占逻辑资源的,这样就造成硬件开销很大。现有的一些与传

9、统相异的基4算法,如采用流水线方式运算,用1个复数乘法器实现基4运算35,虽然节省了一部分资源,并且容易扩展至高基数,但扩展时一次基本蝶算所需的时钟周期数必然增加,如从基4扩至基8,周期数将由4个增至8个。文6与此类似。既然采取顺序做基2蝶算的方式来降低资源消耗会增加基本蝶算的时钟周期,而直接并行做3个复乘又太耗资源,因此可以走降低基2蝶算的实数乘法器再并行的途径。本文采用新颖的排序算法,使得一次基2蝶算只需1个实数乘法器,整个基4运算只消耗了3个实数乘法器,节省了75%的乘法器逻辑资源。为达到高速的设计要求,本文设计采用A ltera 公司的M ercu ry 系列芯片EP 1M 120F

10、484C 5,在Q uartu s 开发平台上实现32b it 的1024点FFT复数浮点运算。系统的结构功能框图如图1所示 。图1系统的结构功能框图1排序算法与传统的基4FFT 算法111传统的基4FFT 算法与实现传统的基4算法是用3个复数乘法器,如图2所示(3个W 表示参与复乘的旋转因子。每次复数乘法用4个实数乘法器,如式(1,2所示。输入数据x r +j x i 与旋转因子co s -jsin 相乘的公式为图2传统的基4FFT 基本运算的信号流图y r =x r co s +x i sin (1j y i =j (x i co s -x r sin (2如此将基4算法的计算结构直接影射

11、至硬件来实现3次复乘,需消耗大量的乘法器逻辑资源(共需12个实数乘法器3。112基4FFT 排序算法基4FFT 基本运算的公式7为A1=A +BWk 1N +CW k 2N +DW k 3N (3B 1=A -j B Wk 1N-CW k 2N+j D k 3N(4C 1=A -BWk 1N +CWk 2N -DW k 3N (5D 1=A +j B Wk 1N -CW k 2N-j D Wk 3N(6式中A ,B ,C 和D 为复数操作数,A 1,B 1,C 1和D 1为一次基4蝶形运算的结果,W k 1N,Wk 2N和W k 3N为参与基4蝶形运算的旋转因子。令A =x +j X (7B

12、=y +j Y (8C =p +j P (9D =q +j Q (10W k 1N=co s 2k 1N-jsin 2k 1N(11W k 2N=co s 2k 2N-jsin 2k 2N(12Wk 3N=co s2k 3N-jsin2k 3N(13则A 1,B 1,C 1和D 1可表示为A1=x 1+j X1(14B 1=y 1+j Y 1(15C 1=p 1+j P1(16D 1=q 1+j Q1(17其中x 1=x +y co s (2k 1 N +Y sin (2k 1 N +p co s (2k 2 N +P sin (2k 2 N +q co s (2k 3 N +Q sin (2

13、k 3 N (18p 1=x -y co s (2k 1 N +Y sin (2k 1 N +p co s (2k 2 N +P sin (2k 2 N -q co s (2k 3 N +Q sin (2k 3 N (19322第2期伍万棱,等:FPGA 实现的基4FFT 处理器高效排序算法研究X1=X+Y co s(2k1 N-y sin(2k1 N+ P co s(2k2 N-p sin(2k2 N+Q co s(2k3 N-q sin(2k3 N(20P1=X-Y co s(2k1 N-y sin(2k1 N+ P co s(2k2 N-p sin(2k2 N-Q co s(2k3 N-

14、q sin(2k3 N(21y1=x+Y co s(2k1 N-y sin(2k1 N-p co s(2k2 N+P sin(2k2 N-Q co s(2k3 N-q sin(2k3 N(22q1=x-Y co s(2k1 N-y sin(2k1 N-p co s(2k2 N+P sin(2k2 N+Q co s(2k3 N-q sin(2k3 N(23Y1=X-y co s(2k1 N+Y sin(2k1 N-P co s(2k2 N-p sin(2k2 N+q co s(2k3 N+Q sin(2k3 N(24Q1=X+y co s(2k1 N+Y sin(2k1 N-P co s(2k2

15、 N-p sin(2k2 N-q co s(2k3 N+Q sin(2k3 N(25观察x1和p1,X1和P1,y1和q1,Y1和Q1四组的具体表达式,可以发现它们对应的实部和虚部中括号内的内容相同,因此可以考虑充分利用FPGA 片内的大量寄存器,将流水线方式3与并行结构8的思想巧妙地结合起来,用4个循环序列对各寄存器进行严格的时序控制,只用一个实数乘法器来实现一次复数乘法;对应于3个不同的复乘用3个实数乘法器,而这3个复乘又是并行的,最后将3个并行结果相加即可。对应的排序方法见表1,2,对应的逻辑结构如图3所示。表1对应的排序方法循环序列RAM读取ROM读取RAM写入s1RAM2读取pRAM

16、3读取yRAM4读取qROM1读取co s(2k3 NROM2读取co s(2k2 NROM3读取co s(2k1 Np1,y1写入RAMs2RAM2读取PRAM3读取YRAM4读取QROM1读取sin(2k3 NROM2读取sin(2k2 NROM3读取sin(2k1 NP1,Y1写入RAMs3RAM1读取x ROM1读取co s(2k3 NROM2读取co s(2k2 NROM3读取co s(2k1 Nx1,q1写入RAMs4RAM1读取X ROM1读取sin(2k3 NROM2读取sin(2k2 NROM3读取sin(2k1 NX1,Q1写入RAM表2各排序模块在各时刻输出的结果序列排序

17、模块2排序模块4排序模块6s1-Q co s(2k3 N-q sin(2k3 N-p co s(2k2 N+P sin(2k2 N+Y co s(2k1 N-y sin(2k1 Ns2+q co s(2k3 N+Q sin(2k3 N-P co s(2k2 N-p sin(2k2 N-y co s(2k1 N+Y sin(2k1 Ns3+Q co s(2k3 N-q sin(2k3 N-p co s(2k2 N+P sin(2k2 N-Y co s(2k1 N-y sin(2k1 Ns4-q co s(2k3 N+Q sin(2k3 N-P co s(2k2 N-p sin(2k2 N+y c

18、o s(2k1 N+Y sin(2k1 N序列排序模块3排序模块5排序模块7s1-q co s(2k3 N+Q sin(2k3 N+p co s(2k2 N+P sin(2k2 N-y co s(2k1 N+Y sin(2k1 Ns2-Q co s(2k3 N-q sin(2k3 N+P co s(2k2 N-p sin(2k2 N-Y co s(2k1 N-y sin(2k1 Ns3+q co s(2k3 N+Q sin(2k3 N+p co s(2k2 N+P sin(2k2 N+y co s(2k1 N+Y sin(2k1 Ns4+Q co s(2k3 N-q sin(2k3 N+P c

19、o s(2k2 N-p sin(2k2 N+Y co s(2k1 N-y sin(2k1 N 422南京航空航天大学学报第37卷 (a (b 图3排序模块1的复乘运算2基4排序算法逻辑实现结构的工作流程RAM 1,RAM 2,RAM 3和RAM 4为容量大小相等的参数化共享式双端口RAM ,对于x 1,X 1,y 1,Y 1,p 1和P 1的读地址,经过变址运算,在4个时钟周期后作为写地址输出,而对于q 1和Q 1则须在5个时钟周期后,由该写地址确定写入哪一片RAM 以及该片RAM 中的具体位置。循环序列s 1,s 2,s 3,s 4输入各个排序模块、寄存器和数据选择器,对它们进行时序控制。蝶

20、形计算结构的工作流程如下:见表1,在s 1时刻,从各RAM 读取B ,C ,D 的实部,各ROM 读取W k 1N ,W k 2N ,W k 3N 的虚部,在s 2时刻,从各RAM 读取B ,C ,D 的虚部,各ROM 读取W k 1N ,W k 2N ,W k 3N 的虚部,然后由各数据选择器对实部和虚部做出时序选择,送对应的排序模块进行第一层次的乘法和加法运算,并锁存中间结果,该层运算的体系结构对于3个复乘都是相同的,所以在s 1,s 2,s 3,s 4各时刻的结果相同,均为图4中的排序模块1(复乘实现见图3;以上各时刻的中间产物需经进一步的寄存操作以改变符号才能最后相加,所以有了第二层次

21、的排序模块。这些排序模块在s 1,s 2, s 3,s 4各时刻输出的产物各不相同,如表2所示。然后将序号为偶数(2,4,6和序号为奇数(3,5,7的模块在各时刻的结果分别相加,即可得到相应时刻的两个运算结果。4个时钟周期内可将4组共8个数据写进RAM 。排序模块1包含了1个实数乘法器、1个实数加法器、若干个寄存器和1个自定义非门,排序模图4基4排序算法对应的逻辑结构框图块2,3,4,5,6,7为数据选择器、寄存器和自定义非门的有机时序结合,则整个基4蝶形处理只含3个实数乘法器和9个实数加法器;由于加法器所耗资源要远少于乘法器,而传统的基4蝶形处理器需消耗3个复数乘法器(即12个实数乘法器和8

22、个复数加法器,故该计算部件节省了75%的乘法器资源。由于传统的基4蝶形结构虽然3次复乘为并行,但输出4个复数计算结果是串行,同样需4个时钟周期6,故本文算法并无速度损失,保持了基4算法应有的优势。与文2用2个实数乘法器实现基2蝶算相比,本文只用了1个,资源得到进一步降低,适应了基4蝶形的并行计算。3结论实验结果表明:用该算法设计的1024点基4FFT 处理器在100M H z 的系统时钟频率下处理速度为51129s 。与各种结构的计算时间对比见表3。可见,本文算法具有较高的效率。另外,本文提出的排序思想由于时序控制特点可以较方便地扩展,但不增加进行一次基本蝶形运算(如作一次基8或基16的蝶形运

23、算的时钟周期数,依然是4个,只需增加4个实数乘法器即可实现基8蝶算,速度就将大大提高。故该算法对于高基数将具有更高的效率。522第2期伍万棱,等:FPGA 实现的基4FFT 处理器高效排序算法研究表3与文9中各种结构的1024点FFT计算时间比较各种结构系统主频M H z计算时间s本文算法10051129文9算法80187368111 X ilinx FFT Co re708916Amph i on FFT578918AD SP221161N10090D EC2A lpha EV56 21164A50095162TM S320C67X2(R adix24166108163TM S320C67X

24、2(R adix2216612413参考文献:FFT处理器的研究J.北京理工大学学报,2003,(3:381385.3J ia L,Gao Y,T enhunen H.Efficient VL S Ii m p lem entati on of radix28FFT algo rithmA.P roceedings of the1999IEEE Pacific R i mConference on Comm unicati ons,Computers andSignal P rocessingC.V icto ria,BC,U SA:IEEE,1999.468471.4J ia L ihong

25、,Gao Yonghong,T enhunen H.A p i pelinedshared2m emo ry arch itecture fo r FFT p rocesso rsA.42nd M idw est Sympo sium on C ircuits andSystem sC.2000,(2:804807.5W u W ei,Ch in Shu2Sh in,Hong Sangjin.A coarse2grained FPGA arch itecture fo r reconfigurablebaseband modulato r demodulato rA.ConferenceR eco rd of the T h irty2S