（电路与系统专业论文）80211n系统中fftifft处理器的设计与实现.pdf

摘要 摘要 8 0 2 1 l n 系统采用了m i m o o f d m 技术，o f d m 技术是利用f f t i f f t 来实 现数据的正交调制和解调，f f t 处理器是o f d m 系统中的核心数据处理单元，为 了实现o f d m 系统的广泛应用，设计基于8 0 2 1 1 n 系统的f f t i f f t 有着重要的实 用价值和应用意义。 本文首先设计了一种应用于8 0 2 1 l n 的6 4 1 2 8 点f f t i f f t 处理器。采用基于 存储器的单蝶形四路并行结构可以有效地实现对连续流的处理。不仅能实现6 4 点 和1 2 8 点f f t i f f t ，而且位宽可以任意配置。采用了一种改进的混合基蝶形单元， 可以实现基4 和基2 运算，和传统的4 路并行方法相比，需要更少的硬件资源。 数据运算采用了块浮点算法，增大了数据的动态范围，有效的解决了f f t 中运算 溢出的问题，以接近定点格式的资源达到了更高的精度。在h j t c0 1 8 u mc m o s 工艺下完成综合、版图设计、静态时序分析和后仿真，投片面积为：2 0 4 x 1 9 6 删n 2 ， 内核面积为：1 3 5 x 1 2 7 m m z ，内核最高工作频率可达3 0 0 m h z 。由仿真波形可以看 出：完成6 4 点f f t i f f t 运算只需4 8 个时钟周期，完成1 2 8 点f f t i f f t 运算只 需1 2 8 个时钟周期。 接着设计了一种可配置高精度f f t i f f t 处理器。设计中采用了基于存储器的 基4 串行结构，- 降低了系统的复杂性，用一个复数乘法器的分时复用实现了基4 蝶形运算，大大节省了资源。采用了一种改进的块浮点算法，有效避免了溢出问 题并且提高了精度。运算点数可配置为6 4 、2 5 6 、1 0 2 4 ，实部、虚部均为1 6 b i t 数 据，不仅可以实现f f t 运算，还可以实现i f f t 运算。在s m i c0 1 3 u mc m o s 工 艺下综合内核面积为1 2 5 x 1 5 8 n 吼2 ，最高频率为2 1 0 m h z 。仿真结果显示了本设 计的高精度特性。 关键词：f f t i f f t ，块浮点，可配置，无冲突地址生成 a b s t r a c t a b s t r a c t t h ec o r et e c h n o l o g yo f8 0 2 1ini st h em i m o ( m u l t i p l e - i n p u tm u l t i p l e o u t p u t ) 一 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 mu s e st h ef f t ( f a s t f o u r i e rt r a n s f o r m ) i f f t ( i n v e r s ef a s tf o u r i e rt r a n s f o r m ) t om o d u l a t ea n dd e m o d u l a t e t h ed a t a f f tp r o c e s s o ri st h ec o r ed a t ap r o c e s s i n gu n i ti no f d ms y s t e m i no r d e rt o r e a l i z et h ew i d ea p p l i c a t i o no fo f d m ，i th a si m p o r t a n tp r a c t i c a lv a l u ea n da p p l i c a t i o n s i g n i f i c a n c ef o r8 0 2 1i nt od e s i g nf f t n f f tp r o c e s s o n i nt h i st h e s i s ，id e s i g na6 4 12 8p o i n tf f t i f f tp r o c e s s e rd e v e l o p e dp r i m a r i l yf o r t h ea p p l i c a t i o ni nam i m o - o f d m m u l t i p l e x i n gb a s e di e e e8 0 2 1i nw l a n b a s e b a n d p r o c e s s o r t h ep a r a l l e la r c h i t e c t u r eo fs i n g l eb u t t e r f l yi sp r o p o s e dt oe f f i c i e n t l yd e a l w i t l ls t r e a m i n gd a t af l o w 。t h ep r o p o s e dp r o c e s s o rn o to n l ys u p p o r t st h eo p e r a t i o no f f f t i f f ti n6 4p o i n t sa n d12 8p o i n t sb u tc a na l s oc o n _ f i gb i t s - w i d t ha r b i t r a r i l y i n a d d i t i o n ，i tu s e sai m p r o v e db u t t e r f l yu n i tc a np e r f o r me i t h e ro n er a d i x 一4b u t t e r f l yo rt w o r a d i x 一2b u t t e r f l i e sa n dn e e d sl e s sh a r d w a r er e s o u r c ec o m p a r e d 、v i t l lt r a d i t i o n a l f o u r - p a r a l l e la p p r o a c h b l o c kf l o a t i n gp o i n ta l g o r i t h mi su s e dt oi n c r e a s et h ed a t a d y n a m i cr a n g ea n ds o l v et h et r o u b l eo fo v e r f l o w ，w h i c hc o s t ss a m ea sf i x e dp o i n t a l g o r i t h mb u ta c h i e v i n gb e t t e rp r e c i s i o n t h ep r o p o s e dp r o c e s s o ri sd e s i g n e di nah j t c 0 1 8 u mc m o s p r o c e s s ，t h el a y o u ts i z ei s2 0 4 x 1 9 6 r a m 2 ，t h ec o r es i z ei s1 3 5 x 1 2 7 r a m 2 t h eh i g h e s tc l o c kf r e q u e n c yi s3 0 0 m h z t h ep r o p o s e dp r o c e s s o rr e q u i r e so n l y4 8c l o c k c y c l e sf o ra6 4p o i n t sf f t i f f ta n d12 8c l o c kc y c l e sf o ra12 8p o i n t sf f t i f f t id e s i g nar e c o n f i g u r a b l eh i g h - p r e c i s i o nf f t 以f f tp r o c e s s o r t h ew h o l ed e s i g n u s e sr a d i x 一4s e r i a la r c h i t e c t u r e ，r e d u c i n gt h es y s t e mc o m p l e x i t ya n ds a v i n gh a r d w a r e r e s o u r c e p r e s e n tai m p r o v e db l o c kf l o a t i n gp o i n ta l g o r i t h mw h i c hs o l v e st h eo v e r f l o w i nl o n gp o i n tf f te f f e c t i v e l ya n di m p r o v e sp r e c i s i o n t h ep o i n tc a nb ec o n f i g e df o r6 4 、 2 5 6 、10 2 4a n dt h er e a la n di m a g i n a r yp a r t so fd a t aa r e16b i t s ，t h ed e s i g nn o to n l yc a n i m p l e m e n tf f t ，b u ta l s oc a ni m p l e m e n ti f f t t h ep r o p o s e dp r o c e s s o ri sd e s i g n e di na s m i co 13 u mc m o s p r o c e s s ，t h ea r e ai s1 2 5 x 1 5 8 r a m 2 a tt h eh i g h e s tc l o c kf r e q u e n c y o f210 m h z t h es i m u l a t er e s u l ts h o w sh i g h - p r e c i s i o no ft h ed e s i g n i i a b s t r a c t k e y w o r d s ：f f t i f f t ，b l o c kf l o a t i n gp o i n t ，c o n f i g u r a b l e ，c o n f l i c tf r e ea d d r e s s i i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：垒垒 日期：加1 。年箩月1 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： ) 导师签名：2 雒 日期：仍加年岁月1 日 第一章绪论 第一章绪论 在无线通信技术飞速发展的今天，o f d m 系统得到了广泛的应用，而快速傅 立叶变换与其反变换正是o f d m 系统中的重要子模块，因此对f f t i f f t 处理器 的设计成为关键。 1 1 课题的研究背景 自2 0 世纪8 0 年代以来，由于数字信号处理技术的飞速发展，正交频分复用 ( 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 技术已经成功应用于非对 称数字用户线( a d s l ) 、数字音频广播( d a b ) 、数字视频广播( d v b ) 、高清晰度 电视( h d t v ) 、无线局域网( w l a n ) 等系统中，而且已经成为无线局域网标准 的一部分。随着人们对通信数据化，宽带化，个人化和移动化的需求增强，o f d m 技术在综合无线接入领域会获得越来越广泛的应用。 o f d m 技术可以将一个频率选择衰减信道分解到多个扁平子信道上，并且更 便于均衡。其次，o f d m 技术可以使各个子载波重叠起来，增加了频谱的利用率。 因此，o f d m 技术被广泛运用到很多标准中，如：i e e e 8 0 2 1 1 a g n ( w i f i ) ，i e e e 8 0 2 1 6 d e ( w i m a x ) ，以及d a b 、d v b t h 和c m m b 数字电视标准口j 。 8 0 2 1 l n 作为一种全新的无线网络协议，其传输速度、覆盖范围和兼容性等方 面，和先前的各类相关标准相比均具有质的飞跃。8 0 2 1 1 n 综合采用了o f d m 和 m i m o ( 多输入多输出) 等先进技术，使无线网络的传输速度提高到 1 0 0 m b s 6 0 0 m b s ，传输距离可达数公里；独特的双频带工作模式( 包含2 4 g h z 和5 g h z 两个工作频段) ，保障了与以往的8 0 2 1 1 a b i g 等标准的兼容【引。 为了完成8 0 2 1 l n 的系统设计，f f t i f f t 处理器是一个关键部件，o f d m 系 统通过f f t i f f t 实现数据的时域和频域之间的变换，即数据子载波的正交调制与 解调。由于f f t i f f t 是o f d m 系统中的核心数据运算单元，研究和设计一种适 合于8 0 2 1 1 n 系统的f f t i f f t 处理器，对于未来主流移动通信o f d m 技术有着重 要的应用意义和实用价值。 电子科技大学硕士学位论文 1 2 课题的研究现状 1 2 1 无线通信技术的发展 无线局域网w l a n ( w i r e l e s sl o c a la r e an e t w o r k ) 就是在不采用传统电缆线的 情况下，提供传统有线局域网的功能，无线局域网的网络能够随着用户的需要移 动或变化，具有传统局域网无法比拟的灵活性。无线局域网的标准主要包括i e e e 推出的8 0 2 1 1 系列标准以及欧洲推出的高性能无线本地局域网( h i p e r l a n ) 标准， 其中i e e e8 0 2 1 1 系列标准经过多年的发展和完善，在技术上不断成熟，在市场上 也得到了广泛的应用，已经成为目前无线局域网的主导技术标准【4 】。 i e e e8 0 2 1 1 无线局域网标准的制订是无线网络技术发展的一个里程碑。它是 i e e e 最初制定的一个无线局域网标准，工作在2 4 g h z 频段，采用直接序列扩频 技术( d i r e c ts e q u e n c es p r e a ds p e c t r u m ，d s s s ) 或跳频扩频技术( f r e q u e n c yh o p p i n g s p r e a ds p e c t r u m ，f h s s ) ，速率最高达到2 m b p s 。但由于2 m b p s 的传输速率，在很 多应用上都不能满足人们的需要，i e e e 工作组又相继推出了8 0 2 1 1 b 和8 0 2 “a 两个新标准。8 0 2 。1l b 标准工作于2 4 g h z 频段，物理层支持1 m b p s ，2 m b p s ， 5 5 m b p s ，及1 1 m b p s4 种传输速率，在上述4 种速率之间进行切换，而且在2 m b s 、 1 m b s 速率时与i e e e8 0 2 1 1 兼容【引。而i e e e 工作组在1 9 9 9 年推出的8 0 2 1 1 a 标 准工作在5 g h z 频段，采用o f d m 技术，其最大传输速率可达到5 4 m b p s 。2 0 0 3 年i e e e 批准了8 0 2 1 1 9 协议标准，该标准工作在2 4 g h z 频段，与8 0 2 1 1 b 后向兼 容，8 0 2 1lg 的两个主要工作模式是直接序列扩频模式以及o f d m 传输模式，其中 直接序列扩频模式与8 0 2 1 l b 标准后向兼容，能够提供最高为5 4 m b p s 的数据传输 速率。目前8 0 2 1 1 系列标准中的最新标准为8 0 2 1 1 n 协议标准，8 0 2 1 1 n 标准结合 了o f d m 和m i m o 两种热点技术，在采用4 天线，4 0 m h z 带宽的条件下，物理 层峰值速率够达到6 0 0 m b p s ，表1 1 显示了8 0 2 1 1 系列标准的比较1 6 j 。 表1 - 18 0 2 1 i 系列标准比较 标准工作频段峰值速率关键技术适用业务 8 0 2 1 l2 4 g h z 2 m b p s d s s s ，f h s s数据 8 0 2 1 1 b2 4 g h z1 1m b p sd s s s 数据，语音，图像 8 0 2 1 1 a5 g h z5 4m b p so f d m 数据，语音，图像 8 0 2 1 l g 2 4 g h z 5 4 m b p s d s s s ，o f d m数据，语音，图像 8 0 2 1 i n2 4 g 5 g h z 6 0 0 m b p so f d m ，m i m o 数据，语音，图像 2 第一章绪论 1 2 2f f t 处理器的研究现状 f f t 算法是c o o l e y 和t u k e y 于1 9 6 5 年提出的一种计算离散傅立叶变换d f t 的快速算法，它的出现给d f t 提供简化算法，大大降低了运算量，使得d f t 应用 在广阔的领域里，f f t 目前在未来主流通信技术o f d m 中也得到了广泛的运用， f f t 是o f d m 技术中关键的数据调制解调模块。 f f t 处理器在国内外都有很多研究，根据不同的f f t 点数和应用要求采用了 不同的蝶形算法和硬件结构。从算法上可以分：基2 ，基4 ，基8 等固定基算法， 还有基2 4 、基2 4 8 等混合基算法。硬件结构主要包括：基于存储器结构的f f t 处理器、流水线结构的f f t 处理器、并行结构和阵列结构的f f t 处理器。并且随 着o f d m 技术的不同应用要求，同一个标准中兼容各种数据速率的传输，即o f d m 系统中有各种不同工作模式需要不同点数的f f t ，因此，f f t 的可配置技术也得 到了广泛的研究。 1 3 本论文的研究内容和结构 本论文主要设计了两种f f t i f f t 处理器，基于8 0 2 1 1 n 的f f t i f f t 处理器和 高精度可配置f f t i f f t 处理器。完成了m a t l a b 定点算法、电路结构设计、r t l 代码设计、仿真验证、a s i c 实现等工作。设计的处理器具有以下特点。 1 基于8 0 2 1 1 n 的f f t i f f t 处理器 采用基于存储器的单蝶形4 路并行结构，实现了4 路并行无冲突地址产生方 法，有效地提高了吞吐率。采用的r a m 双乒乓结构实现了对输入和输出均为连续 数据流的缓存处理。不仅能实现6 4 1 2 8 点f f t 和i f f t ，而且位宽可以根据系统任 意配置。为了提高数据运算的精度，设计采用了块浮点算法，实现了精度与资源 的折中。1 6 位位宽时，在h j t co 1 8 u mc m o s 工艺下综合，整个芯片面积为： 2 0 4 x 1 9 6 m m 2 ，内核的面积为：1 3 5 x 1 2 7 舢m 2 ，内核最高工作频率可达3 0 0 m h z 。 2 高精度可配置f f t i f f t 处理器 采用了基于存储器单蝶形串行结构，降低了系统的复杂性，节省了一定的资 源。实现了一种新颖的块浮点算法，有效避免了溢出问题并且提高了精度。运算 点数可以通过对产生地址计数器的位选择配置为6 4 、2 5 6 、1 0 2 4 ，实部、虚部均为 1 6 b i t 数据，不仅可以实现f f t 运算，还可以实现i f f t 运算。在s m i co 1 3 u mc m o s 工艺下综合的内核面积为1 5 5 m m 2 ，最高频率为2 1 0 m h z 。仿真结果显示了本设计 电子科技大学硕士学位论文 的高精度特性。 本论文章节安排： 第一章介绍本论文的研究背景和研究现状，阐述了本论文的主要研究内容。 第二章介绍o f d m 系统组成和基本工作原理，讨论了离散傅立叶变换基本原 理和快速傅立叶变换基本原理，给出了各种算法的理论推导和常见f f t 处理器的 硬件实现结构。 第三章介绍了基于8 0 2 1 l n 系统的f f t i f f t 处理器的设计，进行了定点算法 分析，给出了处理器的整体结构框图，详细介绍了各个模块的设计思路和实现方 法，给出了功能仿真结果和f p g a 原型验证结果。 第四章介绍了基于8 0 2 1 l n 系统的f f t i f f t 处理器的a s i c 实现，对前端的 各个步骤进行了详细的介绍，给出了后仿的结果，给出了投片的面积、时序等信 息。 第五章介绍了高精度可配置f f t i f f t 处理器的设计，进行了算法分析，给出 了处理器的整体结构框图，详细介绍了各个模块的设计思路和实现方法，给出了 功能仿真结果，并进行了版图设计。 第六章为本论文的结论与展望。 4 第二章o f d m 系统和f f t 原理 第二章o f d m 系统和f f t 原理 o f d m 技术是以f f m f f t 处理器作为核心的数据调制解调单元，本章首先对 o f d m 系统进行介绍，然后介绍离散傅立叶变换的基本原理，进而引出快速傅立 叶变换( f f t ) ，并且详细分析了快速傅立叶变换的各种算法和硬件实现结构。 2 1o f d m 系统 o f d m 技术的基本思想是把信道划分为多个子信道，将高速串行数据流调制 到多个正交的子载波上并行传输，从而使符号速率降低，减少符号间干扰。o f d m 技术允许子载波频谱部分重叠，只要满足子载波之间的正交性就能从混叠的子载 波上分离出数据信息，这样大大提高了频谱的利用率。o f d m 系统组成： 图2 - l0 f d m 系统组成框图 在发送端，首先对输入比特流进行纠错编码和交织，然后将比特映射成p s k 或q a m 数据，插入导频，再通过i f f t 变换将数据调制到多个相互正交的子载波 上并行发送。这些经i f f t 变换后得到的个样点称为一个o f d m 符号，接着给 每一个o f d m 加上循环前缀，以抵抗由于信道的多径效应引起的符号间干扰，再 通过加窗使得系统带宽之外的功率快速下降，最后经过d a 变换通过发射机发送 出去。接收端执行与发送端相反的过程，首先对接收到的信号进行定时和频偏估 计，根据定时估计找到o f d m 符号中有效数据的起始位置，即f f t 的开窗位置， 再对这点的有效数据进行f f t 变换，去除导频，然后进行解调、解交织和解码， 最后恢复出原始数据。 电子科技大学硕士学位论文 2 2 离散傅立叶变换基本原理 离散傅里叶变换( d i s c r e t ef o u r i e rt r a n s f o r m ，简称d f t ) 是数字信号处理领 域中常用的重要数学变换，其实质是对有限长序列傅里叶变换的有限点离散采样， 从而使数字信号处理可以在频域采用简单的数学运算进行，开辟了频域离散化的 道路，大大增加了数字信号处理的灵活性。但是，在很长的一段时间里，由于d f t 的计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到广 泛的应用。 对一个点的有限长序列x ( n ) ，其d f t 为： 彳( 七) = x ( 刀) 嘭，k = o ，1 ，n - 1 ( 2 - 1 ) 其中，旋转因子为： = e - j 2 n n = c o s 唔hs i n ( 争( 2 - 2 ) 反变换i d f t 为： x ( 门) = 一i 、，x ( k ) w d 础，n = o ，1 ，一1 ( 2 3 ) vn = o 可以看出，d f t 和i d f t 的运算量是相同的。通常，公式2 1 中的数均为复数， 因此每计算一个x ( k ) 值，需要次复数乘法和( 一1 ) 次复数加法。而x ( k ) 有个 点，所以完成整个d f t 运算总共需要2 次复数乘法和n ( n 一1 ) 次复数加法。一次 复数乘法直接展开需要4 次实数乘法和2 次实数加法；一次复数加法则需2 次实 数加法。 因而，直接计算d f t ，乘法次数和加法次数都是和2 成正比的，当很大时， 运算量是相当大的，如1 0 2 4 点的d f t 变换，需要复乘一百万次以上，这对实时性 很强的信号处理来说，对计算速度要求太高。因而需要改进对d f t 的计算方法， 以减少运算次数。快速傅立叶变换( f f t ) 正是离散傅立叶变换( d f t ) 的一种快 速算法。 2 3 快速傅立叶变换基本原理 快速傅立叶变换是一种计算离散傅立叶变换的有效算法，最早是由库利和图 6 第二章o f d m 系统和f f t 原理 基于1 9 6 5 年在计算数学上发表的著名的“机器计算复傅立叶级数的神算法” 的文章中提出，经过人们对算法的改进、发展和完善，使d f t 的计算大大简化， 运算时间一般可缩短一、二个数量级，从而使d f t 的运算在实际中真正得到了广 泛的应用。 快速傅立叶变换算法是利用旋转因子的对称性、周期性和可约性，将长序列 的d f t 分解为短序列的d f t 。由于d f t 的运算量和2 成正比的，所以越小使 总的运算量越少。它在算法上基本可以分为两大类，即按时间抽取( d i t ) 法和按 频率抽取( d i f ) 。d i t 算法是把输入序列按其顺序的奇偶分解为越来越短的序列， d i f 算法是把输出序列按其顺序的奇偶分解为越来越短的序列。本节以d i t 算法 为例介绍基2 、基4 、基8 和混合基算法的原理【7 j 。 2 3 1 基2 算法基本原理 点数是2 的整数次幂，将x ( ，? ) 先按刀的奇偶分成两组： 硝x(22，r三掣x，一o，1，生2(r) 2 + 1 ) = j 。 则可将d f t 化为： x ( 尼) = d f t x ( n ) = x ( ) 嘭 = x ( 2 0 w z 睹+ x ( 2 r + 1 ) w j 2 ” = x , ( r ) w j 时+ 蝶x 2 ( r ) w j 庸 ( 2 - 4 ) ( 2 5 ) 利用旋转因子的可约性： 蝶：p 一百2 1 t 2 ：p 印州了n ) ：，：( = e - j 2 z n ) ( 2 6 ) 公式2 - 5 司以写成： 耶) 2 萎北) l t e r 茄2 + 眩丢删吆z( 2 - 7 ) = x ，( 后) + 蝶x 2 ( 七) 式中，五( 七) 和置( 尼) 分别是x l ( r ) 和恐( ，) 的n 2 点d f t 。可以看出，n 点 d f t 已经分解成两个n 2 点的d f t ，它们又可以组合成点的d f t 。但是分解之 电子科技大学硕士学位论文 后都是2 点的序列，而x ( k ) 却有点，还必须计算另一半项数的结果，利用旋 转因子的周期性： r n 2 一ln 2 - 1 五洋+ 七) = 墨( ，) 暇驴”= 五( ，) 喋：= 五( 七) ( 2 - 8 ) ，= 0r 1 0 n 置晴+ | i ) = 置( 忌) ( 2 9 ) 这样，得到了后半部分七值( 七= n 2 ，一1 ) 所对应的五( 七) 和x ：( 尼) 分别等 于前半部分尼值( 尼= 0 1 ，n 2 1 ) 所对应的x 1 ( 尼) 和五( 尼) 。将x ( 后) 表达为前后两 ( 七) ：墨( j j ) + 陟贯j ，2 ( 七) ，七：o ，1 ，= n - 一1 ( 2 - 1 0 ) 后半部分工( 冬+ 七) ： 州麓黧x ? 2 ( 譬= k ，等。p = 墨( 七) 一乃葛 ( 七) ， = o ，1 ，等一1 只要求出( o ，2 ) 区间内所有墨( 七) 和五( 尼) 值，即可求出( o ，n 一1 ) 区间内所 有x ( 七) 值，因此节省了大量的运算8 1 。上两式的运算可以用下面的流图来表示： 五( 七) t ( 七) 五( 七) + 孵x 2 ( j j ) 墨( 七) 一噼五( 七) 图2 - 2 按时间抽取的基2 蝶形运算单元流图符号 每个蝶形运算需要一次复数乘法和两次复数加法。可知，一个点的d f t 分 解为两个2 点的d f t 后，如果直接计算2 点d f t ，则每一个2 点的d f t 需要( 2 ) 2 次复数乘法和( n 2 ) ( n 2 1 ) 次复数加法，将两个n 2 点的d f t 合成 8 第二章o f d m 系统和f f t 原理 为点的d f t 时，要进行2 个蝶形运算，还需要2 次复数乘法和次复数 加法运算。因此通过第一步分解后，共需要2 ( n 2 ) 2 + 2 n 2 2 次复数乘法和 n ( n 2 1 1 + n ：n z 2 次复数加法，因此，总的运算量近似减少了一半。采用流 图表示法，可将上述分解过程表示于图2 3 中。 玉( o ) = x ( o ) x ( 1 ) = x ( 2 ) 玉( 2 ) = x ( 4 ) 五( 3 ) = x ( 6 ) 夏( 0 ) = 工( 1 ) 五( 1 ) = z ( 3 ) 五( 2 ) = “5 ) x x 3 ) = 双7 ) 图2 - 3 按时间抽取将一个n 点的d f t 分解为2 个n 2 点d f t ( n = 8 ) - 而n 2 仍然是偶数，所以可以进一步把每个2 点子序列再按其奇偶部分分 解成两个n 4 点子序列，仍以n = 8 点的d f t 为例进行进一步分解，得到流图2 - 4 ： 五( 0 ) = x ( 0 ) = “o ) 五( 1 ) = 五( 2 ) = z ( 4 ) 葺( 0 ) = 五( 1 ) = x ( 2 ) 五( 1 ) = 五( 3 ) = x ( 6 ) 五( 0 ) = 五( o ) = x ( 1 ) 五( 1 ) = 五( 2 ) = x ( 5 ) 茏( 0 ) = 五( 1 ) = 邢) 艽( 1 ) = 五( 3 ) = x ( 7 ) 图2 - 4 按时间抽取将一个n 点d f t 分解为4 个n 4 点d f t ( n = 8 ) 根据前面的分析可知，利用四个n 4 点d f t 及两级蝶形组合运算来计算点 9 聊 聊 仰 聊 珊 仰 朋 确 z x x x m 聊 仰 卿 聊 删 硼 删 砌 删 炯 焖 姗 电子科技大学硕士学位论文 d f t ，比仅用一次分解组合方式时的计算量又减少了约一半。最后，对剩下的是四 个4 = 2 点的d f t 再进行分解可以得到8 点d f t 的完整流图【9 】。 由流图可见，对n = 2 工时，共有三级蝶形，每一级都由2 个蝶形运算构成， 而每个蝶形要一次复乘和两次复加，所以，每一级运算都需要2 次复数乘法和 次复数加法，这样三级运算总共需要： 复数乘法 m u l t f ：i n l ：冬l o g f ( 2 1 2 ) 二二 复数加法么d 砟= n x l = n l o g 多 ( 2 - 1 3 ) 得到d f t 复数乘法次数和f f t 对比如表2 1 所示： 表2 1d f t 和f f t 的运算量对比 点数d f t 计算量2f f t 计算量n 1 0 9 ? 计算量对比2 n l o g 多， 2422 0 41 682 o 86 42 42 7 3 21 0 2 41 6 06 4 6 44 0 9 63 8 41 0 7 2 5 66 5 5 3 6 2 0 4 8 3 2 0 5 1 2 2 6 2 1 4 44 6 0 85 6 9 1 0 2 4 1 0 4 8 5 7 6 1 0 2 4 01 0 2 4 4 0 9 6 1 6 7 7 7 2 16 4 9 1 5 23 4 l _ 3 2 3 2 基4 算法基本原理 与基2 算法类似，对于点有限长序列x ( n ) 的d f t 按照时域分解展开有： x ( 尼) = x ( 4 n ) w 4 腑+ x ( 4 + 1 ) w 2 肿1 n = on = o + x ( 4 n + 2 ) w 嚣4 肿2 弦+ x ( 4 门+ 3 ) 嘴肿3 弦 n = on z o 对上式进行变量替换，令：x ( 4 n ) = x l ( n ) ，x ( 4 n + 1 ) = x 2 ( n ) ， x ( 4 n + 3 ) = 焉( 甩) ，而且：畋础= 嘭4 ，可以得到： 1 4 - i4 - 1 x ( 尼) = 而( 圳饼。+ 孵恐( 枷嚼。 ，4 1n 4 1 + 蝶毛( 门) 暇；。+ 暇_ ( 门) 蝶；。 n ；0 n = o ( 2 - 1 4 ) x ( 4 n + 2 ) = x 3 ( 玎) ， ( 2 - 1 5 ) n