《软件工程导论》课件ch01-从手工计算到自动计算.pptx

1、第1章 从手工计算到自动计算Computing Machine“形而上者谓之道，形而下者谓之器”-周易系辞上目录 1.1数的表达 1.2手写计算 1.3手工计算工具 1.4巴贝奇机械自动计算机器 1.5减法与补码 1.6逻辑计算 1.7二进制加减法计算机器数的表达证明：一个数各位数之和能被3整除，那么，这个数一定能被3整除目录 1.1数的表达 1.1.1十进制数 1.1.2二-八-十六进制数十进制数123百位十位个位十进制数基数幂十进制数二-八-十六进制数1011第四位第三位第二位第一位二-八-十六进制数数的表达二-八-十六进制的直接转换 事实上，可以定义任何一种进制，例如，三进制、七进制等，

2、从而形成不同的进制体系。例如，我们日常生活中的12或24的小时进制，60秒为1分的60进制，等等。目录 1.1数的表达 1.2手写计算 1.3手工计算工具 1.4巴贝奇机械自动计算机器 1.5减法与补码 1.6逻辑计算 1.7二进制加减法计算机器手写计算的例子 6 9 1 2+9 8 7 6 1 1 0 0 (进位)1 6 7 8 8 (结果)1234+5678=6912；6912+9876=16788 1 2 3 4+5 6 7 8 0 0 1 1 (进位)6 9 1 2 (结果)1234+5678+9876=？手写计算规范化1234+5678+9876=167881234+5678进位00

3、11结果结果69126912+9876进位1100结果结果16788二进制竖式计算 1 0 1 1+0 1 1 1 1 1 1 1 (进位)1 0 0 1 0 (结果)1 0 0 1 0+1 0 0 10 0 0 0 0 (进位)1 1 0 1 1 (结果)1011+0111=10010；10010+1001=11011二进制竖式计算 1 0 1 1+0 1 1 1 1 1 1 1 (进位)1 0 0 1 0 (结果)1 0 0 1 0+1 0 0 10 0 0 0 0 (进位)1 1 0 1 1 (结果)1011+0111=10010；10010+1001=110111011+0111+10

4、01=1101十六进制竖式计算 B 7+1 (进位)1 2 (结果)1 2 9+0 (进位)1 B (结果)B+7=12 12+9=1B转成二进制例1：12(十六进制)=1 0010(二进制)例2：1B(十六进制)=1 1011(二进制)例1：例2：目录 1.1数的表达 1.2手写计算 1.3手工计算工具 1.4巴贝奇机械自动计算机器 1.5减法与补码 1.6逻辑计算 1.7二进制加减法计算机器手工计算机器-算筹春秋战国；“算筹”的使用已经非常普遍了用“算筹”作为工具进行的计算叫“筹算”。经常讲：让我们筹算筹算！数字数字1234567890横式竖式珠算 用珠子构成的计算工具，算盘。The Ch

5、inese Standards AbacusA reconstruction of a Roman abacus in the Cabinet des Mdailles,Bibliothque nationale,Paris.Japanese soroban21档的算盘目录 1.1数的表达 1.2手写计算 1.3手工计算工具 1.4巴贝奇机械自动计算机器 1.5减法与补码 1.6逻辑计算 1.7二进制加减法计算机器计算机器(computing machinery)1275年，西班牙神学家雷蒙德.露利(R.Lullus)发明一种思维机器（“旋转玩具”）1641年法国人帕斯卡(B.Pascal)利

