基于FPGA的快速傅立叶变换

2007-03-09 19:03:27来源: 互联网
摘要:在对FFT(快速傅立叶变换)算法进行研究的基础上,描述了用FPGA实现FFT的方法,并对其中的整体结构、蝶形单元及性能等进行了分析。 关键词:FPGA FFT 傅立叶变换是数字信号处理中的基本操作,广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数N的平方成正比关系,因此,在N较大时,直接应用DFT算法进行谱变换是不切合实际的。然而,快速傅立叶变换技术的出现使情况发生了根本性的变化。本文主要描述了采用FPGA来实现2k/4k/8k点FFT的设计方法。 1 整体结构 一般情况下,N点的傅立叶变换对为: 其中,WN=exp(-2 pi/N)。X(k)和x(n)都为复数。与之相对的快速傅立叶变换有很多种,如DIT(时域抽取法)、DIF(频域抽取法)、Cooley-Tukey和Winograd等。对于2n傅立叶变换,Cooley-Tukey算法可导出DIT和DIF算法。本文运用的基本思想是Cooley-Tukey算法,即将高点数的傅立叶变换通过多重低点数傅立叶变换来实现。虽然DIT与DIF有差别,但由于它们在本质上都是一种基于标号分解的算法,故在运算量和算法复杂性等方面完全一样,而没有性能上的优劣之分,所以可以根据需要任取其中一种,本文主要以DIT方法为对象来讨论。 N=8192点DFT的运算表达式为: 式中,m=(4n1+n2)(2048k1+k2)(n=4n1+n2,k=2048k1+k2)其中n1和k2可取0,1,...,2047,k1和n2可取0,1,2,3。 由式(3)可知,8k傅立叶变换可由4%26;#215;2k的傅立叶变换构成。同理,4k傅立叶变换可由2%26;#215;2k的傅立叶变换构成。而2k傅立叶变换可由128%26;#215;16的傅立叶变换构成。128的傅立叶变换可进一步由16%26;#215;8的傅立叶变换构成,归根结底,整个傅立叶变换可由基2、基4的傅立叶变换构成。2k的FFT可以通过5个基4和1个基2变换来实现;4k的FFT变换可通过6个基4变换来实现;8k的FFT可以通过6个基4和1个基2变换来实现。也就是说:FFT的基本结构可由基2/4模块、复数乘法器、存储单元和存储器控制模块构成,其整体结构如图1所示。 图1中,RAM用来存储输入数据、运算过程中的中间结果以及运算完成后的数据,ROM用来存储旋转因子表。蝶形运算单元即为基2/4模块,控制模块可用于产生控制时序及地址信号,以控制中间运算过程及最后输出结果。 2 蝶形运算器的实现 基4和基2的信号流如图2所示。图中,若A=r0+j*i0,B=r1+j*i1,C=r2+j*i2,D=r3+j*i3是要进行变换的信号,Wk0=c0+j*s0=1,Wk1=c1+j*s1,Wk2=c2+j*s2,Wk3=c3+j*s3为旋转因子,将其分别代入图2中的基4蝶形运算单元,则有: A′=[r0+(r1%26;#215;c1-i1%26;#215;s1)+(r2%26;#215;c2-i2%26;#215;s2)+(r3%26;#215;c3-i3%26;#215;s3)]+j[i0+(i1%26;#215;c1+r1%26;#215;s1)+(i2%26;#215;c2+r2%26;#215;s2)+(i3%26;#215;c3+r3%26;#215;s3)]  (4) B′=[r0+(i1%26;#215;c1+r1%26;#215;s1)-(r2%26;#215;c2-i2%26;#215;s2)-(i3%26;#215;c3+r3%26;#215;s3)]+j[i0-(r1%26;#215;c1-i1%26;#215;s1)-(i2%26;#215;c2+r2%26;#215;s2)+(r3%26;#215;c3-i3%26;#215;s3)]  (5) C′=[r0-(r1%26;#215;c1-i1%26;#215;s1)+(r2%26;#215;c2-i2%26;#215;s2)-(r3%26;#215;c3-i3%26;#215;s3)]+j[i0-(i1%26;#215;c1+r1%26;#215;s1)+(i2%26;#215;c2+r2%26;#215;s2)-(i3%26;#215;c3+r3%26;#215;s3)] (6) D′=[r0-(i1%26;#215;c1+r1%26;#215;s1)-(r2%26;#215;c2-i2%26;#215;s2)+(i3%26;#215;c3+r3%26;#215;s3)]+j[i0+(r1%26;#215;c1-i1%26;#215;s1)-(i2%26;#215;c2+r2%26;#215;s2)-(r3%26;#215;c3-i3%26;#215;s3)] (7) 而在基2蝶形中,Wk0和Wk2的值均为1,这样,将A,B,C和D的表达式代入图2中的基2运算的四个等式中,则有: A′=r0+(r1%26;#215;c1-i1%26;#215;s1)+j[i0+(i1%26;#215;c1+r1%26;#215;s1)] (8) B′=r0- (r1%26;#215;c1-i1%26;#215;s1)+j[i0-(i1%26;#215;c1+r1%26;#215;s1)]  (9) C′=r2+(r3%26;#215;c3-i3%26;#215;s3)+j[i0+(i3%26;#215;c3+r3%26;#215;s3)] (10) D′=r2-(r3%26;#215;c3-i3%26;#215;s3)+j[i0-(i3%26;#215;c3+r3%26;#215;s3)] (11) 在上述式(4)~(11)中有很多类同项,如i1%26;#215;c1+r1%26;#215;s1和r1%26;#215;c1-i1%26;#215;s1等,它们仅仅是加减号的不同,其结构和运算均类似,这就为简化电路提供了可能。同时,在蝶形运算中,复数乘法可以由实数乘法以一定的格式来表示,这也为设计复数乘法器提供了一种实现的途径。 以基4为例,在其运算单元中,实际上只需做三个复数乘法运算,即只须计算BWk1、CWk2和DWk3的值即可,这样在一个基4蝶形单元里面,最多只需要3个复数乘法器就可以了。在实际过程中,在不提高时钟频率下,只要将时序控制好便可利用流水线(Pipeline)技术并只用一个复数乘法器就可完成这三个复数乘法,大大节省了硬件资源。 图2 基2和基4蝶形算法的信号流图 3 FFT的地址 FFT变换后输出的结果通常为一特定的倒序,因此,几级变换后对地址的控制必须准确无误。 倒序的规律是和分解的方式密切相关的,以基8为例,其基本倒序规则如下: 基8可以用2%26;#215;2%26;#215;2三级基2变换来表示,则其输入顺序则可用二进制序列(n1 n2 n3)来表示,变换结束后,其顺序将变为(n3 n2 n1),如:X011→ x110,即输入顺序为3,输出时顺序变为6。 更进一步,对于基16的变换,可由2%26;#215;2%26;#215;2%26;#215;2,4%26;#215;4,4%26;#215;2%26;#215;2等形式来构成,相对于不同的分解形式,往往会有不同的倒序方式。以4%26;#215;4为例,其输入顺序可以用二进制序列(n1 n2 n3 n4)来表示变换结束后,其顺序可变为((n3 n4)(n1 n2)),如: X0111→ x1101。即输入顺序为7,输出时顺序变为13。 在2k/4k/8k的傅立叶变换中,由于要经过多次的基4和基2运算,因此,从每次运算完成后到进入下一次运算前,应对运算的结果进行倒序,以保证运算的正确性。 4 旋转因子 N点傅立叶变换的旋转因子有着明显的周期性和对称性。其周期性表现为: FFT之所以可使运算效率得到提高,就是利用 FFT之所以可使运算效率得到提高,就是利用了对称性和周期性把长序列的DFT逐级分解成几个序列的DFT,并最终以短点数变换来实现长点数变换。 根据旋转因子的对称性和周期性,在利用ROM存储旋转因子时,可以只存储旋转因子表的一部分,而在读出时增加读出地址及符号的控制,这样可以正确实现FFT。因此,充分利用旋转因子的性质,可节省70%以上存储单元。 实际上,由于旋转因子可分解为正、余弦函数的组合,故ROM中存的值为正、余弦函数值的组合。对2k/4k/8k的傅立叶变换来说,只是对一个周期进行不同的分割。由于8k变换的旋转因子包括了2k/4k的所有因子,因此,实现时只要对读ROM的地址进行控制,即可实现2k/4k/8k变换的通用。 5 存储器的控制 因FFT是为时序电路而设计的,因此,控制信号要包括时序的控制信号及存储器的读写地址,并产生各种辅助的指示信号。同时在计算模块的内部,为保证高速,所有的乘法器都须始终保持较高的利用率。这意味着在每一个时钟来临时都要向这些单元输入新的操作数,而这一切都需要控制信号的紧密配合。 为了实现FFT的流形运算,在运算的同时,存储器也要接收数据。这可以采用乒乓RAM的方法来完成。这种方式决定了实现FFT运算的最大时间。对于4k操作,其接收时间为4096个数据周期,这样FFT的最大运算时间就是4096个数据周期。另外,由于输入数据是以一定的时钟为周期依次输入的,故在进行内部运算时,可以用较高的内部时钟进行运算,然后再存入RAM依次输出。 为节省资源,可对存储数据RAM采用原址读出原址写入的方法,即在进行下一级变换的同时,首先应将结果回写到读出数据的RAM存贮器中;而对于ROM,则应采用与运算的数据相对应的方法来读出存储器中旋转因子的值。 在2k/4k/8k傅立叶变换中,要实现通用性,控制器是最主要的模块。2k、4k、8k变换具有不同的内部运算时间和存储器地址,在设计中,针对不同的点数应设计不同的存储器存取地址,同时,在完成变换后,还要对开始输出有用信号的时刻进行指示。 6 硬件的选择 本设计的硬件实现选用的是现场可编程门阵列(FPGA)来满足较高速度的需要。本系统在设计时选用的是ALTERA公司的STRATIX芯片,该芯片中包含有DSP单元,可以完成较为耗费资源的乘法器单元。同时,该器件也包含有大量存储单元,从而可保证旋转因子的精度。 除了一些专用引脚外,FPGA上几乎所有的引脚均可供用户使用,这使得FPGA信号处理方案具有非常好的I/O带宽。大量的I/O引脚和多块存储器可使设计获得优越的并行处理性能。其独立的存储块可作为输入/工作存储区和结果的缓存区,这使得I/O可与FFT计算同时进行。在实现的时间方面,该设计能在4096个时钟周期内完成一个4096点的FFT。若采用10MHz的输入时钟,其变换时间在200μs左右。而由于最新的FPGA使用了MultiTrack互连技术,故可在250MHz以下频率稳定地工作,同时,FFT的实现时间也可以大大缩小。 FFT运算结果的精度与输入数据的位数及运算过程中的位数有关,同时和数据的表示形式也有很大关系。一般来说,浮点方式比定点方式精度高。而在定点计算中,存储器数据的位数越大,运算精度越高,使用的存储单元和逻辑单元也越多。在实际应用中,应根据实际情况折衷选择精度和资源。本设计通过MATLAB进行仿真证明:其实现的变换结果与MATLAB工具箱中的FFT函数相比,信噪比可以达到65db以上,完全可以满足一般工程的实际应用要求。
编辑: 引用地址:http://www.eeworld.com.cn/designarticles/eda/200703/10745.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部

小广播

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: 安防电子 医疗电子 工业控制

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved