《计算机组成原理（第3版）》第三章 计算机算法和算法电路实现

计算机算法和算法电路实现本章介绍计算机组成和系统结构的重要基本概念，信息编码、算法设计和运算器设计等。3计算机算法和算法电路实现3.1各种数据类型的二进制表示3.2加减运算和快速加法器设计3.3乘法和高速乘法算法及电路3.4除法和快速除法电路3.5开方算法及电路实现处理机存储器I/O接口显示器打印机键盘网络鼠标I/O接口总线控制器图1.4硬盘软盘Cache信息编码3.1各种数据类型的二进制表示信息编码内容信息编码数据编码命令编码数值编码字符编码定点数值浮点数值逻辑数值西文中文（指令编码）(I’llexplainitindetailinchapter4.)数据编码数据编码数值编码字符编码定点数值浮点数值逻辑数值西文中文定点整数定点小数数值编码定点数值浮点数值逻辑数值定点整数定点小数数值编码定点数值定点整数定点小数定点数值原码表示补码表示移码表示原码表示补码表示定点整数格式…...0110n-1n-2n-33210.第n-1位为符号位。第n-1位=0，表示正整数；=1，表示负整数；例如：6，原码表示是:1110例如：-6，原码表示是:原码表示:

n-2位—0位为数的绝对值。[x]原=x,x>=0;2n-1+|x|,x=<-1[x]原=[x]原=x=0110x=-0110数值表示范围：正最小值：000…...0000n-1n-2n-33210..正最大值：011…...1111n-1n-2n-33210.+0+（2n-1-1）负最大值：100…...0000n-1n-2n-33210.负最小值：111…...1111n-1n-2n-33210.-0-（2n-1-1）真值机器数数值表示个数：0+（2n-1-1）-（2n-1-1）2n个数值表示范围：+1-1变化的分辨率:1,并且是均允的.0+（2n-1-1）-（2n-1-1）+1-1定点整数格式…...0110n-1n-2n-33210.第n-1位为符号位。第n-1位=0，表示正整数；=1，表示负整数；例如：6，补码表示是:1010例如：-6，补码表示是:补码表示:[x]补=x,x>=0;2n-|x|,x=<-1[x]补=[x]补=x=0110x=-011010000-0110=1010[x]补=x,x>=0;2n-|x|,x=<-1证明:2n-|x|=111…..11+1-|x|=111…..11-|x|+1=[x]反+1从n-1位到0位

[-9]补

10111取反加1的证明0100110111例如求-9的补码:|-9|01001[9]反10110+110111100000数值表示范围：正最小值：000…...0000n-1n-2n-33210.正最大值：011…...1111n-1n-2n-33210.0+（2n-1-1）负最大值：000…...0000n-1n-2n-33210.负最大值：111…...1111n-1n-2n-33210.0-1负最小值：100…...0000n-1n-2n-33210.-2n-1真值机器数数据表示个数：0+(2n-1-1)-2n-12n个数值表示范围+1-1变化的分辨率:1,并且是均允的.0+(2n-1-1)-2n-1+1-1定点整数格式…...n-1n-2n-33210.移码表示:[x]移=x+移码值=x+(2n-1-1)X=[x]移-移码值=[x]移-(2n-1-1)定点小数格式0110第0位为符号位0位=0，表示正整数；=1，表示负整数；例如：0.75，原码表示是:1110例如：-0.75，原码表示是:原码表示:

1位—n-1位为数的绝对值。[x]原=x,0<=x<1;1+|x|,-1<x<=0[x]原=[x]原=…...0123n-1.n-3n-2数值表示范围：正最小值：正最大值：负最大值：负最小值：真值机器数000…...00000123n-1.n-3n-2011…...11110123n-1.n-3n-200…...0000123n-1.n-3n-2111…...11110123n-1.n-3n-21+0-01-2-（n-1）-(1-2-（n-1）)1.00000…00.0000…010.11111…1正最大值：011…...11110123n-1.n-3n-21-2-（n-1）1-2-（n-1）公式说明1-2-（n-1）数据表示个数：02n个数值表示范围：变化的分辨率:,2-（n-1）