6、用齿轮技术做成加法器 1673年，德国人莱布尼茨（G.W.V.Leibniz）在此基础上制造了能加、减、乘、除的计算机器。19世纪世纪30年代，英国人巴贝奇年代，英国人巴贝奇（C.Babbage）设计了用于计算对数、三）设计了用于计算对数、三角函数和其它算术函数的角函数和其它算术函数的“分析机分析机”The work of Babbage Charles Babbage(巴贝奇)(1791 1871)英国数学家、分析哲学家、机械工程师 原型计算机科学家(proto-computer scientist）建立可编程计算机(a programmable computer)思想.其未完成的计算机存放

7、在 London Science Museum.1991年，依据 Babbage的原始设计计划，工程师们制造出来差分机(difference engine),功能完整 验证了在9世纪Babbage的机器是能工作的。Difference engine of BabbagePart of Babbages Difference engine,assembled after his death by Babbages son,using parts found in his laboratoryThe London Science Museums replica difference engine,

8、built from Babbages design.http:/en.wikipedia.org/wiki/Difference_engineBabbage in British Science&History MuseumBabbage机加法运算 曲柄轴每转一圈，执行一次加法和进位操作 奇数和偶数柱子交替执行一次加法 因此，第n个柱子的操作顺序是：1)执行加法，接收第n+1柱子的进位(加法步骤)2)执行进位操作 3)减为零，加到到n 1个柱子上把2N个柱子连成排，就形成了可以计算N位数的计算装置。然后，在用某种动力（例如蒸汽机或人工）带动机器的曲柄轴，这样，每曲柄轴转一定的圈数，就可以完成

9、一个柱子（某一位）的计算，一直到所有的柱子都完成计算或需要计算的所有位都完成计算。一次加法就完成了。目录 1.1数的表达 1.2手写计算 1.3手工计算工具 1.4巴贝奇机械自动计算机器 1.5减法与补码 1.6逻辑计算 1.7二进制加减法计算机器减法运算？有了加法运算，如何做减法运算？让曲轴倒转？减法与补码 有了加法运算，如何做减法减法运算？合理的方法是采用补码。一个数的补码(complements)是最大数减去该数。例如，对于十进制，一位数的补码是9-原数，即下表所列：原数0123456789补码9876543210用减数的补码做运算 考虑下面的减法：先计算减数的补码，218的补码是999

10、-218=781，然后与被减数相加。873（被减数）-218（减数）=655 873（被减数）+781（减数的补数）=1654 （999+被减数-减数）如果计算机器只有三位，最左的“1”就会被卡掉，结果成为654。这就不对了。需要再补1。即，因此，如果用减数补码进行运算，补码应当是“模-原减数+1”。本例中，218的补码是999-218+1=782。873+782=1655。由于机器只有三位数，最高为的“1”被卡掉，结果是655。654+1=655（被减数-减数）1654 -1000 -(999+1)=1654 （被减数-减数-1）用被减数的补码做运算第二种计算方法是，计算被减数的补码，然后加

11、上减数得到一个结果，最后把此结果转换为补码，即为最后结果。同样做873-218运算，873的补码是999-873=126，因此：对计算结果再进行一次补码预算，这样，344的补码是999-344=655。从而用两次补码完成减法运算。对比用减数和被减数分别做补码运算实现的减法，这两种计算的复杂程度基本上一样的。用减数的补码更直接，但要考虑加一的情况。如果把减数的补码直接定义为：模数模数-原码原码+1，就可以简化该运算。，就可以简化该运算。126（873的补数）+218（减数）=344目录 1.1数的表达 1.2手写计算 1.3手工计算工具 1.4巴贝奇机械自动计算机器 1.5减法与补码 1.6逻辑

12、计算 1.6.1 逻辑计算定义 1.6.2 用晶体管构造逻辑运算单元 1.6.3 逻辑向量计算 1.7二进制加减法计算机器1.6.1 逻辑计算逻辑计算定义定义 一个逻辑变量，是只有“真”或“假”两个值的变量，英文表达为True或False，或用0和1表示。接来下定义两个逻辑变量A和B的计算。与运算：记为：A&B，当且仅当A和B都为真时，A&B才为真。或运算：记为：A|B，当且仅当A和B都为假时，A|B才为假。非运算：记为：A，当A为真时，A为假；当A为假时，A为真；异或运算：记为：AB，当且仅当A和B不同时，AB才为真，否则为假。基本逻辑运算表与“与”运算A&BB“或”运算A|BB01 01A

