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

,系 统 总 线,存储器,运算器,控制器,接口与通信,输入/输出设备, 计算机组成原理 ,第六章 计算机的运算方法,1、 数据的表示方式 1.1、符号的处理（正数、负数） 1.2、数值的处理（数制转换） 1.3、小数点的处理（定点、浮点） 1.4、原码的表示方法 1.5、反码的表示方法 1.6、补码的表示方法（重点研究） 1.8、移码的表示方法 1.8、字符、汉字的表示方法 1.9、校验码,第六章 计算机的运算方法,机器数的 表示方法,实际数的 表示方法,研究在机器中怎样用二进制表示十进制数,研究哪种机器数的表示方法更利简化运算,逻辑电路,逻辑表达式,最简表达式,真值表,逻辑功能,化简,现代计算机不仅仅是处理数值领域的问题，还有大量非数值数据，比如：文字、字母及专用符号来表示文字语言，逻辑语言等。,1.8 字符的表示方法,非数值数据的有： ABCZ 26个大写 abcz 26个小写 +-()#* 符号 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码表示。 格式如下： I F 空 A B 空 T H E N 空 R E A D （ C ） 空 73 70 32 65 62 66 32 84 72 69 78 32 82 69 65 68 40 67 41 32 这个语句需要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 0000 0000 0000 1000 0000 0010 0000 1000 0000 0001 0000 1000 0000 0001 0001 1111 1110 0000 0101 0000 0010 0000 1001 0100 0100 ,汉字内码: 汉字ASCII码 使用汉字信息的存储、交换、检索等的机内代码， 内码比字形点阵占用内存少，用二个字节表示一个汉字， 汉字内码表示有许多种，要注意以下几点： 1）码位尽量短，表示的汉字尽量多； 2）码值要连续有序，以便于操作运算； 3）表示两级6763个汉字，每个汉字用两个字节。,1.8 汉字的表示方法,3、汉字的输出 汉字的输出有显示输出（显示器）和打印输出（打印机）。 在接口上都有字库。 计算机以汉字内码的形式输出，打印机根据内码找到点阵再输出。 所以，打印机内部必须有个字库。 汉字字符必须和英文字符区分开，以免造成混淆。 英文字符的机内代码是八位ASCII码，最高为“0”， 汉字字符的机内代码是两个字节，最高位为“1”，区别于ASCII码。,1.8 汉字的表示方法,IBM PC机汉字显示原理,1.8 汉字的表示方法,10110101 10111011,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（数据位）D3D2D1 k=4（校验位）P4P3P2P1,汉明码字 H7 H6 H5 H4 H3 H2 H1 汉明码字 P4 D3 D2 P3 D1 P2 P1,D3 D2 D1 P4 P3 P2 P1 1 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 P1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 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 P1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1,1.9、校验码_ 2）汉明检验,汉明码HmHm-1H2H1编码实现方案：,D3 D2 D1 P4 P3 P2 P1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1,P1= D2D1 P2=D3 D1 P3=D3D2,P4=P3P2P1D3D2D1,S1= P1 D2D1 S2= P2 D3 D1 S3= P3 D3D2 S4=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 P1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1,P1= D7 D5D4D2D1 P2= D7 D6D4D3D1 P3= D4D3D2 P4= 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 = 0 P2= D7 D6D4D3D1 = 1 1 0 1 1 = 0 P3= D4D3D2 = 0 1 0 = 1 P4= 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=0 P2=0 P3=1 P4=0 P5=1 汉明码为111000101100,按配奇原则（1的个数为奇数个）: P1=1 P2=1 P3=0 P4=1 P5=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）溢出的判断方法 方法三：采用双高位