Booth 算法的16×16 并行乘法器_图文

《现代电子技术》 2003 年第 9 期总第 152 期

实战基地

采用 Booth 算法的 16×16 并行乘法器设计
刘 东
( 西南交通大学 计算机与通信工程学院 四川 成都 610031)

摘 要: 介绍了一种可以完成 16 位有符号 无符号二进制数乘法的乘法器。该乘法器采用了改进的 Boo th 算法, 简 化了部分积的符号扩展, 采用 W a llace 树和超前进位加法器来进一步提高电路的运算速度。 本乘法器可以作为嵌入式
CPU 内核的乘法单元, 整个设计用 V HDL 语言实现。

关键词: 乘法器; Boo th 算法; W a llace 树; 超前进位加法器 中图分类号: T P 30116     文献标识码: B      文章编号: 1004 373X ( 2003) 09 021 02

D es ign of Para llel M ult ipl ier for Borth A lgor ithm
LI U Dong
(Schoo l of Com p u ter & Comm un ication Engineering, Sou thw est J iao tong U n iversity, Chengdu, 610031, Ch ina)

Abstract: D escribes a 16 b it m u ltip lier1 It u ses m od ified Boo th a lgo rithm , W a llace T ree, 4 T h is design can be u sed in o ther A S IC design s1 Keywords: m u ltip lier; boo th a lgo rithm ; w a llace tree; the add ition w a re ca rried su rp a sses

2 com p resso r and 32 b it CLA 1

  在专用集成电路设计中, 面积小但功能强大的
CPU 内核可以为设计提供很大的方便。而乘法器又是 CPU 中一个重要的部件, 本文分析了设计乘法器所用

编码输出并行生成部分积。 生成所有部分积后需要对 部分积进行符号扩展以便进行相加, 然后用 W a llace 树形结构加法器将部分积相加得到 32 位乘法结果。

到的算法并提供了乘法器的设计方案。 乘法器的处理 过程大致相同, 都是先生成部分积再相加。 为了提高 乘法器的性能, 可以从减少部分积的个数, 对部分积 的相加采用并行加法。 采用 Boo th 算法[ 1 ] 可以使部分 积的个数减少一半[ 1 ] , 采用 W a llace 树行结构的加法 器完成 N 个部分积需要 lgN 次加法时间[ 2 ] , 最后再使 用超前进位加法器来减少加法运算中进位传播时 间[ 3 ]。本文设计的乘法器由 Boo th 编码、 W a llace 树形 结构和超前进位加法器 3 部分组成。
1 乘法器结构

本乘法器提供 16 位二进制有符号 无符号乘法运 算。 为了区分是有符号还是无符号数, 增加了 1 位即 第 17 位用于符号控制, 有符号则为 1, 无符号则为 0。 无符号数的范围是 0 ~ 216 - 1, 有符合的范围是- 215 ~
2 - 1。 乘法器的结构如图 1 所示。
15

图 1 乘法器结构

2 Booth 算法

在执行一次乘法运算时, 首先乘数和被乘数扩展
1 位符号控制位以判断是有符号数还是无符号数, 然

在乘法器设计中大都采用改进 Boo th 算法以减少 部分积, 简化电路和提高运算速度。 改进的 Boo th 算 法的原理如下: 设乘数:
n- 2

后用并行 Boo th 编码器对乘数进行编码, 根据 Boo th
收稿日期: 2003 02 12

Y = -

2

n- 1

Y n-

1

+

∑2 Y ,  Y
t t t= 0

- 1

= 0

( 1)

那么乘数 Y 也可以表示为:
21

? 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

刘 东: 采用 Boo th 算法的 16×16 并行乘法器设计
n 2- 1

Y =

∑ (Y
t= 0

2 t- 1

+ Y 2 t - 2Y 2 t+ 1 ) 22 t , Y -

1

= 0 ( 2)

其中 n 是偶数, 如果是奇数位的数则需要扩展 1 位。 根据式 ( 2) 可以知道部分积只有位数的一半, 而 且根据 Y 2 t- 1 , Y 2 t , Y 2 t+ 1 的不同, 与被乘数相乘得到的 部分积也不同。表 1 列出了不同的 Y 2 t- 1 , Y 2 t , Y 2 t+ 1 所 对应的对被乘数的操作。 表 1 Booth 编码操作列表
Y 2 t+ 1 Y 2t Y 2 t1