并且是均允的.01-2-（n-1）1-2-（n-1）-(1-2-（n-1）)-(1-2-（n-1）)定点小数格式0110第0位为符号位0位=0，表示正整数；=1，表示负整数；例如：0.75，原码表示是:1010例如：-0.75，原码表示是:补码表示:[x]补=x,0<=x<1;2-|x|,-1<=x<0[x]补=[x]补=…...0123n-1.n-3n-2[x]补=x,

0=<x<1;2

-|x|,-1=<x<0从0位到n-1位

[-0.5625]补取反加“1”的证明例如求-0.5625的补码:|-0.5625|01001[0.5625]反10110+1101112-|x|=1.111….1+2-（n-1）-|x|=1.111….1-|x|+2-（n-1）=[x]反+“1”1000000100110111数值表示范围：正最小值：正最大值：负最大值：负最小值：真值机器数000…...00000123n-1.n-3n-2011…...11110123n-1.n-3n-200…...0000123n-1.n-3n-2111…...11110123n-1.n-3n-210-11-2-（n-1）-2-（n-1）数据表示个数：02n个数值表示范围：变化的分辨率:,2-（n-1）

并且是均允的.01-2-（n-1）1-2-（n-1）-1-14位二进制数在各种不同表示方法下的所能表示的数值100111001111001110011110011100111内存中哪些是数据,哪些是指令PC:11001100AR:11101110指令数据由指令决定数据类型!浮点数值的表示法浮点数是指小数点位置可浮动的数据，通常以下式表示：N=M•RE其中，N为浮点数，M(mantissa)为尾数，E(exponent)为阶码，R(radix)称为阶的基数，也叫底。R是一个常数，一般是2、8或16。sEMseffractionIEEE754浮点数值的表示法sef031302322sef063625251IEEE(InstituteofElectricalandElectronicEngineers)745标准的单精度和双精度浮点格式。s(sign)、e(exponent)f(fraction)单精度双精度IEEE754浮点数值的表示法符号位

s=0,+

1,-阶码e采用移码，尾数f采用原码纯小数。机器数与真值的关系：V=(-1)s•2e-127•

1.f23.34*1022.334*103规格化的非规格化的11.0111*22规格化的非规格化的1.10111*23f隐藏位01000000111011000000000000000000举例说明：V=(-1)s•2e-127•

1.f=(-1)0

•2129-127•

1.fV=22•

1.11011000000000000000000=111.011000000000000000000=7.375例一，机器数真值例二，真值机器数V=3.125=11.001=1.1001•21s=0,e=1+127=128,f=1001000000000000000000001000000010010000000000000000000IEEE754单精度浮点数数的范围01111111100000000000000000000000e=255,f=0：+无穷大00000000000000000000000000000000e=0,f=0：零00000000100000000000000000000000e=00000001,f=0：+最小值

=2-12601111111011111111111111111111111e=11111110,f=1111：+最大值

=2127（2-2-23）02-1262127（2-2-23）2e-127=20-127=2-127数表示的精度2e-30101000=1.000=100.0=4001=1.001=100.1=4.5010=1.010=101.0=5011=1.011=101.1=5.51001011101112e-3=25-3=22000001010011100101110111maxminfhas8patternsperavalue.数表示的精度逻辑数值True2false当事物只有二个状态时可用逻辑值表示!字符编码西文编码：汉字编码：西文编码：ASCII（AmericanStandardCodeforInformationInterchange):规定8个二进制位的最高一位为0，余下的7位可以给出128个编码，表示128个不同的字符。EBCDIC(ExtendedBinaryCodedDecimalInterchangeCode):扩充的二十进制交换码，这种编码使用8位二进制数。可以给出256个编码，表示256个不同的字符。汉字编码：输入程序1输入程序2输入程序n...内码字库1字库2字库m...宋体楷体隶体...全拼码ABC码五笔字型码...汉字输入编码：为了能直接使用西文标准键盘把汉字输入到计算机。汉字内码：汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码。字模码是用点阵表示的汉字字形代码，它是汉字的输出形式。国标码不等于机内码！国标码是我国1981年公布的《通信用汉字字符集（基本集）及其交换码标准》GB2312--80方案。00第一字节第二字节0011000000010010国标码如，“啊”：11第一字节第二字节1011000010010010机内码如，“啊”：区别ASCII汉字字型•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••0150153.2加减运算和快速加法器设计3.2.1补码的加减运算3.2.2快速加法运算3.2.1补码的加减运算[x]补[y]补[x+/-y]补

