（凝聚态物理专业论文）32位高速高性能浮点阵列乘法器的设计.pdf

上海大学硕士学位论文 摘要 本论文主要讨论了4 0 位3 2 位高速高性能浮点数整数阵列乘法器的设计研 究工作，它主要应用于数字信号处理器( d s p ) 芯片中。 文章从d s p 芯片的数据格式和浮点运算入手，具体说明乘法器中允许的数 据格式。同对依据芯片对乘法器的性能要求，从两个方面考虑了乘法器的设计： 一是补码浮点乘法算法的研究，二是乘法器关键电路的设计。 针对补码形式的数据格式，在比较了几种补码乘法算法的基础上，选择较为 理想的改进型b o o t h 算法进行深入论述，并将其应用于乘法器的设计之中。 在电路设计中具体考虑c m o s 电路结构的设计，主要阐述了乘法器中b o o t h 编码电路设计，部分积产生电路设计，全加器电路设计( c s a 及c p a ) ，进位链 电路设计等。通过将本设计用到的关键电路与以往其他设计用到的相关电路进行 h s p i c e 仿真，在面积、时延、功耗等方面进行比较，作者提出了c p l c m o s 编 码器( b o o t h 编码电路) 、c p l 全加器( c s a ) 、曼彻斯特进位和旁路进位相结合 加法器( c p a ) ，这些电路能很好地实现高速高性能乘法器设计。而后完成了乘 法器的总体功能仿真和验证。 在乘法器总体设计、逻辑设计以及电路设计实现的基础上，用全定制设计方 法，并依据上华公司制定的o 6 u m c m o s 工艺的设计规则完成了版图设计。在版 图设计完成之后，先利用软件对乘法器的版图进行寄生参数提取，然后利用 s t a r s i m 软件进行后仿真。在0 - 7 0 。c 温度，电源电压4 5 v 的仿真条件下，乘 法器的工作频率超过6 0 m h z ，功耗电流为2 8 m a 。仿真结果表明，乘法器完全能 够满足d s p 芯片的全部性能指标要求。 关键词：数据格式，改进型b o o t h ，静态电路，传输门电路，c p l 电路 曼彻斯特进位链，可测性设计，全定制版图设计 上潜大学硕士学靛论文 a b s t r a c t 拍ep a p e rm o s t l yd i s c u s s e sad e s i g nf o r4 0 3 2b i t sf l o a t i n g - p o i n to ri n t e g r a l - p o i n t a r r a ym u l t i p l i e ro fh i g hs p e e da n dh i g hp e r f o r m a n c e ，w h i c hi sm a i n l yu s e di nd s p c h i p s i nt h ep a p e r , t h ed a t af o r m a to fd s pa n df l o a to p e r a t i o n sa r ed i s c u s s e df i r s t t ：，； w i t hp e r m i t t e dd a t af o r m a to ff i e 雠m u l t i p l yi nd e t a i l s a tt h es a m et i m e a c c o r d i n gt o t h ed e m a n db yd s pc h i p s ，w et h i n ka b o u tt h ed e s i g nb yt w ow a y s o n ei st h er e s e a r c h o ft h em u l t i p l yi m p l e m e n t a t i o nb y2 sc o m p l e m e n ta l g o r i t h m ；t h eo t h e ri st h ed e s i g n o fp i v o t a lm u l t i p l i e rc i r c u i t s 。 a c c o r d i n g t ot h ec o m p a r i s o no fs e v e r a lm u l t i p l ya l g o r i t h mi nc o m p l e m e n tf o r m a t ， t h et h e s i sd i s c u s s e st h em o d i f i e db o o t h a l g o r i t h ma n du s e si ti nt h em u l t i p l i e rd e s i g n t h ed i s s e r t a t i o na l s oe l a b o r a t e st h ed e s i g no fc m o sc i r c u i t s c o n f i g u r a t i o n ， w h i c hi n c l u d e st h ed e s i g no fb o o t he n c o d e rc i r c u i t ，p a r t i a lp r o d u c tp r o d u c i n gc i r c u i t ， c s aa n dc 黢c i r c u i t s c a r r yc h a i nc i r c u i te t c 。b yc o m p a r i s o no ft h ek e yc i r c u i t s d e s i g n e di nt h i sp a p e rw i t ho t h e rr e l e v a n tc i r c u i t su s i n gh s p i c es i m u l a t i o n ，m a k i n g f u r t h e ra n a l y s i si na r e a ，s p e e d ，p o w e re x p e n d i t u r ea n ds oo n ，c p l c m o se n c o d e r c i r c u i t ，c p la d d e rc i r c u i t ，i m p r o v e ds t a t i cm a n c h e s t e ra n db y p a s sa d d e rc i r c u i th a s b e e nb r o u g h tf o r w a r di nt h i sp a p e r , w h i c hc a l lr e a l i z ec o m m e n d a b l yt h eh i g hs p e e d a n dh i g hp e r f o r m a n c ed e s i g n 蛩l o n 、凌ec o m p l e t e dl o g i cs i m u l a t i o na n dv e r i f yo ft h e m u l t i p l i e rh a v eb e e nf i n i s h e d o nt h eb a s i so fa c c o m p l i s h e dc o l l e c t i v i t yd e s i g n ，l o g i ed e s i g na n dc i r c u i td e s i g n ， t h el a y o u ti sa l s oa c h i e v e db yf u l lc u s t o mw a y s ，w h o s ed e s i g nr u l eb a s e s0 6 u m c m o st e c h n i q u e so fc m s c a n dt h e n t h em u l t i p l i e rp a r a s i t i c a lp a r a m e t e r sa r e p i c k e du pb ys o f i w a ma n dm u l t i l l i e ri sl a t e rs i m u l a t e db ys t a r s i m u n d e rt h e t e m p e r a t u r ef r o mo - 7 0 a n dv o l t a g eo f 4 5 v , i t sw o r k i n gf r e q u e n c ye x c e e d s6 0m 硪 w i t ht h ec o n s u m i n gc u r r e n to f2 8 m a t l l es i m u l a t i o nr e s u l t ss h o wt h a tt h em u l t i p l i e r h a ss a t i s f i e dw i t ha l lp e r f o r m a n c et a r g e t so fd s ph a r d w a r es y s t e m k e yw o r d s ：d a t af o r m a t ，m o d i f i e db o o t h a l g o r i t h m ，s t a t i cc i r c u i t ， p a s s - t r a n s i s t o rc i r c u i t s ，c p lc i r c u i t ，m a n c h e s t e rc a r r yc h a i n ， m e a s u r a b l ed e s i g n ，f u l lc u s t o md e s i g n 越 上海大学硕士学位论文 第一章前言 1 1 数字信号处理系统的研究状况【1 】【2 】 二十世纪六十年代以来，随着计算机和信息技术的高速发展，数字信号处理 技术应运而生并得到迅速的发展。在过去的二十多年时间里，数字信号处理已经 在通信、计算机、网络、工业控制以及家用电器等领域中得到极为广泛的应用。 数字信号处理是利用计算机或专用处理设备，以数字形式对信号进行采集、 变换、滤波、估值、增强、压缩、识别等处理，以得到符合人们需要的信号形式。 数字信号处理的实现方法一般有以下几种： ( i ) 在通用的计算机( 如p c 机) 上用软件( 如f o r t r a n 、c 语言) 实现； ( 2 ) 在通用计算机系统中加上专用的加速处理机实现； ( 3 ) 用通用的单片机( m c u ) 实现( m c u 一般称为微控制器) ； ( 4 ) 用通用的可编程d s p ( d i g i t a ls i g n a lp r o c e s s o r ) 芯片实现； ( 5 ) 用专用的d s p 芯片实现。 在上述几种方法中，第一种方法的缺点是速度较慢，一般可用于d s p 算法 的模拟；第二种和第五种方法专用性强，应用受到很大的限制，第二种方法也不 便于系统的独立运行。现在用得最多的是第三种和第四种方法，m c u 与d s p 都 是以数字信号为处理对象的，但单片机( m c u ) 只能用于实现简单的数字信号 处理，如数字控制等；只有d s p 芯片才能完成复杂的数字信号处理，因为它具 有更适合于数字信号处理的软件和硬件。 虽然数字信号处理的理论发展迅速，但在二十世纪八十年代以前，由于实现 方法的限制，数字信号处理的理论还得不到广泛的应用。直到八十年代初世界上 第一片单片可编程d s p 芯片的诞生，才将理论研究结果广泛应用到低成本的实 际系统中，并且推动了新的理论和应用领域的发展。因而d s p 芯片的诞生为数 字信号处理的应用打开了新的局面，它实时快速地实现了各种数字信号处理算 法，简化了信息处理的程序及速度，大大地促进了现代电子技术及信息技术的发 展。在国外，d s p 芯片己被广泛应用于当今技术革命的各个领域：在我国，d s p 技术也正以极快的速度被应用于科技和国民经济的各个领域。 上海大学硕士学佼论文 1 2d s p 芯片的结构与功能概述 本文涉及的d s p 芯片是通用数字信号处理芯片，它的通用性体现在以下几 方蕊：有6 4 m b 稃诺器空间；多处理器接口，内部及外部产嫩总线等特状态；两 令步 秘葸线搂潍；鼹个定鞋器，疆令枣窍蜀；多重中鼗缭褥。霆瑟该蕊嚣溉霹终 为主处理机应用，又可作为专绢协处理耱应用。 d s p 芯片具谢较高的性能，可在单个时钟周期内完成一次2 4 位整数或3 2 位 浮点数懿著j 亍乘法。该芯片款戳下凡方面获取薅缝髭：药了撬褰系统瓣并行度， 不惜磺件代价，狂c p u 内部设鼹圈条数据总线，从面并行执行乘、搬( 或减) 操作；她蛙总线每数搬总线分离，并且分别设立程序地蛙。两个数据地缴霹d m a ( d i r e c tm e m o r y a c c e s s ) 遮址慧共霆祭谤存稳疆慧线，繇麓滁爨结褥将程亭窝数 据分开，使取指和执行能完全黛叠运行；有专用外设总线，并采用两个专用的地 址加法器；具裔特定高效的指令察支持性能实现；同时系绕采用先进的滚水线黼 控爨磐法，整稳邻嚣条宏缮令程虢孬辩只糖蓑一个霹镑躅麓，爨上一条宏密令援 行到译码时段时下一条宏指令融在执行取指时段，每个时段( 又称为“站”) 都 是不间的宏指令穰“跑”，形成流水线而不问断。 d s p 芯篾采鲻随滔流求线窍式控麓取指辅携令静执行。系统孛每条宏指令必 须经过四站才能究戒指令功能，每站至少占用一个时钟周期。这四个时钟周期按 指令执行顺序分别题取值周裳、译码趱期、读数周裳、执行阂靛。尽管镶条宏指 令获敬措到豢令羧稽交；戒要经掰童述圈夺瘸期，毽在滚零绫燹淬突豹鬟键下，每 个时钟周期可以执行一条宏指令，这就是流水线控制方式吸引人之处。采用先进 兹流水线控制方戏，逮将极太：鞋照摄高计算枧的楚理速度。 d s p 芯冀葵蠢懿逶矮毪帮安黩效辘先各耱疲震攥袋了灵滋豹设嚣警蔽。筵步 该芯片能同时提供谯一些复杂应用中所需的多爨功能。它的热型应用包括在通用 数字信号处理中的数字滤波，棚获，快速傅立叶变换，波形发生等，在控制中的 磁蠹控翻，辊嚣入控铡，激光搿印祝控制等，在军事巾的僚鬻通讯，雷达处理。 声纳处理，图像处蠼，导航等，强外在通信，囱动化，工波，医疗中都攥用到该 d s p 芯片。 2 上海大学硕士学位论文 1 3 乘法器的研究背景及相关内容 随着科学技术的不断发展，对d s p 技术的需求越来越迫切。d s p 数字信号 处理系统作为一种高速专用的微处理器，它具有强大的运算功能和高速的数据传 输能力，专门用于完成各种数字信号的处理。而要完成数字信号的处理就要依靠 各种不同的算法；在各种算法中，通常都能化简成最基本“乘加”运算形式。因 此，d s p 体系结构设计的重要特征是强调“乘加”运算的高速处理能力。而如果 采用普通的计算机软件来实现“乘加”运算，就必须按照程序进行多次加法运算， 效率低、速度慢、成本高，不能满足实时高速信号处理的要求。在这种情况下， 就必须采用专用的硬件乘法器，它能够在单个时钟周期内完成一次乘、加运算。 因而可以毫不夸张地说，硬件乘法器是高性能d s p 的重要部件，是d s p 芯片实 现实时高速信号处理的重要保障。 乘法器的电路有多种形式，在设计乘法器电路之前要先了解乘法运算是如何 进行的。乘法运算的最基本形式是两组正整数的二进制数相乘。例如两组4 位二 进制数相乘，被乘数是口3 n ：a ，a 。，汞数：是b 3 b 2 b l b o ，则可用下列算式求乘积： r 6 p 5p 4p 3p 2p i p o= 乘积 可以看出：从乘数最低位开始，被乘数由乘数逐位相乘后得到相应的部分积， 再将相应位置的部分积全部累加起来得到最后的乘积。但高位乘数的位权与低位 乘数的位权不同，因此，被乘数在与乘数进行乘法运算是必须左移一位，依次类 推，直到乘数各位乘完为止。综观上述乘法运算，可见乘法包括二步基本操作： 计算部分积： 部分积移位后累加。 其中部分积的运算可用a n d 门实现，而部分积的累加可用加法器来完成。 实现上述两组二进制数相乘的乘法器电路形式有很多，包括串串乘法器、串 并乘法器、并并乘法器等。究竟用何种乘法器的电路结构，将取决于系统对乘法 速度- “- ，一- v e 、l 、运算精度等方面的要求，综合进行考虑采取何种硬件电路。 上海大学硕士学位论文 串串乘法器的特点是被乘数和乘数串行输入，乘积亦串行输出。串并乘法器 的被乘数是串行输入，乘数是并行输入，最后乘积是串行输出。这两种乘法器的 电路结构虽然简单，但运算速度较慢，且随着操作数位数的增加运算速度慢，所 需运算时间长的问题显得尤为突出，因而这两种乘法器并不适用于d s p 芯片数 字信号处理系统。 并并乘法器，又称阵列乘法器，它是将被乘数、乘数同时并行输入，所有部 分积项同时并行产生，然后将相关部分积项求和，最后累加得到的乘积再同时并 行输出。随着高速半导体存储器的出现，存储器存取的速度与乘法运算所需时间 之间的不协调也随之激化，因而，对阵列乘法器的研究是十分必要的。阵列乘法 器的运算速度极快，主要应用在以速度要求为主要条件的情况下。而且随着大规 模集成电路的出现，阵列乘法器中具有统一乘法单元使它的结构变得更加经济可 行，版图设计变得更加规整简单，易于v l s i 的实现。 1 4 本论文的研究内容 本论文是作者毕业课题的总结，主要阐述的是3 2 位高速高性能浮点数整数 阵列乘法器的设计，该乘法器已成功应用于d s p 芯片中。芯片的总面积是8 8 m m 2 ( 特征尺寸是o 6 u r n ) ，1 8 1 根管脚栅阵列( p g a ) 封装，芯片的供电电源是 5 v ( 土1 0 ) ，工作温度适宜于o 7 0 ，主时钟频率是6 0 m h z ，在此频率下 d s p 芯片的总功耗电流为1 8 0 m a 。在d s p 芯片中，乘法器的面积不超过芯片总 面积的1 1 6 ，乘法器的功耗不超过芯片总功耗的1 8 或1 1 0 ，遵照该芯片采用的 流水线控制方法，乘法器可以在单个时钟周期内完成一次乘法操作。 本论文首先从d s p 芯片的数据格式和浮点运算入手，具体说明了乘法器允 许的数据格式，相关算法的选取及芯片对乘法器性能的要求。再根据芯片的要求 设计3 2 位高速高性能浮点数整数阵列乘法器，完成了逻辑设计、电路设计。在 电路设计中具体考虑c m o s 电路结构的设计，主要是控制信号产生电路设计， 部分积产生电路设计，全加器电路设计， 行了包括工艺参数在内的h s p i c e 仿真。 虑采用多层布线和s a l i c i d e 的先进技术， 进位链电路设计等，对这些关键电路进 然后对电路进行版图设计，这时需要考 以尽可能多的减少关键通道布线延迟， 4 上海大学硕士学位论文 整个乘法器的版图设计采用的是高性能三层舢、单层多晶硅o 6 u mc m o s 工艺。 乘法器通过仿真和测试验证，实现了d s p 芯片对乘法器的设计参数要求，完成 了相关功能。 该乘法器能在单个时钟周期内执行2 4 位整数或3 2 位浮点数的乘法运算，其 浮点运算能以定点运算速度进行。同时通过并行指令，一个乘法操作和a l u 操 作可在单周期内并行完成各自的操作，从而获得了更高的处理能力。利用 c a n d e n c e 工具完成了乘法器的逻辑、电路设计及版图设计，使它完全能达到预期 的工作速度，满足芯片的要求，很好地实现d s p 芯片的实时高速信号处理能力。 上海大学硕士学位论文 第二章d s p 芯片与乘法器的关系 2 1 时序关系 d s p 芯片采用统一的同步时钟。从芯片输入脚外接晶体振荡器产生振荡信 号，该信号再经过芯片内部的时钟电路产生一对不相叠的系统时钟信号b h l 和 b h 3 。 b h l 经二级反相器形成b 1 h 1 ，b h 3 经一级二输入的“与非”门和一级反相 器形成b 1 h 3 ( 与非门的另一个输入端可由测试电路产生，在联机情况下常为高) 。 乘法器就是用b 1 h 3 和b 1 h 1 作为同步时钟，结合前言中流水线的工作原理，可 分析出d s p 芯片与乘法器的时序关系。 o 取指周期；一译码周期耷读数周期毒一执行周期一 幽；厂 厂 厂 厂 厂 b 1 h 1 ： 厂 厂 厂 厂 厂 卜一1 6 7 n s 叫 根据约定，b 1 h 3 时钟的上跳沿定义为流水线站的开始点，而b l h 3 时钟的 上跳沿至下一个上跳沿的时间定义为一个时钟周期。在流水线中，有些操作需要 执行一个时钟周期，有些操作需要半个时钟周期，即：在时钟b 1 h 3 为高时执行 操作，或在时钟b 1 h 1 为高时执行操作。芯片中的乘法器必须满足在一个时钟周 期内( 约1 6 7 n s ) 完成一次乘法运算，因而该乘法器是在“执行周期”内当b 1 h 3 为高电平时完成一组被乘数与乘数的乘法运算，而当b 1 h 1 为高电平时( 同为“执 行周期”) 将乘法结果输出。 该乘法器还有一个时钟信号c l k ( 如上图所示) ，它在乘法器进行自测试时 才使用。它是由b h 3 经一级二输入“与非”门和一级反相器形成的( 与非门的 另个输入端是由测试电路产生的测试信号，在测试情况下常为高) 。 上海大学硕士学位论文 2 2 数据格式 2 2 1d s p 芯片的数据格式 为了清楚地了解乘法器输入操作数的来源，需要知道d s p 芯片的数据格式。 在d s p 芯片中，数据组成有两种基本类型：整数类型( 包括有符号整数和无符 号整数) ，浮点数类型。d s p 芯片支持整数的短数据格式和单精度格式，也支持 浮点数的短数据格式、单精度格式和扩展精度格式。 当要求精度运算时，浮点运算是合适和无麻烦的运算格式。d s p 芯片可以以 整数运算速度实现浮点运算。浮点能力可以防止整数运算中的溢出问题、操作数 调整问题和其他通常超过整数运算能力的问题。下面将详细讨论d s p 芯片支持 的浮点数据格式。 1 浮点格式 浮点格式由三个区组成：阶码区( 指数区e ) 、一位符号区( s ) 和，j ：数区( f ) 。 其存放格式如图2 1 所示。 pf 一，目* 、l 图2 1 ：一般浮点格式 阶码区是二的补码数，符号区和小数区可以作为一个单元，称为尾数( m a n ) 区。尾数用来表示一个归一化的二的补码数。在归一化表示中，最大非符号有效 位是隐含表示的( 隐含位的位置总是紧靠小数点的左边一位) ，由此提供附加一 位的精度。浮点数x 作为e 、s 和f 区的函数可写为： x = 0 1 i x 2 。 若s = 0 ( 其中x 是正数，1 为隐含的最高有效非符号位) ： x = 1 0 f 2 。若s = l ( 其中x 是负数，0 为隐含的最高有效非符号位) ； x = 0 ( 浮点零) 若在给定指数区宽度中，p = 最大负数二的补码值，j = 0 ，厂= 0 。 d s p 芯片支持三种浮点数据格式。第一种是用于立即浮点操作数的短浮点格 式，由4 位阶码、1 位符号和1 1 位小数组成。第二种是单精度格式，由8 位阶码、 上海大学硕士学位论文 1 位符号和2 3 位小数组成。第三种是扩展精度格式，由8 位阶码、1 位符号和 3 1 位小数组成。 2 浮点格式间的转换 对于输入和输出，浮点运算有几种不同的格式，经常要从一种浮点格式转换 为另一种。格式转换作为浮点运算的部分，不再需要花费另外的时间而在硬件 中自动完成。当一个浮点格式零转换为较高精度格式时，它始终被转换为较高精 度格式中零的表示形式。在下面一些图中，s 一扩展符号位。 短浮点格式转换为单精度浮点格式：阶码区符号扩展，小数区充零。 3 12 8 2 72 4 2 32 21 21 1 0 短浮点格式转换为扩展精度浮点格式：阶码区符号扩展，小数区充零。 3 9 3 63 53 23 13 0 2 01 9 0 单精度浮点格式转换为扩展精度浮点格式：小数区充零。 3 9 3 23 13 08 70 扩展精度浮点格式转换为单精度浮点格式：将o 7 位的小数区截尾。 2 2 2 乘法器的数据格式 在d s p 芯片中，与乘法器相连接的数据总线有四组：c p u l 和c p u 2 总线， r e g i 和r e g 2 总线( 可提高系统的并行度) ，每组总线都是4 0 位 ，这四 组总线的数据经过选择作为操作数送入乘法器，因而进入乘法器中的操作数应该 是4 0 位。但乘法器只支持2 4 位整数( 包括有符号整数和无符号整数) 或3 2 位 单精度浮点数的乘法运算。 对于整数，若输入短整数，则将符号位扩展至2 4 位：若输入无符号短整数， 则将商位充零至2 4 位；若输入单精度整数，则只使用其o 2 3 位，而高位不使用 也不改变。对于浮点数，若输入短浮点数，则阶码区符号扩展，小数区充零：若 输入扩展精度浮点数，则将0 - 7 位的小数区截尾。这些转换都是在硬件中自动完 上海大学硕士学位论文 成而毋须花费更多的时间。所有乘法运算的结果都是以扩展精度格式输出。在乘 法器中，整数或浮点数在四组总线上所处位置的示意图如下： 图2 2 总线上的2 4 位整数操作数 图2 3 总线上的3 2 位单精度浮点操作数 可以看出：整数操作数放在四组总线的2 3 0 位，单精度浮点操作数放在3 9 8 位。其中单精度浮点操作数的尾数放在总线3 1 8 位，阶码放在总线3 9 3 2 位。在 进行整数相乘时，选择总线的2 3 0 位送入乘法阵列，而3 9 3 2 位对应的阶码部分 不使用也不改变；进行单精度浮点数乘法时，选择总线的3 1 8 位送入乘法阵列 作为尾数进行乘法运算，而3 9 3 2 位则送入阶码运算部件进行加法运算。 2 3 浮点运算 由于浮点d s p 芯片具有运算精度高、编程方便和高级语言易于实现等特点， 因而基于浮点数据格式的d s p 芯片得到了广泛的应用。为了高度有效地用硬件 实现浮点运算，d s p 芯片中浮点格式和i e e e 表示的标准浮点格式不同。 2 3 1i e e e 浮点数格式 i e e e 7 5 4 标准1 4 】定义了四种浮点数的格式，即单精度格式、扩展单精度格式、 双精度格式和扩展双精度格式。由于在数字信号处理系统中，单精度格式用得最 多，因此主要讨论i e e e 单精度浮点格式的表示方法。 i e e e 浮点格式： ! ! 塑! ! 。! ! 【一l e 格式中浮点数总长3 2 位。第位s 是尾数m 的符号位，s = 0 表示正数，s = 1 数 作操数 整 、10厂 0 2 孔 数作操点浮 ) d1；8 上海大学硕士学位论文 表示负数；接下8 位表示阶码e ，用无符号数表示，取值范围是0 2 5 5 ；再2 3 位表示小数部分f ，但在小数点左边隐含了一位最高有效位，因此实际上i e e e 单精度浮点数的尾数精度是2 4 位。i e e e 标准格式表示的浮点数值有五种情况： 若0 m ) 00 x ，一l 0000 o00 y 。一1 0 o 0 相加合并，并根据二进制补码加法运算的原则将超出符号位只。的进位舍去 得到如下向量行： 1 00 0 靠，l 0 0 y 0 0 f ff1 p m + n i p m 1p n 1p o 可以很明显的看出，通过对公式后两项的处理，b a u g h w o o l e y 算法产生的 所有部分积都是正的，因而仅需要使用0 类型全加器( 传统全加器) 就可以构成 阵列乘法器完成乘法运算( 如图3 2 所示) ，这点不同于p e z a r i s 算法。 上海大学硕士学位论文 下面用两个位数相同( 均为5 位) 的二进制补码数来说明b a u g h w o o l e y 算 法的操作过程。其运算矩阵最后两行是将1 1 0 0 0 a 。和1 1 0 0 0 b 4 相加 合并成l 0 0 0 o r 。d 4 ， 则矩阵运算过程如下：孟 丑1 | 芦工纠a q ： 目缸 划拉h l = 划 鼬虹a 2 b o 剑划a o b o 一一堑h u 堑蛆扯u a o b l 一锄址过鲤i 世 a o b 2 曾警0 、皇到鲥垒峨! 堕堕一一 鱼一虹姐3 丑2 b “纽1 h 刈2 d b 盘i 一一b 4i b 3 “ b 2 a 4 ：b l a 4 地a 4 型二二二二茳 盥旦旦回酗幽盥哩j 划到 相对p e z a r i s 算法，b a u g h - w o o l e y 算法具有以下优点：全部部分积的形成 由原先的与非门( n a n d ) ，与门( a n d ) 混合形成替换成仅由与门( a n d ) 形 成，这利于电路的实现；部分积的系数都是正的，因而仅需要使用一种类型的 全加器，这使得乘法阵列结构规整：算法中用到的五个特殊部分积x 。、x m - 1 、 y 。、y 。和1 都已包含到电路中，因而不会增加乘法器的附加电路延迟。但 b a u g h - w o o l e y 算法需要花费较多的时间进行求补运算，因而它与p e z a r i s 算法的 速度相当。 9 上海大学硕士学位论文 p e z a r i s 算法和b a u g h - w o o l e y 算法都可以并行地产生部分积，这极大地提高 乘法器的速度，但它们产生的部分积数目没有减少，这又在某种程度上限制了乘 法器速度的提高。 3 3 改进型b o o t h 算法8 】 上述几种算法都可以用来处理补码的乘法运算，但各有优缺点。相对而言， 下面将要讨论的改进型b o o t h 算法是一种较为理想的算法，因为该算法的最大优 点在于它不管乘数和被乘数的符号如何都可以用统一的步骤来完成乘法运算，而 无需对乘积作任何修正。 3 3 1 传统型b o o t h 算法1 9 二十世纪五十年代初，a 1 3 b o o t h 提出了传统型b o o t h 算法。当时他主要是 为了解决有符号数进行乘法运算时出现的符号修正问题而研究的，所以该算法对 于补码表示的两数相乘无需再进行符号位的修正，能自然得到乘积的正确符号， 并且对乘数的运算可以从乘数的任意一端开始。 传统型b o o t h 算法实际上就是补码一位乘法算法。该算法每次从乘数中交叠 地取两位( 。y ，) 来分析产生部分积p 只，其运算规则和取数操作过程分别见表 3 2 和图3 3 。 表3 2b 0 0 t h 算法规则 y i + ly pp i 操作 nn+ 0 上次部分积+ 0 ，右移一位 01+ x 上次部分积+ i x 】补，右移一位 10x 上次部分积+ 【x 】补，右移一位 11 o 上次部分积+ o ，右移一位 t士士土土土土士 图3 3b o o t h 算法取数操作 其中x 表示被乘数，y 表示乘数( 均假设为n 位二进制补码数) ，p p i 表示 部分积，而，一= 0 是附加考察位，帮助分析儿。从上述图表中可归纳出传统型 上海大学硕士学位论文 b o o t h 算法的运算过程：在乘数y 的最后附加一位考察位y i = o ：从乘数的 最低位y 0 开始，倒序每次取两位乘数( n ，y ，) ，根据表3 2 的规定完成相应的“相 加右移”操作；上述第步操作共进行( n + 1 ) 次，最后一次不移位，便可得 到乘积的补码。 对于两个n 位数相乘，传统型b o o t h 算法仍需要进行n 次移位和平均n 2 次加法( 考虑到实际只需作x 的运算) ，这阻碍了乘法器速度的提高。若将传 统型b o o t h