资源描述
第2章 运算方法和运算器,2020年8月12日星期三,2,目录,2.0 数据的类型 2.1 数据与文字的表示方法 （掌握） 2.2 定点加法、减法运算 （掌握） 2.3 定点乘法运算 （理解） 2.4 定点除法运算 （理解） 2.5 定点运算器的组成 （了解） 2.6 浮点运算方法和浮点运算器（掌握）,2020年8月12日星期三,3,学习要求,掌握定点和浮点数的表示方法，表示范围； 掌握定点数的补码加减法、常用的乘除法运算方法； 掌握浮点数的加减运算方法； 掌握数据校验的方法； 理解溢出判断方法； 清楚运算器部件的组成结构及设计方法。,2020年8月12日星期三,4,2.0 数据的类型（1/2）,按数制分： 十进制：在微机中直接运算困难； 二进制：占存储空间少，硬件上易于实现，易于运算； 十六进制：方便观察和使用； 二-十进制：4位二进制数表示1位十进制数，转换简单。 按数据格式分： 真值：没有经过编码的直观数据表示方式，其值可带正负号，任何数制均可； 机器数：符号化编码后的数值(包括正负号的表示)，一般位数固定(8、16、32)，不能随便忽略任何位置上的0或1；,2020年8月12日星期三,5,2.0 数据的类型（2/2）,按数据的表示范围分： 定点数：小数点位置固定，数据表示范围小； 浮点数：小数点位置不固定，数据表示范围较大。 按能否表示负数分： 无符号数：所有均为表示数值，直接用二进制数表示； 有符号数：有正负之分，最高位为符号位，其余位表示数值。 按编码不同又可分为原码、反码、补码、移码,2020年8月12日星期三,6,2.1 数据与文字的表示方法,2.1.1 数据格式 2.1.2 数的机器码表示 2.1.1 数据格式 2.1.3 字符与字符串的表示方法 2.1.4 汉字的表示方法 2.1.5 校验码,2020年8月12日星期三,7,定点数：小数点固定在某一位置的数据； 纯小数： 表示形式 有符号数 x=xSx-1x-2x-n 0 |x|1-2-n ;xs为符号位 无符号数 x=x-1x-2x-nx-(n+1) 0 x 1-2-n-1 ;无符号位 数据表示范围 0.00= 0 |x| 1-2-n = 0.11 纯整数： 表示形式 有符号数 x=x s x n-1 x 1 x 0 |x|2n-1 ;xs为符号位无符号数 x=x n x n-1 x 1 x 0 0 x2n+1-1 ;xn为数值位 注意：小数点的位置是机器约定好的，并没有实际的保存。,x0 x-1x-2x-3 x-n,xnxn-1xn-2x1x0,2.1.1 数据格式定点数,设采用n+1位数据,2020年8月12日星期三,8,定点机的特点,所能表示的数据范围小 使用不方便，运算精度较低 存储单元利用率低,2020年8月12日星期三,9,2.1.2 数的机器码表示（有符号数）,计算机中是不会存储+号的，那么怎么表示符号位呢，怎么让符号位同数值位一道参加运算呢。这就是怎么样把真值转换成机器码（原、反、补、移码） 重点： 1、原码、补码、移码的表示形式 2、补码的定义 3、原码、补码、移码的表示范围,2020年8月12日星期三,10,1、原码表示法定义,定义： 定点小数：x原 定点整数：x原 举例： +0.110 原 0.110 -0.110原 1 - (-0.110) = 1.110 +110原 0110 -110原 23- (-110) 1000 +110 = 1110,x1 x 0 x表示真值,1- x=1+|x| 0 x -1,x2n x 0 n表示数值位,2n- x=2n+|x| 0 x -2n,实际机器中保存时并不保存小数点，等到的就是机器码中的原码。,xn xn-1xn-2x1x0 Xn是符号位，0表示正，1表示负,2020年8月12日星期三,11,1、原码表示法特点,0有两种表示法 +0原 = 0000 ;-0原 = 1000 数据表示范围 定点小数：-1X1 定点整数: -2nX2n （若数值位n=3即：-8X8） 优点 与真值对应关系简单；符号位+真值的绝对值 缺点 参与运算复杂，需要将数值位与符号位分开考虑。减法麻烦,2020年8月12日星期三,12,要将指向5点的时钟调整到3点整，应如何处理？,5-2=3,5+10=3（12自动丢失。12就是模）,补码表示法的引入（1/3）,2020年8月12日星期三,13,继续推导： 5-2=5+10（MOD 12） 5+（-2）=5+10（MOD 12） -2=10（MOD 12） 结论：,在模为12的情况下，-2的补码就是10。一个负数用其补码代替，同样可以得到正确的运算结果。,补码表示法的引入（2/3）,2020年8月12日星期三,14,进一步结论： 在计算机中，机器能表示的数据位数是固定的，其运算都是有模运算。 若是n+1位整数(包含符号位)，则其模为2n+1； 若是小数，则其模为2。 若运算结果超出了计算机所能表示的数值范围，则只保留它的小于模的低n位的数值，超过n位的高位部分就自动舍弃了。,补码表示法的引入（3/3）,2020年8月12日星期三,15,2、补码表示法定义,定义： 定点小数： x补 定点整数： x补 举例： +0.110 补 0.110 -0.110 补 10 + (-0.110) = 1.010 +110补 0110 -110 补 24+(-110 ) 10000 -110 = 1010,x 1 x 0,2+x = 2 - |x| 0 x -1,x 2n x 0,2n+1+x = 2n+1-|x| 0 x -2n,x为n+1位,（mod 2） 模+真值,（mod 2n+1）,实际机器中保存时并不保存小数点,xnxn-1xn-2x1x0,2020年8月12日星期三,16,2、补码表示法特点,0有唯一的表示法 -0补 24+(-0 ) mod 24 0000 +0补 数据表示范围 定点小数：-1X1 定点整数: -2nX2n （若n=3，则-8X8） 加减运算规则 XY补X补 Y补 (mod 2) 只要结果不溢出，可将补码符号位与数值位一起参与运算。 x补补x原 补码除2操作，可通过算术右移实现 -0.0110补11010，则(-0.0110)/10补 = 11101，真值为-0.0011,比原码多一个负的最小值表示（定点小数和定点整数），其编码为1000,2020年8月12日星期三,17,n位二进制数x,则取反后应该是2n1x,再加1就是y=2n1x+1； y取反后应该是2n1y,再加1就是z=2n 1y+1; z =2n1(2n1x+1)+1=x;,2020年8月12日星期三,18,0的补码唯一 纯小数0和0的补码表示： +0补 -0补 20.000=0.000 纯整数0和0的补码表示： +0补 -0补 2n+1 000= 000,-1和-2n 的表示： -1补=2+(-1)=10.000+(-1.000)=1.000 - 2n补 = 2n+1 +(- 2n) = 10000+(-1000) = 1000,2020年8月12日星期三,19,由原码求补码,由原码求补码的简便原则(负数) 除符号位以外,其余各位按位取反，末位加1； 从最低位开始，遇到的第一个1以前的各位保持不变，之后各位取反。,例：X原= 1 1 0 1 1 0 1 0 0,X补=,1 0 1 0 0 1,1 0 0,2020年8月12日星期三,20,由X补求-X补 连符号位一起各位求反，末位加1。 例：X补=1.1010101 解:,由-X补求X补，此规则同样适用。,求相反数的补码,X补= 1 1 0 1 0 1 0 1,0 0 1 0 1 0 1 0,+,1,-X补= 0 0 1 0 1 0 1 1,2020年8月12日星期三,21,3、移码表示法,移码通常用于表示浮点数的阶码 用定点整数形式的移码 把真值平移2n个单位 定义：x移=2n+x2n x -2n 与x补的区别：符号位相反 优点： 可以比较直观地判断两个数据的大小； 浮点数运算时，容易进行对阶操作； 表示浮点数阶码时，容易判断是否下溢； 当阶码为全0时，浮点数下溢。,4位补码与移码,xnxn-1xn-2x1x0,2020年8月12日星期三,22,原、补、移码的编码形式,正数： 原、补码的编码完全相同； 补码和移码的符号位相反，数值位相同； 负数： 原码： 符号位为1 数值部分与真值的绝对值相同 补码： 符号位为1数值部分与原码各位相反，且末位加1 移码： 符号位与补码相反，数值位与补码相同,2020年8月12日星期三,23,课本P22例6以定点整数为例,用数轴形式说明原码、反码、补码、移码表示范围和可能的数码组合情况。,2020年8月12日星期三,24,2020年8月12日星期三,24,课本P22例7将十进制真值(127，1，0，1，127)列表表示成二进制数及原码、反码、补码、移码值。,符号位+0；- 1,数值位各位取反,数值位末位加1,符号位(正负数)取反,负数时,2020年8月12日星期三,25,P22例8设机器字长16位，定点表示，尾数15位，数符1位，问： (1)定点原码整数表示时，最大正数是多少？最小负数是多少？ (2)定点原码小数表示时，最大正数是多少？最小负数是多少？,(215-1) = +32767,-(215-1) = -32767,(1-2-15) = +(1-1/32768),-(1-2-15) = -(1-1/32768),定点原码整数 最大正数 最小负数 定点原码小数 最大正数 最小负数,2020年8月12日星期三,26,2.1.1 数据格式浮点数,浮点数：小数点位置可变，形如科学计数法中的数据表示。 浮点数格式定义： N= Re M M：尾数(mantissa) ，是一个纯小数（整数部分为0的小数），表示数据的全部有效数位，决定着数值的精度； R：基数(radix) ，可以取2、8、10、16，表示当前的数制； 微机中，一般默认为2，隐含表示。 e： 阶码(exponent) ，是一个整数，用于指出小数点在该数中的位置，决定着数据数值的大小。 机器数的一般表示形式,2020年8月12日星期三,27,科学计数法的表示,一个十进制数可以表示成不同的形式： 同理，一个二进制数也可以有多种表示：,2020年8月12日星期三,28,浮点数规格化,浮点数的表示 1.1120=0.11121=11.12-1 规格化的目的 保证浮点数表示的唯一性； 保留更多地有效数字，提高运算的精度。 规格化要求 1/R|尾数|1；R为基数，如2，即大于1/2 规格化处理： 尾数向左移n位(小数点右移)，同时阶码减n； 尾数向右移n位(小数点左移)，同时阶码加n。,右规,左规,2020年8月12日星期三,29,浮点数的规格化,尾数用原码表示时 尾数数值最高数值位为1； 尾数形如0.1（正）；或1.1（负）； 例如，0.01125要规格化则变为0.1124； 0.01125要规格化则变为1.1124； 尾数用补码表示时 尾数最高数值位和尾数符号位相反； 尾数形如0.1（正）；或1.0（负） 例如，0.01125要规格化，则变为0.1124； 0.01125要规格化，则变为1.0124；,2020年8月12日星期三,30,浮点数的数据表示范围 N= Re M,0,最大负数,最小正数,最小负数,最大正数,下溢区,上溢区,上溢区,负数区,正数区,浮点数的溢出：阶码溢出 上溢：阶码大于所能表示的最大值；无穷 下溢：阶码小于所能表示的最小值； 0 机器零： 尾数为 0，或阶码小于所能表示的最小值；,2e,0,2020年8月12日星期三,31,浮点数的最值 N= M Re,设浮点数格式为,移码表示-2m，+(2m-1),补码表示-1，+(1-2-n),-12+( 2m-1 ),-2-n2-2m,+2-n2-2m,+(1-2-n)2+(2m-1),1 ,111;1.0000,0,000;1.1111,0, 000;0.0001,1,111;0.1111,同左,同左,0 000;1 0111,-(2-1+2-n)2-2m,+2-12-2m,同左,同左,0 000;0 1000,2020年8月12日星期三,32,【例1】设浮点数的阶码6位（含符号位），尾数为10位（含符号位），阶码采用补码表示，尾数采用原码表示，分析其浮点数表示范围。,最大正数 N= MRe 最大正数为0.11120111 即（129）231 该浮点数即为规格化数形式；,阶码补码,尾数原码,2020年8月12日星期三,33,【例1】设浮点数的阶码6位（含符号位），尾数为10位（含符号位），阶码采用补码表示，尾数采用原码表示，分析其浮点数表示范围。,最小正数N= MRe 非规格化数形式 最小正数为0.0012100 即29 2（25）= 29 2-32 规格化数形式 最小正数为0.12100 21 2（25） 233,阶码补码,尾数原码,2020年8月12日星期三,34,【例1】设浮点数的阶码6位（含符号位），尾数为10位（含符号位），阶码采用补码表示，尾数采用原码表示，分析其浮点数表示范围。,最小负数N= MRe 最小负数为0.112011 即（129）2（251）= （129） 231 该浮点数即为规格化数形式；,阶码补码,尾数原码,2020年8月12日星期三,35,【例1】设浮点数的阶码6位（含符号位），尾数为10位（含符号位），阶码采用补码表示，尾数采用原码表示，分析其浮点数表示范围。,最大负数 非规格化数形式 最大负数为0.0012100 即 29 2（25）= 29 2-32 规格化数形式 最大负数为0. 12100 即 21 2（25）= 2-1 232,阶码补码,尾数原码,2020年8月12日星期三,36,【例2】设浮点数的阶码6位（含符号位），尾数为10位（含符号位），阶码和尾数均采用补码表示，分析其规格化浮点数表示范围。,最大正数 阶码最大、尾数最大 最大正数为0.1112111 （129）231 最小正数 （规格化后） 最小正数为0.1000232 即2-3221 2-33 注意：不是 因为0.01 2-32不是规格化数。,阶码补码,尾数补码,2020年8月12日星期三,37,【例2】设浮点数的阶码6位（含符号位），尾数为10位（含符号位），阶码和尾数均采用补码表示，分析其规格化浮点数表示范围。,最小的负数 最小负数为1.000231 即231（1）= 231 最大的负数 最大负数为0.1001232 即（ 29+ 21 ）232 注意：因有规格化要求，不是,阶码补码,尾数补码,2020年8月12日星期三,38,浮点数的IEEE754标准表示,IEEE（Institute of Electrical and Electronics Engineers） 美国电气及电子工程师学会 IEEE是一家总部在美国的工程技术和电子专家的组织； IEEE致力于电气、电子、计算机工程和与科学有关的领域的开发和研究，也是计算机网络标准的主要制定者。 为便于软件移植，按照 IEEE754 标准，实际机器内32位浮点数和64位浮点数的标准格式如下：,0,22,23,30,31,23位尾数，仅为数值部分,8位阶码，包括阶符,1位数符,32位浮点数,0,51,52,62,63,64位浮点数,11位阶码，包括阶符,52位尾数，仅为数值部分,1位数符,2020年8月12日星期三,39,32位浮点数的IEEE754 标准表示,数符S：表示浮点数的符号，占1位，0正数、1负数； 尾数M：23位，原码纯小数表示，小数点在尾数域的最前面； 由于原码表示的规格化浮点数要求，最高数值位始终为1，因此该标准中隐藏最高数值位(1)，尾数的实际值为1.M； 阶码E：8 位，采用有偏移值的移码表示； 移127码，即E=e+127，E的8位二进制数即为移127码的编码； 浮点数的真值：N=（-1）S（1.M）2E-127,阶码移码,尾数原码,2020年8月12日星期三,40,IEEE754 标准格式 （64位格式）,其真值表示为： x=（1）S（1.M）2E1023 eE1023,2020年8月12日星期三,41,IEEE754 标准的数据表示,IEEE754 标准中的阶码E 正零、负零 E与M均为零，正负之分由数据符号确定； 正无穷、负无穷 E为全1，M为全零，正负之分由数据符号确定； 阶码E的其余值（0000 00011111 1110）为规格化数据； 真正的指数e的范围为-126+127,E=0000 0000，M=0000 0000,E=1111 1111，M=0000 0000,0000 0000 1111 1111,2020年8月12日星期三,42,IEEE754 标准对特殊数据的表示,2020年8月12日星期三,43,课本P18 例1,例1 若浮点数的754标准存储格式为(41360000)16，求其浮点数的十进制数值。 解： (41360000)16 = 0100 0001 0011 0110 0000 0000 0000 0000 指数e=E-127= 1000 0010 0111 1111=0000 0011=3 尾数1.M=1.011 0110 0000 0000 0000 0000=1.011011 浮点数 N =（-1）S（1.M）2e = （-1）0（1. 011011）23 已经是标准化 = (11.375)10,数符S,阶码E,尾数M,2020年8月12日星期三,44,课本P18 例2,例2 将(20.59375)10转换成754标准的32位浮点数的二进制存储格式。 解： (20.59375)10(10100.10011)2 将尾数规范为1.M的形式： 10100.100111.01001001124e4 可得：M 010010011 S 0E 41271311000 0011 故，32位浮点数的754标准格式为： 0100 0001 1010 0100 1100 0000 0000 0000(41A4C000)16,2020年8月12日星期三,45,单精度浮点数与双精度浮点数,高级语言的float、double使用的即是IEEE754规定的格式。 float ：32位浮点值，也叫单精度浮点数（4字节保存） double：64位浮点值，也叫双精度浮点数（8字节保存） 单精度浮点数的例子：,1位 8位 7位 8位 8位,-1100,0.01,2020年8月12日星期三,46,单精度浮点数与双精度浮点数,除0之外，IEEE754标准中单精度浮点数所能表示的绝对值最小的规格化浮点数的格式为： S 0000 0001 00000000000000000000000 V=（-1）S2-126（1.M）= （-1）S2-126（1+0.000）,除之外，IEEE754标准中单精度浮点数所能表示的绝对值最大的规格化浮点数的格式为： S 1111 1110 11111111111111111111111 V=（-1）S2+127（1.M）= （-1）S2-126（1+1.111）,2020年8月12日星期三,47,求解技巧,例如：将下列十进制数表示成IEEE754格式的32位浮点数二进制存储形式。 27/32 11/512 求解： 27/32=27*(1/32) = (0001 1011)2*2-5 尾数：1.1011；阶码：e=-5+4=-1 ，E=e+127=126 IEEE754数据：0 0111 1110 1011 0000 0000 0000 0000 000 11/512= (0000 1011)2*2-9 尾数：1.011；阶码：e=-9+3=-6 ，E=e+127=121 IEEE754数据：0 0111 1001 0110 0000 0000 0000 0000 00,2020年8月12日星期三,48,例：将十进制数-54表示成二进制定点数(16位)和浮点数(16位，其中数值部分10位，阶码部分4位，阶符和数符各取1位)，并写出它在定点机和浮点机中的机器数形式。,令 x = -54，则x = -110110 16位定点数真值表示： x = -000 0000 0011 0110 定点机器数形式 x原： x补： 浮点数规格化表示：x = -(0.1101100000)2110 浮点机器数形式 x原： x补：,非IEEE754标准,1 000 0000 0011 0110,1 111 1111 1100 1010,0 0110 ; 1 11 0110 0000,0 0110 ; 1 00 1010 0000,2020年8月12日星期三,49,最大正数： x=1+(1-2-23) 2127 最小正数： x=1.0 2-128 最小负数： x=-1+(1-2-23) 2127 最大负数： x=-1.0 2-128,课本P23例9假设一个32位非零规格化浮点数，真值表示为：问：它所表示的规格化的最大正数、最小正数、最大负数、最小负数是多少？（尾数用原码表示，类似IEEE，但不是）,0,1111 1111 1111 1111 1111 111,1111 1111,0,0000 0000 0000 0000 0000 000,0000 0000,1,1111 1111 1111 1111 1111 111,1111 1111,1,0000 0000 0000 0000 0000 000,0000 0000,2020年8月12日星期三,50,浙江大学考研试题,计算机储存程序的特点之一是把数据和指令都作为二进制信号看待。今有一计算机字长32bit，数符位是第31bit；单精度浮点数格式如图所示。 对于二进制数1000 1111 1110 1111 1100 0000 0000 0000 表示一个补码整数，其十进制值是多少？ 表示一个无符号整数，其十进制值是多少？ 表示一个IEEE754标准的单精度浮点数，其值是多少？,2020年8月12日星期三,51,二进制数1000 1111 1110 1111 1100 0000 0000 0000,表示一个补码整数，其十进制值是多少？ 作为补码整数，其对应的原码是1111 0000 0001 0000 0100 0000 0000 0000 十进制值是 -（230+ 229 +228 + 220 + 214 ） 表示一个无符号整数，其十进制值是多少？ 作为无符号整数，其十进制值是231+ 227+ 226 +225 + 224 + 223+ 222 +221 + 219 +218 + 217 +216 + 215 +214,2020年8月12日星期三,52,二进制数1 000 1111 1 110 1111 1100 0000 0000 0000,作为IEEE754标准的单精度浮点数 阶码E是0001 1111 指数e阶码E1270001 11110111 1111 -1100000B-96D 尾数M=110 1111 1100 0000 0000 0000 则1.M=1. 110 1111 1100 0000 0000 0000=1.110 1111 11 单精度浮点数值为： X (-1)s1.M2e-(1.110 1111 11)2-96 -(0.1110 1111 11)2-95 -(1416-11516-21216-3)2-95 -0.31152-95,2020年8月12日星期三,53,2009考研真题,12.一个C语言程序在一台32位机器上运行。程序中定义了三个变量x，y和z，其中x和z是int型，y为short型。当x=127，y=-9时，执行赋值语句z=x+y后，x、y和z的值分别是： x=0000007FH , y=FFF9H , z=00000076H x=0000007FH , y=FFF9H , z=FFFF0076H x=0000007FH , y=FFF7H , z=FFFF0076H x=0000007FH , y=FFF7H , z=00000076H,2020年8月12日星期三,54,2010考研真题,14.假定变量i，f，d数据类型分别为int, float, double(int用补码表示，float和double用IEEE754单精度和双精度浮点数据格式表示)，已知i=785，f=1.5678e3，d=1.5e100，若在32位机器中执行下列关系表达式，则结果为真的是() (I) i=(int)(float)i (II)f=(float)(int)f (III)f=(float)(double)f (IV)(d+f)-d=f A. 仅I和II B. 仅I和III C. 仅II和III D. 仅III和IV,关键是“=”两端的数据类型是否一致！,2020年8月12日星期三,55,2.1.1数据格式十进制数串的表示方法,字符串形式 每个十进制数位占用一个字节； 除保存各数位，还需要指明该数存放的起始地址和总位数； 主要用于非数值计算的应用领域。 压缩的十进制数串形式 采用BCD（二 - 十编码）码表示，一个字节可存放两个十进制数位；4：1 节省存储空间，便于直接完成十进制数的算术运算； 用特殊的二进制编码表示数据正负，如1100正、1101负,2020年8月12日星期三,56,2.1.3 字符与字符串的表示方法,ASCII码(美国国家信息交换标准字符码) 包括128个字符，共需7位编码； ASCII码规定：最高位为0，余下7位作为128个字符的编码。 最高位的作用：奇偶校验；扩展编码。 字符串 指连续的一串字符， 每个字节存一个字符。 当存储字长为2、或4个字节时，在同一个存储单元中; 可按从低位字节向高位字节的顺序存放字符串的内容; 或按从高位字节向低位字节的次序顺序存放字符串的内容。,2020年8月12日星期三,57,2.1.4 汉字的表示方法,汉字的输入编码 目的：直接使用西文标准键盘把汉字输入到计算机 。 分类：主要有数字编码、拼音码 、字形编码三类。 汉字内码 用于汉字信息的存储、交换、检索等操作的机内代码 一般采用两个字节表示，为了和ASCII区别，最高位为1。 汉字字模码 用点阵表示的汉字字形代码，用于汉字的输出。,2020年8月12日星期三,58,中文编码,字符代码化（输入）,数字码 拼音码 字形码,2020年8月12日星期三,59,汉字字模码,2020年8月12日星期三,60,2.1.5 校验码（数据校验）,数据校验原因 为减少和避免数据在计算机系统运行或传送过程中发生错误，在数据的编码上提供了检错和纠错的支持。 数据校验码的定义 能够发现某些错误或具有自动纠错能力的数据编码； 也称检错码； 数据校验的基本原理是扩大码距； 码距：任意两个合法码之间不同的二进制位的最少位数； 仅有一位不同时，称其码距为1。,2020年8月12日星期三,61,码距及作用,设用四位二进制表示16种状态 16种编码都用到了，此时码距为1； 任何一种状态的四位码中的一位或几位出错，就变成另一个合法码； 无查错能力。 若用四位二进制表示8个状态 只用其中的8种编码，而把另8种编码作为非法编码； 可使码距扩大为2； 注意：并不是任选8种编码都可扩大码距；,2020年8月12日星期三,62,校验码的类型,奇偶校验码 判断数据中1的个数设置1位校验位； 分奇校验和偶校验两种，只能检错，无纠错能力； 海明校验码 在奇偶校验的基础上增加校验位而得； 具有检错和纠错的能力； 循环冗余校验码（CRC） 通过模2的除法运算建立数据信息和校验位之间的约定关系； 具有很强的检错纠错能力。,2020年8月12日星期三,63,奇偶校验码概念,奇偶校验原理 在数据中增加1个冗余位，使码距由1增加到2； 如果合法编码中有奇数个位发生了错误，就将成为非法代码。 增加的冗余位称为奇偶校验位。 校验的类型 偶校验：每个码字(包括校验位)中1的数目为偶数。 奇校验：每个码字(包括校验位)中1的数目为奇数。 校验过程 发送端：按照校验类型，在发送数据后添加校验位P； 接收端：对接收到的数据（包括校验位）进行同样类型的校验，决定数据传输中是否存在错误；,2020年8月12日星期三,64,奇偶校验码校验原理,偶校验：在接收端求校验位 P=D7D6D5D4D3D2 D1 D0 P 若P0，则无错；若P1，则有错。 奇校验：在接收端求校验位 P=D7D6D5D4D3D2 D1 D0 P 若P1，则无错；若P0，则有错。 电路实现： 一般采用异或电路得到校验位。,1010 1011,求校验码,偶校验码 1010 1011 1,奇校验码 1010 1011 0,2020年8月12日星期三,65,接收端,字,校验位,校验码,例1： 数据 0010 0001,奇校验码,0010 0001,1,偶校验码,0010 0001,0,例2：数据 ： 0111 0101,偶校验码,0111 0101,1,发送端,（门电路）,0110 0101,1,出错！,奇偶校验码 例题（1/2）,2020年8月12日星期三,66,例3：数据 ： 0111 0101,奇校验码,0111 0101,0,发送端,（门电路）,0110 0111,0,接收端,正确,奇偶校验只能发现 奇数个错误，且不能 纠正错误！,奇偶校验码例题（1/2）,2020年8月12日星期三,67,海明码,海明码是1950年提出的； 只要增加少数的几位校验码，即可检测出多位出错，并能自动恢复一或几位出错信息； 实现原理： 在一个数据中加入几个校验位，每个校验位和某几个特定的信息位构成偶校验的关系； 接收端对每个偶关系进行校验，产生校验因子； 通过校正因子区分无错和码字中的n个不同位置的错误； 不同代码位上的错误会得出不同的校验结果；,2020年8月12日星期三,68,海明码确定校验位的位数,设K为有效信息的位数，r为校验位的位数，则整个码字的位数N应满足不等式： NKr2r1 通常称为（N，K）海明码 设某(7,4)海明码表示的码字长度为 位，校验位数为 位。 例如：数据D3D2D1D0 =1001 K=4，r+5 2r ； 可知，需要校验位3位P3P2P1 ;,7,3,2020年8月12日星期三,69,海明码确定校验位的位置,数据表示 数据位D（DiDi-1D1D0） 、校验位P（PjPj-1P2P1） 海明码H （包括数据位和校验位）：HmHm-1H2H1； 分组原则 每个校验位Pi从低到高被分在海明码中位号2i-1的位置； 例如：数据D3D2D1D0 =1001，校验位P3P2P1 海明码共7位H7H6H2H1 ，各位分配如下：,P1,P2,P3,D0,D1,D2,D3,2020年8月12日星期三,70,海明码校验分组,校验原则 海明码的每一位Hi有多个校验位校验，其关系是被校验的每一位位号等于校验它的各校验位的位号之和； 每个信息位的位置写成用2的幂次之和的形式 ； 例如 H7参与H1、H2、H4的校验； H6参与H2、H4的校验； H5参与H1、H4的校验； H3参与H1、H2的校验； 分组情况,P1,P2,P3,D0,D1,D2,D3,第一组P1,第二组P2,第三组P3,第一组（P1、D3、D1、D0） 第二组（P2、D3、D2、D0 ） 第三组（P3、D3、D2、D1 ）,2020年8月12日星期三,71,海明码校验位的形成,校验位形成公式 P1第一组中所有位(除P1)求异或 Pj 第j组中所有位(除Pj)求异或 为了能检测两个错误，增加一位校验Pj1，放在最高位。 Pj 1所有位(包括P1，P2 ， ， Pj)求异或 例如： P1D3D1 D0 =1 0 1=0 P2D3D2 D0 =1 0 1=0 P3D3D2 D1 =1 0 0=1 P4D3D2D1D0P3P2P1=1001001=1,第一组（P1、D3、D1、D0） 第二组（P2、D3、D2、D0 ） 第三组（P3、D3、D2、D1 ）,但不能纠错！,2020年8月12日星期三,72,海明码接收端校验（1/2）,接收端接收到数据后，分别求S1，S2，S3，Sj S1第一组中所有位(包括P1)求异或 Sj第j组中所有位(包括Pj)求异或 Sj 1 Pj 1 所有位(包括P1，P2 ， ， Pj)求异或 当Sj 11时，有一位出错； 由Sj S3 S2S1 的编码指出出错位号，将其取反，即可纠错。 当Sj 10时，无错或有偶数个错（两个错的可能性比较大）； 当Sj S3 S2S1 0 0 00时，接收的数无错，否则有两个错。,2020年8月12日星期三,73,同上例，接收端接收的数据为 接收端求S S10101=0 S20101=0 S31100=0 S411001 100 =0 若接收端接收到错误的数据 S10101=0 S20111=1 S31110=1 S411101 100 =1,海明码接收端校验（2/2）,第一组（P1、D3、D1、D0） 第二组（P2、D3、D2、D0 ） 第三组（P3、D3、D2、D1 ）,无错误！,1,S4=1，有错误！ S3S2S1=110，H6位有错，应取反！,2020年8月12日星期三,74,【练习】设待校验的数据为D7D010101011，写出其海明校验码。,【解】 确定海明校验位的位数 因为K8， 由NKr 2r1，得9r 2r，校验位的位数为r4。 确定校验位的位置 i：12 11 10 9 8 7 6 5 4 3 2 1 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1 分组（N位分r组）,2020年8月12日星期三,75,【练习】设待校验的数据为D7D010101011，写出其海明校验码。,校验位的形成 P1=D6 D4 D3 D1 D0 1； P2=D6 D5 D3 D2 D0 1 P3=D7 D3 D2 D1 1 ； P4=D7 D6 D5 D4 0 所以，信息码10101011的海明校验码为：1010 0 101 1 1 11,2020年8月12日星期三,76,海明码的纠错与检错能力,一个系统能纠正一位差错时，码距最小是3； 码距为3时，或能纠正一位错，或能检测二位错； 但不能同时纠正一位错并检测二位错。 码距为1至7时，海明码的纠错和检错能力如右表： 码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。,2020年8月12日星期三,77,CRC校验,CRC的工作方法 在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端； 接收端收到的信息按发送端形成循环冗余码同样的算法进行校验； 若无错，则接收；若有错，需重发。 CRC的特点 可检测出所有奇数位错； 可检测出所有双比特的错； 可检测出所有小于、等于校验位长度的突发错。 CRC码的信息字段和校验字段的长度可以任意选定。,2020年8月12日星期三,78,2.2 定点加法、减法运算,2.2.1 补码加法 2.2.2 补码减法 2.2.3 溢出概念与检验方法 2.2.4 基本的二进制加法、减法器,2020年8月12日星期三,79,2.2.1 补码加法,补码加法运算基本公式 定点整数： x+y补 x补 + y补 （mod 2n+1）定点小数： x+y补 x补 + y补 （mod 2） 证明 （1）证明依据：补码的定义(以定点小数为例) （2）证明思路：分三种情况。 (a) x、y均为正值（0，0） (b) x、y一正一负（0，0 或者0） (c) x、y均为负值（0，0）,2020年8月12日星期三,80,补码加法公式证明（1/2）,证明： (a)0,0 补补补(mod 2) (b)0,0 x补=2+x , y补=2+y x补+ y补= 2+x+2+y =2+ (2+x+y) = 2+x+y补 （mod 2） = x+y补,2020年8月12日星期三,81,补码加法公式证明（2/2）,(c)0,0 (0的证明与此相同) x补=x , y补=2+y x补+ y补= x+2+y =2+ (x+y) 当x+y0时，2+(x+y) 2 ，进位2必丢失； 因(x+y) 0 ，故x补+y补= x+y =x+y补 (mod 2) 当x+y0时，2+(x+y) 2 因(x+y) 0 ，故x补+ y补= 2+(x+y) =x+y补 (mod 2),2020年8月12日星期三,82,定点数补码加法举例,例11 +1001, +0101， 求。 解： 补0 1001, 补0 0101 补 0 1001 补0 0101 补 0 1110 所以1110,例12 x1011, 0101, 求。 解： 补0 1011, 补1 1011 补0 1011 补1 1011 补 10 0110 所以+ 0110,2020年8月12日星期三,83,2.2.2 补码减法,补码减法运算基本公式 定点整数：x - y补x补 - y补x补 + -y补 （mod 2n+1） 定点小数：x - y补x补 - y补x补 + -y补 （mod 2） 证明：只需要证明 补补 已证明x+y补 x补 + y补 ，故y补x+y补x补 又xy补 x补 + y补 ，故y补xy补x补 可得y补 + y补x+y补+ xy补x补 x补 x + y + xy补x补 x补 x + x补x补 x补0 补等于补的各位取反，末位加1。,2020年8月12日星期三,84,定点数补码减法举例例13 已知1 1110，2 + 1101， 求：1补，1补，2补，2补。,解： 1补 1 0010 1补 1补1 0 11010 00010 1110 2补 0 1101 2补2补1 1 00100 00011 0011,注意课本上的错误！,注意课本上的错误！,2020年8月12日星期三,85,定点数补码减法举例 例14 1101，0110，求。,解: 补0 1101，补0 0110，补1 1010 补 补补 0 1101 1 1010 10 0111 0 0111 0111,0 1101,) 1 1010,1 0 0111,2020年8月12日星期三,86,2020年8月12日星期三,86,定点数补码加减法运算,基本公式 定点整数：x y补 x补 + y补 （mod 2n+1） 定点小数：x y补 x补 + y补 （mod 2） 定点数补码加减法运算 符号位和数值位可同等处理； 只要结果不溢出，将结果按2n+1或2取模，即为本次运算结果。,2020年8月12日星期三,87,例 设机器字长为8位，补1010 0011， 补0010 1101 ，求xy。,解: 补1101 0011 补 补补 1010 0011 1101 0011 1 0111 0110 0111 0110 118,1010 0011,) 1101 0011,1 0111 0110,x= 93，y= +45 计算过程中，产生了溢出！ 9345=-138 128,2020年8月12日星期三,88,2.2.3 溢出概念与检测方法,溢出 在定点数机器中，数的大小超出了定点数能表示的范围。 上溢 数据大于机器所能表示的最大正数； 下溢 数据小于机器所能表示的最小负数； 例如，4位补码表示的定点整数，范围为-8，+7 若x = 5，y = 4，则x+y产生上溢 若x = -5，y = -4，则x+y产生下溢 若x = 5，y = -4，则x-y产生上溢,2020年8月12日星期三,88,2020年8月12日星期三,89,例题,例15 +1011, +1001,求。 解:补0.1011 补0.1001 补0.1011 补0.1001 补1.0100,例16 -1101, -1111,求。 解:补1.0011 补1.0001 补1.0011 补1.0001 补 0.0101,正数+正数=负数,负数+负数=正数,溢出！,2020年8月12日星期三,90,溢出判别方法直接判别法,方法： 同号补码相加，结果符号位与加数相反； 异号补码相减，结果符号位与减数相同； 特点：硬件实现较复杂； 举例： 若x补=0101，y补=0100，则x+y补=1001 若x补=1011，y补=1100，则x+y补=0111 若x补=0101，y补=1100 ，则x-y补=1001,上溢,下溢,上溢,2020年8月12日星期三,91,溢出判别方法变形补码判别法,变形补码，也叫模4补码：采用双符号位表示补码 判别方法： 特点：硬件实现简单，只需对结果符号位进行异或 举例： 若x补=00101，y补=00100，则x+y补=01001 若x补=11011，y补=11100，则x+y补=10111 若x补=00101，y补=11100 ，则x-y补=01001,上溢,下溢,上溢,2020年8月12日星期三,92,2020年8月12日星期三,92,溢出判别方法进位判别法,0101,) 0100,1001,1,0,0001,) 0100,0101,0,0,V=01=1,V=00=0,判别方法： 最高数值位的进位与符号位的进位是否相同； 判别公式 溢出标志V=Cf Cn-1 其中Cf为符号位产生的进位， Cn-1为最高数值位产生的进位。 举例：,2020年8月12日星期三,93,回顾逻辑门图形符号,2020年8月12日星期三,94,2.2.4 基本的二进制加法/减法器,一位二进制数据的半加器： 加数：Ai、Bi 结果：Si（和） Ci+1（本位向高位的进位） 一位半加器示意图：,一位二进制数据的全加器： 加数：Ai、Bi Ci（低位向本位的进位） 结果：Si（和） Ci+1（本位向高位的进位） 一位全加器示意图：,2020年8月12日星期三,95,一位二进制数据的全加器的逻辑结构,全加运算的真值表如右所示： 两个输出端的逻辑表达式 SiAiBiCi Ci1AiBiBiCiCiAi 全加器逻辑结构：,3T+1T+1T,3T+3T,2020年8月12日星期三,96,多位二进制数据加法器,两个n位的数据A=An-1An-2A1A0，B=Bn-1Bn-2B1B0 和S=Sn-1Sn-2S1S0 采用进位判别法判断运算的溢出： V=CnCn-1,2020年8月12日星期三,97,多位二进制数据加法/减法器,将减法转换成加法 A补 - B补 A补 + -B补 由B补 求-B补 B补 求各位取反，末位加1； 将加减法电路合二为一 使用异或运算； 当M=0时，Bi=Bi 当M=1时，Bi=Bi ；,2020年8月12日星期三,98,多位二进制数据加法/减法器,3T+5T =1*2T+6T,(1*2T+6T)+2T =2*2T+6T,(n-1)*2T+6T,(n*2T+6T)+3T =2nT+9T,动画演示： 2-1.swf,n*2T+6T,2020年8月12日星期三,99,多位二进制加法/减法器的输出延迟,假如每位均采用一位全加器并考虑溢出检测，n位行波进位加法器的延迟时间ta为： tan*2T9T(2n9)T 如果不考虑溢出，则延迟时间ta由Sn-1的输出延迟决定： ta (n-1)*2T6T + 3T (2(n-1)9)T 延迟时间ta 输入稳定后，在最坏情况下加法器得到稳定的输出所需的最长时间。 显然这个时间越小越好。,2020年8月12日星期三,100,2.3 定点乘法运算,2.3.0 串行乘法 2.3.1 原码并行乘法 2.3.2 直接补码并行乘法,2020年8月12日星期三,101,2.3.0 串行乘法,1. 分析笔算乘法,A = 0.1101 B = 0.1011,AB = 0.10001111,0 . 1 1 0 1,0 . 1 0 1 1,1 1 0 1,1 1 0 1,0 0 0 0,1 1 0 1,0 . 1 0 0 0 1 1 1 1,符号位单独处理,乘数的某一位决定是否加被乘数,4个位积一起相加,乘积的位数扩大一倍,乘积的符号心算求得,？,2020年8月12日星期三,102,A B = A 0.1011,= 0.1A + 0.00A + 0.001A +0.0001A,= 0.1A + 0.00A + 0.001( A +0.1A),= 0.1A + 0.010 A + 0. 1( A +0.1A),= 0.1A +0.1 0 A+0.1(A + 0.1A),= 2-1A +2-1 0 A+2-1(A + 2-1(A+0),第一步 被乘数A + 0,第二步 部分积右移1位，得新的部分积,第八步 部分积右移1位，得结果,第三步 部分积 + 被乘数,2. 笔算乘法改进,2020年8月12日星期三,103,0 . 0 0 0 0,0 . 1 1 0 1,0 . 1 1 0 1,0 . 1 1 0 1,0 . 0 0 0 0,0 . 1 1 0 1,初态，部分积 = 0,乘数为 1，加被乘数,乘数为 1，加被乘数,乘数为 0，加 0,乘数为 1，加 被乘数,3. 改进后的笔算乘法过程（竖式）,2020年8月12日星期三,104,小结,乘法运算 加法移位。 若乘数数值位n = 4，则累加 4 次，移位4 次； 乘法过程 由乘数的末位决定被乘数是否与原部分积相加; 被乘数只与部分积的高位相加 部分积右移一位形成新的部分积; 同时乘数右移一位（末位移丢）; 空出高位存放部分积的低位。 硬件构成 3个具有移位功能的寄存器、一个全加器,2020年8月12日星期三,105,A、X、Q 均 n+1 位，移位和加受末位乘数控制,串行乘法的硬件配置,运算前为： n+1位部分积 初值为0 运算后为： 乘积高n+1位,被乘数 乘运算时用到的加数,运算前为： n+1位乘数 运算后为： 乘积低n+1位,2020年8月12日星期三,106,常用的串行乘法运算,原码乘法（符号位和数值位必须分开计算） 原码一位乘 一次判断1位，需判断n次（乘数位数为n）； 原码两位乘 一次判断2位，可提高乘法的运算速度； 补码乘法（符号位和数值位可以等同处理） 补码一位乘 结果修正法需区分乘数正负号，复杂 Booth算法比较法，符号位直接参与运算 补码两位乘,2020年8月12日星期三,107,原码一位乘法,设XXf . X1X2Xn， YYf . Y1Y2Yn，乘积的符号位为Pf，则 PfXfYf |P|X|Y| 求|P|的运算规则如下 被乘数和乘数均取绝对值参加运算，符号位单独考虑； 被乘数取双符号位，部分积的长度同被乘数，初值为0； 从乘数的最低位Yn开始判断： 若Yn1，则部分积加上被乘数|X|，然后右移一位； 若Yn0，则部分积加上0，然后右移一位。 重复，判断n次,例 题,2020年8月12日星期三,108,部分积 乘数 Yn 说 明 0 0. 0 0 0 0 0. 1 0 1 1,例1.若X=0.1101，Y=-0.1011，用原码一位乘法求XY原。,【解答】|X|=00.1101（用双符号位表示），|Y|=0.1011（用单符号位）, 0 0. 1 0 0 0 1 1 1 1 0 右移一位得P4,由于Pf=XfYf=01=1，|P|X|*|Y|=0.10001111，XY原= 1.1000111
展开阅读全文