+ADD/SUB溢出？补码加减运算规则[x+y]补=[x]补+[y]补

[x-y]补=[x+[-y]]补=[x]补+[-y]补[-y]补=[y]补+“1”补码加减运算器判别溢出方法AsBsSsAsBsSs溢出AsBsSs补码加减运算0011(+3)0010(+2)0101(+5)+1100(-4)1101(-3)1001(-7)+1100(-4)0010(+2)1110(-2)+0011(+3)0111(+7)1010(-6)+1101(-3)1001(-7)0110(+6)+上溢！上溢！3.2.2快速加法运算全加器设计全加器真值表输入输出abci

ci+1s0000000101010010111010001101101101011111逻辑表达式：s=a•b•ci

+a•b•ci

+a•b•ci

+a• b•ci+1=a•b+a•ci+b•ciabci+ci+1s=abci逻辑图：sabcici+1逻辑表达式：s=a•b•ci

+a•b•ci

+a•b•ci

+a• b•ci

ci+1=a•b+a•ci+b•ci=ab+(a+b)ci=g+pci=abci逻辑图：sabcici+1abscicoaddc0b0a0s0c1g:进位产生函数p:进位传递函数n位串联加法器abscicoaddabscicoaddabscicoaddabscicoaddc0b0b1a0an-2an-1a1bn-2bn-1s0s1sn-2sn-1c1cncn-1cn-2c2分析：

cn=an-1bn-1+(an-1+bn-1)cn-1=gn-1+pn-1cn-1ci=ai-1bi-1+(ai-1+bi-1)ci-1=gi-1+pi-1ci-1c2=a1b1+(a1+b1)c1=g1+p1c1c1=a0b0+(a0+b0)c0=g0+p0c02级门延迟2级门延迟2级门延迟2级门延迟abscicoaddabscicoaddabscicoaddabscicoaddc0b0b1a0an-2an-1a1bn-2bn-1s0s1sn-2sn-1c1cncn-1cn-2c2解决办法

先行进位加法器abscicoaddabscicoaddabscicoaddabscicoaddc0b0b1a0an-2an-1a1bn-2bn-1s0s1sn-2sn-1c1cncn-1cn-2c2Ci=fi(A,B,c0)ABA=(an-1,

an-2,…,

a1,a0)B=(bn-1,

bn-2,…,

b1,b0)以8位先行进位加法器为例：a0b0a1b1a2b2a3b3a4b4a5b5a6b6a7b7s0s1s2s3s4s5s6s7c0c1c2c3c4c5c6c7c8A=(a7,

a6,…,

a1,a0)B=(b7,

b6,…,

b1,b0)ABCi=fi(A,B,c0)以8位先行进位加法器为例：c2=a1b1+(a1+b1)c1=g1+p1c1=g1+p1(g0+p0c0)=g1+p1g0+p1p0c0c1=a0b0+(a0+b0)c0=g0+p0c0c3=a2b2+(a2+b2)c2=g2+p2c2=g2+p2(g1+p1g0+p1p0c0)=g2+p2g1+p2p1g0+p2

p1p0c0

c4=a3b3+(a3+b3)c3=g3+p3c3=g3+p3(g2+p2g1+p2p1g0+p2

p1p0c0

)=g3+p3g2+p3p2g1+p3

p2

p1g0+p3

p2

p1p0c0