由于结果只有低 32 位有效, 所以计算符号扩展的 和只需要计算到低 32 位即可。 所以:
6 7 2 i+ 18

S =

∑2
i= 0

+ 217 +
5

∑s 2
i i= 0

2 i+ 17

7

= = =

∑s 2
i i= 2

2 i+ 17

+ + +

∑2
i= 0

2 i+ 20

+ s1 219 + 218 + ( 1 + s0 ) 217 + s1 219 + 218 + (s0 + s0 + s0 ) 217 + s1 219 + s0 219 + s0 218 + s0 217 ( 5)

7

5

对被乘数操作 ( 部分积) 部分积= 部分积= 部分积= 部分积= 部分积= 部分积= 部分积= 部分积= 被乘数×0 被乘数× ( + 被乘数× ( + 被乘数× ( + 被乘数× ( 被乘数× ( 被乘数× ( 被乘数×0
1) 1) 2) 2) 1) 1)


i= 2

si 2
i

2 i+ 17

∑2
i= 0

2 i+ 20

7

5 2 i+ 17

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

∑s 2
i= 2

∑2
i= 0

2 i+ 20

从式 ( 5) 可以看出, 对部分积进行符号扩展即将 17 位部分积的最高位 ( 符号扩展位) 取反, 再将符号位左 边 1 位置 ‘1’ , 还要在最后结果的第 17 位加上 1 个 ‘1’ 。
3  W a llace 树 W a llace 树算法是对部分积归约的一种树形算 法, 他利用 CSA (Ca rry Save A dder) 把 3 个部分积简

因为改进的 Boo th 算法要求乘数的位数为偶数, 所以应将乘数符号扩展 ( 乘数为负数是前面扩展 2 个 ) 到 18 位, 然后根据 Boo th 编 ‘1’ , 否则扩展 2 个‘0’ 码得到部分积, 得到部分积后需要对部分积进行相加。 由于操作数可以是有符号数也可以是无符号数, 所以 在相加过程中应该考虑到符号扩展以便正确相加。 由 于乘数扩展到 18 位, 所以产生的部分积有 9 项, 最后 一个部分积不需要符号扩展, 所以只需要扩展前面 8 个部分积且符号扩展值为 s i ( i= 0117) , 全部相加得到 结果是 34 位。 我们可以得到符号扩展的和 S 如下:
8 33
i t

化为 2 个部分积, 2 个 CSA 可以构成 1 个 4 2 压缩 器, 如图 2 所示。 我们用 CSA 和 4 2 压缩器构造过图 3 的 W a llace 树将部分积化简为 2 个 32 位的数, 再通 过 32 位超前进位加法器得到结果。

    S =
k

∑s ∑ 2
i= 0 t= 2 i+ 17

( 3)
图 2 4 2 压缩器结构图

将 s i = 1 - s i 和∑2 t = 2 j ( 2k + 1- j - 1) = 2k + 1 - 2 j 带
t= j

入式 ( 3) 可得:
8

S =

∑ (1 i= 0

si ) (2 - 2
8

33

2 i+ 17

)
8

8

= 8 23 -


i= 0

si 2 8

34


i= 0 i

22 i+ 17 +
8

∑s 2
i i= 0

2 i+ 17

7 2 i+ 17

= 7 233 + 233 = 7 233 + si 233 7

∑s 2
i= 0

33

-

∑2
i= 0

+ s i 233 + 22 i+ 17 +

∑s 2
i i= 0

2 i+ 17

8

8

7


i= 0

si 2 + 2 7

33

33


i= 0

∑s 2
i i= 0

2 i+ 17

16

7

= 7 233 = 7 2 7 33


i= 0

si 2 +
i

33


i= 0

22 i+ 18 +
2 i+ 18


i= 0

2i + 1 +
7

∑s 2
i i= 0

2 i+ 17

7

7 33

∑s 2
i= 0

+
32

∑2
i= 0

+ 2 +

17

∑s 2
i i= 0

2 i+ 17

6

7

= (7 22


i= 0

si ) 2 + 2 +

33


i= 0

22 i+ 18 + 217 +

∑s 2
i i= 0

2 i+ 17

( 4)

图 3  W a llace 树

( 下转第 25 页)  

? 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

