（信息与通信工程专业论文）高速dsp算法的asic实现技术研究.pdf

摘要 为了满足d s p 系统对高速度和大规模计算能力的要求，寻求算法的专用硬件实现是必然 的途径。然而传统专用集成电路( a s i c ) 的设计效率偏低，设计成本较高，严重制约了d s p 算法的a s i c 实现研究以及应用。层次化设计思想的提出，硬件描述语言的引入，以及作为 a s i c 重要分支的现场可编程逻辑器件( f p g a ) 的f f 益发展使得这一问题得到了较好的解决。 f p g a 器件的作用不止于简单地集成若干中小规模集成电路和作为a s i c 器件廉价的代 用品，更重要的是它系统可编程的能力非常适用于进行相关硬件算法的设计、调试、分析、 验证等工作，为硬件算法的实现研究提供了合适的平台。在未来，通用的d s p 处理器将会主 宰复杂算法的应用领域( 例如：多重i f - t h e n e l s e 结构) ，而专用处理器( 以f p g a 为平台) 将会统治更多前端( 传感器) 的应用，例如m a c 、f i r 滤波器、f f t 。因此研究相关算法 的硬件实现技术，对促进专用处理器的发展乃至构建高速d s p 系统都具有重大意义。 本文着重研究有关d s p 算法的硬件实现结构，进行优化设计，并在f p g a 器件上进行实 现验证和性能分析。在研究d s p 基本运算实现结构的基础上，对卷积、f i r 和序列滤波三类 典型算法结构进行了研究分析以及优化设计。文中最后还对一个实际的d s p 系统算法( l m s 算法) 进行了分割设计和实现，充分的检验了有关算法的性能。 关键词：d s p 算法，a s i c ，f p g a ，卷积，f i r ，序列滤波，l m s 算法 第v 页 望堕型兰丝查查兰型塞尘些竺簦连兰 。 a b s t r a c t i ti sn e c e s s a r yt os e e kt h ei m p l e m e n t a t i o na p p r o a c ho fa l g o r i t h mw i t hs p e c i t i ch a r d w a r et o f u l l i l lt h e r e q u e s tf o rh i g hs p e e d a n dc o s m i c a l l yc a p a b i l i t yi nd s ps y s t e m ，w h i l e ，t h ed e s i g n e f f i c i e n c yf o rt h et r a d i t i o na s i ci s o nt h el o ws i d ea n dt h ed e s i g nc o s ti so nt h eh i g hs i d e ，a s s e v e r e l y r e s t r i c tt h e i m p l e m e n t a t i o ns t u d y a n d a p p l i c a t i o n f o rd s pa l g o r i t h mi na s i c t h e h i e r a r c h yd e s i g ni d e ab e i n gp u tf o r w a r d ，h d ll a n g u a g eb e i n gi n t r o d u c e da n df p g a ( t h ei m p o r t a n t e m b r a n c h m e n to f a s i c 、a d v a n c e m e n tm a k et h ep r o b l e ma g o o ds o l u t i o n 1 h ef u n c t i o no ff p g ai sn o to n l yt h a ti ts i m p l yi n t e g r a t e ss o m ei ci nm i n i a t u r ea n d b e i n gt h e c h e a ps u b s t i t u t eo fa s i c ，b u ta l s ot h a ti ti sv e r ys u i t a b l et od e s i g n ，d e b u g ，a n a l y z e ，a n dv e r i f ys o m e h a r d w a r ea l g o r i t h m sw i t hi t sf i e l dp r o g r a m m a b l ec a p a b i l i t ya n do f f e rt h ea p p r o p r i a t ei m p l e m e n t p l a t f o r m i nt h ef u t u r e ，t h cg e n e r a ld s pp r o c e s s o r sw i l ld o m i n a t et h ec o m p l e xa l g o r i t h m sf i e l d ( f o r e x a m p l e ，t h o s ew i t hm u l t i p l ei f - t h e n e l s es t r u c t u r e s ) ，w h i l e ，t h es p e c i f i cp r o c e s s o rb a s e do nt h e f 1 g aw i l lr e i g nt h e a l g o r i t h m si nm a n y s e n s o ra p p l i c a t i o n ，s u c ha sm a c ，f i r ，f f i ：a n ds oo n a s ar e s u l t s t u d y i n gi m p l e m e n t a t i o nt e c h n o l o g yw i t hh a r d w a r ef o rs o m e a l g o r i t h m si sv e r yi m p o r t a n t t oi m p r o v et h es p e c i f i cp r o c e s s o ra n ds e tu pt h e h i g hs p e e dd s ps y s t e m i h i sp a p e rl a y se m p h a s i so ns t u d y i n gt h eh a r d w a r ei m p l e m e n t a t i o ns t r u c t u r ef o rs o m ed s p a l g o r i t h m s ，o p t i m i z i n gt h ed e s i g n ，a n da n a l y z i n gt h ep e r t b m m n c ea n dv e r i f y i n gt h er e s u l t b a s e do n t h es t u d y i n gf o rt h e i m p l e m e n t a t i o no fd s pe l e m e n t a r ya l g o r i t h m s ，w os t u d ya n da n a l y z et h e i m p l e m e n t a t i o ns t r u c t u r ef o rt h r e ec l a s sa l g o r i t h m s ，c o n v o l u t i o n ，f i ra n dr a n ko r d e rf i l t e r , a n d a c c o m p l i s ht h eo p t i m i z a t i o nd e s i g n f o rt h et w oa l g o r i t h m s f i n a l l y , w ea n a l y z eaf a c t u a ld s p s y s t e ma l g o r i t h m ( l m s ) ，d e s i g nt h ei m p l e m e n t a t i o ns t r u c t u r ea n dv e r i f yt h ep e r f o r m a n c eo ft h e i n v o l v e da l g o r i t h m s k e y w o r d s ：d s pa l g o r i t h m ，a s i c ，f p g a ，c o n v o l u t i o n ，f i r ，r a a l ko r d e rf i l t e r ，l m sa l g o r i t h m 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同_ t - 作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：商遂箜! 箕造鲍! ! 塞望拉盔珏塞 学位论文作者签名：堡垒：叠 日期：弘一3 年月角 i 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：直运堕! 篡洼盟i ! ! ! 塞窭技丕盟塞 学位论文作者签名：盒量：塑日期：例年，月，r 日 作者指导教师签名：! 翌鱼日期：2 ，。弓年，月，7 日 里堕型竺垫查盔鲎业耋尘堕兰竺丝苎一 图目录 图11 硬件设计流程” 图1 2 基本的s p a r t a n i l 系列f p g a 框图“ 图i3 v i n c xi t 系列产品结构示意图一 幽2 1超前进位加法器逻辑框图“ 图228 位+ 8 位2 级流水线加法器” 图23 传统的移位累加乘法器结构 罔2 4 改进的移位累加乘法器结构- 图2 5 手算乘法示意图 图2 6 部分积技术实现实例一 图27 传统的加法器树乘法器结构 图2 8 改进的加法器树乘法器结构- 劂2 9 除法实现原理图 图2 1 0 开平方算法示例一 图2 11 开平方算法实现例示” | 冬| 31 传统的p s d s p 和移位加法器d a 结构一 图3 将表分割以产生简化的分巾式算法 图3 3 速度最优的高阶分布式算法 图34 直接彤式的f i r 滤波器一 图3 5 转嚣结构的f i r 滤波器一 图3 6 常数因子的两种实现方式- - 图3 7 应用r a g 算法的滤波器实现 图3 8 中值滤波处理示例- 图3 9 像素窗和原始像索 图3 】0 实现丌窗操作的结构 图31l 中值滤波实现结构 图31 2 第二级中值滤波结果阵列结构 图3 13 处理基元结构示意图 剧4l自适应阵的功能框图” 削4 2 横向滤波器 图43 分割算法为几个并行的部分 第1 i 页 4 ，；o 9 他 h h ” 憾 伸 丝 抖”拍 琳 凹凹 如如引弛 n 拈柏 国防科学技术犬学研究生院学位论文 第1 i i 页 国防科学技术大学研究生院学位论文 表目录 表1儿种加法运算仿真实现结果 1 0 表2 训步的编码 1 2 表3b o o l h 编码表” 13 表4 几种乘法运算仿真实现结槊 1 6 表5 丌方算法实现结果1 9 农6 直接f i r 滤波器改进前后结果指标比较”2 7 丧7 处理基元的组编码3 2 表8 两利，滤波器结构实现结果数据3 3 国防科学技术火学研究生院学位论文 第一章绪论 1 1 引言 在现代数字信号处理领域中，对实时性的要求日益增强，而随着传感器以及数字采集 技术的不断提高，我们所能够获取的信息更加丰富，需要处理的数据量更大，因此对于现 代数字信号处理系统来讲，高速度和大规模的计算能力足十分必要的。虽然目前数字信弓 处理( d s p ) 系统的实现方案有多种选择，但是无疑完全硬件的实现方案总是要比软件的 实现方案能够提供的速度更快、数据吞吐量更大。而在硬件实现方案中只有专用集成电路 ( a s i c ) j 能够从根本上满足系统对体积、功耗、重量、实时性、可靠性、保密性等要求。 与通用集成电路相比，a s i c 的优点上面已经提到，然而随着数字信号处理所涉及领 域的同渐增多，系统算法日趋多样化，计算的复杂性日益提高，因此算法硬件实现的难度 也相应增加，并且由于设计能力跟不上、纹计复杂度提高这个突出矛盾的存在，使得a s i c 设计效率偏低，设计成本较高，这严重制约了相关d s p 算法的a s i c 实现。为了在保证设 计质量的前提下，提高设计能力，人们必须改变设计方法。实现该目标有以下两条途径i 。j ： 1 采用高层次设计工具，使得设计者可以在高层次开始设计； 2 采用更为结构化的设计方法学，使得设计者可以大量重复使用前人过去设计的部 件。 标准硬件描述语言i h j 的出现( 如v h d l 和v e r i l o g 语言) ，促进了集成电子系统的高 层次设计，而作为a s i c 重要分支的现场可编程逻辑器件( f p g a ) 的日益发展使得a s i c 的结构化设计、验证等工作更加灵活、便利，从而推动了d s p 算法的a s i c 实现技术研究。 本文的目标就是分析研究基本的d s p 算法特点，根据层次化设计思想，以f p g a 器件 为设计平台，给出相应的算法硬件实现结构，并进行设计优化，进而使用硬件描述语言对 其实现，研究不同的算法结构在实现中的效果，设计出可供重复使用的标准器件模块。 1 2d s p 算法设计平台 通用d s p 处理器 通用的数字信号处理器( d s p s ) 是一类商品化的硬件芯片，在性能和设计复杂度方面 第1 页 邕堕型竺丝查盔= | 三塑壅尘竖兰垡笙苎 介于a s i c 和p c 之| l 口j ，可以使用汇编语言和c 语言进行编程开发。虽然开发过程中仍然 需要硬件设计知识，但是对于众多具有c 语言知识的设计者来讲，进行开发设计的难度大 大降低了。然而，如果不使用多个数字信号处理器，在一个d s p 系统中就不易实现算法的 并行化。算法的性能虽然优于p c ，却低于a s i c 开发的系统，因此在某些情况下，a s i c 或者f p g a 系统仍然是设计者唯一的选择i2 1 。当然，d s p s 仍然是一种非常通用而且有效的 处理实时数据的方法。而且在浮点运算领域d s p s 仍然处于主导地位，但是本文的研究范 围不涉及浮点运算，因为针对算法的结构优化设计而占，定点运算已经足够说明问题了。 2 专用处理器 应用专用集成电路技术，针对特定算法的特点，采用寄存器、逻辑元件的特定组合和 连接即可设计出专用处理器，在牺牲可编程灵活性的代价下，特定内核处理的速度可大幅 度提高p i 。除了速度外，降低成本也足使用专用处理器的重要原因。除了足够的处理资源， 那些为了灵活性的开销都可以免除。精心设计的专用处理器，能够吸收许多支撑性的集成 电路，减少芯片数量、印制板的面积和集成的难度。同样，降低功耗也是采用专用处理器 的原因之一。 作为a s i c 重要分支的现场可编程逻辑器件( f f g a ) 的曰益发展克服了传统a s i c 设计 的缺点，以f p g a 为平台设计的专用处理器可以用来实现一些并行设计思想，这在通用数 字信号处理器( d s p s ) 中是无法实现的。虽然设计者可以在门级进行f p g a 设计以得到更 加优化的实现结构，但是这对设计者有较高的要求，因而大多设计者是使用硬件描述语言 ( v h d l 或v e r i l o g ) 来进行高层设计实现，硬件描述语言的设计方法同软件设计方法相似， 这种以软件的观点进行硬件设计所需要的额外支撑耗费较低，而且可以进行设计抽象。本 文研究的高速d s p 算法就是在充分利用f p g a 技术优势的基础上，采用硬件描述语言进行设 计实现的。 3 发展趋势 本质上，在d s p 算法的开发设计中，通用d s p 处理器的解决方案是一种软件的实现 方法，而以f p g a 为平台的专j = = | 处理器实现方案是一种硬件的实现方法”1 。算法硬件的实 现方法可以针对具体情况实现专门化，不需要耗费对指令进行解释的时间，也不需要为了 能适应更普遍的情况而使硬件增加许多辅助的线路，而且可以利用空间扩展实现高度的并 行计算，因而速度更快，硬件利用率更高。 籀2 页 国防科学技术大学研究生院学位论文 虽然通用的可编程数字信号处理器( p r o g r a m m a b l ed i g i t a ls i g n a lp r o c e s s o lp d s p ) 在近 2 0 年里也已经取得了巨大的成功，然而它运算时的指令开销大，不易实现算法的并行化， 计算速度难以提高，硬件的利用率比较低卅：而且还可以进一步证明，在进行前端简单算 法的开发设计中，f p g a 技术要比p d s p 更有效率。据称，在未来，p d s p 将会主宰复杂算 法的应用领域( 例如：多重i g t h e n e l s e 结构) ，而f p g a 将会统治更多前端( 传感器) 的 应用，例如m a c 、f i r 滤波器1 4 1 。 1 3 设计实现 i设计流程 进行d s p 算法的硬件设计实现流程如图1 1 所示1 5 1 1 6 1 1 7 1 1 剐，该图充分显示了h d l 设计环境 和专门的f p g a 7 ：发工具之问的联系。第一步，使用硬件描述语言( h d l ) 生成算法设计： 然后对h d i 。代码进行语法检查并将设计综合( 编译) 优化到确定的元件库中，常用的专业 优化工具有s y n p l i c i t y 公司的s y n p l i f y s y n p l i f yp r o ，s y n o p s y s 公司的f p g ae x p r e s s 等，另外， f p g a 厂商的集成开发环境也带有一些综台工具，如x i l i n xi s e 中的x s t 等。在本文的研究 工作中这几种综合工具都有使用。综合优化完成后，要用专用的仿真工具对设计进行功能 仿真，验证电路功能是否符合设计要求。本文使用的仿真工具为m o d e lt e c h 公司的 m o d e l s i m 软件。功能仿真确认无误后，要使用器件开发商提供的专门的布局布线工具软件 对设计进行处理并映射到具体的器件中去，在这里设计人员可以利用开发商提供的专门的 工具来观察设计的平面布置图( f l o o r p l a n ) 以及其分层结构，进一步帮助设计者验证该步 工作是否符合设计要求。布局布线之后，需要做时序仿真，这一步很重要，这种仿真包含 的延时信息最为全面、准确，能够较好的反映芯片的实际工作情况。如果这一步被确认正 确，那么就可以将生成的配置文件( 门级设训) 写入j 芯片中进行测试。 每个仿真步骤如果出现问题，就需要根据错误的定位返回到相应的步骤更改或者重新 设计。一般来讲，中间步骤很难控制，所以大多数时候都是直接返回到最初设计。 第3 页 堕堕至! 望垫查查堂型塞生些兰垡笙苎一一 图1 1 硬件设计流程 2 f p g a 器件 f p g a 是一类称为现场可编程逻辑( f i e l d - p r o g r a m m a b l el o g i c 、f p l ) 器件中的一员。f p l 被定义为含有现场可反复使用的小规模逻辑模块和单元的可编程器件。鉴于f p g a 是特定 用途的集成电路，所以f p g a 被认为是一种专用集成电路( a s i c ) 技术。但是，通常设计 a s i c 类电路需要额外的半导体处理步骤，而f p l 是不需要这些步骤的。这些额外的步骤能 够提供更高级别的、更高性能的a s i c ，但是同时也增加了不可重复的工程成本 ( n o n r c o c c u r r i n ge n g i n e e r i n g ，n r e ) 。如前文所述，可编程门阵列解决方案的设计者可以完 全控制设计的实现过程，而不需要任何实际的集成电路制造设备或者因为后者而延缓设计 进度1 6 i | 7 i 。 本文设计所选择的v i r t c x i i l 9 】系列和s p a r t a n _ i i u o l 系列器件是x i l i n x 公司新一代f p g a 产品中的两种代表类型。其中v i r t e x i i 系列是x i l i n x 公司高密度、高性能f p g a 产品的代 表，它们具有逻辑容量大、片内r a m 多、时钟频率高、含有硬件乘法器运算单元、支持 多种接v i 标准等特点。s p a r t a n _ i i 系列是x i l i n x 公司低成本、低密度f p g a 的代表，它们 采用成熟的f p g a 结构，支持流行的接口标准，具有适量的逻辑资源和片内r a m ，并提供 灵活的时钟管理。 s p a r t a n l i 系列提供了较高的性价比和适中的逻辑资源，其逻辑框图如下所示： 第4 页 国防科学技术大学研究生院学位论文 回 0 0 0 0 0 0 垦 一口口o o e 等广 玉噩 吕 氕 蚕盏爿 3 0 - d l l 圜 口 】0 0 一 咖咖唧咖 o o 0 0 0 0 田髑日 o o o o o o 回 王 芷 u o 图1 2 基本的s p a r t a n l l 系列f p g a 框图 相对于s p a n a n i i 系列而占，v i r t e x1 i 系列提供了更加丰富的资源，其逻辑框图如下所示： d c mi x ；mi o b 勖 司 s o l v e l r a m m u l l i p l i o r 图1 - 3v i a e xi i 系列产品结构示意图 从技术角度来讲，x i l i n xf p g a s 是s r a m 器件。这就意味着：醛片必须在加电后才能 够被编程配黄。而可配置逻辑块( c o n f i g u r a b l el o g i cb l o c k s ，c l b s ) 足这两个系列f p g a 的基本逻辑单元。s p a r t a n l i 系y l j 中每个c l b 包含2 个s l i c c s ，而v i r i e x1 i 系列中则包含4 个 s l i c e s ，两者的每个s l i c e 均包含2 个4 一i ，u t ( f ，g ) 和2 个d 触发器，以及快速进位逻辑。 每个l u t 部可以用作一个1 6 x i 的异步r a m 。 第5 页 peecceceeck匕cl匕! 口口口口口口口口 口口口口口口口口! 口口口口口口口 国防科学技术人学研究生院学位论文 x i l i n xv i r t “i i 系列相对于s p a r t a n - 】i 系列而言密度更大、资源更加丰富、性能更高， 那么相同的算法在这两种不同的结构上实现性能当然也会有所差别，当然成本也有不同。 本文将会针对各类算法研究重点的不同而选择相应的器件，但是这并不是本文研究的重 点。本文主要是在同一结构的f p g a 上对算法的不同结构进行分析研究、设计实现，从而 找到优化的算法结构。 1 4 本文所做的主要工作 为了满足d s p 系统对高速度和大规模的计算能力的要求，寻求算法的硬件实现是必然 的途径。而f p g a 器件的作用不止于简单地集成若干中小规模集成电路和作为a s i c 器件 廉价的代用品，更重要的足它系统可编程的能力非常适用于进行相关硬件算法的设计、调 试、分析、验证等工作，为硬件算法的实现研究提供了合适的平台。在本文中，我们着重 研究d s p 算法的实现结构，进行优化设计。并在f p g a 器件上进行实现验证和性能分析。 本文的内容安排如下：第一章，对d s p 算法实现平台以及相应硬件体系结构和开发 流程作一个全面的介绍；第二章，具体分析几种基本d s p 运算的实现结构，并予以设计实 现；第三章，研究分析三类经典d s p 算法( 卷积、f i r 和序列滤波) 的硬件实现技术；第 四章，对一个实际的d s p 系统算法进行分割和并行化设计：第五章，总结全文。 第6 页 里堕型堂垫查查兰竺塞生些兰堡兰塞 一 一， 第二章基本运算单元及其实现技术 2 1 加法 加法运算是最基本的算术运算，无论是减法、乘法、除法或f i r 运算，最终都要分解 为加法运算。同样的，加法器是最基本的算术运算单元。加法器中最小的单元是全加器， 全加器中有两个数据输入端a 和b ，和一个进位输入端c i n ( 简写9 c ) ，一个和数输出端s u m 和一个进位输出端c o u t 。 逻辑表达式足： s u m ax o r bx o r c i n c o u t 2 a a n dbo r c i na n d ( a o r b ) 以全加器为基本单元，实现加法器的方法有许多种，本文主要讨论三种：串联加法器， 超自口进位加法器，流水线加法器。 1 串联加法器 串联加法器由全加器级连而成，上一级的进位作为下一级的输入。这种结构是最简单 的加法器实现方式，但速度慢，高位运算必须等低位进位到柬后才能进行，当字长较大时， 由于进位要经过多次传递，因此延时将非常可观( 字长为n 的加法运算需要n 1 级门延时) ， 显然不适应实时处理的要求，所以高性能的d s p 器件中一般不用这种结构的加法器。 2 超前进位加法器 超前进位加法器也称行波进位加法器( r i p p l e 。c a r r ya d d e r ) 1 1 10 对串联加法器进行研究 发现串联加法运算的延时主要是由进位的延时产生的。因此超前进位加法器从进位的角度 考虑加法问题，各位彼此独立，最后运算结果不依赖于进位的传播，因此它的延时较小， 速度相对较快。 下面是一个4 位+ 4 位加法器的超前进位链。其中，s u m ( n ) 置j 第n 位部分和，a ( n ) 和b ( n ) 为两个操作数的第n 位，c o g jc i 分别为进位输入和输出，c ( n ) 为向高为传输的进位。p ( n ) 为第n 位进位传输函数( - g p 为1 则向高位传输低位进位) ，g ( n ) 为第n 位进位生成函数( 若 g 为l 则必定产生进位) 。 p ( n ) 2 a ( n ) x o rb ( n ) 第7 页 国防科学技术人学研究生院学位论文 g ( n ) = a ( n ) a n db ( n ) s u m ( n ) = a ( n ) x o rb ( n ) x o rc ( n ) c f 0 1 = c i c ( 1 ) 2g ( 0 ) o r ( p ( 0 ) a n dc ( 0 ) ) = g ( o ) o r ( p ( o ) a n d c i ) c ( 2 ) = g ( 1 ) o r ( p ( 1 ) a n dc 0 ) ) 2 g ( 1 ) o r ( p ( 1 ) a n d g ( o ) ) o r ( p ( 1 ) a n dp ( o ) a n d c i ) c ( 3 ) = ：g ( 2 ) o r ( p ( 2 ) a n dc ( 2 ) ) 2 g ( 2 ) o r ( i ) ( 2 ) a n dg ( 1 ) ) o r ( p ( 2 ) a n dp ( 1 ) a n dg ( o ) ) o r ( p ( 2 ) a n dp ( 1 ) a n dp ( o ) a n d c i ) c ( 4 ) 2g ( 3 ) o r ( p ( 3 ) a n dc ( 3 ) ) 。g ( 3 ) o r ( p ( 3 ) a n dg ( 2 ) ) o r ( p ( 3 ) a n dp ( 2 ) a n dg ( 1 ) ) o r ( p ( 3 ) a n dp ( 2 ) a n dp ( 1 ) a n dg ( 0 ) ) o r ( p ( 3 ) a n dp ( 2 ) a n dp ( 1 ) a n dp ( 0 ) a n dc i ) c o2 c ( 4 ) 根据上述式子可得如下逻辑图2 1 h 3 g ( 3 )j 1 2 ) u 2 ) 图2 i 超前进位加法器逻辑框图 可见去掉迭代关系后，则各位彼此独立，进位传播不复存在，总的延迟只是两级门延 迟。相对应串行进位加法器而亩，其高速也就白不待言。 由于超前进位链并不是越长越好，整个加法器的速度同连线延迟、逻辑门的扇入扇出 能力以及逻辑门延迟等有关，需要综合考虑。因此一般来讲规模较小的加法器( 4 位+ 4 位) 第8 页 国防科学技术大学研究生院学位论文 可以直接使用超i j 进位链，规模较大的加法器需要分解成较小的单元进行，单元之间的进 位同样使用超前进位链实现。在实际应用中，可以拟制多种方案，综合考虑后选取最优方 案。 3 并行加法器和流水线结构 并行加法器又称查找表型加法器。这种结构预先将n 位加法表放在一个查找表中，使 用操作数作为地址去访问查找表，得到的输出数据就是加法值。例如，一个4 位+ 4 位的加 法器可以放到一个2 5 6 * 5 的查找表中。 并行加法器速度快，只有一级门延时，对于实现4 位以下的加法器比较合适。但增加 并行加法器的位数，却受到查找表容量的限制( 指数级增长) 。这时可以采用流水线加法 器。下面以一个8 位+ 8 位的加法运算来介绍流水线结构加法器： s t l m ；a + b 其中，a = ( a t , a 6 ，a l ，a 0 ) ，b = ( b 7 ，b 6 ，b l ，b 0 ) ，s u m = ( s 7 ，s 6 ，s l ，s o ) 。 上述加法可以分解为： s u m = a + b = 【( a 7 ，a 6 ，a 5 ，a 4 ) + ( b 7 ，b 6 ，b 5 ，b 4 ) + 2 4 + ( a 3 ，a 2 ，a l ，a 0 ) + ( b 3 ，b 2 ，b l ，b 0 ) = s u m l + 2 4 + s u m 2 其中，s u m l 和s u m 2 称为部分和。 经过改进，实现8 位十8 位的加法运算只需要2 个4 位加法器，在f p g a 中由于查找表输入 线少，往往需要分解为更小的规模进行。在c p l d 中实现4 位十4 位的加法器就比较容易了。 经过分解后的加法运算门延时等于各级运算门延时之和。为了提高加法嚣的工作速度，可 以采用流水线技术。流水线技术将每一步运算都用寄存器暂存。尽管单个运算需要多个时 钟周期才能得到结果，但由于操作数是不断地加到运算输入端的，所以总的效果是每个加 法运算平均消耗的时间等于锁存时钟的周期。8 位流水线加法器【6 1 可以用图2 2 说明。 图2 28 位+ 8 位2 级流水线加法器 第9 页 里堕型鲎垫查盔堂竺塞尘竖堂篁笙兰 使用流水线结构将使加法器的运算速度明显提高。但速度的提高是以牺牲资源为代价 的。 实现加法器的方法还有许多，如曼彻斯特进位加法器、条件求和加法器、进位选择加 法器，基本思想都足解决进位传输延迟的问题。以曼彻斯特进位加法器为例：当两个操作 数对应位全为。时，不会产生进位；当全为l 时，肯定产生进位；其他情况，传输上一位的 进位值。 4 加法器设计实现 加法运算是最基本的算术运算，无论是减法、乘法、除法或f f t 运算，最终都要分解 为加法运算。实现加法运算的方法有许多。从速度和资源耗费等多方面综合考虑，实现规 模较小的加法器可以使用查找表加法器，规模较大的加法器可以使用流水线加法器柬实 现。当然在具体实现上代码的风格不同最后综合出来的效果也有较大差异，主要表现在资 源占用和运算速度上，为作比较，本文在x i l n x 公司提供的i s e 4 1 i 软件环境下，使用v h d l 和v e r i l o g 语言实现了上面讨论的几种加法器，综合工具选择f p g ae x p r w e s s ，f p g a 器件选择为s p a r t a n 2 系列韵x c 2 s 3 0 5 p q 2 0 8 ，结果详见下表： 表l 几种加法运算仿真实现结果 模块 器仲规模 资源消耗最火逻辑延最大延迟时间 类型 s i i c e g a t e 迟时间( n s ) l o g i c + r o u t e ( n s ) 串行 4 t t + 4 伉64 89 0 9 21 2 9 4 5 进何 8 位+ 8 忙1 29 61 1 7 0 4】85 2 0 1 6 伎+ 1 6 他2 41 9 2i 6 9 2 82 9 8 6 5 加法器 3 2 位+ 3 2 位4 83 8 42 7 - 3 7 65 4 3 2 7 超前4 位+ 4 位76 68 4 3 91 2 3 4 8 进位 加法器 1 6 位+ 1 6 位3 i3 3 61 4 3 1 62 6 1 7 7 8 位+ 8 位77 7 i ( 4 级) 3 01 8 1 65 8 7 7 ( m i n i m u mp e r i o d ) 流水线1 6 位+ 1 6 位3 5 9 2 1 0 9 2 4 9 6 3 8 结构( 4 级，8 级、 5 9 ，6 671 8 3 5 9 7 0 5 0 1 6 ( m i n i m u mp e r i o d ) 加法器3 2 位+ 3 2 位 9 77 1 5 666 2 28 6 8 3 1 4 0 】o ( 4 级8 级，1 3 l9 9 6 07 2 7 6 1 0 0 2 4 1 6 级)1 3 41 1 1 4 85 9 7 0 ( m i n i m u mp e r i o d ) 从速度的角度来讲，流水线结构加法器最优，从资源占用的角度来讲，串行进位加法 器占用资源最少。总的来看，速度( 性能) 和资源消耗( 刀：销) 是一对矛盾。 第10 页 国防科学技术大学研究生院学位论文 对于流水线加法器，流水深度同运算速度在一定程度上是成正比的，然而随着流水深 度的增加，连线延迟在总的延迟中所占的比重越来越大，逻辑延迟所占比重逐渐变小，总 的延迟不一定减小，而资源耗费却直线上升。 2 2 乘法 乘泫是d s p 运算中的基本类型，应用也最为广泛。我们知道，乘法最基本的操作就是 移位相加，各类乘法最终都要归结为这一点，然而如何实现移位相加却有多种方法，进行 相应的改造后就可以得到一些更为适合硬件实现的结构l l “。本文主要讨论分析移位累加乘 法器、查询表乘法器、b o o t h 乘法器、加法器树结构乘法器。 1 移位累加乘法器 移位累加是最基本的硬件乘法器实现方式，基本原理如图2 3 所示：将两个操作数分别 以串行和并行模式输入到乘法器的输入端，用串行输入操作数的每一位依次去乘并行输入 的操作数，每次的结果称之为部分积，将每次相乘得到的部分积加到累加器里，形成部分 和，部分和在与下一个部分积相加i j 要进行移位操作。 串 r 输 图2 3 传统的移位累加乘法器结构 仔细观察传统的移位累加乘法器可以发现：第一，虽然两个n f y 的操作数相乘结果为 2 n 位，但是中间过程的每一个部分积都为n 位，移位相加的有效宽度也是n 位，因此可以 考虑用n 位的加法器来代替2 n 位的加法器以减少资源耗费：第二，可以考虑将移位和累加 合在一起进行，实现一步得到部分和，这样只需要n ( 酬l j ) b 2 n ) 个时钟周期就可以完成。 运算框图如下所示：将串行操作数存于寄存器a 中，并行操作数存于寄存器b 中，部分 和存于寄存器s 中，这三个寄存器位宽都为n ，- b # f 设置一个一位的寄存器c 用以存放临时 进位。 第ll 页 国防科学技术大学研究生院学位论文 图2 4改进的移位累加乘法器结构 首先，将寄存器s 清零，部分积由a 【o 决定( 零或b ) ，将位宽都为n 的部分积和寄存 器s 中的值输入到一个n 位的加法器中求和，结果( 含进位) 与a n i ：1 合并在一起形成2 n 位的部分和，然后将这2 n 位部分和的高n 位送到寄存器s 中，低n 位送到寄存器a 中继续进 行运算，直到n 个周期为止。这样，该运算只需要一个n 位的加法器，n 个时钟周期就可 完成。 2 布思( b o o t h ) 乘法器 布思算法( b o o t ha l g o r i t h m ) 是由布思夫妇首先提出来的，他们发现：当二进制乘数 中连续出现1 位时，可以通过使用减法来减少所需进行累加的部分积的数量。例如， 用乘数1 5 ( a ) 去乘被乘数8 9 ( b ) ，这需要四个lxb 的部分积移位累加，而这同1 6b b 所得的结果是一致的。这实际上就是c s d ( c a n o n i cs i g n e dd i g i t ) 编码的思想，后文还将详 细叙述。 我们这里只讨论比较简单的一种情况。首先假设乘数a 位宽为n ，若n 为奇数，则扩展 为偶数。扩展的实现只需在高位前添零即可( 假设a 为无符号数；如果a 为有符号数，则用 补码表示：补码扩展其最高位，并无影响。) 这样经过处理后，乘数a 位宽为m ，m 为偶数。 则编码做表如下： 表2 初步的编码 a 2 na 2 n ，l q 0o o o lb lo 2 b 1l 3 b 注：表中n = l ，2 3 m 2 ，a 2 n 为a 的第2 n f 立，q ) l j 部分积。 第12 页 国防科学技术人学研究生院学位论文 其中+ 3 b 的运算，j = | 普通的加法器不能一次完成。如果分为两次执行，则又降低了速 度。我们可将3 b n 作( 4 b b ) 来处理，本次操作执行一b ，用一个欠账触发器c j 记下欠账，下 一次操作时再： b j z + 4 b 。由于本次累加后部分积要右移两位，从相对关系来看，相当于被 乘数左移了两位，因而下一次实际上只需执行+ b ，就等于前次完成t + 4 b 操作。据此，可 得靠思编码表如下： 表3b o o t h 编码表 a 2 na 2 n ic j n 1 q c j n 0oo+ 0 o 0ol+ bo olo+ b0 o1 1+ 2 b0 lo0+ 2 b0 10l- b l i 10b l l1 1ol 上述稚思编码一次处理了两位，确定运算量0 、b 、2 b 、b ，形成( m 2 ) 项编码项、乘 积项，若乘数有效位为n ，则需作n 2 次移位，最多作n 2 + 1 次累加。相对于移位累加乘 法器来讲，该算法方便快捷。但是由于引入了欠账触发器c j ，相当于在高二位和低二位之 间存在着借位传播，如果用迭代方式，则可用一位寄存器保存此借位，但最高两位可能会 出现借位，会增加一次特殊运算，对此需特别注意。 3 查找表乘法器 把乘积放在存储器中，使用操作数作为地址访问存储器，得到的输出数据就是乘法运 算的结果。查询表方式的乘法器速度等于所使用的存储器的速度，小型乘法器使用这种技 术非常合适。x i l i n x 公司的现场可编程器件( f p g a ) 就是基于查找表结构的，因而在其中 实现查找表型乘法器非常方便，同时速度也非常快，但是随着操作数精度的提高，查找表 变得非常庞大。例如，8 位乘法器需要2 s + s + 1 6 这样大的存储器。有鉴于此，我们可以考虑 引入部分积技术，考虑如图2 4 所示的手算乘法： 第l3 页 里堕型堂垫查盔堂婴鍪尘竖鲎丝堕苎一一一 0 76 7 6 76 7 l 盟垃4 生盟型 2 82 8 2 82 8 2 4 0 2 4 0 2 4 0 + 2 4 0 3 5 03 5 u3 5 03 5 0 1 31 1 1 1 q + 3 0 0 0+ 3 0 0 0 + 3 0 0 0 3 6 l83 6 1 83 6 i8 3 6 i8 躅2 5 手算乘法示意图 这里分别计算每一位数字的乘法，然后将各个部分积进行移位和相加