基于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×2k的傅立叶变换构成。同理,4k傅立叶变换可由2×2k的傅立叶变换构成。而2k傅立叶变换可由128×16的傅立叶变换构成。128的傅立叶变换可进一步由16×8的傅立叶变换构成,归根结底,整个傅立叶变换可由基2、基4的傅立叶变换构成。2k的FFT可以通过5个基4和1个基2变换来实现;4k的FFT变换可通过6个基4变换来实现;8k的FFT可以通过6个基4和1个基2变换来实现。也就是说:FFT的基本结构可由基2/4模块、复数乘法器、存储单元和存储器控制模块构成,其整体结构如图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×c1-i1×s1)+(r2×c2-i2×s2)+(r3×c3-i3×s3)]+j[i0+(i1×c1+r1×s1)+(i2×c2+r2×s2)+(i3×c3+r3×s3)]?? (4)
B′=[r0+(i1×c1+r1×s1)-(r2×c2-i2×s2)-(i3×c3+r3×s3)]+j[i0-(r1×c1-i1×s1)-(i2×c2+r2×s2)+(r3×c3-i3×s3)] (5)
C′=[r0-(r1×c1-i1×s1)+(r2×c2-i2×s2)-(r3×c3-i3×s3)]+j[i0-(i1×c1+r1×s1)+(i2×c2+r2×s2)-(i3×c3+r3×s3)] (6)
D′=[r0-(i1×c1+r1×s1)-(r2×c2-i2×s2)+(i3×c3+r3×s3)]+j[i0+(r1×c1-i1×s1)-(i2×c2+r2×s2)-(r3×c3-i3×s3)]?? (7)
而在基2蝶形中,Wk0和Wk2的值均为1,这样,将A,B,C和D的表达式代入图2中的基2运算的四个等式中,则有:
A′=r0+(r1×c1-i1×s1)+j[i0+(i1×c1+r1×s1)]?? (8)
B′=r0- (r1×c1-i1×s1)+j[i0-(i1×c1+r1×s1)] (9)
C′=r2+(r3×c3-i3×s3)+j[i0+(i3×c3+r3×s3)]?? (10)
D′=r2-(r3×c3-i3×s3)+j[i0-(i3×c3+r3×s3)]?? (11)
在上述式(4)~(11)中有很多类同项,如i1×c1+r1×s1和r1×c1-i1×s1等,它们仅仅是加减号的不同,其结构和运算均类似,这就为简化威廉希尔官方网站 提供了可能。同时,在蝶形运算中,复数乘法可以由实数乘法以一定的格式来表示,这也为设计复数乘法器提供了一种实现的途径。
以基4为例,在其运算单元中,实际上只需做三个复数乘法运算,即只须计算BWk1、CWk2和DWk3的值即可,这样在一个基4蝶形单元里面,最多只需要3个复数乘法器就可以了。在实际过程中,在不提高时钟频率下,只要将时序控制好?煴憧衫?用流水线(Pipeline)技术并只用一个复数乘法器就可完成这三个复数乘法,大大节省了硬件资源。
3FFT的地址
FFT变换后输出的结果通常为一特定的倒序,因此,几级变换后对地址的控制必须准确无误。
倒序的规律是和分解的方式密切相关的,以基8为例,其基本倒序规则如下:
基8可以用2×2×2**基2变换来表示,则其输入顺序则可用二进制序列(n1 n2 n3)来表示,变换结束后,其顺序将变为(n3 n2 n1),如:X?煟埃保保?→ x?煟保保埃牐?即输入顺序为3,输出时顺序变为6。
更进一步,对于基16的变换,可由2×2×2×2,4×4,4×2×2等形式来构成,相对于不同的分解形式,往往会有不同的倒序方式。以4×4为例,其输入顺序可以用二进制序列(n1 n2 n3 n4)来表示变换结束后,其顺序可变为((n3 n4)(n1 n2)),如:X?煟埃保保保?→ x?煟保保埃保牎<词淙胨承蛭?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个数据周期,这样?煟疲疲缘淖畲笤怂闶奔渚褪牵矗埃梗陡鍪?据周期。另外,由于输入数据是以一定的时钟为周期依次输入的,故在进行内部运算时,可以用较高的内部时钟进行运算,然后再存入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以上,完全可以满足一般工程的实际应用要求。
原文标题:基于FPGA的快速傅立叶变换
文章出处:【微信公众号:FPGA之家】欢迎添加关注!文章转载请注明出处。
审核编辑:汤梓红
-
FPGA
+关注
关注
1629文章
21735浏览量
603175 -
算法
+关注
关注
23文章
4610浏览量
92860 -
FFT
+关注
关注
15文章
434浏览量
59376
原文标题:基于FPGA的快速傅立叶变换
文章出处:【微信号:zhuyandz,微信公众号:FPGA之家】欢迎添加关注!文章转载请注明出处。
发布评论请先 登录
相关推荐
评论