计算机算法和算法逻辑实现-课件

计算机组成原理第六-八讲计算机算法和算法逻辑实现

计算机组成原理第六-八讲计算机算法和算法逻辑实现1、定点数加减法运算及电路实现 补码的加减法运算，全加器，溢出，快速加法运算（进位链），74181ALU2、定点数乘除运算和电路实现 原码、补码，布斯算法，原码恢复余数、不恢复余数3、快速乘除法运算技术和电路实现 布斯高基乘法，阵列乘法器，阵列除法器4、浮点数四则运算以及实现 加减乘除本讲安排1、定点数加减法运算及电路实现本讲安排本讲将解决的主要问题掌握计算机算法。加减乘除运算方法和运算器的构成，原码和补码的加减乘除四则运算，浮点数的四则运算。

本讲将解决的主要问题掌握计算机算法。补码加、减法溢出概念与检测方法基本的二进制加法/减法器十进制加法器补码加、减法溢出概念与检测方法基本的二进制加法/减法器十进制加法规则：先判符号位，若相同，绝对值相加，结果符号不变;若不同，则作减法，|大|-|小|，结果符号与|大|相同。减法规则：两个原码表示的数相减，首先将减数符号取反，然后将被减数与符号取反后的减数按原码加法进行运算。补码加法1.原码加/减法运算加法规则：补码加法1.原码加/减法运算补码加法的公式:[x]补＋[y]补＝[x＋y]补(mod2)

在模2意义下,任意两数的补码之和等于该两数之和的补码。这是补码加法的理论基础。2.补码加法运算特点：不需要事先判断符号，符号位与码值位一起参加运算。符号位相加后若有进位，则舍去该进位数字。补码加法的公式:[x]补＋[y]补＝[x＋y]补

假设采用定点小数表示,因此证明的先决条件是:

︱x︱﹤1,︱y︱﹤1,︱x＋y︱﹤1。(1)x﹥0,y﹥0,则x＋y﹥0。

相加两数都是正数,故其和也一定是正数。正数的补码和原码是一样的,可得：

[x]补＋[y]补＝x＋y＝[x＋y]补

(mod2)公式证明:假设采用定点小数表示,因此证明的先决条件是:(1)(2)x﹥0,y﹤0,则x＋y>0或x＋y<0。相加的两数一个为正,一个为负,因此相加结果有正、负两种可能。根据补码定义，

∵[x]补＝x,

[y]补＝2＋y

∴[x]补＋[y]补＝x＋2＋y＝2＋(x＋y)

当x+y>0时,2+(x+y)>2,进位2必丢失,又因(x+y)>0，故[x]补＋[y]补＝x＋y＝[x＋y]补

(mod2)

当x＋y<0时,2＋(x＋y)<2,又因(x+y)<0，故

[x]补＋[y]补＝2＋(x＋y)＝[x＋y]补

(mod2)(2)x﹥0,y﹤0,则x＋y>0(3)x<0,y>0,则x＋y>0或x＋y<0。同(2),把x和y的位置对调即可。(4)x<0,y<0,则x＋y<0。相加两数都是负数,则其和也一定是负数。∵[x]补＝2＋x,

[y]补＝2＋y∴[x]补＋[y]补＝2＋x＋2＋y＝2＋(2＋x＋y)

因为|x＋y|<1,1<(2＋x＋y)<2,2＋(2＋x＋y)进位2

必丢失，又因x+y<0

故[x]补＋[y]补＝2＋(x＋y)＝[x＋y]补

(mod2)(3)x<0,y>0,则x＋y>0或x＋

至此证明了在模2意义下，任意两数的补码之和等于该两数之和的补码。

其结论也适用于定点整数。补码加法的特点：

（1）符号位要作为数的一部分一起参加运算；（2）在模2的意义下相加，即大于2的进位要丢掉。结论：至此证明了在模2意义下，任意两数的补码之和等于该两数之例:

x＝0.1001,y＝0.0101,求x＋y。解:

[x]补＝0.1001,[y]补＝0.0101[x]补

0.1001

＋[y]补

0.0101

[x＋y]补

0.1110

所以x＋y＝＋0.1110例:

x＝＋0.1011,y＝－0.0101,求x＋y。所以x＋y＝0.0110解:

[x]补＝0.1011,

[y]补＝1.1011[x]补

0.1011＋[y]补

1.1011

[x＋y]补

10.0110

例:x＝0.1001,y＝0.0101,求x＋补码减法减法运算要设法化为加法完成补码减法运算的公式：

[x－y]补＝[x]补－[y]补＝[x]补＋[－y]补公式证明：只要证明[–y]补＝–[y]补,上式即得证。∵[x＋y]补＝[x]补＋[y]补

(mod2)

令y=－x∴[0]补＝[x]补+[－

x]补

故[－x]补＝－[x]补(mod2)

证明：补码减法减法运算要设法化为加法完成例:

x＝＋0.1101,y＝＋0.0110,求x－y。解:

[x]补＝0.1101

[y]补＝0.0110,

[－y]补＝1.1010[x]补

0.1101

＋[－y]补

1.1010

[x－y]补

10.0111

x－y＝＋0.0111解：[x]补=1.0011[y]补=1.1010[-y]补=0.0110

[x]补

1.0011+[-y]补

0.0110[x-y]补

1.1001

例：x=-0.1101，y=-0.0110，求x-y=?∴x--y=-0.0111例:x＝＋0.1101,y＝＋0.0110,求

溢出及与检测方法

在定点小数机器中,数的表示范围为|ｘ|<1。在运算过程中如出现大于1的现象,称为“溢出”。机器定点小数表示上溢下溢1.概念溢出及与检测方法在定点小数机器中,数的表示范围为|ｘ

解：

[x]补=0.1011

[y]补=0.1001

[x]补

0.1011

+

[y]补

0.1001

[x+y]补

1.0100

两个正数相加的结果成为负数，这显然是错误的。例:x=+0.1011,y=+0.1001,求x+y。

例:x=-0.1101,y=-0.1011,求x+y。解：

[x]补=1.0011

[y]补=1.0101

[x]补

1.0011

+

[y]补

1.0101

[x+y]补

0.1000

两个负数相加的结果成为正数，这同样是错误的。

解：

[x]补=0.1011

发生错误的原因，是因为运算结果产生了溢出。两个正数相加:结果大于机器所能表示的最大正数，称为上溢；两个负数相加：结果小于机器所能表示的最小负数，称为下溢。机器定点小数表示上溢下溢[分析]：发生错误的原因，是因为运算结果产生了溢出。机器定2.溢出的检测方法

[x]补

0.1011

+

[y]补

0.1001

[x+y]补

1.0100

[x]补

1.0011

+

[y]补

1.0101

[x+y]补

0.1000溢出逻辑表达式为：

V＝S1S2Sc+S1S2Sc(1)单符号位法FAVz0y0x0判断电路判断电路2.溢出的检测方法

[x]补

0.1

一个符号位只能表示正、负两种情况，当产生溢出时，符号位的含义就会发生混乱。如果将符号位扩充为两位(Sf1、Sf2)，其所能表示的信息量将随之扩大，既能判别是否溢出，又能指出结果的符号。

(2)双符号位法双符号位法也称为“变形补码”或“模4补码”。变形补码定义：[x]补=x0

x<24+x-2x<0

（mod4)一个符号位只能表示正、负两种情况，当产生溢出时，

•

任何小于1的正数：两个符号位都是“0”，即00.x1x2...xn;

•

任何大于-1的负数：两个符号位都是“1”，即11.x1x2…xn

两数变形补码之和等于两数和的变形补码，要求：

•

两个符号位都看做数码一样参加运算；

•

两数进行以4为模的加法，即最高符号位上产生的进位要丢掉模4补码加法公式：

[x]补+[y]补=[x+y]补

（mod4)采用变形补码后数的表示：•任何小于1的正数：两个符号位都是“0”，即00.Sf1Sf2

＝00结果为正数，无溢出

01结果正溢

10结果负溢

11结果为负数，无溢出即：结果的两个符号位的代码不一致时，表示溢出;

两个符号位的代码一致时，表示没有溢出。

不管溢出与否，最高符号位永远表示结果的正确符号。溢出逻辑表达式为：

V＝Sf1⊕Sf2

中Sf1和Sf2分别为最高符号位和第二符号位，此逻辑表达式可用异或门实现。双符号位的含义如下：Sf1Sf2＝00结果为正

解：

[x]补=00.1100

[y]补=00.1000

[x]补

00.1100

+

[y]补

00.1000

01.0100

符号位出现“01”，表示已溢出，正溢。即结果大于+1例

x=+0.1100,y=+0.1000,求x+y。

解：

[x]补=11.0100

[y]补=11.1000

[x]补

11.0100

+

[y]补

11.1000

10.1100符号位出现“10”，表示已溢出，负溢出。即结果小于-1例

x=-0.1100,y=-0.1000,求x+y。

解：

[x]补=00.1100

从上面例中看到：当最高有效位有进位而符号位无进位时,产生上溢；当最高有效位无进位而符号位有进位时,产生下溢。（简单地说是正数相加为负数或负数相加为正数则产生溢出）故溢出逻辑表达式为：V＝Cf⊕Co

