Video在线视频

接下来我们开始说乘法器

我们知道乘法器实际上是由加法器组成的

这是乘法器的表达式

这里的X是个M位无符号二进制数

X可以表达为这个

Y是个N位二进制数

表达式是这个

Z是X和Y的积

Z是个M+N位二进制数

Z=X*Y，等于这个

这是基础数学的内容

你可以看到

X是被乘数，Y是乘数

X是1011，Y是1111.

我们从这里开始计算，1乘1等于1

1乘1等于1,1乘0等于0

1乘1等于1.

还有这个

这有这个

这叫部分积

在产生部分积之后

我们要把部分积累加起来

就像这样

1+1等于0，进位是1.

我们需要产生部分积、

累加部分积和最终相加

从这里你可以看到

实际上被乘数是被按顺序

进行与、移位然后累加

你可以看到

这比加法器复杂

这需要用硬件实现

如果我们只用软件实现这个

性能会很差

而且能耗会非常高

这是基于RCA的乘法器

行波进位加法器

你能看到这种乘法器的基本原理

以及它的基本结构

这里包括了操作单元

全加器

以及半加器

半加器只有两个输入

输入A，输入B和两个输出，和以及进位

半加器并没有进位的输入

所以这里我们可以看到结构中有全加器

全加器、以及两个半加器，这一级深度是n-1

这一级是是n-2，这是m

这是n乘n乘法器

由n个半加器组成的

例如这里

我们有1,2,3,4,4个半加器

n乘n减2个全加器

和n平方个与门

如果这是m*n乘法器

这由n个半加器组成

而且m*n-m-n个全加器

m乘n个与门

你们可以自己数

这是n-1，这是n-2，这是m

这张胶片告诉我们

怎么计算基于RCA的乘法器的关键路径

你可以看到这是进位传播

这是“和”传播

我们实际上有几条关键路径

例如这个

这是关键路径

这是进位传播路径1

这是“和“传播路径

还有这个

所以这里有几条关键路径

所以基于逐位进位

加法器的4*4乘法器

