（微电子学与固体电子学专业论文）块浮点fft处理器系统的设计.pdf

摘要 摘要 随着集成电路技术的迅猛发展，电子设计自动化( e l e c t r o n i c sd e s i g n a u t o m a t i o n ) 成为重要的设计方法，已经广泛应用于数字信号处理系统等许多领域。而且，近 年来门电路数量和系统复杂性以指数倍增加，产品设计中的功能验证也日益重要。 现场可编程门阵列是一种半定制电路，也是一种新型可编程器。随着它的广泛应 用和快速发展，电子系统设计方法不断创新。 离散傅立叶变换( d i s c r e t ef o u r i e rt r a n s f o r m a t i o n ) 是数字信号分析与处理的重 要变换工具，而f f t ( ( f a s tf o u r i e rt r a n s f o r m a t i o n ) ) 是d f t 的一种快速算法，是数 字信号处理的核心技术，广泛应用于语音识别、图像处理、雷达系统、频谱分析 等领域。不同的应用场合，需要不同性能的f f t 处理器，特别是针对下一代以f f t 为核心技术的移动通信( 4 g ) 出现，使f f t 处理器的研究具有重要的现实意义。本 文研究基于f p g a 的大规模可编程逻辑器件的块浮点f f t 的实现。 首先阐述了f f t 的理论基础，根据f f t 算法的特点，对6 4 点f f t 硬件电路 结构及其工作原理进行了研究。详尽分析了f f t 的具体实现，用d i t 还是用d i f ， 而且比较了定点、浮点、块浮点的优劣，阐述了块浮点的相关运算，最终采用1 6 位块浮点进行数据运算。采用串行数据输入输出方式，在f p g a 内部运用并行计 算，整体架构采用同步时序设计。提出一种新的地址映射算法，简单可行。利用 旋转因子和乒乓r a m 结构的特点，使f f t 的运行周期大为缩短。 本文以q u a r t u s l i8 0 ，m o d e l s i m a l t e r a6 1g 和m o d e l s i ms e6 2 b 为软件平台， 用v e r i l o g 语言实现6 4 点块浮点结构，并以f p g a 芯片c y c l o n ei ie p 2 c 3 5 f 4 8 4 c 8 为硬件平台，整体设计顺利通过功能仿真和时序仿真。仿真结果表明其计算结果 达到了一定的精度，运算速度可以满足一般实时信号处理的要求。 关键词：块浮点；快速傅里叶变换；地址映射；f p g a a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e g r a t e dc i r c u i tt e c h n o l o g y , t h et e c h n o l o g yo f e d ah a sb e e nb e c o m i n ga ni m p o r t a n td e s i g nm e t h o d a n dt h i st e c h n o l o g yh a sa l r e a d y u s e di nm a n yf i e l d s ，e s p e c i a l l yi nd i g i t a ls i g n a lp r o c e s sf i e l d m o r e o v e r , t h eg a t e sc o u n t s a n ds y s t e mc o m p l e x i t i e sh a v ea l le x p o n e n t i a li n c r e a s e ，a n dt h ef u n c t i o n a lv e r i f i c a t i o no f p r o d u c tp l a y s a s i g n i f i c a n t r o l e f i e l dp r o g r a m m a b l eg a t ea r r a y ( f p g a ) i sa s e m i c u s t o mi n t e g r a t e dc i r c u i ta n dan e wt y p eo fp r o g r a m m a b l ed e v i c e w i t ht h ew i d e a p p l i c a t i o na n di m p r o v e m e n to ff p g a ，t h em e t h o do fe l e c t r o n i cs y s t e md e s i g ni s i n n o v a t e da l lt h et i m e 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 ) i st h ei m p o r t a n tt r a n s f o r m a t i o nt o o lo fd i g i t a l s i g n a la n a l y s i sa n dp r o c e s s i n gs y s t e m s a n df a s tf o u r i e rt r a n s f o r mo ：f t ) ，t h ef a s t a r i t h m e t i co fd f t , i st h ev i t a lt e c h n i q u eo fd s ef f th a sa l r e a d yw i d e l ya p p l i e di n s p e e c hr e c o g n i t i o n ，i m a g ep r o c e s s i n g ，r a d a rs y s t e m ，s p e c t r u ma n a l y s i s ，a n d s oo n d i f f e r e n t s y s t e m sn e e dd i f f e r e n tp e r f o r m a n c ef f t a n dw i t ht h ea d v e n to fn e x t g e n e r a t i o n4 g b a s e do nf f t , s t u d y i n gt h ei m p l e m e n t a t i o no ff f tp r o c e s s o ri sn e c e s s a r y s ot h i sp a p e rp r o p o s e sa nf f tp r o c e s s o rd e s i g nb a s eo nf p g a t h i sp a p e ri n t r o d u c e st h eb a s i ct h e o r yo ff f t a n dt h eh a r d w a r ea r c h i t e c t u r ea n d p r i n c i p l eo f 6 4p o i n tf f ta r er e s e a r c h e da c c o r d i n gt ot h ea r i t h m e t i cp r o p e r t yo f f f t i n p a r t i c u l a r , i td i s c u s s e st h a tu s i n gw h i c hm e t h o d t oc a r r yo u tf f t ，d i to rd i f , r a d i x2o r r a d i x4 m o r e o v e r , t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ff l o a t i n gp o i n t ，f i x e dp o i n ta n d b l o c kf l o a t i n gp o i n ta r ec o m p a r e d ，s oi tf m a l l yu s e s16b i tb l o c kf l o a t i n gp o i n tt od e s i g n t h ef f ts y s t e m t h ew h o l ed e s i g na d o p t ss y n c h r o n o u ss e q u e n t i a la r c h i t e c t u r e ，s e r i a l i n p u ta n do u t p u ta n dp a r a l l e lc o m p u t a t i o ni nf p g a c o n s i d e r i n gt h ep r o p e r t yo f t w i d d l e f a c t o r sa n dp i n g - p o n gr a m ，an e ws i m p l ea d d r e s sm a p p i n gi sp r o p o s e da n dt h ec l o c k c y c l e si sr e d u c e d t h i sp a p e rr e a l i z e sab l o c kf l o a t i n gp o i n tf f ts y s t e mo f6 4p o i n t sb yu s i n g h a r d w a r e d e s c r i p t i o nl a n g u a g e a tt h es o f t w a r e p l a t f o r m o fq u a r t u s l i 8 0 ， m o d e l s i m a l t e r a6 1ga n dm o d e l s i m6 2 ba n da tt h eh a r d w a r ep l a t f o r mo fa l t e r a c y e l o n e l ie p 2 c 3 5 f 4 8 4 c 8 a n dt h ef u n c t i o ns i m u l a t i o na n dt i m es i m u l a t i o no ft h e i i a b s t r a c t s y s t e ma r ep a s s e d t h ee x p e r i m e n ts i m u l a t i o ni n d i c a t e st h a tt h ea c c u r a c yo fc a l c u l a t i o n r e s u l ti sr a t h e rg o o d , a n dt h es p e e do ft h es y s t e mc a l lm e e tt h er e q u i r m e n to fc o m m o n r e a l t i m ed i g i t a ls i g n a lp r o c e s s i n g k e yw o r d s ：b l o c kf l o a t i n gp o i n t ；f f t - a d d r e s sm a p p i n g ；f p g a i i i 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位t p 请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的。对所研究的课题有新的见解。据我所知。除 文中特别加以说明、标注和致谢酌地方外论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作酌同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位申请人( 学位论文作者) 签名：三曩型 2 0 9 年占月 日 关于学位论文著作权使用授权书 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文舌勺要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 麒供公众检素、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学住论文( 氟质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名： 叁錾扭 2 0 0 年l f r 月多日 学位论文指导教师签名： 2 0 1 1 研究背景 第一章绪论 随着集成电路技术与数字设计技术的发展，数字信号处理( d i g i t a ls i g n a l p r o c e s s i n g ) 技术已深入到各个学科领域，其应用又是多种多样，以达到提取有用信 息便于应用的目的【1 】。但数字信号处理基本上从以下两个方面来解决信号的处理问 题：一个是时域方法，即数字滤波；另一个是频域方法，即频谱分析。处理的任 务大致分为三类：卷积，用于各种滤波器，对给定频率范围的原始信号进行加工( 通 过或滤出) 来提高信噪比；相关，用于信号比较，分析随机信号的功率谱密度；变 换，用于分析信号的频率组成，对信号进行识别。相对于模拟信号，数字信号具 有精度高、灵活性高、可靠性强、容易大规模集成、时分复用、可获得高性能指 标和二维与多维处理等优点。随着数字硬件速度更快、使用更简单、价格更便宜、 可用性更强，数字信号处理已经发展成为一项成熟的技术，并且在许多应用领域 中逐步代替了传统的模拟信号处理系统。 由数字信号处理的基本理论可知，卷积可以转化为d f t 来实现，实际上其它 许多算法，如相关、谱分析等也都可以转化为d f t 来实现；此外，各种系统的分 析、设计和实现中都会用到d f t 的计算问题。所以，d f t 在各种数字信号处理中 起着核心作用，而d f t 的快速算法快速傅立叶变换f f t 就成为了数字信号处理的 最核心技术之一，对f f t 算法及其实现方式的研究是很有意义的【2 】。在不同的领 域中，随着功能的不同，对f f t 实现的要求也存在着差别在速度上，低端应用和 高端应用存在着每秒万次至每秒亿次的不同；在精度上，定点、块浮点和浮点运 算可满足不同的需求，其中又以浮点运算实现的精度最高，可胜任各种应用场合 对精度的需求。因此，使用块浮点f f t 运算，配合以高速、低成本的电路实现， 可全面提升系统性能。 随着通信智能化、大数据量、高速实时的多媒体应用的需求不断增岁3 1 ，处理 1 河瘸大学微电子学与鬻俸电子学2 0 0 7 缀颁毕堑论文 信号的类型已经不仅仅局限于对常规数据的处理，还需要处理大量的语音信号和 视频信号等【4 】。这类信号的特点是数字化、宽频带、大数据量、高速度，因此数字 信号处理对系统的要求越来越高。以前的基于d s p 处理器芯片的数字信号处理系 统，是依照冯诺依曼结构设计的，其取指与存指的瓶颈导致指令只能串行执行，尽 管有些经过优化后的结构提高了运算速度，还是来能真正体现出信号处理算法的 内在特征，因此已经不能满足墨益提高的整机系统的要求。 采用a s i c 技术设计专用芯片可以克服d s p 芯片的缺陷。a s i c 技术就是针对 算法的特点采用了流水并行处理的结构，因此它能够最大程度地提高算法的运算 速度，郎克服了传统的微处理器的串行取指译码执行的工作模式，采用脉动阵列 处理器作为基本处理单元，并以高度并行流水的作业方式，从而大大提高了算法 的执行速度鞫效率。但它不具备d s p 处理器的可编程性及由此带来的灵活性，褥 且其开发费用太昂贵、周期较长，尤其是算法需要得到改进时，必须付出曩大的 代价投入芯片，使得a s i c 解决方案网益失去其实用性【5 】。 随着1 9 8 4 年x i l i n x 公司推出了世界上第一个f p g a 芯片，现场可编程门阵列 f p g a ( f i e l dp r o g r a m m a b l e g a t ea r r a y ) 技术就开始迅速发展。f p g a 非常适合于各种 算术运算，包括含有大量乘加运算的数字信号处理算法。用f p g a 设计d s p 系统 时，可以利用并行结构和算术运算的优点，充分零娃媚硬件资源，并在性能上超过 d s p 器件。f p g a 可以e l l 设计者根据算法的内在结构设计合适的处理阵列，避免前 者串行执行指令的低效性。f p g a 可避免初期巨大的开发投资，同时拥有微处理器 的通用性和灵活性翻。在算法修改时，短时闻内就将薪的算法键诸实际。f p g a 正 在越来越多地替代a s i c 和d s p 用作前端数字信号处理的运算r 7 - 9 。 现今，用f p g a 来进行系统集成设计己成为一种极为普遍的现象( 1o 】。f p g a 厂商a l t e r a 公司和x i l i n x 公司都研制? f f ti p 核，但是价格昂贵，难以在我匿基 层普及应用。因此，自主研发基于f p g a 芯片的f f t ，把f f t 实时性的要求和f p g a 芯片设计的灵活性结合起来，实现并行算法与硬件结构的优化配置，提高f f t 处 理精度，满足现代信号处理的高速度、高可靠性要求，成为当今我国数字信号处 2 第一章绪论 理的个研究点。因此，研究基于f p g a 实现块浮点的f f t 处理器具有十分重要 的现实意义。 1 2f f t 算法研究现状 离散傅立叶变换可以使数字信号处理中的频域采样按照数字运算的方法进 行。它可以作为一种数学工具来描述离散信号的时域与频域表示的关系，大大增 加了数字信号处理的灵活性。所以离散傅立叶变换不仅在理论上有重要意义，而 且在各种数字信号处理中起着核心的作用。但由于d f t 的计算量很大，因此在很 长一段时间内其应用受到很大的限制。 直到1 9 6 5 年c o o l y 和t u k e y 首次提出快速计算d f t 的方法【1 l 】，使离散傅立叶 变换的应用取得重大突破。此后，快速傅立叶变换一直是数字信号处理理论研究 的一个重要课题。 快速计算d f t 的方法大概可以分为两类【1 3 】。 一类是递归型算法，将一维d f t 转化为容易计算的二维或多维d f t ，以 c o o l e y _ t l l k e y 算法为代表，如基2 、基4 、基8 、分裂基及任意因子数的组合f f t 算法。利用旋转因子的周期性和对称性，使长序列的d f t 分解为简单的几个点之 间的交叉运算，从而大大减少运算工作量。此时f f t 的分解法又归为两种，一种 是将时间序列x ( n ) ( n 为时间标号) 进行逐次分解；另一种是将频率序列x ( k ) ( k 为频 率标号) 进行逐次分解【1 4 】。 另一类是将d f t 转变为卷积，利用卷积的快速算法计算d f t ，其代表是 w i n o g r a d 傅立叶算法( w i n o g r a df o u r i e rt r a n s f o r ma l g o r i t h m ) 和素因子算法( p r i m e f a c t o r a l g o r i t h m ) ，这类算法也就是f f t 点数n 不等于2 的整数次幂的算法，这类 算法利用下标映射和数论以及近代数学的知识，去掉级间的旋转因子，从而减少 运算量。这些算法是根据g o o d - - t h o m a s 提出的索引变换，将一个长度n = n l n 2 的d f t 变换成二维d f t ，没有c o o l e y - - t u k e y 中的旋转因子【1 5 】。w m o g r a d 类算法 在运算量上有很大优势，使用的乘法器比c o o l e y 。t u k e y 算法少，但控制复杂，控 3 溺露大学徽奄子学与鬻体电子学2 0 0 7 缀疆毕监论文 制单元实现起来相对麻烦很多。在硬件实现中，不仅要考虑算法的运算量，还要 考虑算法的复杂度。因此，w i n o g r a d 类算法的现实价值远远低于c o o l e y t u r k e y 类 算法。 因此在硬件电路中，算法规则、控制简单的c o o l e y t u r k e y 算法更适合大规模 的集成。其中分裂基算法具有一定的优势，综合了基4 和基2 算法的运算特点， 但其蝶式运算结构在控制上要复杂许多，不易于实现。基4 和基2 算法是露前普 遍采取的两种算法【1 6 1 。 羔。3f f t 处理器的研究现状 现在，f f t 的理论研究已经相当成熟，随着数字信号处理领域的飞速发展， 很多场合需要高精度的f f t 处理器，而且集成电路技术飞跃发展，自主研发商性 能f f t 处理器成为盛然。因此，很多入对f f t 处理器的实现方法徽了大量的研究， 选用不同的硬件，综合考虑了硬件特性和满足系统要求。 f f t 处理器的实现方案，主要有三种途径。 ( 1 ) 数字信号处理芯片d s p 实现 一般数字信号处理算法，采用通用可编程硬件处理器技术来实现。这种实现 方法具有软件设计多用性的优点，能够适用于需要f f t 运算进行信号处理的应用 场合。目前国际采用单片通用d s p 实现1 0 2 4 点1 6 位定点运算的f f t 处理的速度 达到几十或数百斗s 量级，其中采用t i 公司的t m s 3 2 0 c 6 2 x 系列d s p 达到6 6 1 t s 数量级处理速度f 翔。t m s 3 2 0 c 6 4 x 系列d s p 达到l o 雌量级，t m s 3 2 0 c 6 7 x 系列 处理1 0 2 4 点基2 算法的f f t 需1 2 4 3 0 i t s 。但由于d s p 本身性能及程序指令顺序 执行的限制，难以实现离速、大规模的f f t 运算。在进行大点数f f t 计算时，并 行算法与d s p 处理器的寻址能力不相适应，不能鸯效利用数据传输的带宽和运算 能力，造成硬件资源的浪费f 嘲。 ( 2 ) 利用专用集成电路( a s i c ) 实现 对于f f t 的特有算法，用专用集成电路实现f f t 在一些特殊功能的表现相 4 第一章绪论 当好。这种方法运算速度快，而且不易被破解，可以保护设计者的成果不被盗用， 非常适合实时和对可靠性要求较高的信号处理系统。但是a s i c 开发和生产需要比 较长的时间，而且也不可重构，可编程能力有限，设计费用极其昂贵，并且生产 之后不易修改，不适合处理算法和参数经常改变的场合【1 9 】。 ( 3 ) 现场可编程门阵y 0 ( f p g a ) 实现 f p g a 实现数字信号处理最显著的特点就是高速、性能好。f p g a 有内置的高 速乘法器和加法器，尤其适合于乘法和累加等重复性的d s p 任务。f p g a 的存储 量大。除了一些专用引脚外，f p g a 上几乎所有的引脚均可供用户使用，这使得 f p g a 信号处理方案具有非常高性能的i o 带宽。大量的i o 引脚和多块存储器可 让系统在设计中获得优越的并行处理性能。最新的f p g a 产品中已经集成了r a m 、 f i f o 以及嵌入式c p u 等模块。f p g a 不仅具有a s i c 的许多特点，例如在规模、 重量和功耗等方面都有所降低，而且吞吐量高，能够更好地防止未授权复制。知 识产权( i n t e l l e c t u a lp r o p e r t y ，i p ) p 勺核的出现使硬件设计可以在模块或部件级基础上 进行复用，提高了设计生产效率和避免了错误的发生【2 0 1 。元器件和开发成本进一 步降低，开发时间也大大缩短，并且具有可重复编程的特性，非常适合实现f f t 算法。 随着f p g a 技术的普及，以及f f t 算法在各个领域的广泛应用，使用f p g a 设计f f t 正在世界范围内兴起。国内外都有关的研究与应用并取得良好的效益。 采用x i l i n x 公司的f f ti p 内核处理1 6 位1 0 2 4 点数据，在v i r t e xi i 系列两结构、 2 4 6 m h z 系统时钟下，速度达到2 5 4 9 9 s 量级【2 1 1 。a l t e r a 公司0 6 年4 月推出的 f f ti p 核，全面支持a l t e r a 公司的最新器件，使用此f f t 核计算1 6 位1 0 2 4 点数 据，在3 3 2 m h z 系统时钟下仅需要6 3 “s 瞄】。 虽然这些公司的i p 核可最大程度的发挥芯片的性能，但其价格昂贵( a l u m 公 司的f f ti p 核售价为7 9 9 5 美元) 【2 3 j ，而且用i p 核实现f f t ，外围需要进行外部 r a m 配置，外围引脚较多时不利于使用，也不利于针对特殊要求进行修改，所以 i p 核还难以在我国基层应用领域普及【2 4 】。而且由于产权问题，用户往往看不到i p 5 河南大学微电子学与固体电子学2 0 0 7 级硕士毕业论文 里面的设计，无法深入地理解、掌握算法，更无法移植到其它厂商的f p g a 平台 或a s i c 平台上。我国的f p g a 技术起步较晚，但进入2 l 世纪后，发展势头迅猛， 而且取得了许多成绩【2 5 - 3 2 1 。但由于技术基础薄弱，所设计的f f t 处理器无论在速 度、精度还是系统可扩展度上都与国外产品有一定差距。因此，自主研发基于f p g a 的f f t 算法，利用f p g a 芯片的丰富硬件资源和设计的灵活性，在深刻理解f f t 算法原理和结构的基础上，实现快速的f f t 算法模块，满足现代信号处理的高精 度、高可靠性要求，是一项非常有意义的工作。 1 4f p g a 发展现状 在当今世界上，f p g a 的两个供应商a l t e r a 和x i l i n x 在该领域绝对是龙头老 大，可以比作“可口可乐 和“百事可乐，没有第三家f p g a 厂商可以与它们相 抗衡。比如2 0 0 7 年1 1 月，以前做f p g a 的q u i c k l o g i c 公司确定淡出f p g a 市场， 并改行发展c s s p ( 客户特殊标准产品) 。 f p g a 全球使用情况如图1 1 所示3 3 1 ，通常来说，在欧洲用x i l i n x 的人多，在 日本和亚太地区用a l t e r a 的人多，在美国则是平分秋色。x i l i n x 是f p g a 的发明者， 老牌的f p g a 公司，是最大可编程逻辑器件供应商之一。产品种类较全。在研究 机构和高端应用中一般都选用x i l i n x ，但是x i l i n x 的东西一般价格比较高，并且 x i l i n x 的大学计划做得不是很好。a l t e r a 的有些产品在密度、性能和低功耗上遥遥 领先，其大学计划做得很好，而且给学校很多免费的东西，包括软件和开发板， 所以很多学校都在用，亚洲和欧洲的用a l t e r a 的更多些。a l t e r a 在中国推广得更好， 尤其是在高校，所以教材上介绍的大部分都是a l t e r a 。针对开发环境而言，q u a r t u s i i 比i s e 综合快很多，更容易上手，而且它与自己的产品匹配性能更好，q u a r t u si i 8 0 版本在业界更是深得好评。本设计中选用a l t e r a 的c y c l o n ei i 芯片。c y c l o n ei i 是是a l t e r a 公司c y c l o n e 系列的第二代产品。该产品将采用t s m c 公司低k 介质 的9 0 n m 工艺制造，从而将产品成本降低3 0 ，同时将逻辑密度提升3 倍。所以价 钱很便宜，性能又非常不错，还支持n i o si i 嵌入式处理器，n i o s1 1 只用了5 0 的 6 第一章绪论 逻辑单元就实现了2 倍于n i o s 的性能，实现了更高性能，还降低了成本。c y c l o n e i i 密度分布范围广，含有丰富的存储器和嵌入式数字信号处理乘法器，并提供多 种封装选择，广泛的i p 核支持。c y c l o n el i 器件还支持低成本应用中常见的各种 外部存储器接口和i o 协议。c y c l o n ei i 器件是汽车、通信、消费类、视频处理、 测试和测量以及其他终端市场解决方案的理想选择。 总之，全球p u ) 胛g a 产品6 0 以上是由a l t e r a 和x i l i n x 提供的。可以肯定 的是，a l t e r a 和x i l i n x 共同决定了p l d f p g a 技术的发展方向。 1 5f p g a 设计流程 x i i ln ) c 图1 1 全球f p g a 使用情况 f p g a 大多采用自顶向下的设计流程，f p g a 设计大体分为设计方案提出、 设计输入、功能仿真、设计综合、综合后仿真、布局布线、时序仿真、在线调试 等几个步骤，如果哪个步骤出错，到相应步骤进行修改，比如当功能仿真、综合 仿真、时序仿真出现问题，那么马上对设计进行优化修改，然后再次输入，再次 验证。这样循环往复，直到所以的验证结果和理论结果一致。设计流程如图12 所 示，下面分别介绍各个设计步骤3 4 训】。 7 河鬻大学微电子学与瓣俘电子学2 0 0 7 缀硕毕监论文 图1 2f p g a 设计流程图 l 。5 。王设计方案 在系统设计之前，首先要进行的是提出设计方案，进行方案可行性的理论论 证，然后进行器件选择等其它准备工作。需要根据设计任务要求，如系统的功能 霹复杂度，对工作速度和期间本身的资源、成本及连线的可布性等方面进行权衡， 选择合适的设计方案和合适的器件类型。一般采用自顶向下的设计方法。 l 。5 2 设计输入 设计输入包括使用硬件描述语言h d l 、状态凰与原理圈输入三种方式。h d l 设计方式是现今设计大规模数字集成电路的良好形式。h d l 语言描述在状态机、 控制逻辑、总线功能方逝较强，使其描述的电路能在特定综合器作用下以具体硬 件单元较好地实现。而原理鎏输入在顶层设计、数据通路逻辑、手工最优化电路 8 第一章绪论 等方面具有图形化强、单元节俭、功能明确等特点，另外，在a l t e r a 公司q u a r t u s 软件环境下，可以使用m o m o r ye d i t o r 对内部m e m o r y 进行直接编辑置入数据。 本文采用v e r i l o g 硬件描述语言编写。 1 5 3 功能仿真 仿真是指使用设计软件包对已实现的设计进行完整测试，模拟实际物理环境 下的工作情况，此时的功能仿真也叫前仿真，是指仅对逻辑功能进行测试。设计 输入完成后，要用专用的仿真工具对设计进行功能仿真，验证电路功能是否符合 设计要求。常用的仿真工具主要以m o d e lt e c h 公司的m o d e l s i m 为主流。通过该 仿真能及时发现设计中的错误可以加快设计进度，提高设计的可靠性。 1 5 4 设计综合 综合是针对给定的电路实现功能和实现此电路的约束条件，如速度、功耗、 成本及电路类型等，通过计算机进行优化处理，获得一个能满足上述要求的电路 设计方案。综合的结果则是一个硬件电路的实现方案，该方案必须同时满足预期 的功能和约束条件。对于综合来说，满足要求的方案可能有多个，综合器将产生 一个最优的或接近最优的结果。因此，综合的过程也就是设计目标的优化过程， 最后获得的结构与综合器的工作性能有关。 1 5 5 综合后仿真 综合后还需要仿真检查综合结果是否与原设计一致。在仿真时，把综合生 成的标准延时文件反标注到综合仿真模型中去，可估计门延时带来的影响。综合 后仿真虽然比功能仿真精确一些，但是只能估计门延时，不能估计线延时仿真 结果与布线后的实际情况还有一定的差距，并不十分准确。这种仿真的主要目的 在于检查综合器的综合结果是否与设计输入一致。 1 5 6 布局布线 综合输出的逻辑网表适配到具体f p g a c p l d 器件上，这个过程就叫做实 现因为只有器件开发商最了解器件的内部结果，所以实现步骤必须选用器件开 9 河南大学微电子学与固体电子学2 0 0 7 级硕士毕业论文 发商提供的工具在实现过程中最主要的过程是布局布线。所谓布局，是将逻辑 网表中的硬件原语或者底层单元合理地适配到f p g a 内部的固有硬件结构上，布 局的优劣对于设计的最终设计结果( 在速度和面积两个方面) 影响很大。所谓布线， 是指根据布局的拓扑结果，利用f p g a 内部的各种连线资源，合理正确连接各个 元件的过程。 1 5 7 时序仿真 布局布线之后生成的仿真时延文件包含的时延信息最全。不仅包含门延时， 还包含实际布线延时，所以布线后仿真最准确能较好地反映芯片的实际工作情 况。布局布线后仿真的主要目的是在于发现时序违规( t i m i n gv i o l a t i o n ) 。从某种程 度来讲，静态时序分析( s t a t i ct i m i n ga n a l y z e r ) 可以说是整个f p g a 设计中最重要 的步骤，它允许设计者详尽地分析所有关键路径并得出一个有次序的报告，而且 报告中含有其它调试信息，比如每个网络节点的扇出或容性负载等。静态时序分 析器可以用来检查设计的逻辑和时序，以便识别可靠的踪迹，检测建立和保持时 间的配合，可以提高工作主频或减少关键路径的延时。与综合过程相似，静态时 序分析也是一个重复的过程，它与布局布线步骤紧密相连，这个操作通常要进行 多次直到时序约束得到很好的满足。 1 5 8 在线调试 设计开发的最后步骤就是在线调试，也称作将生成的配置文件写入苍片中进 行测试。示波器和逻辑分析仪是的主要调试工具。逻辑分析仪的很专业，而且高 速，但价格昂贵，灵活性差。使用q u a r t u si i 内嵌的逻辑分析仪( s i g n a l t a pi i ) 可以 很好地解决上述矛盾。s i g n a l t a pi i 是一种f p g a 在线片内信号分析工具，它的主 要功能是通过j t a g 口，在线、实时地读出f p g a 的内部信号。其基本原理是利用 f p g a 中未使用的存储模块( b l o c kr a m ) ，根据用户设定的触发条件将信号实时地 保存到这些存储模块中，然后通过j t a g 口传送到计算机，在计算机屏幕上显示出 时序波形。 1 0 第章绪论 1 6 本论文的研究内容 研究块浮点的快速傅立叶变换的f p g a 实现既可以减少国外对f f t 实现上采 用固核或硬核的技术封锁的限制，又可灵活地为各种工程应用提供满足要求的f f t 处理器，也为更高效率的f f t 芯片的设计和实现打下基础，这涉及算法选取、定 点和浮点分析、处理器结构设计、系统仿真与验证等。论文主要内容按以下部分 展开。 第一章阐述了选题的背景、意义，相关技术的研究现状，以及f p g a 的发展 现状和设计流程。 第二章探讨了f f t 的基本原理，基本算法，分析了基2 和基4 算法的优劣， 着重分析了采用d i t 算法和d i f 算法的不同影响。 第三章介绍了数值在计算机中的表示方法。 第四章详细说明了块浮点设计方案，对比了定点、浮点实现f f t 的精度、速 度问题。针对i e e e7 5 4 标准的单精度浮点，提出具体的1 6 位浮点表示方法。 第五章介绍了基于f p g a 的块浮点f f t 的具体设计，采用串行输入输出，双 口r a m 乒乓设计，简单实用的地址映射方法，多级并行处理蝶形单元。设计出 1 6 位浮点的6 4 点f f t 处理系统，6 7 个周期完成，与一些研究者的设计相比，周 期缩短了许多【4 2 】。 第六章给出了f p g a 环境下f f t 系统的仿真结果。 第七章对本文进行了总结和展望。 第二章f f t 算法理论研究 2 1 离散傅里叶变换 1 8 2 2 年法国工程师傅立叶( f o u r i e r ) 指出，一个任意的周期函数x ( t ) 都可以分解 为无穷多个不同频率正弦信号的和，这即是傅立叶级数。求解傅立叶系数的过程就 是傅立叶变换。一个连续的信号可以看作是一个个小信号的叠加，从时域叠加与从 频域叠加都可以组成原来的信号，将信号这么分解后有助于处理【4 3 1 。 离散傅立叶变换开辟了频域离散化的道路，使数字信号处理也可以在频域上采 用数字运算方法进行，特别是它的多种快速算法，使信号的实时处理和设备的简化 得以实现，所以离散傅立叶变换不仅在理论上有重要意义，而且在各种数字信号处 理中起着核心的作用。在d f t 中时间和频率变量都取离散值。 在一维d f t 中，设x ( n ) 是长为n 的复数序列，其d f t 变换定义为 x ( 蛉b ( n ) 蝶七， k = 0 ，1 ，n 1 ( 2 1 ) 逆变换( i n v e r s ed i s c r e t ef o u r i e rt r a n s f o r m ) 为 x ( n ) = 面1 x ( k 疗，n = o ，l ，n - 1 ( 2 2 ) n = 0 其中，= e x p ( - ，等) ，称为旋转因子。x ( n ) 和嘭都是复数，x ( k ) 也是复数，因 此每计算一个x ( n ) 需要n 次复数乘法以及( n 1 ) 复数加法。而x ( n ) 一共有n 个点， 所以完成整个d f t 运算总共需要n 2 次复数乘法以及n ( n 1 ) 次复数加法。当n 较 大时，计算量太大，无法得到实际的应用。 2 2 快速傅里叶变换 由于起初的傅立叶变换运算量巨大，使得在实际应用中受到极大限制。直到 1 9 6 5 年发表的c o o l e y - t u k e y 快速傅立叶变换算法，使得傅立叶变换和卷积这类难 13 河南大学微电子学与固体电子学专业2 0 0 7 级硕士学位论文 度很大的计算工作的复杂度从n 2 量级降到n l 0 9 2 n 量级，开创了数字信号处理的一 个新里程。它的基本思想在于，利用旋转因子的一些特性，将原有的n 点序列分 解成两个或更多的较短序列，这些短序列的d f t 可重新组合成原序列的d f t ，而 总的运算次数却比直接的d f t 算法少得多，从而达到提高速度的目的。 旋转因子的一些性质。 ( 1 ) 嘭的共轭对称性：( 嘭) = 嘭 ( 2 ) 嘭的周期性：嘭= 嘴+ 弦= 蝶似+ ( 3 ) 嘭的可约性：嘭= 形舻 ( 4 ) 可以推导出，w o = 1 ，吲胆= 一1 ，孵+ 坨= 一嘴 快速傅里叶变换算法正是由于旋转因子的这些特性而发展起来的。 2 3 算法选取 2 3 1 基2 和基4 算法的选取 针对f f t 的具体算法，一般常用的是基2 、基4 算法。对于基2 - f f t 算法，其 基本蝶形如下图所示。 五( 七) x 2 ( 后) 以k ) x ( k + n 2 ) 图2 1 基2 - d i f 蝶形变换 它的蝶形计算公式是 嚣譬鸶三鬻删删 x ( 七+ 2 ) = z 1 ( 七) 一x 2 ( 七) 】嘴 、 从该公式可以看出，在基2 算法中，每个蝶形运算单元都包括1 次复数乘法、 2 次复数加法。n f n = 2 肘，m 为偶数) 点序列的基2 f f t 算法，总的运算量为学1 。g ： 次复数乘法，n l o g ：n 次复数加法。 第二章f f t 算法理论研究 基4 算法蝶形变换图形为 ) 聊 x ( n + n 4 ) x ( n + l r l 2 ) x ( n + 3 n 4 ) 对应的蝶形计算公式为 图2 2 基4 d i f 蝶形变换 x k n ) 勋 蝴 x o ( n ) = x ( n ) + x ( n + 4 ) + x ( n + n 2 ) + x ( n + 3 n 4 ) 工l ( 栉) = 【x ( 即) 一豇( 聆+ 4 ) 一工( 刀+ 2 ) + 办( 刀+ 3 4 ) 】矽嚣( 2 - 4 ) x 2 ( 胛) = 【x ( 力) 一x ( n + n 4 ) + x ( ，z + 2 ) 一x ( n + 3 n 4 ) 】陟焉” x 3 ( 甩) = 【x ( ”) + j x ( n + n 4 ) - x ( n + 2 ) 一x ( n + 3 n 1 4 ) w 君” 由上图可知每个基4 蝶形运算单元包括3 次复数乘法、8 次复数加法。采用基 一 4 算法计算n 点序列的f f t 共需要 ，n l o g ：n 次复数乘法、n l 0 9 2n 次复数加法。 o 比较基2 和基4 算法的运算量可知，两者复数加法次数相同，但基4 算法所需 复数乘法为基2 算法的3 4 ，因此基4 算法具有更快的数据处理速度。但基2 的每 个蝶形运算对2 点进行，而基4 的每个蝶形运算对4 个点进行，因此设计复杂度大 大增加，用更多资源，系统稳定性也会因此降低。 在大规模集成电路设计中，系统模块的易实现性以及稳定性是十分重要的。本 文f f t 系统采用基2 算法，而且进行数据并行处理，保证系统稳定性，提高了基2 算法的处理速度。 2 3 2d i t 和d i f 的选取 f f t 算法的基本原理是把长序列的d f t 逐次分解为较短序列的d f t 。按照抽 取方式的不同可分为d i t - f f t ( 按时域抽取) 和d i f f f t ( 按频域抽取) 算法。2 3 式介绍的是d i f f f t 蝶形的基本形式。下面对d i t - f f t 的计算方法做简要介绍。 1 5 河南大学微电子学与固体电子学专业2 0 0 7 级硕士学位论文 r l x ( k ) = x ( 刀肘 n = o = x (