其中Cf为符号位产生的进位,Co为最高有效位产生的进位。此逻辑表达式也可用异或门实现。(3)利用进位值的判别法[x]补

00.1100+[y]补

00.1000

01.1000[x]补

11.0100+[y]补

11.1000

10.1100从上面例中看到：(3)利用进位值的判别法[x]补

0FAFAz1z0Vc1c0y1x1y0x0FAFAVz1c0c1z0x1y1y0x0V＝C1⊕Co

V＝Sf1⊕Sf2判断电路FAFAz1z0Vc1c0y1x1y0x0FAFAVz1c0基本的二进制加法/减法器加法运算：Ai+Bi+Ci=Si(Ci+1)加数进位输入和进位输出一位全加器真值表输入输出AiBiCiSiCi＋10000000110010100110110010101011100111111逻辑方程Si＝Ai⊕Bi⊕CiCi＋1＝AiBi＋BiCi＋CiAi1.一位全加器基本的二进制加法/减法器加法运算：Ai+Bi逻辑方程Si＝Ai⊕Bi⊕CiCi＋1=AiBi＋BiCi＋CiAiCi=AiBi+(AiBi)Ci-1逻辑电路（一位全加器）常用的全加器逻辑电路FACi+1CiSiAiBi逻辑符号逻辑方程Si＝Ai⊕Bi⊕CiCi＋1=AiBi＋BiCi2.n位的行波进位加减器n个1位的全加器(FA)可级联成一个n位的行波进位加减器。2.n位的行波进位加减器n个1位的全加器(FA)T被定义为相应于单级逻辑电路的单位门延迟。

