基于fpga 的快速傅立叶变换.doc

基于FPGA的快速傅立叶变换作者：连冰宫丰奎张力李兵兵 文章來源：国外电子元器件摘要：在对FFT (快速傅立叶变换)算法进行研究的基础上，描述了用FPGA实现FFT的方法，并对其中的整体结构、蝶形单 元及性能等进行了分析1整体结构一般情况下，N点的傅立叶变换对为：XQ)二 DFT[兀(n)]二£兀5) W# (1)n = 0X(n) = H)FT[xa)]=爲 EXQ)町必(2)/V 4 = 0其中，WN= e x p(-2 p i / N)o 乂(1<)和*(口)都为复数与之相对的快速傅立叶变换有很多种，如D I T(时域抽取 法)、D I F (频域抽取法)、Coo 1 ey — Tukey和W i n o g r a d等对于2 n傅立叶变换，Coo 1 e y — T u k e y算法可导出D I T和D I F算法本文运用的基木思想是C o o 1 e y-T u k c y算法，即将高点数的傅立叶变换通 过多垂低点数傅立叶变换來实现虽然D 1 T与D 1 F有差别，但山于它们在本质上都是…种基于标号分解的算法,故在运算 昴和算法复杂性等方面完全一样，而没有性能上的优劣之分,所以可以根据需要任取其中一种，本文主要以D I T方法为对象 來讨论。