这个的延时是(M-1+N-2）*tcarry

这个代表进位传播时间

还有这个，（N-1）乘以tsum

这代表“和“的传播时间

最后还要加上tand

这与加法器是不一样的

在加法器中

只有tcarry乘以位数

然而在乘法器中

tsum也要乘以位数

所以tcarry和tsum都很重要

所以乘法器的设计技巧是

保证每个单元的“和”与进位的延时是一样的

这非常重要

还记得我上一堂课

介绍过的电路图吗？

我说过这是

基于传输门的全加器

它的特性是进位延迟和

“和”延迟是一样的

对于乘法器的实现来说

这是非常重要的优点

这是进位保留乘法器

我们实际上将这个的进位输出传输到这个

而不是这里的半加器

所以这个全加器的进位输出

可以被传输到这个全加器

这叫做进位保留乘法器

因此我们可以得到短得多的关键路径

代价只是稍微增加一些面积

因为最终我们需要一个合并加法器

来把进位输出和所有的“和”合并在一起

这条路径的延迟等于（N-1）*tcarry

加上tand，和合并加法器的延时

这是进位保留乘法器

接下来，我们怎么加速乘法过程？

因此我将介绍

改进过的基4booth乘法器

RCA乘法器的副作用是

部分积的累加操作太多了

导致其需要一个很大的加法器阵列

解决方法是

我们可以减少部分积的数量

这样我们可以提高性能

基本想法是

我们不产生所有的部分积

例如我们知道0乘X等于0

1乘X等于X对吧？

我么可以通过将乘数2位

合并的方式来减少部分积

例如00等于0,01等于1

10意味着这个要乘以2

在二进制中这意味着这要左移1位对吧？

11代表3,3可以理解为4减1.

根据这个想法

我们可以得到改进过的

基4booth乘法器的编码规则

我们将y-1=0增加到LSB

LSB是最低位

我们可以将符号位拓展到偶数字长

这是MSB扩展

从LSB开始分成三位一组

彼此之间有1位重叠

接下来将每一组编码为yi-1 + yi – 2yi+1

这张胶片告诉我们编码规则的细节

LSB扩展法则

我们需要向乘数的LSB增加一个观察位（y-1=0）

还有MSB拓展法则

我们有两种情况

第一种情况，如果位数是偶数

需要将MSB扩展两位

第二种情况

如果位数是奇数，MSB需要扩展1位

最后我们得到了偶数位长

如果是有符号数

等于符号位

如果是无符号位

这两位等于0.

对这也是类似的

对于有符号数这一位等于符号位

对于无符号数这一位等于0.

因此我们可以观察并对各位进行分类

首先观察yi+1 yi yi-1

yi-1是观察位

然后观察这个

此时yi+1是观察位

这是对编码规则的总结

在拓展和分组之后

开始从最低位开始对每3位进行编码

这里你可以看到

我们有000、001直到111.

根据编码法则

yi-1 + yi -2*yi+1

最终得到了这个

这是0

这个加这个减去二倍这个

这是0.

这是+X

根据这个

这也是X对吧？

例如这个

这个加上这个减2乘以X等于-2X

根据编码法则我们有这张表

我们怎么证明如果我们

按照编码法则计算

我们可以得到相同的结果？

我来给你们证明

例如是无符号

二进制数的位数n是偶数

X乘以Y，Y是乘数

Y等于y(n-1)y（n-2）……y(2)y(1)y(0)

X乘以Y等于这个对吧

这里我们可以将y(n-1)加上y(n)

减去两倍y(n+1)

假设这个等于0

这个等于0，这个等于0.

这个乘以2的0次方

2的2次方、2的4次方

LSB扩展一位y(-1)，它等于0

这个表示符号位扩展

向最高位进行符号位扩展

我们知道这个等于4的0次方

这是4的1次方

4的2次方

所以这是基4的

我们证明了这和之前

X*Y的结果是一样的

如果无符号数的位数n是奇数

证明还是成立的

X*Y等于这个

这也是基-4的

我们可以证明像这样的扩展是正确的

编码法则也是正确的

对2补码也是类似的

这两个例子讲的

是无符号二进制数

如果考虑的是2补码，它也是正确的

因此改进过的基4booth乘法器

可以用这个表示

我来给你们看个例子

这是改进过的

基4booth乘法器的例子

如果把10011010考虑为无符号数

我们怎么根据编码法则来进行编码？

首先我们增加LSB，这等于0.

在最高位我们增加两个0.

然后我们将数字每3个分成一组

接下来根据编码法则

y(i-1) + y(i) - 2 * y(i+1)

然后这个等于-2X

可以表达为(bar 1,0)

这是-X对吧

这个等于(0, bar 1).

然后2X，(1,0)，然后-2X，(bar 1,0)

还有X，(0,1).

这是假设为无符号二进制数的情况

如果这是有符号数

我们仍然

向最低位扩展0

对于符号位，我们扩展两位

这是1，这也是1.

我们每3为分组

最后我们可以得到所有的部分积

这是乘法过程的例子

如果X等于这个，1101，Y等于1001

这是4位乘4位，等于8位对吧？

如果X和Y是无符号二进制数

因此都是正数

所以在十进制中X等于13

Y等于9,13*7等于117对吧？

乘数Y等于1001

我们在这增加0

因为这是无符号数

所以我们向MSB增加两个0.

根据编码法则

我们发现这个等于+X

这个等于这个加上这个减去两倍这个

等于-2X

这个等于+X

所以这里是X

这里是0

还有-2X，我们怎么实现-2X？

我们可以左移一位

然后对各位取反

然后再加1

左移之后的右边空余位取0.

所以这里是100110

代表-2X

这里是X

之后我们可以累加部分和

最终我们得到了117.

对2补码也是类似的

如果X和Y是2补码，就是负数

因此X等于-3

Y等于-7，X乘以Y等于21.

在这种情况下

LSB扩展是0

Y MSB扩展是11.

这个计算出来是+X

这是-2X

经过化简和累加

我们把部分积加起来

最终结果等于21.

基4的优点是

部分积的数量少了一半

而且可以计算无符号二进制数

也可以计算2补码

缺点是如果改进过的基4booth乘法器

不止有0和X

还需要译码+2X、-2X和-X

我来给你们出道思考题

X等于1010，Y等于0111

如果X和Y是2补码

请用改进过的基-4

booth乘法器计算X*Y

如果X和Y是无符号数

请用改进过的基-4 booth乘法器计算X*Y

我来总结一下乘法器

优化的目标和二进制加法器不同

我们不仅仅需要优化进位链

还需要优化乘法器中的

求和电路

然而在二进制加法器中

我们只需要优化进位链对吧？

再强调一次，要找到关键路径

我们需要先找到关键路径

还有其它一些可用的优化技术

例如数据编码，booth数据编码

这是我们第一次接触

系统级的优化方法