计算机组成原理06-计算机的运算方法.ppt

,系统总线,存储器,运算器,控制器,接口与通信,输入/输出设备,计算机组成原理,第六章 计算机的运算方法,1、数据的表示方式 1.1、符号的处理（正数、负数）1.2、数值的处理（数制转换）1.3、小数点的处理（定点、浮点）1.4、原码的表示方法1.5、反码的表示方法 1.6、补码的表示方法（重点研究）1.8、移码的表示方法 1.8、字符、汉字的表示方法1.9、校验码,第六章 计算机的运算方法,机器数的表示方法,实际数的表示方法,研究在机器中怎样用二进制表示十进制数,研究哪种机器数的表示方法更利简化运算,逻辑电路,逻辑表达式,最简表达式,真值表,逻辑功能,化简,现代计算机不仅仅是处理数值领域的问题，还有大量非数值数据，比如：文字、字母及专用符号来表示文字语言，逻辑语言等。,1.8 字符的表示方法,非数值数据的有：ABCZ26个大写abcz26个小写+-()#*符号0129数字国际上广泛采用美国国家信息交换标准代码-ASCII 码（P214）用7位二进制编码表示，27=128字符。,ASCII字符编码表P214,表中编码符号的排列次序为 b7b6b5b4b3b2b1b0 b7恒等于“0”，b6b5b4为高位部分，b3b2b1b0为低位部分。,例如:“A”=0100 0001=（65）10=（41）H“；”=0011 1011=（59）10=（4B）H字符串是指连续的一串字符，它们占用内存中连续个存储单元.每个字节存放一个字符（字符以ASCII码表示）例如:字符串 IF AB THEN READ（C）象这样字符串存放在内存中，每个字节中存放相应字符的 ASCII码值，空格也占用一个字节的位置。,1.8 字符的表示方法,二进制代码只代表不同的字符，而无数值大小。,例如:字符串IF AB THEN READ（C）以ASCII码表示。格式如下：IF空A B空THEN 空READ（C）空7370326562663284726978328269656840674132这个语句需要20个字节来存放。,1.8 字符的表示方法,内存中真正存放的是ASCII码,1981年国家标准局GB2312信息交换汉字编码字符集收集了常用汉字6763个，分一级汉字库3755个，二级汉字库3008个。1、汉字的输入在计算机系统中使用汉字，首先要解决的问题是如何把汉字输入到计算机内，直接标准键盘进行输入，就必须为汉字设计编码。汉字编码方法：数字编码（区位码，国际区位码）拼音码（以汉语拼音基础的输入方法）字形码（五笔字形输入法）,1.8 汉字的表示方法,1）数字编码输入 优点：无重码，内部编码转换比较方便，每个编码长度都一样。缺点：记忆难。2）拼音码 以汉语拼音的输入方法，几乎掌握汉语拼音的人都可以使用。优点：不需要训练，不要记忆 缺点：汉字同音字太多，输入重码率很高，对输入影响速度。3）字型编码 以汉字的形状确定编码，汉字总数虽少，但它总是一笔一划组 成，全部汉字的部首和笔画是有限的，这就是五笔字型编码。优点：无重码，速度快4）其他输入法 在以上三种编码的基础上为了加快输入速度，发展词组输入，联想输入，王码输入，几何数码输入等多种快速输入方法。,1.8 汉字的表示方法,智能联想,2、汉字的存储 汉字的存储有两方面的含义：字形码的存储和汉字内码存储。字形码是以汉字点阵表示的汉字字形代码，它是汉字的输出形式存储。输出汉字点阵有16x16点阵，24X24点阵，32X32点阵。字形码点阵的信息量很大的，占用内存空间大，以16X16点阵为例，每个汉字要占用32个字节，二级汉字大约占256K字节。,1.8 汉字的表示方法,点阵只能用来构成字库，不能用于机器内存储。,汉字字形点阵及编码,1.8 汉字的表示方法,0000 0000 1000 00000000 0000 1000 00000010 0000 1000 00000001 0000 1000 00000001 0001 1111 11100000 0101 0000 00100000 1001 0100 0100,汉字内码:汉字ASCII码 使用汉字信息的存储、交换、检索等的机内代码，内码比字形点阵占用内存少，用二个字节表示一个汉字，汉字内码表示有许多种，要注意以下几点：1）码位尽量短，表示的汉字尽量多；2）码值要连续有序，以便于操作运算；3）表示两级6763个汉字，每个汉字用两个字节。,1.8 汉字的表示方法,3、汉字的输出 汉字的输出有显示输出（显示器）和打印输出（打印机）。在接口上都有字库。计算机以汉字内码的形式输出，打印机根据内码找到点阵再输出。所以，打印机内部必须有个字库。汉字字符必须和英文字符区分开，以免造成混淆。英文字符的机内代码是八位ASCII码，最高为“0”，汉字字符的机内代码是两个字节，最高位为“1”，区别于ASCII码。,1.8 汉字的表示方法,IBM PC机汉字显示原理,1.8 汉字的表示方法,1011010110111011,1、数据的表示方式 1.1、符号的处理（正数、负数）1.2、数值的处理（数制转换）1.3、小数点的处理（定点、浮点）1.4、原码的表示方法1.5、反码的表示方法 1.6、补码的表示方法（重点研究）1.8、移码的表示方法 1.8、字符、汉字的表示方法1.9、校验码,第六章 计算机的运算方法,机器数的表示方法,实际数的表示方法,数据在计算机中存取、传送，要求绝对正确，如果某一位出错，就不能得到正确的结果，但实际上由于某种随机干扰容易发生错误。比如：1）硬盘、软盘进行读写的时候，因为机械运动，容易出错；2）内存用的时间长了，老化了。所以计算机一开机检查内存。向内存写进数据再读出数据，反复检验几次是否出错。3）数据在总线上传送，因信号衰减、传输质量的问题或受潮。出错以后，要能够判断出来，哪一位出错了，并要检验过来。因此，为了提高计算机的可靠性，除了采用选用更高可靠性的器件，更好的生产工艺等措施之外，还可以从数据编码上想一些办法。,1.9、校验码,为了发现和校正错误，计算机广泛采用容错技术，现在的检验办法大多采用“冗余校验”：原始数据+校验位（冗余部分）将原始数据和校验位一起按某种规律编码，存入存储器或向外发送。当从存储器读出或者接收代码时，按同一编码规律进行译码或计算。然后，判断传输过程中是否有错，哪一位出错了。,传送码字=原始数据位+校验位,原始数据,结果数据,编码过程,译码过程,根据原始数据求得校验位，加上原始数据一并发送。,检查接收到的码字发现/改正错误，取出原始数据。,1.9、校验码,保证相同,用来发现一位数据出错，没有该错能力,介绍三种常用的校验码：1）奇偶检错码：（输入输出设备 P216）用于并行数据传送中，发现一位或奇数数据出错，没有纠错能力。2）汉明检错与纠错码：（内存的读写校验 P100）用于并行数据传送中，发现一位或两位数据出错，并纠错。3）循环冗余码：（硬盘的读写校验 P144）用于串行数据传送中，在网络传送数据时多用。,1.9、校验码,重点,重点,了解,1、奇偶检验码：用于并行传输、一位或奇数检错。P216 工作原理：在n位原始数据位上加上 1 位校验位，使得 n+1 位码字 中“1”的个数总保持为奇数（奇校验）或为偶数（偶校验）个。,1.9、校验码_ 1）奇偶检验,0001,10101,00101,00001,10001,0101,原始数据,新的码字,校验位,奇校验,偶校验,校验位,1、奇偶检验 发送端产生一个检验位，使“1”的个数是奇数（或偶数）并一起发送。接收端对读出或接收到的数据要进行奇偶性判别。若奇偶性规则被破坏，则出错，否则为正确。奇偶检验只能发现奇数个错，且不能纠错。统计表明：90%以上的错误能用奇偶检验法来实现。所以，奇偶检验是最简单、应用广泛的检验码。,1.9、校验码_ 1）奇偶检验,奇数个“1”相异或结果为“1”。偶数个“1”相异或结果为“0”。,Review:逻辑运算与数字逻辑电路,异或电路的特殊功能：奇偶检测电路,利用此特性可十分方便组成奇偶校验位的产生电路。也可十分方便组成奇偶校验码的检验电路。,B,A,D,C,P=0,奇偶检验位产生电路,奇校验码检测电路,检验输出,0,1,1,0,输入：ABCD=0110 则 P=0110=0接收：ABCDP=0 结果正确=1 结果出错,异或电路的特殊功能：奇偶检测电路,B,A,D,C,P,P,P=0,P=0,Review:逻辑运算与数字逻辑电路,1.9、校验码_ 2）汉明检验,2、汉明检验：用于并行传输、多位检错、纠错处理。工作原理：为 n 个数据位设立 k 个检验位。使 n+k 位组成的码字同时具有两个特性：1）能发现 n+k 位中任何一位出错，并改正；2）能发现 n+k 位中任何两位同时出错，无法纠正。,校验码的位数k和数据的位数n应满足关系：2kn+k+1,汉明码字=数据+校验位=HmHm-1H2H1（m=n+k）每个校验位Pi在汉明码中被分在位号2i-1的位置，其余各位为数据位，按从低向高逐位依次排列。例如:数据位 n=3，校验位 k=4，汉明码字位 m=7，4个校验位P4P3P2P1对应的汉明码位号应分别为：H7，H4，H2，H1（Pi的位号等于2i-1）P4只能放在H7一位上，它已经是汉明码的最高位了。其余为数据位 D3 D2 D1，则有如下排列关系：,1.9、校验码_ 2）汉明检验,2、汉明检验,n=3（数据位）D3D2D1k=4（校验位）P4P3P2P1,汉明码字 H7 H6 H5 H4 H3 H2 H1 汉明码字 P4 D3 D2 P3 D1 P2 P1,D3 D2 D1 P4 P3 P2 P11 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1,通过一张表分配不同的数据位组合来形成每个校验位的值。步骤一、准备工作：按次序排列数据位+校验位；分别在不同横行中的P1、P2、P3、P4各列写1；在最顶横行其他各列填写1；P1、P2、P3、P4的其他位置写0；,1.9、校验码_ 2）汉明检验,汉明码HmHm-1H2H1编码实现方案：,步骤二、为各校验位分配数据位组合：看表的低三横行右侧4列的编码值分别为：1（001）2（010）4（100）0（000）低3横行左侧3列各列填写合理的编码值，其规则为：使用没有在右侧4列的最小正整数值，即 3(011)5(101)6(110),6 5 3,0 4 2 1,D3 D2 D1 P4 P3 P2 P11 1 1 1 1 1 11 1 0 0 1 0 01 0 1 0 0 1 00 1 1 0 0 0 1,1.9、校验码_ 2）汉明检验,汉明码HmHm-1H2H1编码实现方案：,步骤三、写出各校验位的编码逻辑表达式：用P1、P2、P3、P4取值为 1 的横行中，取值为 1 的数据位 进行异或运算求得每个校验位的值，结果是：P1=D2D1，P2=D3D1，P3=D3D2 用其他各校验位及各数据位进行异或运算求得总校验位P4，用于区分无错、奇数位错、偶数位错 3 种情况。总校验位 P4=P3P2P1D3D2D1,D3 D2 D1 P4 P3 P2 P11 1 1 1 1 1 11 1 0 0 1 0 01 0 1 0 0 1 00 1 1 0 0 0 1,1.9、校验码_ 2）汉明检验,汉明码HmHm-1H2H1编码实现方案：,D3 D2 D1 P4 P3 P2 P11 1 1 1 1 1 11 1 0 0 1 0 01 0 1 0 0 1 00 1 1 0 0 0 1,P1=D2D1P2=D3 D1P3=D3D2,P4=P3P2P1D3D2D1,S1=P1 D2D1S2=P2 D3 D1S3=P3 D3D2S4=P4P3P2P1D3D2D1,如果有数据为 110，则算的：则 P1=1，P2=1，P3=0，P4=0,若 S4 S3 S2 S1=0000：无错,若S4 S3 S2 S1=1011：一位出错当3个S为1，且S4为1时。例如：仅D1错。,若S4 S3 S2 S1=0001：偶数出错当S4为0，且S3 S2 S1 不为000。例如：P2 D1错。,1.9、校验码_ 2）汉明检验,汉明码HmHm-1H2H1编码实现方案：,发送,编码方案,译码方案,P4 D3D2P3D1P2P1,0110011,最终通过S4 S3 S2 S1 四路信号的结果，判断传输的信号是否有误，哪位有误。,D7 D6 D5 D4 D3 D2 D1 P5 P4 P3 P2 P11 1 1 1 1 1 1 1 1 1 1 11 1 1 0 0 0 0 0 1 0 0 00 0 0 1 1 1 0 0 0 1 0 01 1 0 1 1 0 1 0 0 0 1 01 0 1 1 0 1 1 0 0 0 0 1,P1=D7 D5D4D2D1P2=D7 D6D4D3D1 P3=D4D3D2P4=D7D6D5,P5=P4 P3P2P1 D7D6 D5D4D3D2D1,1.9、校验码_ 2）汉明检验,例如：发送数据为1100101，求汉明码。（n=7，k=5）,11 10 9 7 6 5 3,0 8 4 2 1,汉明码排序为：P5 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1,Pi在2i-1,P1=D7 D5D4D2D1=1 0 0 0 1=0P2=D7 D6D4D3D1=1 1 0 1 1=0P3=D4D3D2=0 1 0=1P4=D7D6D5=1 1 0=0,P5=P4 P3P2P1 D7D6 D5D4D3D2D1=0 1 0 0 1 1 0 0 1 0 1=1,1.9、校验码_ 2）汉明检验,例如：发送数据为1100101，求汉明码。（n=7，k=5）,汉明码排序为：P5 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1,Pi在2i-1,按配偶原则（1的个数为偶数）:P1=0P2=0P3=1P4=0P5=1汉明码为111000101100,按配奇原则（1的个数为奇数个）:P1=1P2=1P3=0P4=1P5=0汉明码为011010100111,1.9、校验码_ 3）循环冗余码,对原始数据，用一多项式（通过查数学表得到）去除，除得的余数就是校验位的值。（这里的除是模2除法运算）数据位（n）+校验位（k）=新的码字(n+k),3、循环冗余码 CRC：用于串行数据传送中多位检错纠错处理。P144,模2运算：按位模2相加，运算时不考虑进位和借位。1）模2加：即按位加，可用异或逻辑实现。2）模2加与模2减的结果相同，即00=0，01=1，10=1，11=0。两个相同的数据的模2和为0。3）模2乘按模2加求部分积之和。4）模2除按模2减求部分余数。,模2除：被除数后先补上k-1个0；每求一位商，余数少一位。上商原则：被除数首位为1，商取1；首位为0，商取0。当余数位数小于除数位数时，该余数即为结果。,数据位 n=3，校验位 k=4 数据为 100，查数学表得到生成多项式 10111求出的校验值=1011循环校验码 CRC（n+k 位）=数据位n+校验位k=1001011,1.9、校验码_ 3）循环冗余码,3、循环冗余码 CRC,将收到的循环校验码 1001011 还用约定的生成多项式10111去除，如果码字无误则余数应为0，如有某一位出错，则余数不为0，不同位数出错余数不同。,1.9、校验码_ 3）循环冗余码,3、循环冗余码 CRC的译码与纠错,第六章 计算机的运算方法,2、定点加、减法运算与实现2.1、补码定点加、减运算2.2、溢出概念与检测方法2.3、补码定点加法器,注释：前面我们讨论了数的补码表示方法，采用补码表示，减法可用加法来实现，对设计硬件来讲，只要设计一个加法器就可以实现加、减运算了，不需要再配一个减法器了。,1、补码加法 两个补码数相加（连同符号位），和的补码等于两数补码之和。即：X+Y 补=X 补+Y 补2、补码减法 原则上讲：X-Y 补=X 补-Y 补 可见需要一个减法器，而现在只有加法器，如何得到 X-Y 补呢？我们可以根据补码加法公式推出：X-Y 补=X+（-Y）补=X 补+-Y 补 这样，减法的问题就归结到如何求-Y 补的问题了。-Y 补=/Y 补+1 也就是说：-Y 补 等于 Y 补连同符号位在内求反加1。,2.1、补码定点加、减运算,例1、Y=0.1010 Y补=0.1010-Y 补=1.0110例2、Y=-0.1010 Y补=1.0110-Y 补=0.1010例3、已知 X 补=0.0010，Y补=1.1010 求 X-Y 补=？解：X 补=0.0010+）-Y补=0.0110 X-Y 补=0.1000 这就是运算求得的正确结果。,2.1、补码定点加、减运算,例4、已知 X 补=1.1011，Y补=0.0110 求 X-Y 补=？解：X 补=1.1011+）-Y补=1.1010 Y补 是正数，-Y补 变成一负数 X-Y 补=11.0101 以2为模的情况下，符号位的进位1在机器中将会自动舍弃，故得出的就是正确的结果 X-Y 补。,2.1、补码定点加、减运算,第六章 计算机的运算方法,2、定点加、减法运算与实现2.1、补码定点加、减运算2.2、溢出概念与检测方法2.3、补码定点加法器,1）溢出的产生 例1：X 补=0.1011+）Y 补=0.0111 X+Y 补=1.0010 例2：X 补=1.0101+）Y补=1.1001 X+Y 补=0.1110,从例1例2中看出，两个正数相加，结果是一负数（符号位为1），而两个负数相加，结果是一个正数（符号位为0），显然结果错误。,2.2、溢出概念与检测方法,溢出原因分析：寄存器的位数一旦确定下来，就有了容量的限制，数值表示的范围就固定了。如果运算过程中数值位超出了机器允许表示的范围，跑到符号位上从而改变了符号的性质，就产生溢出。,符号位,数值位,显然，机器允许表示范围应该为+127 到-128 之间，大于 127 称为上溢或正溢出，小于-128 称为下溢或负溢出。,2.2、溢出概念与检测方法,2）溢出的判断方法 计算机只能判断溢出，不能处理溢出！下面介绍计算机判断溢出的方法。方法一：设 X补=X0 X1 X2 Xn，Y补=Y0 Y1 Y2 Yn，和（或差）为 S 补=S0 S1 S2 Sn。则溢出条件为：V=X0 Y0/S0+/X0/Y0 S0,2.2、溢出概念与检测方法,00.1001+00.0011 00.1100 不溢出,11.0111+11.1101 11.0100 不溢出,00.1101+00.1001 01.0110 正溢出,11.0011+11.0111 10.1010 负溢出,观察下列算式：,当运算结果两符号位的值不一致时，表示溢出，若设两符号位为 Sf1 和 Sf2，则：V=Sf1 Sf2,2）溢出的判断方法 方法二：采用变形补码（双符号位补码）,比喻：比如第一道河坝拦不住水了，就再设一道。,这种方法好，但是增加一个符号位后，数据表示范围缩小了，最好改进只设置一个符号位！,2.2、溢出概念与检测方法,2）溢出的判断方法 方法三：采用双高位判断 数值部分最高位产生的进位为Cs；（设置一触发器）符号位部分向上产生的进位为Cf。（设置一触发器）溢出条件公式：V=Cs Cf,0.1001+0.0011 0.1100 不溢出,1.0111+1.1101 1.0100 不溢出,0.1101+0.1001 1.0110 溢出,1.0011+1.0111 0.1010 溢出,Cf=0 Cs=0,Cf=1 Cs=1,Cf=0 Cs=1,Cf=1 Cs=0,2.2、溢出概念与检测方法,第六章 计算机的运算方法,2、定点加、减法运算与实现2.1、补码定点加、减运算2.2、溢出概念与检测方法2.3、补码定点加法器,设两寄存器中存放A，B两数，进行运算.A寄存器：A0.A1 A2 An B寄存器:B0.B1 B2 Bn 则：A+B=A0.A1 A2 An+B0.B1 B2 Bn A-B=A0.A1 A2 An+B0.B1 B2 Bn+0.0001,运算结果：A+B A AB A,累加器A：硬件要支持软件，软件中有循环程序设计，所以要设计累加器。SUM=1+2+3+4+5+100 S=S+X,2.3、补码定点加法器,X 补,Y 补,X+Y 补=X 补+Y 补,X-Y 补=X 补+/Y 补+1,CPA,2.3、补码定点加法器,+A,+B,-B,实现加法运算的逻辑示例,A+B A AB A,Q,/Q,2.3、补码定点加法减法器,对实现电路的补充说明：功能 所需要的控制信号加 ADD+A+B A CPA（写入）减 SUB+A/+B+1 A CPA（写入）,将两种功能的控制命令综合起来，得：+A=ADD 或 SUB+B=ADD/+B=SUB+1=SUB-A=ADD 或 SUBCPA=ADD 或 SUB,复习与作业,复习章节：第6章 计算机的运算方法6.3.2 加法与减法运算 作业：P291 19 补充考研真题：1、写出信息码01101110的汉明校验码，要求能指出和纠正一位出错位。（n=8,k=5,写出完整的校验过程。）,