N= 8 1 9 2点D F T的运算表达式为：8191 ・ 3 2047X(K)^ S E %(nin2) Wm (3)fi 0 nl s0n2 = 0式中，m=(4n l+n2)( 2048k l+k2)(n = 4n l+n2, k = 2(J48kl+k2 )其中 n 1 和 k 2 可収 0 ,1 , 2 0 4 7 , k 1 和 n 2 可取 0 J ,2,3 o山式(3 )可知，8 k傅立叶变换可山4 X 2 k的傅立叶变换构成同理，4 k傅立叶变换可山2 X 2 k的傅立叶变换构 成而2 k傅立叶变换可山12 8X1 6的傅立叶变换构成1 2 8的傅立叶变换可进一步山1 6 X 8的傅立叶变换构成，归 根结底，整个傅立叶变换可山基2、基4的傅立叶变换构成2 k的F F T可以通过5个基4和I个基2变换来实现；4 k的 FFT变换可通过6个基4变换來实现；8 k的FFT可以通过6个基4和1个基2变换來实现也就是说：FFT的基本结构町山基2 / 4模块、复数乘法器、存储单元和存储器控制模块构成…其整体结构如图1所示图I中，RAM用來存储输入数据、运算过程中的中间结果以及运算完成后的数据，ROM用來存储旋转因子表。

蝶形运 算单元即为基2 /4模块，控制模块可用于产生控制时序及地址信号，以控制中间运算过程及最后输出结呆T孚形运算号元— 」I弓子 控制［r6m ］ 信号2蝶形运算器的实现基4和基2的信号流如图2所示图中，若A=r0 + j * i 0 , B=rl+j*i 1, C=r2 + j*i2, D= r 3 + j * i 3是要进行变换的信号，W kO=cO+j*sO=l, Wkl=cl+j*sl,图1总体框图Wk2 = c2+j*s2, Wk3 = c3+j*s3 为旋转因子，将其分别代入图2中的基4蝶形运算单元，则有：=[T0 +( r 1 X c 1 - i 1 X s I )+( r 2 X c 2 - i 2 X s 2 )+( r 3 X cx s 3)]+j [ i0 +( iI )+( i 2 X c 2 + r 2 X s 2 )+( i 3Xc3 + r3Xs3)]0 +( i 1 X c 1 + r 1 X s 1 )-( r 2 X c 2 - i 2 X s 2)-( i 3 X cX s 3)]+j f i1 )-( i 2Xc2 + r2Xs 2) + (r3Xc3-i 3 X s 3 )1 (5)Cf =[r0 -( r 1 X c 1 - i 1 X s 1 )+( r 2 X c 2 - i 2 X s 2)-( rX s 3 )]+j [ i0 -( il)+(i 2Xc2+r2Xs2)-(i 3Xc3+r3Xs3)](0 -( i 1 X c 1 + r 1 X s 1 )-( r 2 X c 2 - i 2 X s 2 )+( iX s 3)]+j [ i0 4-( r1 )-( i 2Xc2+r2Xs 2)-(r3Xc3-i 3 X s 3 )J而在基2蝶形中，W k 0和Wk 2的值均为1,这样，将A, B, C和D的表达式代入图2中的基2运算的四个等式中,则有:2 = rO+(rlXcl-i I X s 1 )+ j [ i 0 +( i 1 X c I + r I X s I )] ( 8 )B ' = r 0 - ( r I X c I - i 1 X s 1 )+ j [ i 0 -( i 1 X c I + r I X s 1 )] ( 9 )C‘ = r2+(r3Xc3-i 3 X s 3 )+ j [ i 0 +( i 3Xc3+r3Xs3)] ( 1 0 )D‘ = r2-(r3Xc3-i 3 X s 3 )+ j [ i 0 -( i 3Xc3+r3Xs3)] ( 1 1 )在上述式(4 )〜(1 1 )中有很多类同项，如i 1 X c 1 + r 1 X s 1和r 1 X c 1 — i 1 X s 1等，它们仅仅是加减 号的不同，其结构和运算均类似，这就为简化电路提供了可能。

同时，在蝶形运算中，复数乘法可以111实数乘袪以一定的格式 來表示，这也为设计复数乘法器提供了一种实现的途径以基4为例，在其运算单元4 实际上只需做三个复数乘法运算，即只须计算BWk 1、CWk 2和DWk 3的值即可,这样在一个基4蝶形单元里面,最多只需要3个复数乘法器就可以了在实际过程中,在不提高时钟频率下，只要将时序控制便可利用流水线(Pipeline)技术并只用一个复数乘法器就可完成这三个复数乘法，大大节省了独件资源A，A =A^ BWk{ +C 妙 zBzCzDzB・=A・ jB0好■ CW竝 +- BWk{^CWkl - DWkZD =A+ jBWkx +CWJjDW*3WWkQAzCzBx=C+D炉妇BW(a)基4峡形图£基2和基4蝶形算法的信号流图(b)D夕基2蝶形=C-DWnFFT的地址F F T变换后输出的结果通常为一特定的倒序,因此，几级变换后对地址的控制必须准确无谋倒序的规律是和分解的方式密切相关的，以基8为例，其基木倒序规则如下:基8可以用2X2X2三级基2变换來表示，则其输入顺序则可用二进制序列(n 1 n 2 n 3 )來农示，变换结束后,其顺序将变为(n3n2nl),如：X 0 1 1 - x 1 1 0 ,即输入顺序为3 ,输出时顺序变为6。

更进一步，对于基1 6的变换，可由2X2X2X2, 4X4, 4X2X2等形式來构成，相对于不同的分解形式，往往 会有不同的倒序方式以4X4为例，其输入顺序可以用二进制序列(n 1 n 2 n 3 n 4 )來表示变换结束后，其顺序可变 为((n 3 n 4 ) ( n 1 n 2 )),如：X 0 111 〜x 110 1 即输入顺序为7 ,输出时顺序变为1 3在2 k / 4 k / 8 k的傅立叶变换中，山于要经过多次的基4和基2运算，因此 从每次运算完成后到进入下一次运算前, 应对运算的结果进行倒序，以保证运算的正确性4旋转因子N点傅立叶变换的旋转因了令若叨显的周期性和对称性其周期性表现为:FFT之所以可使运算效率得到提高，就是利用妙旷山=wTi对称性表现为W^m= m 或者（甲E_m）* = Wm莊防今=一F F T之所以可使运算效率得到提高，就是利用了对称性和周期性把长序列的D F T逐级分解成几个序列的D F T,并最 终以短点数变换來实现长点数变换根据旋转因子的对称性和周期性，在利用R0M存储旋转因子时,可以只存储旋转因了表的一部分，而在读出时增加读出 地址及符号的控制，这样可以正确实现FFT。

因此,充分利用旋转因子的性质，可节省7 0 %以上存储单元实际上,山于旋转因子可分解为正、余弦函数的组合，故ROM中存的值为正、余弦函数值的组合对2 k / 4 k / 8 k 的傅立叶变换來说，只是对一个周期进行不同的分割山于8 k变换的旋转因子包括了 2 k / 4 k的所有因子，因此，实现时 只要对读ROM的地址进行控制，即可实现2 k / 4 k / 8 k变换的通用5存储器的控制因FFT是为时序电路而设计的，因此,控制信号要包括时序的控制信号及存储器的读写地址,并产生各种辅助的指示信 号同时在计算模块的内部，为保证高速，所有的乘法器都须始终保持较高的利用率这意味着在每一个时钟來临时都要向这 些单元输入新的操作数,而这一切都需要控制信号的紧密配合为了实现FFT的流形运算，在运算的同时，存储器也要接收数据这可以采用乒乓RAM的方法來完成这种方式决定 了实现FFT运算的最大时间对于4 k操作,其接收时间为4 0 9 6个数据周期,这样 FFT的最大运算时间就是4 0 9 6个数据周期另外，山于输入数据是以一定的时钟为周期依次输入的，故在进行内部运算时，可以用较高的内部时钟进行运 算，然后再存入RAM依次输出。

为节省资源，可对存储数据RAM采用原址读出原址写入的方法，即在进行下一级变换的同时，首先应将结果冋写到读出 数据的R A M存贮器中：而对于ROM,则应采用与运算的数据相对应的方法來读出存储器中旋转因子的值在2 k / 4 k / 8 k傅立叶变换中，要实现通用性，控制器是最主要的模块2 k、4 k、8 k变换具有不同的内部运算时间和存储器地址，在设计中，钊•对不同的点数应设计不同的存储器存取地址，同时，在完成变换后，还要对开始输出有用信号的时刻进行指示6硬件的选择木设计的硬件实现选用的是现场可编程门阵列(FP G A)來满足较高速度的需要木系统在设计时选用的是A LTERA 公司的STRAT 1 X芯片，该芯片中包含有DSP单元，可以完成较为耗费资源的乘法器单元同时，该器件也包含有大量 存储单元，从而可保证旋转因子的持度除了一些专用引脚外，FPGA上儿乎所有的引脚均可供用户使用，这使得FPGA信号处理方案具有非常好的I /0带 宽大最的I / 0引脚和多块存储器可使设计获得优越的并行处理性能其独立的存储块可作为输入/工作存储区和结果的缓 存区，这使得I /0可与FFT计算同时进行在实现的时间方面，该设计能在4 0 9 6个时钟周期内完成一个4 0 9 6点的 F FT。

若采用1 0 MH z的输入时钟，其变换时间在2 0 Ops左右而山于最新的F PG A使用了 M u 1 t i T r a c k互 连技术，故可在2 5 0 MHz以下频率稳定地工作，同时，FFT的实现时间也可以大大缩小FFT运算结呆的粘度与输入数据的位数及运算过程中的位数有关，同时和数据的表示形式也有很大关系一般來说，浮 点方式比定点方式秸度高而在定点计算中，存储器数据的位数越大,运算楙度越高,使用的存储单元和逻辑单元也越多在 实际应用中，应根据实际情况折衷选择精度和资源木设计通过MAT LAB进行仿真证明：其实现的变换结果与MATLABH具箱中的FFT函数相比，信噪比可以达到6 5 d b以上，完全可以满足一般工程的实际应用要求。