多路并行流水线型基2-2FFT算法实现_杨苗苗.pdf

第2卷 第2期V o l.2 N o.2 2 0 2 3年4月 J o u r n a l o f A r m y E n g i n e e r i n g U n i v e r s i t y o f P L A A p r.2 0 2 3多路并行流水线型基22F F T算法实现杨苗苗,郭 锋,张永亮(陆军工程大学 军械士官学校,湖北 武汉 4 3 0 0 7 0)摘要:F F T算法作为O F DM系统的核心算子占用其系统处理的大多数时间,为提高O F DM系统数据传输速度,提出了一种改进的多路并行流水线型基22F F T实现架构。在实现过程中着重对旋转因子的存储进行片上缓存优化,减少了乘法运算次数从而减小整体运算复杂度;设计的数据整合模块用于控制时序,从而保证P路并行流水型架构正确实现,数据运算吞吐率成P倍提高。R T L仿真结果表明,与同类架构相比,提出的架构在硬件开销适中的同时使得性能分别提升了1.2 7%、2.0 4%、5 0.8 8%,并且具有F F T点数可扩展的特点,可满足随着通信标准的不断提高,F F T点数逐渐增大的实际应用需求。关键词:正交频分复用;快速傅里叶变换;并行流水线;多路径延迟交叉;基22 中图分类号:T N 4 7D O I:1 0.1 2 0 1 8/j.i s s n.2 0 9 7-0 7 3 0.2 0 2 2 0 1 1 0 0 0 1I m p l e m e n t a t i o n o f M u l t i-p a t h P a r a l l e l-P i p e l i n e d R a d i x 22 F F T A l g o r i t h m YANG M i a o m i a o,GUO F e n g,Z HANG Y o n g l i a n g(O r d n a n c e N C O A c a d e m y,A r m y E n g i n e e r i n g U n i v e r s i t y o f P L A,Wu h a n 4 3 0 0 7 0,C h i n a)A b s t r a c t:A s t h e c o r e o p e r a t o r o f t h e o r t h o g o n a l f r e q u e n c y d i v i s i o n m u l t i p l e x i n g(O F DM)s y s t e m,t h e f a s t F o u r i e r t r a n s f o r m(F F T)a l g o r i t h m o c c u p i e s m o s t o f t h e s y s t e m p r o c e s s i n g t i m e.I n o r d e r t o i m p r o v e t h e d a t a t r a n s m i s s i o n s p e e d o f t h e O F DM s y s t e m,a m o d i f i e d m u l t i-p a t h p a r a l l e l-p i p e l i n e d r a d i x 22 F F T i m p l e m e n t a t i o n a r c h i t e c t u r e i s p r o p o s e d.D u r i n g i m p l e m e n t a t i o n,t h e o n-c h i p c a c h e o p t i m i z a t i o n i s f o c u s e d o n t h e s t o r a g e o f t h e t w i d d l e f a c t o r,w h i c h r e d u c e s t h e n u m b e r o f m u l t i p l i c a t i o n s a n d t h e o v e r a l l c o m p u t a-t i o n a l c o m p l e x i t y.T h e d e s i g n e d d a t a i n t e g r a t i o n m o d u l e i s u s e d t o c o n t r o l t h e t i m i n g,s o a s t o e n s u r e t h e c o r r e c t i m p l e m e n t a t i o n o f t h e P-c h a n n e l p a r a l l e l p i p e l i n e a r c h i t e c t u r e,w i t h t h e t h r o u g h p u t r a t e o f d a t a o p-e r a t i o n i n c r e a s e d b y P t i m e s.T h e R T L s i m u l a t i o n r e s u l t s s h o w t h a t,c o m p a r e d w i t h t h e s i m i l a r a r c h i t e c-t u r e s i n t h r e e d i m e n s i o n s,t h e p r o p o s e d o n e h a s a p e r f o r m a n c e a d v a n t a g e b y 1.2 7%,2.0 4%a n d 5 0.8 8%r e s p e c t i v e l y w i t h t h e m o d e r a t e h a r d w a r e o v e r h e a d s;w i t h t h e g r e a t s c a l a b i l i t y o f t h e F F T p o i n t s,t h e p r o-p o s e d a r c h i t e c t u r e c a n m e e t t h e p r a c t i c a l a p p l i c a t i o n r e q u i r e m e n t s f o r g r a d u a l l y i n c r e a s i n g F F T p o i n t s,w i t h t h e u p g r a d e o f t h e c o mm u n i c a t i o n s t a n d a r d s.K e y w o r d s:o r t h o g o n a l f r e q u e n c y d i v i s i o n m u l t i p l e x i n g(O F DM);f a s t F o u r i e r t r a n s f o r m(F F T);p a r a l l e l-p i p e l i n e d;m u l t i-p a t h d e l a y c o mm u t a t o r(MD C);r a d i x 22 收稿日期:2 0 2 2-0 1-1 0基金项目:军内科研项目(KYWH Z BWX 2 1 5 8)。第一作者(通信作者):杨苗苗,讲师,主要研究超大规模集成电路设计,1 0 1 0 9 3 2 0 2 2q q.c o m。正交频分复用(o r t h o g o n a l f r e q u e n c y d i v i s i o n m u l t i p l e x i n g,O F DM)作为一种多载波调制技术在空间光通信、移动通信及电力载波通信等领域得到广泛应用1,是解决高速数据在无线信道中传输问题的关键技术2。O F DM系统的调制和解调过程主要由快速傅里叶变换(f a s t F o u r i e r t r a n s f o r m,F F T)算法完成1,因此F F T运算的 高效实现对O F DM系统的效率和可靠性具有显著的影响。随着长期演进技 术升级版(l o n g t e r m e v o l u t i o n-a d-v a n c e d,L T E-A)、第五代移动通信技术(5 t h g e n e r a-t i o n m o b i l e c o mm u n i c a t i o n t e c h n o l o g y,5 G)、物联网等通信标准的不断发展以及F F T算法在现代高速信号处理中的广泛应用,如何更快更灵活地实现F F T算法成为一个研究热点3。F F T运算流程整体呈流水线模式,前一项运算的输出是下一项运算的输入,不可逆向实现。这种流水处理模式在保证较快运行速度的同时,硬件开销适中,是一种能较好均衡数据吞吐率和硬件开销的实现方案。目前在O F DM系统中,应用最广泛的流水线型F F T实现架构是单路径延迟反馈(s i n g l e-p a t h d e l a y f e e d b a c k,S D F)架构和多路径延迟交叉(m u l t i-p a t h d e l a y c o mm u t a t o r,MD C)架构4。对于S D F架构,其工作流程如图1(a)所示,N点F F T架构实现一般由l o g2N个计算级组成5,每个蝶形运算单元都是单通路流水作业。当F F T运算流水线正常运行时,每个时钟周期可以产生一个F F T运算结果,满足实时运算需求,每一级蝶形运算的输出仍可存储在本级存储单元中,因此寄存器缓存利用率高达1 0 0%,硬件复杂度小。而对于MD C架构,其工作流程如图1(b)所示,可支持多路数据同时输入6。经过第一级处理单元,产生两个不同步的运算结果,其中一个需暂时存储在缓存器中,然后在正确的时序下与另一个计算结果一起进入下一级运算单元,因此MD C架构内部的存储单元占用比S D F架构多,其处理速度的提高是以耗费硬件资源为代价的7-8。综上,两种方案各有利弊。图1 S D F和MD C架构示意为解决以上难题,一种新型基2n-MD C架构成为O F DM领域实现F F T运算的研究热门,它在保留MD C架构控制简单优点的同时,硬件资源开销适中9。本文设计的F F T实架构便是基于此种方案。其创新点在于:一是通过对旋转因子进行离线生成,减小了旋转因子的存储,使得在保障了性能的同时也减少硬件开销;二是设计了数据整合模块控制运算时序正确,从而保证P路并行流水线型架构正确实现,数据运算吞吐率成P倍提高;三是设计的架构具有可扩展性,可满足随着通信标准的不断提高,F F T点数逐渐增大的实际应用需求。1 并行流水线MD C-F F T实现架构设计的MD C-F F T实现架构主要由蝶形运算单元模块、旋转因子模块以及数据整合模块组成,如图2所示。以1 6点F F T运算4路并行为例,其中,蝶形运算单元模块完成整个架构最主要的基22蝶形运算;旋转因子模块用来存储MAT L A B离线生成的第1级运算所需的旋转因子;数据整合模块的作用是调节时序,确保每一级蝶形运算均在正确的时序控制下进行。图2 1 6点MD C-F F T架构对于图2架构,其每级运算的数据流特征为:将输入采样序列用二进制表示为I=bn-1,b1,b0,n=l o g2N为F F T运算级数,s表示当前运算级数。进行蝶形运算操作的一组数据的序列规律可以总结如下:在任意级的F F T运算中,进行蝶形运算操作的一组数是比特位bn-s不同而其他位均相同的两个输入序列。如图3所示,对于1 6点F F T运算的第3级,