13、000 A001101 111 “非”运算AA “异或”运算ABB 0101 A00110 110逻辑运算体系逻辑运算也遵循一定的运算规律。例如：结合律(Associativity)：x|(y|z)=(x|y)|z，以及 x&(y&z)=(x&y)&z 交换律(Commutativity)：x|y=y|x，以及 x&y=y&x 分配律(Distributivity)：x&(y|z)=(x&y)|(x&z)恒等律(Identity):x|0=x，x&1=x 归零律(Annihilator)：x&0=0 逻辑运算最小体系 第四个（异或）定义是多余的，可以用前三个定义，推导出来，例如：1.AB=(A

14、|B)&(A|B)2.AB=(A&B)&(A&B)3.AB=(A&B)|(A&B)进一步，与、或、非是否可以归纳为两个运算呢？例如，或运算可以归纳为非和与两种运算，事实上，A|B=(A&B)。同样，A&B=(A|B)。逻辑计算中只需要两个符号，（非、与），或（非、或）这是逻辑运算的最小体系1.6.2 用晶体管构造逻辑运算单元 二极管是一种单向导通的电路。其导电特征如图所示，(a)和(b)分别表达对二极管的正向和反向导电的特征测试。“与”运算的构造输入/输出电压特征逻辑“与”真值表输入输出输入输出VAVBVLABL0V0V0V0000 V5V0 V0105V0V0V1005V5V5V111“或”

15、运算的构造输入/输出电压特征逻辑或真值表输入输出输入输出VAVBVFABF0V0V0V0000 V5V5V0115V0V5V1015V5V5V111“非”门的构造要复杂一些，需要用开关型的三极管(注：另一种三极管主要用于信号放大)构造。输入/输出电压特征逻辑“非”真值表输入输出输入输出VAVFAF0 V5V015V0V10逻辑电路由其3种基本门电路(或称判定元素)组成。用电路用电路(电阻电阻、电容、二极管、三极管等分立、电容、二极管、三极管等分立原件原件)构成出逻辑运算电路。构成出逻辑运算电路。或或用半导体构造出集成电路的逻辑单元。用半导体构造出集成电路的逻辑单元。在在数字系统基础数字系统基础

16、中进一步学习。中进一步学习。电路工程师：制造逻辑电路单元基本门电路可以扩展成以下的扩展逻辑电路最后一个叫作缓冲器(buffer)，为两个非门串联以达到改变输出电阻的目的。可以提高带负载的能力。1.6.3逻辑向量逻辑向量计算计算 01101001&01010101 01101001|01010101 01101001 010101010111100 01010101 10101010 01000001011111010011110010101010与或非异或可以构造更有趣的逻辑向量运算 01101001&00001111 00001001 01101001|0000111101101111100

17、10110 01101001 11111111只要后四位，屏蔽前四位前四位不变，后面全为真每位都反着目录 1.1数的表达 1.2手写计算 1.3手工计算工具 1.4巴贝奇机械自动计算机器 1.5减法与补码 1.6逻辑计算 1.7二进制加减法计算机器目录 1.7二进制加减法计算机器 1.7.1用逻辑电路实现二进制的加法器 1.7.2 二进制的反码与补码器 1.7.3 二进制加/减法器 1.7.4 二进制数正负数范围逻辑向量运算与算术运算 11111111-01010101 1010101010101010算术运算：模-数 01010101 1010101010101010逻辑运算：非这不就是二进

18、制的反码运算？逻辑向量运算与算术运算算术运算：加法 01101001|0101010101111101逻辑运算：或+0110100101010101100000110111100进位进位无无进位结果进位结果00111100(有进位有进位)结果结果 01101001&01010101 01000001逻辑运算：与结果不一样！结果不一样！结果有点一样！？结果有点一样！？00111100逻辑向量运算与算术运算算术运算：加法+0110100101010101100000110111110进位进位无无进位结果进位结果00111100(有进位有进位)结果结果 01101001 01010101001111

19、00逻辑运算：异或好像一样？吔！无无进位结果进位结果不一样？吔！1.7.1用逻辑电路实现二进制加法器 两个多位的二进制数相加时，最低位不用考虑进位，即，输入量为两个，即A0、B0；输出量为两个，即S0、C1。S0表示本位的相加结果，C1表示向上一位的进位。这与逻辑“异或”的运算是一样的。记为：S0=A0+B0 C1 即：A0+B0=(C1,S0)半加器 可以构造出第一位的加法，称为半加器(Half Adder)S0是A0和B0的异或运算，即，两者不同时，输出为真。-因为，可以用”与、或、非”运算构造出异或运算。此题有解输入输出加数1加数2进位S(本位)A0B0C1S00000010110011

