（微电子学与固体电子学专业论文）全数字ofdm收信机中fft处理器设计.pdf

中文摘要 摘要：随着电子技术的高速发展，快速傅立叶变换( f f t , f a s tf o u r i e rt r a n s f o r m ) 作 为数字信号处理的核心技术之一，被广泛应用于各种不同领域，如多媒体、通信 和图像处理等领域中。正交频分复用( o f d m ) 技术是一种可以有效对抗信号波形间 干扰的高速传输技术，成为第四代移动通信的首选技术。在o f d m 收信机中，f f t 被用来对各个子信道做正交调制。f f t 是o f d m 系统中硬件实现较为复杂和困难 的一部分，其处理速度及硬件面积等性能对整个o f d m 系统而言都是至关重要的。 因此全数字o f d m 收信机中f f t 处理器设计是当前数字信号处理及移动通信技术 研究的热点问题。近年来超大规模集成电路和d s p 技术的发展，也为全数字 o f d m 收信机中f f t 处理器的实现提供了硬件基础。 本文主要研究用于o f d m 系统的f f t 处理器的设计。概况地介绍了f f r 处理 器发展现状和o f d m 的基本概念、基本工作原理、系统框图。总结了o f d m 系统 的优缺点，f f t 处理器的重要性。详细阐述了数字信号处理理论中快速傅立叶变 换的理论基础。对f f t 的各种算法，f f t 处理器的硬件结构以及各部分的具体实 现方法进行了详细的描述。 重点研究的内容是：采用了按时间抽取基2 的阵列结构进行设计和仿真。合 理地使用加法器、乘法器，特别是对乘法器进行了详细地研究。分析了两种快速 乘法算法，最后根据实际需求，采用了b o o t h 算法。通过分析，将b o o t h 算法与流 水线结合，满足速度的要求，并用v e r i l o gh d l 语言进行描述，编写代码，通过功 能仿真及时序分析验证了其快速性。在此基础之上，设计了f f t 的蝶形运算单元， 降低了运算复杂度，提高了蝶形运算单元的速度。然后根据f f r r 的运算特点，对 整体结构进行r t l 级设计，在功能仿真之后，采用t s m c0 1 8 9 mc m o s 工艺对 蝶形单元进行了逻辑综合和版图设计，对生成的面积报告、功率报告、时序报告 进行分析。 本设计使用m a t l a b 、m o d e l s i m 、q u a r t u si i 、s y n p l i f y 、d e s i g nc o m p i l e r 、 e n c o u n t e r 等软件完成了算法验证、r t l 编码、功能仿真、逻辑综合、版图设计。 关键词：f f t ；o f d m ；蝶形运算；b o o t h 算法：流水线 分类号：t n 9 1 1 7 2 a bs t r a c t a b s t r a c t ：f f t ( f a s tf o u r i e rt r a n s f o r m ) i st h ec o r et e c h n i q u eo fd s p ( d i g i t a ls i g n a l p r o c e s s i n g ) w i t ht h er a p i dd e v e l o p m e n to fe l e c t r o n i ct e c h n o l o g y ，f f th a sb e e nw i d e l y u s e di na r e a so fm u l t i m e d i a ，c o m m u n i c a t i o n ，i m a g ep r o c e s s i n g o f d m ( o r t h o g o n a l f r e q u e n c yd i v i s i o nm u l t i p l e x i n g ) i sah i g h - s p e e dt r a n s a c t i o nt e c h n o l o g yw h i c hc a l l d e f e a ti c i ( i n t e r - c h a n n e li n t e r f e r e n c e ) a n di s l ( i n t e r - s y m b o li n t e r f e r e n c e ) o f d mh a s b e e nt h ef i r s tc h o i c ei n4 gm o b i l ec o m m u n i c a t i o nt e c h n o l o g y i no f d mr e c e i v e r s y s t e m ，f f ti su s e dt om o d u l a t et h es u b - c a r r i e r s f f ti st h em o s tc o m p l e xa n dd i f f i c u l t p a r ti nt h eo f d ms y s t e m ，t h u si t sp r o c e s s i n gs p e e da n da r e aa r ee x t r e m e l yi m p o r t a n t f o r t h ew h o l eo f d ms y s t e m b e c a u s ea l lo fa b o v e ，t h ef f tp r o c e s s o rb a s e do n a l l - d i g i t a lo f d mr e c e i v e rh a sb e e nv e r yp o p u l a r r e c e n t l yt h ed e v e l o p m e n to f v l s i ( v e r yl a r g es c a l ei n t e g r a t i o n ) a n dd s ps u p p l yt h eh a r d w a r ef o u n d a t i o nf o rt h e f f tp r o c e s s o rb a s e do na l l - d i g i t a lo f d mr e c e i v e r t h ep a p e rm a i n l yd i s c u s s e st h ed e s i g no ft h ef f tp r o c e s s o rb a s e do na l l d i g i t a l o f d mr e c e i v e r i ti n t r o d u c e st h es t a t u sq u oo fd e v e l o p m e n to ff f tp r o c e s s o ra n d b a s i ct h e o r yo fo f d ms y s t e m i td i s c u s s e st h et h e o r e t i c a lf o u n d a t i o no fd i g i t a ls i g n a l p r o c e s s i n ga n dp r i n c i p l eo ff f t ，i n c l u d i n gs o m ek i n d so fa l g o r i t h m ，t h eh a r d w a r e i m p l e m e n t a t i o na r c h i t e c t u r e m o s ti m p o r t a n t l y , i ts e l e c tt h ed i t ( d e c i m a t i o ni nt i m e ) r a d i x 2a l g o r i t h ma r r a y s t r u c t u r et od e s i g nt h ef f tp r o c e s s o r i te l a b o r a t e st h em u l t i p l i e ra n da d d e r , e s p e c i a l l y t h em u l t i p l i e ri sd i s c u s s e d i ta l s od i s c u s st h eh a r d w a r ei m p l e m e n t a t i o no fc a s c a d e s t r u c t u r ea n df u n c t i o nm o d u l e s t h ef f tb u t t e r f l yc o m p u t i n gu n i ti sd e s i g n e db yb o o t h p i p e l i n es t r u c t u r e s oi t c a nr e d u c et h ec o m p l e x i t ya n di n c r e a s et h es p e e do ft h e b u t t e r f l yu n i t a f t e rf u n c t i o ns i m u l a t i o n w i t ht s m c0 18p mc m o st e c h n o l o g y , i t m a k e st h el o g i c a ls y n t h e s i sa n dt h el a y o u td e s i g n i ta l s oa n a l y s e st h ea r e a , p o w e ra n d t i m i n gr e p o r t s t h ed e s i g nu s e st h es o f t w a r es u c ha sm a t l a b ，m o d e l s i m ，q u a r t u si i ，s y n p l i f y , d e s i g nc o m p i l e r , e n c o u n t e r , e t c i tf i n i s h e da l g o r i t h mv e r i f i c a t i o n ，r t lc o d i n g ， f u n c t i o ns i m u l a t i o n ，l o g i c a ls y n t h e s i s ，l a y o u td e s i g n k e y w o r d s ：f f t ，o f d m ，b u t t e r f l yc a l c u l a t e ，b o o t ha l g o r i t h m ，p i p e l i n e c i 。a s s n o ：t n 9 1 1 7 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：王。黾，任 签字日期：2 矿口万年月p 日 导师签名：放k 签字日期：仉内绛多月汐日 独创性声明 本人声明所星交的学位论文是本人在导师指导下进行的研究王作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 两使瘸过的材料。与我一厨工作的同恚对本研究所徽的任何贡献均已在论文中作 了明确的说明并表示了谢意。 1 ，一 ， 学位论文作者签名：王魁 丕 签字日期： 2 p 露年多月7 日 5 9 致谢 本论文的研究工作是在我的导师骆丽教授的悉心指导下完成的，骆丽教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来 骆丽老师对我的关心和指导。 骆丽教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予 了我很大的关心和帮助，在此向骆丽老师表示衷心的谢意。 此外，李修函老师对于我的科研工作和论文都提出了许多的宝贵意见，在此 表示衷心的感谢。 在实验室工作及撰写论文期间，彭琼、蒋吴、沈宏、赵建飞、李宁等同学对 我论文的研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 1 引言 快速傅立叶变换( f 踊作为数字信号处理的一个重要的分析z 吴，被广泛应用 在声学、语音、电信和图像处理等领域中。近年来，在o f d m 系统中，快速傅立 叶变换与反变换( f f l y i f f d 处理器被用来实现子载波调制与解调，是o f d m 系统 的关键技术之一。 i 1 课题研究的背景 从2 0 世纪8 0 年代中期第一代模拟移动通信系统商用开贻至今，短短的十几 年闻经历了第代数字移动通信系统( 2 g ) 铁萌芽到完善的整个发展过程，直至今天 人们对第三代移动通信系统( 3 g ) 的商用开发、部署和对第四代移动通信系统( 4 0 ) 的研究，移动通信的发展可谓日新月异。 o f d m 是多载波传输方案的实现方式之一，是实现复杂度最低、应雳最广的 一种多载波调制方案。正因为o f d m 满在的多径对抗能力，且可以灵活地和其他 接入方式结合成衍生系统，所以o f d m 已经被列入4 g 无线通信系统的可能解决 方案，受到众多研究者的广泛关注。 o f d m 除了在移动通信系统中被采用，还广泛焉于各种数字传输蠢透信中： ( 1 ) 高比特率数字用户线系统( h d s l ) ( 2 ) 不对称数字用户线系统( a d s u ( 3 ) 甚高比特率数字用户线系统( v h d s l ) ( 4 ) 数字音频广播( d a b ) 系统 ( 5 ) 数字视频广播( d v b ) 和h d t v 地而传播系统。 o f d m 系统的一大特点，也是优点就是在发送端采用i f f t 调制，在接收端采 用f f t 解调。快速傅立嚏交换( f f t ) 的葶| 入，大大降低了o f d m 的复杂性，提升 了系统的性能。 1 2f f t 处理器研究现状 当今f f t 处理器实现形式主要有三种： ( 1 ) 使用d s p 通过软件编程米实现。这种方法虽然灵活性很大，但受d s p 本 身 生能及程序指令顺序执行的限铆，难以实现高速、大规模的f f t 运算。 ( 2 ) 震f p g a 设计f f t 。謦祷在国际上，以f p g a 芯片生产厂商为主的公司 在基于f p g a 设计f f t 的综合研究方面处于领先地位。而且由于f p g a 芯片生产 厂商对本厂生产芯片性能上的了解，设计的f f t 处理器可以最大限度的发挥芯片 的性熊。f p g a 厂商a l t e r a 公霹和x i l i n x 公镯都研制了f f ti p 核，性熊鼍冀常 优越。健其价格十分昂贵。短时间难以在基层普及使用。 ( 3 ) 用专用f f t 芯片或用户定制的大规模集成电路实现。这种方法可以实现 很高的运算速度，但灵活性较差，且研发费用较高。表1 1 为不同器件完成1 0 2 4 点f f t 运算所需要的对闻比较 表1 1 不同器件宪成1 0 2 4 点f h 运算时间比较 器件类型生产商器件时事巾( 龌z )运算时问( u s ) d s pt it m 5 3 2 0 c 6 2 0 73 0 0 4 3 2 d s pa d ia d s p 2 l1 6 08 01 2 0 p o e w rp cm o t o r o l a 船c 7 4 1 04 5 03 6 f p g ax i n li n i x x c v 3 0 0 e1 0 04 l f p g aa 1 t e r a2 0 k 1 0 0 e1 0 05 2 1 3 本论文主要研究内容 本文主要研究应翔予全数字o f d m 收信税中的硝点复数f h 处理器的设计， 对当前f f t 处理器研究现状进行了阐述，介绍了基于f f t 的o f d m 发展历史及现 状、基本原理、系统模型，总结了o f d m 系统的优缺点。对f f t 算法进行详细的 研究，对几种r a d i x 蝶形运算进行了比较。研究了f f t 硬件实现结构，从运算速 度及占耀资源两方甏进行了比较。提出按时闻抽取基乏的采用阵列处理结构的f 盯 的设计方案。概括地分析了v e r i i o gh d l 语言的优点，阐述了r t l 级设计流程及 方法。着蕈研究了加法器和乘法器爽现原理，使用b o o t h 算法优化f f t 蝶形单元。 采焉v e r i l o gh d l 语富进行r t l 编码，功能仿真通过后，使用e d a 工具s y n o p s y s 公司的d e s i g nc o m p i l e r 及c a d e n c e 公司豹s o ce n c o u n t e r 对蝶形运算单元进行逻 辑综合和版图设计。本设计使用t s m c0 1 8 m 工艺库。 2 2o f d m 的基本原理 2 。1o f d m 技术发震历史及现状 在无线通信系统中，各种物体对传输信号的反射导致了多径传播。由于不同 传播途径具有不同的、随机的延迟特性，从而使得无线信道表现出时间色散特性。 因此弓| 起的符号闻干扰f l s l ，i n t e r - s y m b o li n t e r f e r e n c e ) 是无线通信系统设计中必须 考虑的问题，特别是在高速传输的环境中。多载波传输技术是让数据以较高的速 率在较大时延的信道上传输的途径之一。它的基本思想足把一个高速率的数据流 分解成许多低速率的子数据流，以并行方式在多个子信道上传输。在每个子信道 上，符号周糯将大于原始的符号周期，从而可以消除或部分消除i s i 。正交羰分复 用( o f d m ，o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ) 是多载波传输技术的一种。 与其它多载波传输技术不同，在o f d m 中各子信道之间在时域上相互正交，因此 信遵干扰的影响被减小为在每个子信道上乘以一个复传输因予，在接收端不需要 时域的均衡器，大大简化了接收端的信号处理过程口j 。 o f d m 最早起源于2 0 世纪5 0 年代中期，即k i n e p l e x 系统，此系统目的是在 有严重多径衰落效应的高频无线信道中实现无线传输，但此系统使崩的是传统的 多载波系统的实现方式，系统还是糖当复杂。直羽1 9 7 1 年，w e i n s t e i n 彝e b e r t 把 离散傅立叶变换( d f t , d i s c r e t ef o u r i e rt r a n s f o r m ) 应用到并行传输系统中，才不弭利 用带通滤波器，而是在基带处理就可以实现频分复用( f d m ，f r e q u e n c yd i v i s i o n m u l t i p l e x i n g ) 。并且d f t 可用快速傅立时变换( f 飘f a s tf o u r i e rt r a n s f o r m ) 来实现， 大大减小了系统的复杂度。 2 0 世纪6 0 年代，o f d m 技术应片j 在军方高频无线通信系统中。自从2 0 世纪 8 0 年代以来，o f d m 在数字音频广播( d a b ) 、数字视频广播( d v b ) 、有线电话网 上基j ：现有铜双绞线的菲怼称高魄特率数字雳户线技术( 铡如a d s l ) 、基予 i e e e 8 0 2 1 1 系列标准的无线局域网( w l a n ) 以及基于i e e e 8 0 2 1 6 系列标准为代表 的宽带无线城域网( w m a n ) 中得到了应用。3 g p p 最近提出的3 g 长期演进3 g l t e ( l o n gt e r me v o l u t i o n ) 计划中也将采用o f d m 技术作为新的无线接入技术【3 1 。 2 2o f d m 技术原理 o f d m 是多载波通信豹一种。与普通多载波技术不同，在o f d m 系统中各子 信道在时间上相互茁交，在频率上耀互重叠，如图2 1 所示。 图2 io f d m 系统( 左) 与普通多载波系统( 右) 频带使用比较 f i g u r e 2 1c o m p a r i s o no f f r e q u e n c yb e t w e e no f d ms y s t e ma n dc o m m o n m u t l i c a r r i e r ss y s t e m 为保证子信道之间相互正交，子信道的频率阚隔鲈可选择为各子信道上的符 号周期的倒数，即a f ；1 n t , 式中n = 形a f 为子信道的个数。这样就胄 峰 l c o s ( 2 9 t + 彩e o s 【2 戤z + 6 f ) t d t = o ( 2 一1 ) 乞 o f d m 信号x ( t ) 可以写为 x ( o = x 女( f ) 扩雕 ( 2 2 ) ( 2 砣) 式中k 为予载波数雌= w 。+ k a w ：w k 为第k 个子载波频率；w c 载波频率 x k ( t ) 为t 时刻第k 个子载波要调制的复星座点。假定在一个符号周期内x k ( f ) 为定值，燹l jx k ( t ) = 露) 设信号采样频率为| ，t ，可以得到信号鲶采样僮为 符- t x ( n t s ) 篇x ( k ) e “雌讹帆 ( 2 3 ) 假设一个符号周期砟内含有l ( 个采样值，即墨= 皿，不失一般性t 令敝= 0 ， 剡2 3 ) 可化为 x ( n t s ) - - x ( k ) e j ( 峨( 2 - 4 ) n = l 将其与离散傅立时逆变换( i d f t ) 形式对比： g ( n t ) = g ( k k t ) e 7 2 砌7 鬈 ( 2 5 ) 可以看出，若把x ( k ) 看作频域采样信号，x ( n t 。) 为对应的时域信号，当 a f = i k l = l 成立时，两式等价。由此可知，若选择载波频率间隔为l t f ，则 o f d m 信号不僵保持了芷交性，两且可以焉d f t 来定义，并镌够通过籀梁的 4 f f 影裕汀交换模块实瑗信号豹瀵捌与解溪。 循环前缀( c p ) 就是将o f d m 码元最后一部分复制到各码元的前端，如阉2 2 所示。 。 圈2 2o f d m 码元循环前缀示意图 f i g u r e 2 2c y c l e p r e f i xo fo f d ms y m b o l 这样传输中鲍o f d m 信号旱现周则性。c p 对于消除码阅手扰和保持载波间的 正交犊起着关键作用。另外要注意的是，c p 作为种保护间隔( g i ，g u a r di n t e r v a l ) ， 它传递的实际上是冗余信息，将占用额外的频谱和功率资源。为了减少这种开销， 可以通过合理的系统设计，使得c p 占用系统资源足够小。事实上o f d m 系统是 通过牺牲小部分资源，来降低接收潺的复杂度。 根据上面的分析不难看出，o f d m 系统具有如卜- 优点h l ： ( 1 ) 各个子信道中的正交调制和解调可以采用i d f t 和d f t 来实现。对于予 信道数很大的系统，还可以用f f t 来实现。这样运算量就很小，实现简单。 ( 2 ) 无线数据业务一般都存在凄摹对称挂，即下行链路中转输昀数据量要远远 大子上行链路中的数据传输量，如i n t e r n e t 业务中的网页浏览、f t p 下载等。另一 方面，移动终端功率一般小于i w ，在大蜂窝环境下传输速率低于1 0 k b i v s 1 0 0 k b i t s ；两基站发送功率可以较大，有可能提离lm b i v s 以上的传输速率。瞩此 无论从用户数据业务的使用需求，还是苁移动通信系统自身的要求考虑，都希望 物理层支持非对称高速数据传输，而o f d m 系统可以很容易地通过使用不同数量 的子信道来实现上行和下行链路l 卜不同的传输速率。 ( 3 ) 实际的信遂多数都是频率选择缝衰落倍道，但是不霹能所有的子僚遂都 同时处于深衰落。因此，性能差的只是其中的小部分信道，就可以通过信道编码 来得到最终的解调数据。还可以通过动态数据分配和动态子信道分配来充分利用 信噪比较高的子信道，从而提升系统性能。 ( 4 ) o f d m 系统由于其频分特性，容易与其健多种多址方式楣结合馒孀，构 成o f d m a 系统，其中包括多载波码分多址( m c c d m a ) 、跳频o f d m 以及 o f d m t d m a 等。 ( 5 ) 传统的频分多路传输方法中，将频带分为若于个不糍干的子频带来传输 并行的数据流，在接收端用一组滤波器来分离各个子信道。这种方法的优点是简 5 单、直接，缺点是频谱的剩震率低，子信道之阆耍露有足够的保护频带，蔼置多 个滤波器的实现也有不少困难。而o f d m 系统幽于各个子载波之间存在正交性， 允许子信道的频谱相甄重叠，因此与常规的频分复用系统相比，o f d m 系统可以 最大限度地剥用频谱资源。 o f d m 系统由于存在多个正交的子载波，丽且其输出信号是多个子信道蠡勺叠 加，因此与单载波系统相比，存在如下主要缺点： ( 1 ) 易受频率偏差的影响。由于子信道的频谱相互覆盖，这就对它们之间的 正交褴提出了严格的要求。然丽囱予无线信道存在时交性，在传输过程中会缀现 无线信号的频率偏移，例如多普勒频移，或者由于发射机载波频率与接收机本地 振荡器之间存在的频率偏差，都会使得o f d m 系统子载波之间的正交性遭到破坏， 从而导致子信道的信号相互干扰( i c i ) ，这种对频率偏差敏感是o f d m 系统的主要 缺点之一。 ( 2 ) 存在较高的峰值平均功率比。与单载波系统相比，由于多载波调制系统 的输出是多个子信道信号的叠加，因此如果多个信号的相位一致时，所得到的叠 加信号的瞬时功率就会远远大子信号的平均功率，导致较大的峰值半均功率冼 ( p a p r ) 。这样就对发射机内放大器的线性提冉了很高的要求。 不过这两个缺点都已经有了相应的解决方法并且这些方法还将随着研究的深 入而不断改进。 2 3 基于f f t 的o f d m 系统模型 o f d m 系统模型如图2 3 所示。 输入的二元数字序列首先进行审并转换和编码映射，然后经过快速傅立时逆 变换( i f f t ) 对编码后的星座点进行基带调制，再经并串转换、d a 转换及低通滤 波后上变频送到信道。接收端的处理过程与发送端相反，信道出来的信号先经过 下变频、低逶滤波、a d 转换及串并转换后，再进行快速傅立叶变换( f f t ) ，然后 对所得数据进行均衡，以校正信道失真，最终进行译码判决_ 和并串转换，恢复出 原始的二元数字序y l j t 4 。 6 串行输入 串 编 并 上 码n 点 d a 映i f m |变 并 审 l p f 频 射 噬声一赢 纾输滋 并 缓 串下 码均n 点 l p f 变 映 衡 f f i d 审 并 频 射 图2 3 基- 7 = f f t 鳇o f d m 系统模型 f i g u r e 2 3s g u c t u r eo f o f d ms y s t e mb a s e do n 搿谭 本文研究的用于o f d m 系统中的f f t 处理器的基本参数指标为6 4 点，数据 以1 6 b i t 定点补码表示，工作频率在5 0 m h z 以上。 2 4 本章小结 本耄概况地介绍了o f d m 的基本原理、技术特点、系统模型。分析了o f d m 系统的优缺点。用i f f t 餍f t 来实现子载波调制与解调，也是大优点。可冕f h 的重要性。 7 3f f t 处理器整体方案设计 3 1 离散傅立叶变换( d f t ) 宥限长序列在数字信号处理中是很重要的一种序列。可以导出反映它的“有 限长 特点的一种有用工具是离散傅立叶变换( d f t , d i s c r e t ef o u r i e rt r a n s f o r m ) 。离 散傅立叶变换开辟了频域离散化的道路，使数字信号处理也可以在频域上采用数 字运算方法迸嚣，它可以作为一种数学工具来描述离散信号的辩域与频域表示的 关系，大大增加了数字信号处理的灵活性，特别是它的多种快速算法，使信号的 实时处理和设备的简化得以实现，所以离散傅立叶变换不仅在理论上有重要意义， 丽且在各种数字信号处理的算法( 如耀关、滤波、谱估计等) 中起着核心作用。 对于一个长度为n 的有限长序列n ) ，其离散傅立时交换定义 正变换 ，- 1 x ( k ) - l ) v z i x 例= x 0 职，o k _ n - 1 ( 3 1 ) 删 反变换 ，- i x ( n ) = 1 d f t x ( k ) = ( 1 n ) 枣z x ( k y “，o 行n - 1 ( 3 2 ) k = o 其中转学= e - j 2 砝腰，x ( n ) 和x ( 1 ( ) 是一个有限长序列的离教傅立时变换对。已 知其中的一令痔列，就能唯一地确定另一个序列。d f t 把信号或滤波器扶时域变 换到频域，这主要是为了研究信号或滤波器的频率特性。通过d f t 的变换，将离 散的数字信号变换为不同频率分量的和，使得更加清楚地了解信号的频率分布。 这一变换主要用来分析滤波器形状和信号频谱对信号而言，d f t 提供的信息称为 信号的频谱，对滤波器纛言，d f t 待裂酶信息称为滤波器的频搴响应，它由鼹部 分组成：幅度响应耩相位响应，幅度响应给出了滤波器鲍形状。 1 9 6 5 年c o o l e y 和t u k e y 发表的关于d f t 的著名论文，使计算n 点的d f t 运 算量从n 2 降为n l 0 9 2 n ，引起了各国学者的广泛关注。三十多年来，d f t 各种快速 算法榛继出现，成为数值数学方程最活跃的一个领域。 3 2 快速傅立叶变换( f f t ) 5 】 快速傅立时变换( f 瓯f a s tf o u r i e rt r a n s f o r m ) 是近代数值数学最重要的成果之 一，在众多领域中发挥了很大的作用，它的意义远远超过一个算法的范围，它使 某些数据的事后处理及系统的模拟研究进入到数据的实时处理，在数字信号处理 和图像处理等方面为广泛采用数字方法打开了一个崭耨的局面。 8 上一节绘凄了d f t 正反变换麴公式，二者的差别只在于w n 的指数符号不同， 以及茬一个常数乘因子i n ，因而下面我们只讨论d f t 正变换的运算量。反变换 运算量是完全相同的。由式( 3 1 ) 可知完成整个d f t 运算总共需要n 2 次复数乘法及 n 烈1 ) 次复数加法。我们知道复数运算实际上是由实数运算来宠成的。所以藕个 d f t 运算总共需要4n 2 次实数乘法和2 n ( 2 n 1 ) 次实数加法。当n 很大时，运算量 是很可观的。因此需臻改进d f t 的计算方法，以大大减少运算次数。 下丽讨论减少运算工作量的途径。仔细观察d f t 的运算就可以看出，利用系 数吲的以下固有特性，就可班减小d f t 的运算量： ( 1 ) 孵的对称性i 孵 = 形 ( 2 ) 时的周期j 陛孵拳彬扩m 。= 嘴似+ ) ( 3 ) 暇的可约性唆= ，w ，。m r a n k ，嘭一，w ，n n k ，。m 由此可得出暇 - 哗州。= 甄威，嘴理= - 1 ，哕锅理江一蛾 这样，( 1 ) 利用这些特性，使d f t 运算巾有些项可以台并；( 2 ) 利用w 的 对称性、周期性和可约性，可以将长序列的d f r 分解为短序列的d f t 。快速傅立 时变换算法正是基于这样的基本思想瑟发展起来的。它的算法基本上可以分为琵 大类，即按时间擒取算法( d i t , d e c i m a t i o ni nt i m e ) 和按频率抽取算法( d i e d e c i m a t i o ni nf r e q u e n c y ) 。 3 2 1 按时间抽取( d i t ) 的基2f f t 算法 将n = 2 l 的序列x ( n ) ( n = 0 ，1 ，n 1 ) 先按n 的奇偶分成以下两组： 偶序列： x ( o ) ，x ( 2 ) ，x ( 4 ) 。，x ( n - 2 ) 奇序歹薯：1 ) ，x 3 ) ，5 ) , x f n 1 ) 则可将d f t 化为 n - ! 一l- i 以凳) = 脚咄刎= 蝴= z x ( n ) w ：+ x ( 嚣) 嘭 r l = on = 0n = 0 f 气气、 撑为捣教n 为奇数 v 。7 ，2 1 】v 2 - l n 2 1 ，2 - 1 = x ( 2 ，) 嚼睹十x ( 2 r + 1 ) w f f 川= 一( r ) ( 2 ) 睹+ 蝶石：( ，) ( 暇2 ) 庸 r 端or = or = or = o 其中f 0 ，l ，n 2 一l 利用系数时的可约性，即峨_ e - j 2 脚- e - 2 训m 2 = ，2 式( 3 3 ) 可表示成 9 = 玉( 哟嚼2 + 蝶恐( r 孵2 = 五国+ 蛾五( 妨 o _ k _ n 2 1 ( 3 - 4 ) e - - o瑚 式( 3 - 4 ) o px l ( k ) 与x 2 ( k ) 分别是x l ( r ) 及x 2 ( r ) 的n 2 点d f t ，然后应用系数的周 期性，即毗：= 暇譬m 孙，可得到 j ( n 2 + 受) = x ；妻) 盖二( n 2 + k ) 蓦爻，2 ( 露) 残的确定 对第m 级运算，一个d i t 蝶形运算的两节点“距离”为2 睁i ，就有 x 。( k ) = x 0 一i ( 七) + x 。一l ( 七+ 2 ”1 ) 陟z ( 3 * 1 0 ) x 二( k + 2 ”q ) = 爿_ 一l ( 七) 一爿0 i ( 忌+ 2 ”_ 1 ) 石 ( 3 一1 1 ) 把主式中，蝶形运算两节点中的第一个节点标号值，露k 值，表示成l 位烈宅l ) 二进制数。然后把此二迸制数乘上2 b m ，即将此l 位二进制数左移l m 位，把右 边空出的位置补零，此数即为所求r 的二进制数。 3 2 2 按频率抽联( d i f ) 的基一2f f t 算法 频率抽取f f t 算法是在把n = 2 l 的序列x ( n ) ( n = o ，l ，n 1 ) 按n 的奇偶分组之 前，先把输入按n 的顺序分成前后诱半： 前半序甍：x ( o ) ，x ( 1 ) ，2 ) ，x ( n 2 1 ) 后半序列：x ( n 2 ) ，x ( n 2 + 1 ) ，x ( n 2 + 2 ) ，x f n 1 ) 因此，x ( n ) 的n 点f f t 可以表示成： n 2 - 1弘l纠 艇幻= 磅孵积渺萨= 嚣磅+ 砌+ 2 ) 垆2 】枣 曙0 k n - l ( 3 1 2 ) ，= = o r r = n f 2h 神 n ，2 - i k 为偶数时x ( 2 k ) = x ( n ) + x ( n + n 2 ) w u 2 时o k 】暇暇菇o _ k x ( 7 ) 图3 48 点的d i ff f r 运算流图 f i g u r e 3 48p o i n t sd i ff f tc o m p u t i n gf l o w 对比图3 1 和图3 3 可以看出，d i t 和d i f 两种f f t 算法基本蝶形有所不同。 d i f 的复数乘法只出现在减法之后，d i t 则是先作复乘后作加减法。除此之外， d | f 具奢与d i t 相同的运算特点。 3 3 几种r a d i x 蝶形运算的比较 上一节讨论的f f t 算法以2 为基数。下面讨论d i t 其它基数的f 玎算法，然 后再比较它们的运算量。 3 3 。1 基4 算法讨论 以时间抽取法为例，基4 算法是把n = 4 0 的序列分解为 删茹取锄癣磁+ z x ( 4 m + l 嬲竹瓣+ e 4 m + 獬黼磷+ 懒+ 瓣瓣鞲( 3 1 6 ) m f f i on w om = om = o 其中0 m n 4 10 k n 一1 令x ( 4 m ) _ a ( m ) ，x ( 4 m + 1 ) = b ( m ) ，x ( 4 m + 2 ) ：c ( m ) ，x ( 4 m + 3 ) = d ( m ) ，因为睇槭= 嗡 所以( 3 16 ) f f j 表示为： 4 - - l4 - - 1 ，扣l 4 - 1 烈露) 徽8 彻y 蒗+ 蝶矗( 埘箩巧蕊+ 碟c ( 矽巧器+ 转斧疗( 掰萝鬈麓( 3 1 7 ) m = om = or n = 0m = 0 又令 n 1 4 - 1w | 4 - 1n | 4 - 1n | 4 - 1 艿= 6 ( 脚炒篇a = a ( m ) w f f ：4c = c ( m 矽篇d 。矗( 肼沙溉 m = om = om = o m = o 煲| j 有 抓七) = 彳+ b 峨+ c 嚼十d 职r x ( k + n 4 ) = a - j b w ；一c w 蛩七j d w x ( k + 3 n 4 ) = 矗 b w ：一c w 蛩一；嘲 x ( k + n 2 ) = a j b w ：+ c w 蛩一j d w 挚0 1 8 ) 由式( 3 1 8 ) 我们可以注意到一些便于硬件实现的特点：如可以把加数分组： a + c w 嚣露暇+ d 峨xa - c 暇艿畋一d 峨x 然后辩进行二次加等等。 3 3 2 几种r a d i x 蝶形运算量比较 由公式( 3 7 ) ( 3 18 ) ，毙较基一2 和基4 算法磺俘实现，1 个基也蝶形运算单元包 含1 个复数乘法器和2 个复数加法器，1 个基- 4 蝶形运算单元由3 个复数乘法器和 8 个复数加法器组成。不进行逻辑优化，每个复数乘法器由4 个文数乘法器和2 个 实数加法器组成【6 】。根据基数和点数的不同，可以得到如表3 。2 所永的运算量比较 表其审l - - i 0 9 2 n 。 对表3 2 中的数据分析不难得到：从基2 到基- 4 ，乘、加法的运算次数发夺了 比较大的跳变，而从基_ 4 到基8 以及基1 6 ，运算次数变化的幅度就不是很明显了。 而摹2 的算法，很显然是最容易控制的，控制操作最简单，基珥算法的控制性比 较复杂一些，毽仍然暴有帮基- 2 算法的可类比性。而基焉与基。1 6 算法的控制复杂 度与撼4 相比跳变得就很明显了。对于点数很高的序列，从运算速度和控制逻辑 复杂度折中考虑，基“算法在f f t 处理实现中具有最高的性价比【7 1 。 1 4 表3 2 几种r a d i x 运算囊比较 t a b l e 3 2c o m p a r i s o no f d i f f e r e n tr a d i xc o m p u t a t i o n f f t 算法实数乘法 实数加法 基一2 ( 2 l - 4 ) n + 4( 3 l - 2 ) n + 2 基一4 ( 1 。5 l - 4 ) n + 4( 2 7 5 l - 2 ) n + 2 基一8( 1 3 3 3 l - 4 ) n + 4( 2 7 5 l - 4 ) n + 4 基- 1 6( 1 3 1 2 5 l - 4 ) n + 4( 2 7 1 8 7 5 l - 2 ) n + 4 针对本课题需要“点复数专用f f t 处理器的设计，由于要处理的序列点数不 多，运算量不大，选熙了操佐简单、容易控制静纂- 2 算法。并簏保证系统需要的 工作速度和实时数据处理的要求。 3 4f f t 硬件实现结构研究 参照图3 5 所示的8 点基2 按时间抽取运算流程图嗍，综合起来f f t 硬件实现 结构有四种：顺序处辉、级联处理。并行迭代处理和阵列处理。 x(o)t、：一 囊 夕x 0 ) 3 4 1 顺序处理 图3 5 鬈点蒸之按时闽撼取逡蕤滚程圈 f i g u r e 3 5 8p o i n t sr a d i x - 2d i tc o m p u t i n g 顺序处理f f t 只用一个蝶形运算单元，输入量、中问量、输出量均使用同一 存储器。它的运算顺序是从第级的第一个蝶形够元开始依次计算，完成第级 所有蝶形单元运算詹，再进行第二级运算，直到算完所有级的蝶形单元为止。这 样就完成了f f t 的全部运算。如图3 5 所示，按照圈中蝶彤上栋号从l 到1 2 的顺 1 5 、，、i，、l，、，、，、i，、， 1 2 3 4 5 6 7 ，k，l、，t，t，l x x x x x x x 序进行计算。由于输入数据是按自然颓序排列的，魏果不徽处理，刹输出数据是 倒序排列的。这种处理方法的优点是节省硬件资源。但缺点也很明显，由于只使 用一个蝶形运算单元，造成运算速度缓慢，控制复杂。为了提高效率，可以使用 双内存结构( x 2r a m 结构) 。结合乒乓操作的思想，终部电路弱用运算模块运算 时空闲