T通常采用一个“与非”门或一个“或非”门的时间延迟来作为度量单位。3TXNOR异或非3TXOT异或2TOR或2TAND与TNOT非TNOR或非TNAND与非时间延迟逻辑符号（正逻辑）门的功能门的名称典型门电路的逻辑符号和延迟时间接线逻辑(与或非)AOIT+TRC3.n位的行波进位加法器的问题时间延迟T被定义为相应于单级逻辑电路的单位门延迟。3TXN(1)对一位全加器(FA)来说，Si的时间延迟为6T(每级异或门延迟3T)；Ci＋1的时间延迟为5T。3T3TTT(1)对一位全加器(FA)来说，Si的时间延迟为6T(每级3(2)n位行波进位加法器的延迟时间ta为:

•9T为最低位上的两极“异或”门再加上溢出“异或”门的总时间；

•2T为每级进位链的延迟时间。ta＝n·2T＋9T＝(2n＋9)T考虑溢出检测时，有：当不考虑溢出检测时，有：ta＝(n-1)·2T＋9T

ta为在加法器的输入端输入加数和被加数后,在最坏的情况下加法器输出端得到稳定的求和输出所需要的最长时间。

ta越小越好。(2)n位行波进位加法器的延迟时间ta为:•9T为最缺点：(1)串行进位,它的运算时间长；(2)只能完成加法和减法两种操作而不能完成逻辑操作。多功能算术/逻辑运算单元(ALU):

不仅具有多种算术运算和逻辑运算的功能；而且具有先行进位逻辑。从而能实现高速运算。由一位全加器(FA)构成的行波进位加法器:缺点：由一位全加器(FA)构成的行波进位加法器:1.基本思想Si＝Ai⊕Bi⊕Ci一位全加器(FA)的逻辑表达式为:将Ai和Bi先组合成由控制参数S0,S1,S2,S3控制的组合函数Xi和Yi；(2)然后再将Xi,Yi和下一位进位数通过全加器进行全加。这样,不同的控制参数可以得到不同的组合函数,因而能够实现多种算术运算和逻辑运算。解决方案：

多功能算术/逻辑运算单元(ALU)将全加器的功能扩展以完成多种算术逻辑运算。Ci＋1=AiBi·(Ci·(Ai⊕Bi))=AiBi＋BiCi＋CiAi1.基本思想Si＝Ai⊕Bi⊕Ci一位全加器(FA)的逻辑表S0S1S2S3X0Y0

参数S0,S1,S2,S3

分别控制输入Ai

和Bi

,产生Y和X的函数。其中：Yi是受S0,S1控制的Ai和Bi的组合函数；Xi是受S2

,S3控制的Ai和Bi组合函数。

函数关系如表所示。Xi＝S2S3＋S2S3(Ai＋Bi)＋S2S3(Ai＋Bi)＋S2S3Ai

Yi＝S0S1Ai＋S0S1AiBi＋S0S1AiBi•

核心部分是由两个半加器组成的全加器。•

由M控制第二级半加器选择逻辑运算或算术运算（所需的低位进位Cn

）。一位ALU基本逻辑电路S0S1S2S3X0Y0参数S0,S1,S2,S3S0S1

Yi

S2S3

Xi

0

0

0

1

1

0

1

1Ai

AiBi

AiBi

00

0

0

1

1

0

1

11

Ai＋Bi

Ai＋Bi

Ai

进一步化简:Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1BiAi+S0Bi+S1BiS3AiBi+S2AiBiXiYi==Yi

Fi＝Yi⊕Xi⊕Cn+iCn＋i＋1＝Yi＋XiCn＋iS0S1YiS2S3Xi00

01

10

综上所述，ALU的一位逻辑表达式为：Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1Bi

Fi＝Yi⊕Xi⊕Cn+iCn＋i＋1＝Yi＋XiCn＋i综上所述，ALU的一位逻辑表达式为：Xi=S3AiBi4位之间采用先行进位（并行进位）公式。根据Cn＋i＋1＝Yi＋XiCn＋i，每一位的进位公式可递推如下：

•

第0位向第1位的进位公式为:

Cn＋1＝Y0＋X0Cn

(其中Cn是向第0位（末位）的进位)

•

第1位向第2位的进位公式为:

Cn＋2＝Y1＋X1Cn＋1＝Y1＋Y0X1＋X0X1Cn

•

第2位向第3位的进位公式为:

Cn＋3＝Y2＋X2Cn＋2＝Y2＋Y1X1＋Y0X1X2＋X0X1X2Cn•

第3位的进位输出（即整个4位运算进位输出）公式为:

Cn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn4位ALU的进位关系及逻辑电路4位之间采用先行进位（并行进位）公式。4位ALU的进位关系Cn＋1＝Y0＋X0CnCn＋2＝Y1＋X1Cn＋1＝Y1＋Y0X1＋X0X1Cn

Cn＋3＝Y2＋X2Cn＋2＝Y2＋Y1X1＋Y0X1X2＋X0X1X2CnCn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn

Cn+4是最后进位输出。逻辑表达式表明,这是一个先行进位逻辑。换句话说,第0位的进位输入Cn可以直接传送到最高位上去,因而可以实现高速运算。下图为用上述原始推导公式实现的4位算术/逻辑运算单元(ALU)

——74181ALU从进位关系上看Cn＋1＝Y0＋X0Cn从进位关系上看X0Y0X1Y1X2Y2X3Y3

正逻辑表示的74181X0Y0X1Y1X2Y2X3

第3位的进位输出（即整个4位运算进位输出）公式为:

Cn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn设G＝Y3＋Y2X3＋Y1X2X3＋Y0X1X2X3

P＝X0X1X2X3

则

Cn＋4＝G＋PCn

其中G称为进位发生输出,P称为进位传送输出。在电路中多加这两个进位输出的目的,是为了便于实现多片（组）ALU之间的先行进位。P和G的含义第3位的进位输出（即整个4位运算进位输出）公式为:P和G的负逻辑表示的74181X0Y0X1Y1X2Y2X3Y3负逻辑表示的74181X0Y0X1Y1X2

2.算术逻辑运算的实现上图中控制端Ｍ用来控制ALU进行算术运算还是进行逻辑运算:Ｍ＝0时：

Ｍ对进位信号没有任何影响。此时Fi

不仅与本位的被操作数Yi和操作数Xi

有关,而且与向本位的进位值Cn+i

有关,因此Ｍ＝0时,进行算术操作。

Ｍ＝1时：

封锁了各位的进位输出,即Cn+i

＝0,因此各位的运算结果Fi

仅与Yi

和Xi

有关,故Ｍ＝1时,进行逻辑操作。2.算术逻辑运算的实现上图中控制端Ｍ用来控制ALU进行算术下图为工作于负逻辑和正逻辑操作方式的74181ALU方框图。两种操作是等效的。•

对正逻辑操作数来说：

算术运算称高电平操作；逻辑运算称正逻辑操作

(即高电平为“1”,低电平为“0”)。•

对于负逻辑操作数来说:

正好相反。下图为工作于负逻辑和正逻辑操作方式的74181ALU方框图。AA+BA+B减1A加AB（A+B）加ABA减B减1AB减1A加ABA加B（A+B）加ABAB减1A加A*（A+B）加A（A+B）加AA减1AA+BAB逻辑0ABBABABA+BABBAB逻辑1A+BA+BA

A减1AB减1

AB减1

减1A加（A+B）AB加（A+B）A减B减1A+BA加（A+B）A加BAB加（A+B）A+BA加A*AB加AAB加AA

AAB

A+B

逻辑1

A+BB

ABA+B

ABAB

BA+B

逻辑0AB

ABALLLLLLLHLLHLLLHHLHLLLHLHLHHLLHHHHLLLHLLHHLHLHLHHHHLLHHLHHHHLHHHH算术运算M=LCn=H逻辑M=H算术运算M=LCn=L逻辑M=H正逻辑输入与输出负逻辑输入与输出工作方式选择输入S3S2S1S0

AAA减1AL(1)H＝高电平,L＝低电平；(2)*表示每一位均移到下一个更高位,即A*＝2A。(3)

算术运算操作是用补码表示法来表示的，其中：

“加”是指算术加，运算时要考虑进位；符号“＋”是指“逻辑加”。(4)

减法是用补码方法进行的，其中数的反码是内部产生的,而结果输出“A减B减1”，因此做减法时需在最末位产生一个强迫进位(加1),以便产生“A减B”的结果。(5)

“A＝B”输出端可指示两个数是否相等；(1)H＝高电平,L＝低电平；3.并行加法器的进位逻辑74181ALU为4位并行加法器，组成16位的并行加法器——怎么办？

4片(组)74181连接——怎样连？

•

组与组之间串行连接

•

组与组之间并行连接3.并行加法器的进位逻辑74181ALU为4位并行加法器组间串行进位C4＝G0＋P0C0C8＝G1＋P1C4C12＝G2＋P2C8C16＝G3＋P3C12进位关系Cn＋1＝Y0＋X0CnCn＋2＝Y1＋X1Cn＋1＝Y1＋Y0X1＋X0X1Cn

Cn＋3＝Y2＋X2Cn＋2＝Y2＋Y1X1＋Y0X1X2＋X0X1X2CnCn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn组内组间X0Y0X1Y1X2Y2X3Y3X0Y0X1Y1X2Y2X3Y3C4C8C4C00011G＝Y3＋Y2X3＋Y1X2X3＋Y0X1X2X3

P＝X0X1X2X3组间串行进位C4＝G0＋P0C0C8＝G1＋P1C4C1第1组4-1位并行进位X3Y3X2Y1X1Y1X0Y0C4C3C2C1第2组8-5位并行进位X7Y7X6Y6X5Y5X4Y4C8C7C6C5第3组12-9位并行进位X11Y11X10Y10X9Y9X8Y8C12C11C10C9第4组16-13位并行进位X15Y15X14Y14X13Y13X12Y12C16C15C14C13进位传递时间C16C12C8C4C01.534.56tyC1CC16C12C8C4C01.534.57tyC1C5.589.5第1组X3Y3X2Y1X1Y1X0Y0C4C3C2C1第2组(2)组间并行进位——两级先行进位的ALU由串行进位关系C8=G1＋P1C4=G1+P1(G0＋P0C0)=G1+G0P1+P0P1C0得：C4＝G0＋P0C0C8＝G1＋P1C4C12＝G2＋P2C8C16＝G3＋P3C12C4=G0＋P0C0C12=G2＋P2C8=G2+P2(G1+G0P1+P0P1Cn)=G2+G1P2+G0P1P2+P0P1P2C0C16=G3+P3C12=G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3C0

=G*＋P*C0其中:P*＝P0P1P2P3G*＝G3＋G2P3＋G1P1P2＋G0P1P2P3根据上述公式实现逻辑电路:(2)组间并行进位——两级先行进位的ALU由串行进位关系C8

X0Y0X1Y1X2Y2X3Y3

C12C8C4

X0Y0X1Y1X2Y2X3Y3

X0Y0X1Y1X2Y2X3Y3

0X0Y0X1Y1X2Y2X3Y3C12C进位的传递时间C16C12C8C4C01.534.56tyC1CC3第1小组X3~0Y3~0C3C2C1P0G0第2小组X7~4Y7~4C7C6C5P1G1第3小组X11~8Y11~8C11C10C9P2G2第4小组X15~12Y15~12C15C14C3P3G3第二级进位链C0C4C8C12C16进位的传递时间C16C12C8C4C01.534.56由上图可见，•

当Xi和Yi形成以后，经过1.5ty，产生第一小组的C1，C2，C3

和所有的Gi、Pi；•

经过1.5ty，由第二级进位链产生C4，C8，C12，C16；•

再经1.5ty后，产生第2，3，4小组内的C5C6C7，

C9C10C11，C13C14C15。整个进位传递时间为4.5ty。由上图可见，•经过1.5ty，由第二级进位链产生C4，C84.先行进位部件（CLA）——7418274182是一个并行进位部件，其内部结构图如下：其中G*称为成组进位发生输出，P*称为成组进位传送输出。4.先行进位部件（CLA）——7418274182是一Cn+ｘ=G0+P0CnCn+ｙ=G1+P1Cn+ｘ=G1+G0P1+P0P1CnCn+ｚ=G2+P2Cn+ｙ=G2+G1P2+G0P1P2+P0P1P2CnCn＋4=G3+P3Cn+ｚ=G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3Cn

=G*＋P*Cn其中:P*＝P0P1P2P3

G*＝G3＋G2P3＋G1P1P2＋G0P1P2P3先行进位部件74182CLA所提供的进位逻辑关系如下：Cn+ｘ=G0+P0Cn先行进位部件74182CLA所提供74181ALU设置了P和G两个本组先行进位输出端。如果将四片74181的P,G输出端送入到74182先行进位部件（CLA）,又可实现第二级的先行进位,即组与组之间的先行进位。例：16位字长ALU的构成G*P*74181ALU设置了P和G两个本组先行进位输出端。例：•C3、C7、C11是由74182同时形成的；•

其不同点是74182还提供大组间的进位函数G*

和大组传递条件P*，以便在位数更长时组成下一级先行进位链。由图可知：•C3、C7、C11是由74182同时形成的；由图可知：

用若干个74181ALU位片,与配套的74182先行进位部件CLA在一起,可构成一个全字长的ALU。例：全字长的ALU的构成用两个16位全先行进位部件级联组成的32位ALU逻辑方框图。用若干个74181ALU位片,与配套的74182十进制加法器

十进制加法器可由BCD码(二－十进制码)来设计,它可以在二进制加法器的基础上加上适当的“校正”逻辑来实现。70111+6+0110131101

（=D）

+011010011（=13）30011+5+010181000（=8）X+Y+C<10不调整X+Y+C>10调整十进制加法器十进制加法器可由BCD码(二－十进制码)故：

1.和为10～15时，加6校正；

2.和数有进位时，加6校正。和数(4位)有进位调整2800101000+9＋000010013700110001（=31）

＋0000011000110111(=37)故：和数(4位)2800101001.一位BCD码行波式进位加法器一般结构：0111010101111001101111011111.一位BCD码行波式进位加法器一般结构：01110102.n位BCD码行波式进位加法器一般结构：2.n位BCD码行波式进位加法器一般结构：原码乘法补码乘法定点乘法运算原码乘法补码乘法定点乘法运算

设n位被乘数和乘数用定点小数表示

被乘数

[x]原＝xf.xn－1…x1x0

乘数

[y]原＝yf.yn－1…y1y0

则乘积

[z]原＝(xf⊕yf)＋(0.xn－1…x1x0)(0.yn－1…y1y0)

式中，xf为被乘数符号，

yf为乘数符号。原码一位乘法1.乘法的手工算法设n位被乘数和乘数用定点小数表示原码一位乘法1.(2)手工运算过程：设ｘ＝0.1101,ｙ＝0.10110.1101(x)0.1011(y)110111010000+11010.10001111(z)(1)乘积符号的运算规则：同号相乘为正，异号相乘为负。(2)手工运算过程：设ｘ＝0.1101,ｙ＝0.1011(1)机器通常只有n位长,两个n位数相乘,乘积可能为2n位。(2)只有两个操作数相加的加法器难以胜任将n位积一次相加起来的运算。机器与人们习惯的算法不同之处：0.1101x×0.1011y0.00001101x共4次右移

0.0001101x共3次右移

0.000000x共2次右移

+0.01101x共1次右移

0.10001111

2.适合定点机的形式(1)机器通常只有n位长,两个n位数相乘,乘积可能

为了适合两个操作数相加的加法器，将xy改写成下面形式：xy=x(0.1011)=0.1x+0.00x+0.001x+0.0001x=0.1{x+0.1[0+0.1(x+0.1x)]}=2-1{x+2-1[0+2-1(x+2-1x)]}

根据此式，按式中括号可表达的层次，从内向外逐次进行移位累加。为了适合两个操作数相加的加法器，将xy改写成下面形式一般而言，设被乘数x,乘数y都是小于1的n位定点正数：

x=0.x1x2......xn<1y=0.y1y2......yn<1其乘积为：x·y=x(0.y1y2......yn)=x(y12-1+y22-2+…+yn2-n)=2-1(y1x+2-1(y2x+2-1(…+2-1(yn-1x+2-1(ynx+0))…)))一般而言，设被乘数x,乘数y都是小于1的n位定点正数：其乘积形成递推公式

令zi表示第i次部分积，则根据从内到外的原则有：

z0=0,z1=2-1(ynx+z0)z2=2-1(yn-1x+z1)┊zi=2-1(yn-i+1x+zi-1)┊zn=xy=2-1(y1x+zn-1)特点：每次只需要相加两个数，然后右移一位。且相加的两个数（部分积和位积）都只有n位，因而不需要2n位的加法器。形成递推公式令zi表示第i次部分积，则根据从内到外的原则3.原码一位乘法流程图

开始zi=0,i=0yn=1?zi+0zi+xzi,y右移一位，i=i+1i=n?

结束yynn3.原码一位乘法流程图开始zi=0,部分积乘数说明最后结果：xy=0.10001111

00.0000yf1011

z0=0+00.1101y4=1,+x00.1101

00.01101yf101右移，得z1+00.1101y3=1,+x

01.001100.100111yf

10右移，得z2+00.0000y2=0,+0

00.100100.0100111yf

1右移，得z3+00.1101y1=1,+x01.000100.10001111yf右移，得z4=xy例：x=0.1101,y=0.1011,求x·y

。部分积乘数说明最后结果：xy=0.1000114.原码一位乘硬件逻辑原理图

R0→

R1→ynR2

计数器i

部分积z

被乘数x

乘数y

LDR0LDR1

T1,T2,…

Ti

QQ加法器RS启动ynCx计数器：对移位的次数进行计数，以便判断乘法运算是否结束。当计数器i=n时，计数器i的溢出信号使控制触发器Cx

置0，关闭时序脉冲T，乘法操作结束。4.原码一位乘硬件逻辑原理图R0→R1→ynR2计数

原码一位乘法的主要问题是：符号位不能参与运算，而补码乘法可以实现符号位直接参与运算。2补码一位乘法1.原码一位乘的缺点2.补码一位乘法的规律推导

采用比较法。比较法是Booth夫妇首先提出来的，又称Booth算法。原码一位乘法的主要问题是：符号位不能参与运算，2

设[x]补

=x0.x1x2…xn

当x0时,x0=0，Booth算法[x]补=0.x1x2…xn==x=-1+0.x1x2…xn=-1+x=-x0+真值与补码的关系：

当x0时,x0=1，[x]补=1.x1x2…xn=2+xx=1.x1x2…xn-2(1)真值和补码之间的关系设[x]补=x0.x1x2…xnBooth算法[x

在补码机器中，一个数不论其正负，连同符号位向右移一位，符号位保持不变，就等于乘1/2。

设[x]补

=x0.x1x2…xn

∵x=-x0+∴x=-x0+121212=-x0+x0+1212=-x0+写成补码的形式，即得：要得到[2-ix]补,连同符号位右移i位即可(2)补码的右移12[

x]补

=

x0.x0x1x2…xn在补码机器中，一个数不论其正负，连同符号位向右移一位，

设被乘数

[x]补

=x0.x1x2…xn

乘数[y]补

=y0.y1y2…yn

均为任意符号，则有补码乘法算式：[x·y]补=[x]补·y或：[x·y]补=[x]补·

(3)补码乘法规则设被乘数[x]补=x0.x1x2…xn[x·y1）、当被乘数x符号任意，乘数y符号为正时：

根据补码定义：==yyyy.]y[nL210补)(modxxxxx.x]x[nn+=+==+L1210222补∴

由于（y1y2…yn)是大于或等于1的正整数，根据模运算性质（大于2的部分全部丢掉）有：2(y1y2…yn)=2∴(mod2)即：公式证明1）、当被乘数x符号任意，乘数y符号为正时：==yyyy.]2）、当被乘数x符号任意，乘数y符号为负时：)(modyyyy.]y[n22121+==L补xxx.x]x[n210=L补∵∴又因(0.y1y2…yn)>0所以：2）、当被乘数x符号任意，乘数y符号为负时：)(modyy(mod2)=[x]补·=[x]补·y(mod2)=[x]补·=[x]补·y

为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。(yn+1是增加的附加位，初值为0)公式展开为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加

将上式改为接近于分步运算逻辑实现的递推关系。补]z[00=补补补}]x)[yy(]z{[]z[nn12112-+=--补补补}]x)[yy(]z{[]z[ininii12112-+=+-+---补补补}]x)[yy(]z{[]z[nn11112-+=--补补补}]x)[yy(]z{[]z[nn10112-+=+-MM递推公式补补补补]x)[yy(]z[]z[]yx[nn011-+==+·最后一步不移位将上式改为接近于分步运算逻辑实现的递推关系。补]z[00=由此可见：每次都是在前次部分积的基础上，由（yi+1-yi)

决定对[x]补的操作，然后再右移一位，得到新的部分积；重复进行。yn+1，yn的作用：开始操作时，补充一位yn+1,使其初始为0。由yn+1yn

判断进行什么操作；然后再由ynyn-1

判断第二步进行什么操作…。

若

ynyn＋1=０1则

yi＋1-yi=1做加[x]补运算；ynyn＋1=１０

则

yi＋1-yi=-１做加[-x]补运算；ynyn＋1=１1ynyn＋1=0０则yi＋1-yi=0

[zi]加0，即保持不变；

由此可见：yn+1，yn的作用：若ynyn＋1=０1补码一位乘的运算规则(1)如果yn=yn+1

，则部分积[zi]加0，再右移一位；(2)如果ynyn+1=01

，则部分积[zi]加[x]补，再右移一位；(2)如果ynyn+1=10

，则部分积[zi]加[-x]补,再右移一位；

如此重复n+1步，但最后一步不移位。包括一位符号位，所得乘积为2n+1位，其中n为尾数位数。补码一位乘的运算规则(1)如果yn=yn+1，则部分积算法流程图

开始结束[zi]补+[x]补→[zi]补[zi]补+[-x]补→[zi]补[z]补=0,i=0ynyn+1=?[zi]补不变i=n+1？[zi]补,y右移一位，i=i+1011001或11YN算法流程图开始结束[zi]补+[x]补→[zi]补[zi00.00001.00110yn+1=0+00.1011ynyn+1=10,加[-x]补

00.101100.0101110011右移一位+00.0000ynyn+1=11,加000.010100.00101

11001右移一位+11.0101ynyn+1=01,加[x]补

11.011111.1011111100右移一位+00.0000ynyn+1=00,加011.101111.11011111

10右移一位+00.1011ynyn+1=10,加[-x]补

00.10001111

10最后一位不移位例：[x]补=1.0101，[y]补=1.0011,求[x·y]补=？[-x]补=0.1011[x·y]补=0.10001111算法步骤存在错误!!!部分积乘数

ynyn+1说明00.00001000000101100yn+1=0+000000ynyn+1=00,加0000000000000010110右移一位+110011ynyn+1=10,加[-x]补

1100111110011

01011右移一位+000000ynyn+1=11,加011.100111.1100110101右移一位+001101ynyn+1=01,加[x]补

0010010001001110

10右移一位+110011ynyn+1=10,加[-x]补

1101111110

10最后一位不移位[x]补=001101，[y]补=10110,[-x]补=110011[x·y]补=101111110部分积乘数

ynyn+1说明例：x=13,y=-10求x·y=？x·y=-010000010=-82H=补码一位乘逻辑原理图

R0→

R1→ynyn+1R2

计数器i

部分积z

被乘数x乘数y

+1LDR0LDR1

T1,T2,…+1

Ti

QQ加法器RS启动Cxf

+-yn+1ynyn+1yn多开关路原反1001QQ4.补码一位乘逻辑原理图R0→R1→ynyn+1R2[注]被乘数寄存器R2的每一位用原码（触发器Q端）或反码（触发器Q端）经多路开关送出；送[-x]补时，即送R2反码且在加法器最末为加1；(2)R0保存部分积，其符号与加法器符号位f始终一致。(3)当计数器i=n+1时，封锁LDR1、LDR0信号，使最后一步不移位。[注]高基乘法以上讨论的乘法都只是检查一位二进制位。能否同时检查K位二进制位？以K=2，C=A×B为例如果这两位二进制位为00，则加0如果这两位二进制位为01，则加A如果这两位二进制位为10，则加2A如果这两位二进制位为11，则加3A2A=4A—2A3A=4A—A如果这两位二进制位为11，则减A，4A待下一次补上，由于部分积已右移两位，原来加4A变成加A如何知道有4A的操作哪？两位二进制位为10或11，则加4A高基乘法以上讨论的乘法都只是检查一位二进制位。如果这两位二进B的低两位前次移出的位

运算

注释2i+12i2i-10000+0+0001+A+0+A010+A+A+0011+2A+A+A100-2A+4A-2A+0101-A+4A-2A+A110-A+4A-A+01110+4A-A+ABooth4基乘法算法B的低两位前次移出的位

2i+12i2i-10000例：A=011011，B=011001，计算C=A×B。0000000101001

0010，加[A]补+1110010111001011111001

010100算术右移两位+0011100100,加[-2A]补

001100000001100

010

101算术右移两位+00