20、110全加器 进一步，考虑有进位时的加法，即，有3个输入Ai，Bi和Ci，有两个输出端，即Si及Ci+1。称为全加器（Full Adder）。&表示“与”运算AiBiCiCi+1Si0000000101010010111010000101101101011111 先“与”，后“或”异或观察结果，Si是Ai，Bi和Ci三者的“异或”。进位Ci+1=Ai&Bi|Ai&Ci|Bi&Ci表示三个加数中两个数同时为1时，才有进位，因此，先做两两相“与”，再做“或”运算，就是进位Ci+1。4位二进制的加法器 用一个半加器和若干个全加器，可以构造出多位二进制的加法器。下图是一个四位二进制的加法器，第一位A0

21、+B0，用一个半加器(HA)，之后的各位用全加器（FA）。1.7.2 二进制的反码与补码器 减法运算可以转换为加法运算，仿照前面十进制补码原理，将减数B变成补码后，再与被减数相加，其和（如有进位舍弃）就是两数之差，即，X Y补=X补Y补 原码变为反码：可控反相器就是为了使原码变为反码设计的电路。这实际上是一个异或门，异或门的特征是：两者相同则输出为0，两者不同则输出为1。各位补码器 SUB作为控制端，SUB=0，表示为正数，补码Y与原码B0相同，否则，SUB=1，补码Y与原码B0相反。1.7.3二进制加二进制加/减法器减法器4位二进制数加法器减法器综合电路 在前面的4位二进制数加法电路上增加4

22、个可控反相器，并将最低位的半加器也改用全加器，就可以得到4位二进制数加法器减法器综合电路SUB是控制器，表达是做加法还是减法运算。控制节奏的节拍器节拍1节拍2节拍3节拍4验证：加法运算例如，如果有下面两个二进制数：A=A3A2A1A0 B=B3B2B1B0则可将这两个数的各位分别送入该电路的对应端，于是：当SUB=0时，电路作加法运算：A+B。第0位：A0+B0其他各位为：A1+B1+C1 A2+B2+C2 A3+B3+C3验证：减法运算1.7.4 二进制数正负数范围 对于多位的二进制数，要考虑正数和负数，一般用最高为代表正负数的符号：0表示正数，1表示为负数。例如，十进制的2，在8位字长的二

23、进制中是：而-2则表达为：0000001010000010符号位符号位因此，8位二进制的范围为：-127-0+0127。显然，-0和+0只能有一个作为0。1000 0000符号位同时也可以看做数字位，这样127（0111 1111）+1（0000 0001）=1000 0000=128(包括符号位)这与负零是一样的，为保持符号位的作用，将其作为-128：即，-128（1000 0000）=-0(1000 0000)前面说的：负零=-128（1000 0000）结论：8位二进制的范围为：-1280127 同理，N位的二进制数表达的范围:是-2N-1,+2N-1-1，而不是-2N-1,+2N-1，

24、也不是-2N-1-1，+2N-1-1 例如，16位二进制的整数范围是-32768+32767 负数总比正数多一个，因为-0是最大的负数-2N-1总结 目标：探索自动计算机器 数的表达体系（各种进制表达和相互转换）算术运算体系（加减法，乘除法）加减法自动计算机器 逻辑运算体系 最小体系：(非、或),(非、与)用电路构造出逻辑运算(机器)用逻辑运算(机器)实现二进制的算术运算(机器)构造出可以实现逻辑运算、算术运算的电路(机器)作业 1.证明：逻辑计算中只需要两个运算符，（非、与），或者（非、或）。注意：要证明，而不能只抄袭书上的公式。进一步思考，能否只用一个运算符？3.把十进制数，189,128,510,1023，转换为二进制数；把二进制数，10101011分别转换为十进制、八进制、十六进制和三进制数。