《现代电子技术》 2003 年第 9 期总第 152 期 测量 V s 改变前后的输出电压 V o1 和 V o2 , 测 5 个数据, 组成 4 组, 电压调整率为 V o1 - V o2 V o1 ×100% 。 从表 1 所得到的数据可以算出该稳压电源的电压 调整率为: ( 01009% + 01018% + 0+ 01018% ) 4= 01011% V 表 2 输出电压负载调整率
V o1 V V o2 V

实战基地
( 2117% + 2159% + 1161% + 2103% ) 4= 2110% V 413 开关电源波形测试

用示波器观察输出电压 V o 的波形图如图 3 所示。
5 结 语

负载调整率
2117% 2159% 1161% 2103%

11105 10181 10153 10136

10181 10153 10136 10115

本文利用集成芯片 U C3842 设计的电流制型脉宽 调制开关稳压电源克服了电压控制型脉宽调制开关稳 压电源频响慢、 电压调整率和负载调整率低的缺点, 电 路结构简单, 成本低、 体积小、 易实现。 该稳压电源 是目前实用和理想的稳压电源, 具有很大的发展前景。 参 考 文 献
[ 1 ]  王兆安, 黄俊 1 电力电子技术 [M ] 1 北京: 机

412 负载调整率 ( 抗负载波动能力) 测试

将 R P3 左旋到底, 用万用表测量输出电压 V o1 , 再 将 R P 3 右旋, 测量输出电压 V o2 , 测 5 个数据, 组成 4 组, 则负载调整率为 V o1 - V o2 V o1 ×100% 。 从表 2 所得到的数据可以算出该稳压电源的负载 调整率为:

械工业出版社, 20021 [ 2 ]   [ 美 ] 戈特利布 IM 1 稳压电源 [M ] 1 北京: 科 学出版社, 19931

作者简介 朱俊林 1967 年出生, 大学本科, 工程师。 主要研究方向为电力电子传动。 刘细平 1976 年出生, 控制理论与控制工程研究生, 助教。 研究方向为电力电子传动, 计算机智能监控。 许伦辉 1965 年出生, 教授, 博士。 主要研究方向为计算机智能监控, 智能交通等。

( 上接第 22 页) 4 结 论 save adder t rees in m u lt ip liers [D ] 1 U RL h t tp: elec eng r 1ok sta te 1edu lg john 6263 lectu res m u lt ree 1p df, N ovem ber 19991 [3]   W a llace C S 1 A suggest ion fo r a fa st m u lt ip lier T ran sact ion s on E lect ron ic Com p u ters, 1964, 13 ( 2) : 14 171 [ 4 ]  D avid D ahan 117 × 17 b it h igh p erfo rm ance 1 fu lly syn thesizab le [ 5 ]  V o jin G, O k lobdzija 1Genera l da ta p a th o rga n iza t ion of A M A C U n it fo r VL S I i m p lem en ta t ion of D SP p rocesso rs [ S ] 1 F ina l R epo rt, 1997 ~ 98 fo r M ICRO P ro ject 97 1291 [ 6 ]  葛亮, 唐志敏 1 一种支持无符号数的流水线乘 法器 [J ] 1 微电子学与计算机, 2002, ( 10) : 17 191 Jou rna l of [J ] 1 IEEE

该乘法器用 V HDL 语言实现整个设计, 实现乘法 器用到的门数为 4 942 门。 本乘法器所采用的改进
Boo th 算法和 W a llace 数化简部分积也是设计高性能 CPU 通常采用的方法, 可以完成 16×16 无符号 有符

号数的乘法运算, 整个设计简单高效。 还可以将乘法 部件应用到其他设计中去。 参 考 文 献
[ 1 ]  Boo th A D 1 A signed b ina ry m u lt ip lica t ion techn ique [ J ] 1 Q ua rterly M echan ics and A pp lied M a them a t ics, 1951, 4 ( 2) : 236 2401 [ 2 ]   ECEN 6263 A dvanced VL S I D esign 1 Ca rry

作者简介 刘 东 男, 1978 年出生, 四川绵阳人, 硕士。 研究方向为专用集成电路设计。

25
? 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.


相关文档

采用Booth算法的16×16并行乘法器设计
采用Booth算法的16_16并行乘法器设计_刘东
一种新的Booth乘法器设计方法
16×16位高速低功耗并行乘法器的实现
booth算法(乘法器)
16位booth流水线乘法器设计
第十六章 并行算法
基于booth算法的4位乘法器
并行算法实现乘法器中期报告
四位并行乘法器
电脑版