c5=a4b4+(a4+b4)c4=g4+p4c4=g4+p4(g3+p3g2+p3p2g1+p3

p2

p1g0+p3

p2

p1p0c0

)=g4+p4g3+p4p3g2+p4

p3p2g1+p4

p3

p2p1g0+p4p3

p2

p1p0c0

c6=a5b5+(a5+b5)c5=g5+p5c5=g5+p5(g4+p4g3+p4p3g2+p4

p3p2g1+p4

p3

p2p1g0+p4p3

p2

p1p0c0

)=g5+p5g4+p5p4g3+p5

p4p3g2+p5

p4

p3p2g1+p5p4

p3

p2p1g0+p5

p4p3

p2

p1p0c0

以8位先行进位加法器为例：c7=a6b6+(a6+b6)c6=g6+p6c6=g6+p6(g5+p5g4+p5p4g3+p5

p4p3g2+p5

p4

p3p2g1+p5p4

p3

p2p1g0

+p5

p4p3

p2

p1p0c0)=g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1

+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

以8位先行进位加法器为例：问题1：扇入太多c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

c8以8位先行进位加法器为例：问题2：扇出太多c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

p7以8位先行进位加法器为例：问题3：电路不规则，需要长线驱动c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

解决办法a0b0a1b1a2b2a3b3a4b4a5b5a6b6a7b7s0s1s2s3s4s5s6s7c0c1c2c3c4c5c6c7c8A3-0B3-0A7-4B7-4c4解决办法a0b0a1b1a2b2a3b3a4b4a5b5a6b6a7b7s0s1s2s3s4s5s6s7c0c1c2c3c4c5c6c7c8C1=a0b0+(a0+b0)C0=g0+p0C0C1=g0+p0C0C2=g1+p1C1=g1+p1(g0+p0C0)=g1+p1g0+p1p0C0

=G1,0+P1,0C0C2=G1,0+P1,0C0C3=g2+p2C2C4=G3,2+P3,2C2C5=g4+p4C4C6=G5,4+P5,4C4C7=g6+p6C6C8=G7,6+P7,6C6G1,0=g1+p1g0;

P1,0=p1p0a1,0b1,0a3,2b3,2a5,4b5,4a7,6b7,6以8位先行进位加法器为例：实用的a0b0s0a1b1s1a2b2s2a3b3s3a4b4s4a5b5s5a6b6s6a7b7s7c0p0g0c6p6g6c5p5g5c7p7g7c4p4g4c3p3g3c2p2g2c1p1g1G1,0c0G3,2G5,4G7,6c0c0P1,0P3,2P5,4P7,6c2c4c4c4G3,0P3,0G7,4P7,4G7,0P7,0C4=G3,2+P3,2C2=G3,2+P3,2G1,0+P3,2P1,0C0=G3,0+P3,0C0C2=G1,0+P1,0C0C1=a0b0+(a0+b0)C0=C2=g1+p1C1=g1+p1(g0+p0C0)=g1+p1g0+p1p0C0=g0+p0C0G1,0+P1,0C0C3==g2+p2C2C4=g3+p3C3=g3+p3(g2+p2C2)=g3+p3g2+p3p2C2=G3,2+P3,2C2=G3,2+P3,2(G1,0+P1,0C0)=G3,2+P3,2G1,0+P3,2

P1,0C0=C5=a4b4+(a4+b4)C4=g4+p4C4C6

=G5,4+P5,4C4C7==g6+p6C6G3,0+P3,0C0C8=G7,4+P7,4C4=G7,4+P7,4(G3,0+P3,0C0)=G7,4+P7,4G3,0+P7,4P3,0C0)=G7,0+P7,0C03.3乘法和高速乘法算法及电路3.3.1无符号整数乘法及电路一位二进制的乘法运算规则:0x0=0,0x1=0,1x0=0,1x1=1十进制乘法二进制乘法1234432112342468370249365332114被乘数:乘数:乘积:1001101000001001

00001001

1011010被乘数:乘数:乘积:二进制乘法1001101000001001

00