（电工理论与新技术专业论文）fft处理器的设计与实现.pdf

d e s i g na n dr e a l i z a t i o no ft h ef f tp r o c e s s o r a b s t r a c t t h i sp a p e rb r i n g sf o r w a r dad e s i g na n dr e a l i z a t i o nf o rt h ef f tp r o c e s s o r t h e d e s i g n i n c l u d e ss y s t e ma r c h i t e c t u r ed e s i g n 、a r i t h m e t i cr e a l i z a t i o n 、f p g a r e a l i z a t i o n 、v e r i f i c a t i o na n dt e s t b e n c he t c t h ed e s i g nh a sm a d eag o o db a s ef o rt h e f u t u r ed e v e l o p m e n to ft h ef f tp r o c e s s o r t h ep r o c e s s o rc a nb eu s e di nr e a lt i m e p r o c e s s i n ge t c t h ef i r s tc h a p t e ri st h es u m m a r i z a t i o nw h i c hl o o k sb a c kt h ed e v e l o p m e n t h i s t o r yo ft h ef f t a r i t h m e t i ca n di t sa p p l i c a t i o ni ne a c hd o m a n i a l t h es e c o n dc h a p t e rb r i n g sf o r w a r dt w ok i n d sf f ta r i t h m e t i ca n df o u rh a r d w a r e a r c h i t e c t u r e s t h i sc h a p t e rm a k ec h o i c eo nr e a l i z a t i o n t h et h i r dc h a p t e rd i c u s s e st h ed e s i g no ff f tc o n t r o l l e r sc o m p u t eu n i t h e r e w et a l k sa b o u th o wt od e s i g na d d e ra n dm u l t i p l i e r w eu s et h ea d v a n c ec a r r yc h a i n t od e s i g nt h ea d d e ra n du s et h ea r r a ya r c i t e c h u r et od e s i g nm u l t i p l i e r t h ef o u r t h c h a p t e rm a i n l y d i s c u s sf f t p r o c e s s o r s a r c h i t e c t u r ea n d r e a l i z a t i o n h e r e ，w ei n t r o d u c et h er e a l i z a t i o no fc o n t r o l l e ra n dd i s c u s st h es t a t e t r a n s f e ri nt h ec o n t r o l l e r w ea l s od i s c u s st h er e a l i z a t i o no ft h ea d d e r s sg e n e r a t o r u n i t t h ef i f t hc h a p t e rm a k e se m u l a t i o na n dm a k e se x e p e c t a t i o no ft h ef f tc o n t r o l l e r k e y w o r d s ：f f tp r o c e s s o r d s pd f t b u t t e r f l yo p e r a t i o n 插图清单 图1 1用d f t 计算循环卷积 图2 - 1蝶形运算符号， 图2 2n 点d f t 的一次时域抽取分解图( n = 8 ) 图2 3n 点d f t 的第二次时域抽取分解图( n = 8 ) 图2 - 4n 点d i i - f f t 运算流图( n = 8 ) 图2 5基一4d i t 蝶形单元信号流图 图2 - 6 基4 - d i t 蝶形单元信号流图 图2 7n = 8 按时间抽取基2 f f t 的信号流 图2 - 8n = 8 流水式f f t 的第一级运算模块 图2 - 9阵列式f f t 处理模式图 图3 1 i e e e3 2 浮点格式 图3 - 2一个带符号的长度为b 位定点小数的表示 图3 。】一位全加器， 图3 24 位级连加法器一 图3 34 位超前进位链， 图3 - 4求补电路一 图3 5加法器综合 图3 5运算原理图 图3 - 6 运算步骤图 图3 7两个4 位无符号数相乘的阵列乘法器 图3 _ 8两个4 位无符号数斜进位的阵列乘法器 图3 - 9串行累加 图3 1 0 并行结构一 图3 - t 1 保留进位加法器一 图3 1 2w a l l a c e 结构 图3 1 3 串行结构 3 2 3 3 3 3 图3 1 4 压缩器延时和一级超前进位加法器延时3 5 图3 1 5 压缩器延时和一级超前进位加法器延时3 5 图3 1 6 乘法器的综合3 7 图4 1处理器的操作步骤3 8 图4 2f f t 处理器框架图3 9 图4 3蝶形处理单元4 0 国4 - 4f f t 处理器中使用的周期波形4 1 图4 5 地址发生器单元4 5 图4 6m o o r ef s m 的基本结构4 9 图4 7 m e a l yf s m 的基本结构4 9 图5 1l e 正常模式5 2 图5 2l e 算术模式5 3 图5 3 s t r a i x 的分层进位结构一5 3 图5 - 4蝶形单元的综合结果5 5 图5 5控制器综合结果5 5 j 墙p mm坫加加弱丝笛拍”凹汐n” 表2 1 表2 2 表3 1 表3 - 2 表3 2 表3 3 表4 1 表4 - 2 表4 3 p 值变化顺序 地址列表 码制 表格清单 一位加法器真值表 手算硬件实现 5 3 计数器真值表 蝶形运算步骤 基本序列发生器地址 x , y 地址 1 4 l5 2 l 2 2 2 8 3 4 4 1 4 6 4 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包禽为获得 宣魍工业态堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签字嚏字嗍5 年牛月二f 日 学位论文版权使用授权书 本学位论文作者完全了解盒匿工些盍堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 鱼世工些盘堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：嘏儒後 签字日期：墨年乒月西日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名 ) 孙匕 签字目期：“d 辟印月托日 ， 电话： 邮编： 致谢 我的硕士研究生生活随着这篇论文的完成，也将结束了。在这难忘的两年多微电子 所的研究生生活中，我遇到了很多良师益友。他们都给我了很多的帮助和关怀，能在这 样的环境f 学习让我感到非常的幸福。现在大家都要分开了，在这里我只能默默的祝福 他”j 身体健康万事如意1 1 尤其是我的导师高明伦教授和我的师母潘剑宏老师。正是高 老师的学识和人品吸引了我们义无反顾的投入到集成电路设计的行业，带领我们进入了 一个充满神奇的专业! 】 在这里我还不得不提起和我一级的兄弟们，他们幽默、勤奋、善良、热情、活泼。 他们所有的优良品质都深深的感染了我。能够和他们一起学习、生活让我受益非浅。他 们是：郭舒生、张俊、杨明、郭彦、王科、孙华波、圣应山、陈巨、鲁斌、曹睿、刘涛。 感谢胡永华老师、王锐老师、张多利老师、张溯老师、宋宇鲲博十等。他们都给了 我很大的帮助。 最后，感谢我的家人。你们无微不至的关怀和照顾，让我可以无后顾之忧的完成我 的学业。 作者：胡德俊 2 0 0 6 年4 月于科技楼 1 1f f t 概述 1 1 1f f t 算法概述 第一章绪论 使用计算机开展数值计算工作离不开离散傅立叶变换( d f t ) 。d f t 不仅在 理论研究上有着重要的意义，而且在各种工程数字信号处理系统中起着核心的 作用。 d f t 广泛应用在数字通讯、语音处理、图像处理、谱估计、仿真、系统分 析、雷达、光学、医学影像、天文等应用领域中。d f t 也用于计算循环卷积( 图 1 1 ) 、线性卷积或信号的谱分析等纯数学领域。 图1 1 用d f t 计算循环卷积 在实际应用中，f f t 是最常见的数字信号处理算法，它在各种数字信号处 理系统中扮演重要的角色。本文研究了5 1 2 点f f t 处理器。在信号处理过程中， 频域分析往往比时域分析方便和高效，f f t 是时域和频域转换的基本运算。例 如，通过计算信号序列的f f t 可以直接分析它的数字频谱：在计算数字滤波器 的输出响应时需要进行卷积运算，它可以通过先进行f f t 运算而后将信号频谱 与系统频晌相乘再进行i f f t 变换得到：匹配滤波器需要相关运算，同样可以 通过f f t 运算得到。 f f t 运算就是建立在d f t 的基础上的，而实现f f t 的基本思想是：利用 d f t 的系数特性，合并d f t 运算中的某些项，把长序列变成短序列d f t ，从 而来减少其运算量。它的算法原理为，设序列点数n = 2 ，l 为整数。若不满 足，则补零。一种有效的f f t 算法就是基2f f t 算法，算法大概实现方法是将 x m ) 按n 的奇偶分成两组则x ( 咒) 的d f t 为 砸幼= x 时+ x ( n ) w 紫n # 偶数n 嫡数 n 2 - 1n 1 2 1 = 缸扫) 磉打+ x ( 2 r + 1 ) w 嚣n ( 2 ” r = o r - - o ，2 _ 1n 2 - 1 = 五驴) 咿+ 碟e a h ( r ) w 。2 打 r = 0 r = 0 就这样不断的分解，这样会大大的降低运算量。下面的章节会进一步对这个方 法进行讨论。 1 1 2f f t 的算法实现方法 f f t 算法本身已经相当成熟，很多领域对其高速实时运算的要求却不断提 高，实现f f t 算法的硬件方法也在不断地优化。目前主要有三种硬件实现方式： 通用数字信号处理芯片( d s p ) 、可编程逻辑器件及专用集成电路。选择哪种方 法实现f f t 算法，必须综合考虑f f t 算法、系统的要求及实现方法的特点。 通用d s p 是一种适合于进行数字信号处理的微处理器，其主要应用是实时 快速地实现各种数字信号处理算法。 目前国际市场采用单片通用d s p 实现1 0 2 4 点1 6 位字长、定点、块浮点或 浮点运算的f f t 处理的速度达到几十到数百u s 量级，其中采用t i 公司的 t m s 3 2 0 c 6 2 x 系列d s p 达到6 6 u s 数量级处理速度，t m s 3 2 0 c 6 4 x 系列d s p 达 到1 0 u s 量级，t m s 3 2 0 c 6 7 x 处理1 0 2 4 点基2 算法的f f t 需要1 2 4 3 0 u s 。 可编程逻辑器件目前正朝着更高速、更高集成度、更强功能和更灵活的方 向发展，它不仅已成为标准逻辑器件的个强有力的竞争对手，也成为掩膜式 专用集成电路的竞争者。由于v l s i 技术的高速发展，数字设计技术和方法的 进一步成熟，为新一代高速实时的f f t 、f i r 专用芯片或其他专门用途的信号 处理芯片提供了很好的基础。大规模可编程技术的发展，都使得专用处理器的 实现越来越有效和实用。同时，i p 核的出现使硬件设计可以在模块或部件级基 础上进行复用，提高了设计生产效率和避免了错误的发生。 可编程逻辑器件的厂商x i l i n x 、a l t e r a 公司都为数字信号处理提供了宏功 能模块或i p 内核，如高速乘法器、浮点算法功能、f f t 、i i r 滤波器、f i r 滤波 器等，可以直接调用。这些功能的内核大都是根据各种f p g a 芯片的结构进行 布局和布线优化过的，其资源利用率得到了较大的提高。在大容量f p g a 设计 中采用i p 模块可以缩短设计周期和上市时间，降低风险，提高系统的性能和可 靠性，如a l t e r a 公司的能够实现5 1 2 点、t 6 位、复数f f t 的i p 核在系统时钟 为9 6 m h z 时，处理速度可达2 7 u s 。x i l i n x 公司f f ti p 核处理1 0 2 4 点1 6 位字 长的f f t 运算，在t m s 配置下可以达到4 0 9 6 个时钟周期，即如果是1 0 0 m h z 外频时钟，处理速度达到4 0 9 6 u s 量级。但是用i p 核实现f f t ，需要外部r a m 配置，外围引脚较多不利于使用，且不利于针对特殊要求进行修改。 1 1 3f f t 处理技术的现状 ( 一) 高速f f t 处理的重要性 1 f f t 作为时域和频域转换的基本运算，是谱分析的必要前提，在通信等 数字信号处理领域有着极为广泛的应用。实时高速信号处理系统，如数 字语音编码、雷达信号处理、声纳信号分析、数字滤波、射电干涉阵等， 都需要使用专业f f t 计算设备进行实时处理。 2 f f t 专用芯片可以使成本降低，运算速度大幅度提高。过去通常用d s p 芯片，近年来专用a s l c 芯片无论在性能还是在成本上都呈现出越来越 大的优势。美国的r a d i x 公司提供的f f t 专用芯片就得到了极为广泛的 应用，得到了很大的收益。在国家安全上讲自主研发这项技术都是十分 重要的。 ( 二) 现状 目前国外f f t 通用数字信号处理器做成的f f t 处理器，处理2 5 6 点数据速 度较快的是t i 公司的t m s 3 2 0 系列，可以达到1 0 0 u s 。t i 公司的d s pc 6 7 x 系 列实现1 0 2 4 个复数点可达到5 6 u s 量级处理速度。而在国内，近年来我国的数 字信号处理学科发展也较快。d s p 处理器已经在我国的数字通信、信号处理、 雷达、电子对抗、图像处理等方面得到了广泛的应用，为科学技术和国民经济 建设创造了很大价值。全国有很多高校、科研机构的信号处理实验室都在大力 研究性能更高的数字信号处理设备，取得了很多研究成果。我国的科研人员通 过对先进的d s p 芯片的研究，已经研制出一些高性能处理设备的解决方案，并 且在板级p c b 设计方面，也取得了宝贵的设计经验。 我国某电子技术研究所研制的d s p 雷达数字信号处理通用模块，它使用 了6 片a d s p 2 1 0 6 0 和大规模可编程器件构成通用处理模块。通过信号处理算法 并行设计、系统多数据流设计、处理任务分配调度程序设计，实现高速实时雷 达数字信号处理。以f f t 算法为例，将任务分为3 个流水处理过程：f f t 、复 数乘法、i f f t ，实现多片d s p 组成并行处理。在3 3m h z 时钟下，l0 2 4 点处 理通过时间为0 7m s ，可以实现单通道数据率为1m h z ，双通道并行工作为2 m h z 。 国内的一些大学所研制的基于t m s 3 2 0 c 6 2 0 1 的高速实时数字信号处理平 台，实现基一2 的复数f f t ，允许输入数据的动态范围1 6 七i t ，可以实现5 9u s 内完成5 1 2 点的f f t ，1 3 0g s 内可以完成10 2 4 点的f f t 。 1 2 课题的意义 虽然傅立叶变换已经提出了上百年的时间，但因为运算量太大而直没有 得到发展。在数字信号处理的发展进程中，促进数字信号处理发展的其中一个 原因就是c o o l e y 和t u c k e y ( 1 9 6 5 年) 对一种计算离散傅立叶变换( d i s c r e t e f o u r i e r t r a n s f o r m ，d f t ) 的有效算法的提出。正是这样一个好的算法解决了数 字信号处理的运算速度。f f t 算法是快速傅立叶变换的缩写，正是快速傅立叶 变换彻底改变了傅立叶变换的运算量。它大大节省了运算时间，它让及时处理 大量的数据成为可能。也正是这类的快速算法让数字信号处理技术得到了长足 的发展。 实时数字信号处理的技术大大推动了许多领域的发展。现代数字信号处理 是面向高速、大容量数据流的实时处理，有些高端应用场合如雷达、声纳、地 震信号分析等，需要每秒几亿次到上千亿次以上的浮点运算速度，在射电干涉 仪中更达到了几十万亿次的运算速度，这可以通过高速v l s i 器件并行处理或 多级流水处理等来达到。本文就是对f f t 处理器地实现进行了基本的研究，为 将来的高速数字信号处理打下一个基础。 1 3 本文主要内容 本论文的主要内容安排如下： 1 ) 第二章结合课题任务，分析了f f t 处理器的相关技术方案， 包括： a 、离散傅立叶变换的原理； b 、快速傅立叶变换的原理 c 、f f t 中的基2 、基4 算法； d 、f f t 处理器的结构选择。 各方案的选择依据课题的需要，并综合考虑是否易于硬件实现，能否满足 实现中的模块化、规则化的要求。 2 ) 第三章根据设计要求，讨论了运算单元的设计。并给出了具体的设计例 子。 3 ) 第四章介绍了这个f f t 处理器的设计与实现 包括： a 、讨论了f f t 处理器的架构； b 、讨论了f f t 处理器一些主要单元的设计； 4 ) 第五章具体分析了这个处理器的仿真问题，并做出展望。 1 4 本章小结 本章回顾了f f t 算法的发展历史，以及f f t 算法在各个领域的应用。利用 d f t 系数的特性，合并d f t 运算中的某些项，把长序列变成短序列，从而减少 其运算量。f f t 算法是基于可以将一个长度为n 的序列的离散傅立叶变换逐次 分解为较短的离散傅立叶变换来计算这一基本原理。 4 第二章傅立叶变换的快速算法及硬件结构的选择 2 1离散傅立叶变抉 设x ( n ) 为有限长序列，长度为n ，我们把它看成周期序列烈功的一个周期， 而把x ( ”) 看成x ( ”) 以n 为周期进行周期延拓的结果。这样就建立了有限序列 烈脚和周期序列之间联系，即 x ( 聆) = ；鼢癸群。1 习惯上定义周期序列x ( ”) 的第一个周期( n z o n 一1 ) 为主值区间，x ( n ) 是 ；( ) 的主值序列。 x 0 ) 和x 研) 之间的关系可简写为 ；( ”) = 砥功) 及面0 = 面力嘶力 其中d ( ) 是长度为n 的矩形序列 j ( 刀) = 0 1 , ，0 纳 i i e ) 次复数乘法和( n 2 - - 1 ) + 2 n 2 = n 2 2 圈2 - 1 蝶形运算符号 复数加法运算。由此可见，仅仅经过一次分解，就使运算量减少了近一半。既 然这样分解对减少d f t 的运算量是有效的，且n = 2 ”，n 2 仍然是偶数，故可 以对n 2 点再作进一步分解。 与第一次分解相同，将x 1 ( r ) 按奇偶分解成两个n 4 长的子序列x 3 ( z ) s nx 。( ，) ，即 耄翁2 1 科，一。凡筹一= 五( + 1 ) f ”4 那么，五( k ) 又可表示为 五( 功= 而( 2 ，煳2 k ：十西( 2 ，+ 1 嘴m = 为( ，蹋+ 嗡：i ( ，聪 式中 = 五+ 瞄2 五，t ：0 1 。n 2 1 图2 - 2n 点d f t 的一次时域抽取分解图( n = 8 ) _ v ，4 - l 五( 后) = 鼍( ，聪= d f t x 3 ( i ) i = 0 五( 尼) = 强u 嘲。= d p t x 4 ( i ) 同理，由玛( 七) 和x 4 ( k ) 的周期性和陟万2 的对称性( ，w ，k + 2 n h = 一呜2 ) 最后得 到： 烈2篙期k=0,1,n4-1(k+n4) z s = 墨( 后) 一嘴：五j 用同样的方法可计算出 五( 动= 卫+ 孵。疋( 后) 五( j j + 4 ) = 五 ) 一唠2 五( 的f k = o , 1 , , n 4 - 1 2 6 其中 n 4 - 1 五( 后) = 砖( ，) 嘲。= d f t x s ( 1 ) ，= 0 n 4 - 1 z 。( 尼) = x 。( ，) 嘣。= d f t x 。( 例 ，= o 毛( ，) = 恐( 2 ，) 1 毪= 葺( 2 ，+ 1 ) l = o , 1 , , n 4 - 1 这样，经过第二次分解，又将n 2 点d f t 分解为两个n 4 点d f t 和2 , 5 式或 9 2 6 式所示的n 4 个蝶形运算，如图2 - 3 示。依次类推，经过m - 1 次分解，最 后将n 点d f t 分解成n 2 个2 点d f t ，并最终形成了f f t 运算。一个完整的 8 点d i t - f f t 运算流图如图2 - 5 所示。图中用到的关系式眩，。= 咿。图中输入 序列不是顺序排列，但从下面可以看出，其排列是有规律的。 图2 - 3n 点d f t 的第二次时域抽取分解图( n = 8 ) 2 2 2 基4 快速傅立叶算法 ) q o ) ) 辽1 ) ) 辽2 ) 3 ) 4 ) ) ( ( 5 ) x ( 6 ) ) 7 ) 对于n = 4 7 ，基4 - d i t 具有l o g 。n = ，次迭代运算，每次迭代包含n 4 个蝶 形单元。公式2 7 为基4 蝶形单元运算的一般表达式，用信号流表示如图2 4 所示。 a = ( a + c w 2 ) + ( b 矿+ d w ”) b 、_ ( a c w 2 ) 一j ( b w 一d w 3 ) c = ( a + c w 2 ) 一( s w + d w ) d 、- ( a c w 2 ) + ( b 矿一d w 3 ) 2 7 2 8 图2 4n 点d i t - f f t 运算流图( n = 8 ) x ( o ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) ) 7 ) 图2 - 5 基一4d i t 蝶形单元信号流图 n ， 2 7 式中，a 、b 、c 、d 和a 、b 、c 、d 、都是复数，w _ = e 习- o ”，进行一 次蝶乘共需3 次复乘和8 次复加运算。图2 6 是n = 6 4 点的基4 - d i t 信号流图。 从中可以看出，基4 - d i t 过程是正序输入倒序输出。6 4 点数据只需进行3 次迭 代运算，每次迭代运算含有n 4 = 1 6 个蝶形单元，因此共需1 4 4 次复数乘法。 与基2 f f t 相比较，同样的n = 6 4 ，基2 算法应做6 次迭代，每次迭代含n 2 = 3 2 个蝶形运算，每个蝶形运算做一次复数乘法运算，因而需1 9 2 次复数乘法。 同样，用基4 算法实现2 5 6 点f f t 运算需要进行4 次迭代，每次迭代有6 4 个 蝶形单元，共需进行7 6 8 次复数乘法运算：用基2 算法应做8 次迭代，每次迭 代含有1 2 8 个蝶形单元，共需进行1 0 2 4 次复数乘法运算。可见基4 d i t 比基 一2 f f t 节省约四分之一的乘法运算量。下面从六个方面对基4 d i t 算法流程的 特点予以说明： 1 同址运算 从2 7 式可以看出，每个蝶形单元涉及四个输入数据( a ，b ，c ，d ) 和四 个输出数据( a ，b ，c ，d ) 。一旦这四个输出数据计算出来，四个旧的数据就无 用了，新数据可以占据旧数据的存储单元，因此，基4 - d i t 是一种同址运算。 2 蝶形组 在信号流程图中，连线相互交迭的若干个蝶形称为一个蝶形组。所说的连 ，。￥m褰 线相互关系。如图2 - 6 ，第一次迭代1 6 个蝶形的连线相互间均有交迭部分，但 是每个蝶形的计算只和蝶形连线端点的数据有关。 在各次迭代中，所包含的蝶形组数目不同。在图2 - 6 中，第一次迭代，只 有一个蝶形组，第二次迭代有四组，最后一次迭代，所有蝶形均不互相交迭， 即每个蝶形单元自成个蝶形组。一般地，第m 次迭代有4 ”。个蝶形组，但各 次迭代的数目是相同的，既有n 4 个蝶形单元。那么，随着蝶形组数的增加， 每个蝶形组内地蝶形单元地数目就相应减少。在图2 - 5 ，第一次迭代一个蝶形 组包含了1 6 个蝶形单元，第二次迭代有四个蝶形组，每组包含4 个蝶形单元。 般地，在第m 次迭代中，每个蝶形组内包含掣+ g = 矿一个蝶形单元设计 的四个结点，其间距= n 矿( m 为迭代次数) 。 3节点间距 若结点a 的地址为a 则，结点b 的地址为b = a + 结点c 的地址为 c = b + = a + 2 a 结点d 的地址为d = c + = 口+ 3 a 4 跳跃 每次迭代开始，结点a 的地址a 总是从0 开始。以后计算完一个蝶形单元 a 顺序加1 ，直至一个蝶形组计算完毕，a 产生跳跃。跳跃后的第一个地址应是 跳跃前最后一个蝶形组结点d 的地址d 加1 。 5 整序 基4 f f t 是同址运算，因而当输入数据是自然顺序，其输出结果就是倒序 状态。 要使输出结果按频率自然顺序排列，必须经过一次整序操作。具体来说， 是将输出结果之序号( 或存储器地址) 按四迸制数作倒序排列。例如，第1 6 号数据( 四进制表示1 0 0 ) 应和第1 号数据( 四进制表示为0 0 1 ) 交换位置，第 2 7 号数据( 四进制表示为1 2 3 ) 应和第5 7 号数据( 四进制表示为3 2 i ) 交换位 鼍，等等。 69 一个基4 蝶形单元中，包含，、2 p 、w 3 p 三个旋转因子，因而只需确定 个p 值，三个旋转因子均可确定下来。每次迭代开始时，p 总为0 。在一个蝶 形组内，p 值不变。每当一个蝶形组计算完毕而转入下一个蝶形组时，p 值改变 一次。其变化的顺序恰好是o 一1 ) 位四进制数顺序加1 的倒序输出。对于n = 6 4 ， ( y 一1 ) = 2 ，p 的变化顺序如表2 1 所示 1 2 图2 - 6 基4 - d i t 蝶形单元信号流图 1 3 十进制 四进制 倒序输出p 十进制表示 0 0 00 0 0 l0 1】o4 20 22 08 30 33 01 2 41 00 11 5 1 11 1 5 61 22 19 7l33 l13 82 00 22 92 11 26 1 02 22 21 0 1 l2 33 21 4 1 23 00 33 1 33 11 37 1 43 22 31 l 1 53 33 31 5 2 2 3 算法选择 虽然，基4 算法的运算量较基一2 算法的运算量有所减小，但是它还是有自 身的不足：首先，基4 的f f t 运算只能处理4 ”点数，而基2 的算法可以处理任 意2 ”点数，对于像5 1 2 点f f t 的操作，如果采用基4 的算法要先将其扩展为 1 0 2 4 点再进行处理，这使得基4 算法的运算量有很大的增加。其次，基4 的蝶 形运算单元的结构较基2 的蝶形单元更为复杂。这主要反映在两个方面：第一， 基4 算法蝶形运算单元内包含的数学运算单元，尤其是乘法器比基一2 的多。即 使是经过优化的基一4 蝶形运算单元仍然包含三个乘法器，后面我们将可以看到， 经过优化的基一2 蝶形单元只需要两个乘法器。由于乘法器的硬件开销是很大的， 所以基一2 算法较基4 算法所用的硬件资源要少3 0 。第二，基4 蝶形单元内 的拓扑结构、连线方式较基- 2 蝶形单元复杂得多。在现有的半导体工艺条件下， 连线延迟已经远大于逻辑门所引起的延迟，尤其是在f p g a 中，这一特点表现 得更加明显。基一4 蝶形单元得复杂连线方式不但增加了连线的长度，而且降低 了布线器的效率，这必将降低了整个处理单元的工作速度。 综合这些因素，在设计中我们采用了基2 的算法。上面的图2 2 反应了 f f t - d i t 算法首先输入的数据被存储在相应的地址中如表中所示。每一级f f t 计算的结果也如表中所示，最终的结果是逆序输出的。 1 4 第一级操第二级操 第三级操 地址输入 位反操作 作 作作 0 0 0 0 13 2 50o 0 0 0 1l o 52 552 0 6 0 6 5 0 0 1 0 1 5o 53 53 5 3 5 o o l l 233 53 5 0 0 6 0 6 5 0 1 0 0一21 1 2 0 6 0 6 5 5 0 1 0 11 52 52 50 0 6 0 6 5 0 0 6 0 6 5 0 1 1 0- 1 2 5l一0 0 6 0 6 53 5 0 1 1 1 l12 52 ，0 6 0 6 52 0 6 0 6 5 1 0 0 00 o0oo 1 0 0 1oo0o4 9 7 4 9 1 0 1 000o3 53 5 1 0 1 100o3 5 0 0 2 5 1 5 1 1 0 00 oo4 9 7 4 9o 1 1 0 l 0o00 0 2 5 150 0 2 5 1 5 1 1 1 0o000 0 2 5 1 5 3 5 1 1 1 1o014 9 7 4 9 4 9 7 4 9 2 3f f t 处理器的硬件结构选择 f f t 专用硬件结构的形式有四种：顺序处理、级联处理、并行迭代和阵列 处理。下面就每种结构进行说明： 2 3 1 顺序处理 图2 7 显示的为n = 8 按时间抽取的基一2f f t 流程图，顺序处理机只使用 一个f f t 运算单元。输入量、中间结果及输出量都使用同一个存储装置。这种 顺序处理机所使用的硬件设备量最少。它的运算顺序是先算第一列4 个蝶乘， 然后依次再算第二列的、第三列的各4 个蝶乘，直到算完1 2 个蝶乘，这样就完 成了f f t 的全部运算。输出量f ( k ) 是倒序的，也可以重新定序按自然数序列输 出f ( k 1 。这种处理方法的特点是：一个运算单元，顺序执行2 l o g ，n 次。 2 3 2 级联处理 图2 7n = 8 按时间抽取基一2 f f t 的信号流 假若每一级n 2 只蝶乘都使用一个独立的运算单元加以运算，即在n = 8 时用第一个运算单元计算第一列4 只“蝴蝶”，第二个单元计算第二列。这样数 据输入的流通速度可以增加1 0 9 ：倍。级联处理的特点是：使用l o g ：个运算 单元并行运算；每个单元执行n 2 次蝶算，每个运算单元含有时延用的缓冲存 储，见图2 - 8 。 2 3 3 并行迭代 图2 - 8n = 8 流水式f f t 的第一级运算模块 假若对一列中的n 2 个蝶乘，用n 2 个运算单元并行运算，如用4 个运算 单元一起算第一列的4 个蝶乘，然后再一次算第二列、第三列的4 个蝶乘，这 就是说每列的运算是并行，而各列相继的迭代是连续的，这就是并行迭代运算。 它的特点是：有n 2 个运算单元，并行执行n 2 个蝶乘。 2 3 4 阵列结构 可以考虑在一个处理机中并行实现蝶乘，它把顺序和级联的方式组合起来， 如在n = 8 时，它可以并行运算1 2 个蝶乘。阵列式结构处理模式图见图2 - 9 。 o 1 2 3 4 5 6 ，卜， 冲邵酢踯 冰琊球m 输叁输出数据流水 2 4 本章小节 图2 - 9 阵列式f f t 处理模式图 本章讨论了两种f f t 算法。在详细讨论两种算法的优劣的基础上，我 们选择了基一2 算法进行设计。同时本章给出了f f t 算法的四种结构。可 以看出，上述四种结构中的蝶形运算单元的数目与f f t 执行时间的乘积是 常数。因此f f t 运算速度的提高是以付出相应的硬件量为代价的。选择f f t 运算结构的过程，即是在运算速度和硬件开销间进行折中的过程。在本文 的设计中，我们选择了阵列式结构。 第三章f f t 处理器的运算单元的设计 7 f t 处理器的运算单元的设计是指加法器和乘法器的设计，下面就分别介 绍这一部分的设计。 3 1 数字表示 在大多数数字计算机和专用数字信号处理器实现的数字滤波算法中，数字 ( 和信号变量) 用二进制表示。在二进制形式中，数字使用符号0 和1 来表示， 称为比特，其中二进制点将数字的整数部分和小数部分分开。例如，十进制 1 1 6 2 5 的二进制表示为 1 0 l la1 0 1 。这里使用表示二进制点。二进制点 左边的四位1 0 1 l 形成整数部分，而位于二进制点右边的三位1 0 l 代表数字的小 数部分。通常，二迸制数玎的十进制等效表示包含b 个整数位和b 个小数位， a b 一1 a 口一2 a l a o a a 一1 a 一2 a 一6 由 b l o ：2 7 b 给出。这里，每一个位日，的值取1 或者0 。最左端的位a 。称为最高位( m s b ) ， 而最右边的位o 。称为最低位( d s b ) 。 为了避免包含数字0 和1 的十进制数和包含比特0 和1 的二进制数之间的 混淆，我们将在十进制最低位的右边加上一个下标1 0 来表示十进制，而在二进 制数最低位的右边加上一个下标2 来表示二进制。因此，例如，11 0 1 。表示一 个十进制数，而11 0 1 ：就表示一个二进制数，其十进制等效为1 3 。如果表示 没有二义性，也可以不用下标。 表示一个数的一组位称为字，而一个字包含的位的数目称之为字长或字的 大小。典型字长是2 的整数幂，如8 、1 6 或3 2 。字的大小通常用字节表示，一 个字节代表8 个位。例如，一个4 字节的字相当于3 2 位。 实现两个二进制数的加法和乘法运算的数字电路，是根据是否固定二进制 小数点的位置来计算二进制数而专门设计的。数字有两种基本的二进制表示， 即定点和浮点，详细见下面的讨论。 3 1 1 定点表示 在这类表示中，二进制的小数点被假定固定在特定的位置，而运算电路在 执行算术运算时则首先寻找这个位置。只要对于两个数它们都在同一个位置， 数字加法器的加法运算独立于被加的两个数的二进制点的位置。但是在计算两 个二进制数的乘积时，小数点的位置就很难确定，除非它们是两个整数或者两 个小数。因为两个整数相乘的结果还是个整数；同样，两个小数的乘积也是 一个小数。因此，在数字信号处理中，定点数通常表示为小数 在定点表示法中，我们用b 位表示非负数叩的范围，具体为 0 2 7 - 1 类似的，也可以在定点表示法中用1 3 位表示非负整数町的范围，具体为 0 7 7 _ 1 一r 在任何一种情况中，叩的范围是固定的。如果。和吼。分别代表b 位定点中所 表示的数的最大值和最小值，则可用1 3 位表示的数的动态范围为r = 彳。- r , 。， 而该表示的分辨率定义为 万= 击 这里，占也就是所知的量化级。 3 2 浮点表示 在规范的浮点表示中，正数玎用两个参数来表示，即尾数m 和指数或阶码 e ，形如 刀= 坯芋 这里，尾数m 为限制在范围 三m 1 2 内的二进制小数。而指数e 为个正的或负的二进制整数。 浮点表示法对表示数的范围提供一个可变的分辨率。随着被表示数的幅度 增长，分辨率指数地增长。通过把寄存器的磁位分配给指数而剩下的位分 配给尾数，浮点数被存储在寄存器中。如果在浮点数和定点数的表示中用到的 全部位数相同，即b = b + b e ，那么前者比后者提供更大的动态范围 最广泛遵循的3 2 位和6 4 位表示的浮点形式是由a n s i i e e e 标准7 5 4 1 9 8 5 给出的( i e e e 8 5 ) 。在这种形式中，一个3 2 位数被分成几部分。指数部分具有 8 位长度，尾数部分具有2 3 位长度，还有一位安排用作符号位，如图3 - 1 所示。 指数部分采用有偏形式编码为e 一1 2 7 。这样，在这种结构下，浮点数，7 表示为 7 7 = 卜1 ) 5 封 3 1 其尾数的范围在 0 m 1 内。通过解释3 1 式，可给出下面的规定： 1 如果e = 2 5 5 且m 0 ，则叩不是一个数字( 简写为n a n ) 。 2 如果e = 2 5 5 且m = 0 ，则7 7 = ( - 1 ) 6 - o 。 3 如果0 e 。 3 3 1 增量二进制表示 在双极数模转换中用到的增量二进制表示，是具有一个附加符号位的长度 为b 位的小数，该小数可以看成是用一个长度( b + 1 ) 的二迸制数来表示最大 值为2 1 的十进制数。这些二进制数的一半表示负小数，而剩下的一半表示正 小数，如表3 1 所示的当b = 3 时的情况。注意，增量二迸制码可以简单的通过 将补码的符号位取反来得到。 表3 1 码制 十进制等效 原码反码补码补码二进制 7 8 o a l l l od 1 1 1oa 1 1 1la 1 1 1 6 8 oa 1 1ooa 1 1 006 1 1o16 1 10 5 8 0 io i0 d io io a io i 1d io i 4 8 o 6 1o oo 1o o o6 1o o1a ioo 3 8 0 6 0 1 1 o6 0 1 】06 0 1 1 1 0 1 l 2 8 0 0 1 0o a 0 1 00 a 0 10 1a0 10 1 8 0 6 0 0 1 o 60 0 1 0 a o ojj d 0 0 1 0 o6 0 0 0 0 d o o o 0a 0 0 0 1 oo o 0 1 。0 0 0 16 1 1 i n ，an a 1 8 1 a 0 0 1 ia 1 io1a 1 1 1 o 1 1 1 2 8 1 d0 1o 16 10 1 ia 1 l0 o 。0 3 8 la0 1 1 16 1oo 16 10 1 o d l0 1 4 8 1a 1oo1a o l i 1 io ooa 1oo 5 8 1a 10 1 1d0 1o 1a0 1 1 o a 0 1 1 6 8 1a 1 1o l d 0 0 1 1a0 1o 0 d 0 1 0 7 8 i6 1 1 116 0o o l 0 0 1o a 0 0 1 8 8n an a 1 oo oo 0 0 0 3 3 2 符号数表示 二迸制符号数( s d ) 是一个采用二进制的三值表示形式。这三个数字为0 ，1 ， 1 ( 最后一个符号表示1 ) 。在许多例子中，因为表示二进制数的s d 需要更少 的非零位，所以它可以用于实现一个较快的硬件乘法运算算法。我们可以通过 一个简单的算法将二进制数转换为与其等价的s d 形式。该简单算法如下。设 a _ 1 a _ 2 i q a a b 表示一个二进制数，其等效的s d 表示用c _ i c _ 2 如表示，s d 数的位c 一。 通过下面的关系确定： t = a t a f ， i = b , b l ，1 2 1 这罩，a = 0 。 3 3 3 十六进制表示 在采用可编程的d s p 芯片编程时，为了紧凑，一般是用二进制数的十六进 制表示。在这种形式中，二进制数从二进制点开始，每四位分为一组。每个四 位组的十进制由十进制数字0 至9 和字母表的六个字母a 至f 形成的十六个符 号来表示。