第2章运算方法与运算器ppt课件.ppt

《第2章运算方法与运算器ppt课件.ppt》由会员分享，可在线阅读，更多相关《第2章运算方法与运算器ppt课件.ppt（97页珍藏版）》请在三一文库上搜索。

1、第 2 章 运算方法与运算器,2,计算机内部信息,信息,控制信息,数据信息,指令,控制字,数值型数据,非数值型数据,定点数,浮点数,数 字,字 符,汉 字,数据信息化的表示方法,计算机内部流动的信息：控制信息（指令）；数据信息（数值信息、非数值信息）。 数值信息：（定点数、浮点数）机器数（原码、反码、补码、移码）。 非数值信息：BCD码（表示十进制数）；ASCII码（表示西文字符）；国标码（表示汉字）；声音；图像（音频、视频）等编码。 对于所有信息在传送时进行抗干扰编码奇偶校验编码、海明校验编码、CRC校验编码。,4,2.0 数制与数制转换,任何 R 进制数 N 均可表示为 (N)RK-mR-

2、m K-1R-1K0R0K1R1 KnRn R：基值。表示系数Ki可以取0，1，R-1共R个数字并且是逢R进一的。 Ri：位权值。KiRi表示Ki在数列中所代表的实际数值。 任何进位计数制都具有两个基本因素：基值和位权值。,5,计算机中常用进位计数制 二进制 数字： 0，1 进位方式： 逢二进一 后缀：B 如10100011B 八进制 数字：0，1，2，3，4，5，6，7 进位方式： 逢八进一 后缀：O 或 Q 如137.67Q,6,十进制 数字：0，1，2，3，4，5，6，7，8，9 进位方式：逢十进一 后缀：D 或 无 如1357.26 十六进制 数字： 0，1，2，3，4，5，6，7，8

3、，9，A，B，C，D，E，F 进位方式：逢十六进一 后缀：H 如 19BF.36EH,7,数制转换原则：,若 两个有理数相等= 则 这两个有理数的整数部分、小数部分应分别相等。 因此，数制转换原则为：,整数部分、小数部分、分别进行转换,8,1. 任意进制数转换为十进制数,方法：按权展开相加。即利用按位展开公式将系数与位权值相乘后求和。 例1. 将二进制数10110011.10111转换为十进制数。 (10110011.10111)2 272524212021232425 1283216210.50.1250.06250.03125 (179.71875)10,9,例2.将八进制数263.56转

4、换为十进制数。 (263.56)8 282681380581682 1284830.6250.09375 (179.71875)10 例3.将十六进制数B3.B8转换为十进制数。 (B3.B8)16 B1613160B1618162 111613160111618162 17630.68750.03125 (179.71875)10,10,2.十进制数转换为任意进制数,转换方法：整数部分除基取余 把被转换的十进制整数除以基数R，取其余数即为R进制整数的最低位的数字。 再用基数R去除前次所得的商，所得余数即为R进制整数相应位的数字。 重复，直到商为0为止。 转换方法：小数部分乘基取整 把被转换的

5、十进制小数乘以基数R，取乘积的整数部分作为R进制小数的最高位的数字。 再用基数R乘前一步乘积的小数部分，取新的乘积的整数部分为R进制小数相应位的数字。 重复，直到乘积的小数部分为。或求得所要求的位数为止。,11,例3. 将(233.8125)10转换为二进制数。 整数部分 2 233 1 余数 2 116 0 2 58 0 2 29 1 2 14 0 2 7 1 2 3 1 2 1 1 0 (233)10(11101001)2,12,小数部分 0.8125 2 1.6250 2 1.2500 2 0.5000 2 1.0000 (0.8125)10(0.1101)2 (233.8125)10(

6、11101001.1101)2,13,例4. 将(233.8125)10转换为十六进制数。 整数部分 16 233 9 16 14 14 0 小数部分 0.8125 16 4.8750 16 13.0000 (233.8125)10(E9.4D)16,14,3. 二、八、十六进制数之间的转换,因为1624，823 二进制数与八进制数之间的转换方法： 整数部分从最低有效位开始，每三位二进制数对应一位八进制数，不足三位高位补“0”。 小数部分从最高有效位开始，每三位二进制数对应一位八进制数，不足三位，低位补“0”。 二进制与十六进制数间的转换方法： 整数部分从最低有效位开始，每四位二进制数对应一位

7、十六进制数，不足四位高位补“0”。 小数部分从最高有效位开始，每四位二进制数对应一位十六进制数，不足四位低位补“0”。,15,例5. 将转换(1011100.10111)2为八进制和十六进制数。 001011100.101110 1 3 4 . 5 6 (1011100.10111)2(134.56)8 01011100.10111000 5 C . B 8 (1011100.10111)2(5C.B8)16,2.1 数据信息的表示方法,2.1.1 数值数据编码的表示方法 2.1.2 非数值数据编码的表示方法 2.1.3 信息抗干扰编码的表示方法,2.1.1 数值数据的表示,符号,数值部分,真

8、值与机器数,真值与机器数,例：设机器字为8b字长， 数N1的真值为（+1100100）2， 数N2的真值为（-1100100）2， 则N1 、N2对应的机器数为：,2.机器数的编码表示,通常有四种表示法： 原码表示法 补码表示法 反码表示法 移码表示法,（1）原码表示法,保持原有的数值部分的形式不变，只将符号用二进制代码表示。 原码表示是最简单的机器数表示方法。 纯小数原码表示定义 纯整数原码表示定义,原码,纯小数原码表示定义,纯小数时，设 x=x0. x1 x2 xn ，其中x0为符号位，共n+1位字长，则,例如，若x1=+0.1011 x2=-0.1011， 字长为8b，则其原码分别为：

9、x1原=0.1011000 x2原=1 + 0.1011000 =1.1011000,零的原码有正零和负零两种形式： +0原=0.00 00 -0原 =1.00 00,纯整数原码表示定义,纯整数时，设 x=x0x1 x2 xn ，其中x0为符号位，共n+1位字长，则,例如，若x1=+1011 x2=-1011， 字长为8b，则其原码分别为： x1原=00001011 x2原= 27+ 00001011 =10001011,零的原码有正零和负零两种形式： +0原=000 00 -0原 =100 00,原码的特点： 采用原码表示法简单易懂，适用于表示带符号数。 它的最大缺点是零有两种表示形式：+0

10、与-0。故不能用于加/减运算。,（2）补码表示法,计算机中，运算结果模数时，说明该值已超出机器的表示范围，模数自然丢掉。,模/模数：计算器具的容量。,计算机中，机器数表示数据的字长即位数是固定的。,n+1位数的模数= n+1位数全为1后，再在最末位加1,n位整数的模数=2n+1 n位小数的模数=2,25,补码概念的导入,引入补码的目的是为了解决机器数的运算问题。 补码概念的导入：根据运算时“模”的概念，以机器钟为例 525+ -2补=5103 （Mod 12） 对于某一确定的模，某数减去一个数，可以用加上那个数的负数的补数来代替。 x补Mx （Mod M） 当x0时，Mx 大于M，把M丢掉，所

11、以x补x ，即正数的补数等于其本身。 当x0时，x补MxM|x|，所以负数的补数等于模与该数绝对值之差。,纯小数补码表示定义,纯小数时，设 x=x0. x1 x2 xn-1 ，其中x0为符号位，共n位字长，则,例如，若x1=+0.1011 x2=-0.1011， 字长为8b，则其补码分别为： x1补=0.1011000 x2补=2 - 0.1011000 =1.0101000,补码的零只有一个，即0.0000000。 补码1.0000000表示负1,(mod 2),纯整数补码表示定义,纯整数时，设 x=x0x1 x2 xn-1 ，其中x0为符号位，共n位字长，则,例如，若x1=+1011 x2

12、=-1011， 字长为8b，则其补码分别为： x1补=00001011 x2补= 28-00001011 =11110101,(mod 2n+1),对补码进行运算，可将加、减运算统一成加法运算，降低了对计算机运算器的要求，因此得到广泛的应用。,原码求补码的方法： 正数，不变（相同）即原码=补码； 负数，符号位不变，数值位按位取反加1。,补码求真值方法： 正数， x补= x原 负数，对 x补补= x原 原码求真值：x原符号位0+，1 。,（3）反码表示法,对于正数来说，反码=原码=补码。 对于负数来说， 符号位：与原码、补码的符号位定义相同。 数值：将原码的数值位按位变反。 例如，若x1=+0.

13、1011 x2=-0.1011， 字长为8b。 x1反=0.1011000= x1原= x1补 x2反=1.0100111 x2补=1.0101000 x2原=1.1011000 反码的零有两个0.0000和1.11111,（4）移码,移码也叫增码，常用来表示整数形式的计算机浮点数的阶码（表示指数）。 若纯整数X为n位（包括符号位），则其移码定义为： x移=2n+x补 -2nX2n-1,方法：补码将符号位求反可得移码 设字长为8b，若x1=+1000(2)， x2=-1000(2)， x1补=00001000 x1移=10001000 x2补=11111000 x2移=01111000,原、反

14、、补、移码转换方法,正数 原码=反码=补码 移码=补码符号位取反，数值位不变 负数 反码=原码符号位不变，数值位取反 补码=反码末位加1 移码=补码符号位取反，数值位不变,数的定点表示,计算机中小数的小数点并不是用某个数字来表示的，而是用隐含的小数点的位置来表示。 根据小数点的位置是否固定，又可分为 定点表示 定点小数表示形式 定点整数表示形式 浮点表示,数的定点表示, 定点小数 将小数点固定在符号位df之后、数值最高位d-1之前，这就是定点小数形式。其格式如下所示：, 定点整数 将小数点固定在数的最低位d0之后，这就是定点整数形式。其格式如下所示：,设字长为8b，用原码表示时，其表示范围如下

15、： 最小负数 最大负数 最小正数 最大正数 1.1111111 1.0000001 0.0000001 0.1111111 -（1-2） -27 27 1-27,定点小数的表示范围：,设字长为8b，用补码表示时，其表示范围如下： 最小负数 最大负数 最小正数 最大正数 1.0000000 1.1111111 0.0000001 0.1111111 -1 -27 27 1-27,设字长为8b，用原码表示时，其表示范围如下： 最小负数 最大负数 最小正数 最大正数 11111111 10000001 00000001 01111111 -（27-1）=-127 -1 +1 27-1=127 设字长

16、为8b，用补码表示时，其表示范围如下： 最小负数 最大负数 最小正数 最大正数 10000000 11111111 00000001 01111111 -27=-128 -1 +1 27-1=127,定点整数的表示范围：,数的浮点表示法,浮点表示法把字长分成阶码（表示指数）和尾数（表示数值）两部分。X=DRE 阶码E：用整数形式表示，指明小数点在数据中的位置，决定了浮点数的表示范围。 尾数D：用定点小数表示，给出有效数字的位数决定了浮点数的表示精度； 阶码的底R：一般为2、8或16 ，且隐含规定，在浮点数表示中不出现，通常取2；, 浮点数的表示格式,决定范围,决定精度,第一种浮点格式,浮点数另

17、一种格式：,存储的数X可表示为X=D2E。,39,(2) 浮点数的规格化,浮点数采用规格化表示方法的目的： 为了提高运算精度，充分利用尾数的有效数位。 为了浮点数表示的唯一性。 例：0.100100230.00100125 对于二进制数，就是要满足,浮点数规格化,原码规格化后 正数为 0.1的形式。 负数为 1.1的形式。 补码规格化后 正数为 0.1的形式。 负数为 1.0的形式。,通过调整阶码，使其尾数D满足下面形式的数：,当尾数的值不为 0 时，尾数域的最高有效位应为1，否则以修改阶码同时左右移小数点的办法，使其变成这一表示形式。,41,规格化数的定义,浮点数的尾数D满足 的数为规格化数

18、。 原码表示的规格化数 对于D原Sf.S1S2Sn，则其规格化标志是： S1 1 即：D原0.1xxx 或 D原1.1xxx 补码表示的规格化数 对于D补Sf.S1S2Sn，其规格化标志是： SfS11 即：D补0.1xxx 或 D补1.0xxx, 浮点数的表示举例,某机用16b表示一个数，阶码部分占8b（含一位符号位），尾数部分占8b（含一位符号位）。设x1=-100 ，x2=127/256，试写出x1和x2的两种浮点数表示格式。,例2.1, x1=-100= -（01100100.）2=-270.1100100 阶码的补码为（+7）补=00000111 阶码的移码为（+7）移=100001

19、11 尾数=1.0011100 （规格化补码） 第一种浮点表示的格式为 00000111，1.0011100 第二种浮点表示的格式为 1，10000111，0011100,解：,移码,补码, x2=127/256=（1111111）22-8 = 2-10.1111111 阶码的补码为（-1）补=11111111 阶码的移码为（-1）移=01111111 尾数=0.1111111（规格化补码） 第一种浮点表示的格式为 11111111，0.1111111 第二种浮点表示的格式为 0，01111111，1111111,解, 浮点数的表示范围,设阶码和尾数各为4b（各包含一个符号位），则其浮点数的表

20、示表示范围分别为：,最小负数 最大负数 最小正数 最大正数 201111.000 210001.011 210000.100 201110.111 211111.000 200001.011 200000.100 211110.111 -271 -2-8（23+21 ） 2-821 27（1-23）,规格化浮点数表示范围,二进制补码,阶码用移码,十进制真值,(5) 溢出问题,定点数判断溢出的办法是对数值本身进行判断， 浮点数是对规格化后的阶码进行判断。 当浮点数阶码大于机器的最大阶码，称为上溢； 机器产生上溢时，不能再继续运算，一般要进行中断处理。 而小于最小阶码时，称为下溢。 出现下溢时，一

21、般规定把浮点数各位强迫为零(当做零处理)，机器仍可继续进行运算。,2.1.2 非数值数据的表示,非数值数据：文字和符号（字符）、图像、声音等 非数值数据的表示：对其进行二进制编码 1、字符编码 BCD ASCII 2、汉字编码,1、字符编码,字符的表示：采用字符编码，即用规定的二进制数表示文字和符号的方法。 ASCII码(American Standard Code For Information Interchange) ：美国标准信息交换码，为国际标准。,常用的7位ASCII码的每个字符都由7个二进制位b6b0 表示，有128个编码，最多可表示128种字符；其中包括： 10个数字09：30

22、H39H，顺序排列 26个大写字母AZ：41H5AH ，顺序排列 26个小写字母az：61H7AH ，顺序排列 各种运算符号和标点符号等。,其中95个编码，对应着计算机终端能敲入并且可以显示的95个字符，打印机设备也能打印这95个字符，如大小写各26个英文字母，09这10个数字符，通用的运算符和标点符号，*，/， 等等。,在计算机中，用1B（一个字节）表示一个ASCII码，其最高一位(b7位)填0，余下的7b可以给出128个编码，表示128个不同的字符和控制码。,另外的33个字符，其编码值为031和127，则不对应任何一个可以显示或打印的实际字符，它们被用作控制码，控制计算机某些外围设备的工作

23、特性和某些计算机软件的运行情况。,ASCII码编码表,53,二十进制码（BCD码）,BCD（Binary Coded Decimal）码：使用二进制来编码十进制数字09。 编码方法：一般使用4位二进制编码来表示1位十进制数字，在16个编码中选用10个来表示数字09。不同的选择构成不同的BCD码 。,54,几种常见的BCD码,8421码： 特点：4位二进制数位的权从高到低依次是8、4、2、1；8421码实际上就是十进制数字09的二进制编码本身。 是最常用的一种BCD码，在没有特别指出的一般情况下，所提到的BCD码通常就是指8421码。 余3码：对应的8421码加上0011构成的。,55,十进制数

24、串的表示方法,非压缩格式字符串形式： 用ASCII码来表示十进制数字或符号位，即1个字节存放1位十进制数字或符号位。 字符n ；字符2；字符1； 定义：用一个字节存放一个十进制BCD码和标志符。 格式：标志BCD 例： 35H； 05H 特点： 存储单元利用率低，1个n位数串需占用n个连续单元存储。 该格式主要用于数串的输入与输出。,56,十进制数串的表示方法,压缩格式的字符串形式： 用BCD码来表示十进制数字，即1个字节存放2个十进制的数字；符号位放在最低位数字位之后:一般用 B（1011）表示正号;用 D（1101）表示负号。 例如 258被表示成258BH，占用两个字节，-34被表示为0

25、34DH，也占用两个字节。 定义：用一个字节存放2个十进制BCD码数位 特点： 存储单元利用率高。 可用于BCD串的存储和算术运算。 共同点：必须给出它在主存中的首地址和位长。,57,十进制数串的表示方法,采用十进制表示数据的优点是： 对于需要大量地进行输入输出数据而运算简单的场合，大大减少了十二和二十转换，提高了机器的运行效率； 十进制数串的位长可变，许多机器中规定该长度从0到31，有的甚至更长。不受定点数和浮点数统一格式的约束，从而提高了数据的表示范围和运算精度。,2、汉字编码,对于汉字，计算机的处理技术必须解决三个问题： 汉字输入 汉字存储与交换 汉字输出 它们分别对应着汉字输入码、内码

26、、字模码的概念。 因此，汉字编码系统存在以下三种编码： 1、汉字输入码 2、汉字内码 3、汉字字模码,（1）汉字输入码,汉字输入码也称外码，是为了将汉字输入计算机而编制的代码，是代表某一汉字的一串键盘符号。 汉字输入码种类： 数字编码：如区位码、国标码等。 拼音编码：如全拼码、双拼码、简拼码、智能ABC等。 。 字形编码：如王码五笔、郑码等。,（1）汉字输入码,两种典型的数字编码： 区位码：是将国家标准局公布的6763个两级汉字分为94个区，每个区分94位，实际上把汉字表示成二维数组，每个汉字在数组中的下标就是区位码。 例如“中”字位于54区48位，“中”字的区位码即为“5448”。 国标码：

27、将区位码加2020H，占用两个字节 例如“中”字的国标码为区位码5448的区码和位码转化为16进制，为3630H，再加2020H得国标码5650H。,61,汉字输入码,拼音码：利用汉字的字音属性对汉字编码。 如：全拼、双拼、智能ABC、紫光拼音输入法等。 特点：易记。但击键次数多，重码多，不能盲打。 字形码：以汉字的笔划和顺序为基础的编码。也称字形编码。 如：五笔字型、郑码等。 特点：便于快速输入和盲打，但要经过训练和记忆。,（2）汉字机内码,汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码，一般采用两个字节表示。 汉字可以通过不同的输入法输入，但其内码在计算机中是唯一的。 英文字符的

28、机内代码是7位的ASCII码，当用一个字节表示时，最高位为“0”。为了与英文字符能相互区别，汉字机内代码中两个字节的最高位均规定为“1”。 机内码等于汉字国标码加上8080H。 例如“中”字的机内码为D6D0H。,（3）汉字字模码,汉字字模码又称汉字字形码，它是将汉字字形经过点阵数字化后形成的一串二进制数，用于汉字的显示和打印。 根据汉字输出的要求不同，点阵有以下几种： 简易型汉字：1616， 32字节/汉字 普通型汉字：2424， 72字节/汉字 提高型汉字：3232， 128字节/汉字 精密型汉字：4848 288字节/汉字 汉字字库：将所有汉字的字模点阵代码按内码顺序集中起来，构成了汉字

29、库。,64,对于1616的汉字字形点阵，国标两级7445个汉字和符号要占用256K字节。如果有4种字体，则需1MB存储空间。 因为字形点阵的信息量很大，所占存储空间也很大，因此字形点阵不用于机内存储，而采用汉字库存储。字库中存储了每个汉字的点阵代码。当显示输出或打印输出时才检索字库，输出字形点阵，得到字形。 当机内装有多种汉字系统时，各系统自带的字库，在同时使用时，有时会发生冲突。,65,例：1616的汉字字形点阵，每个汉字要占用32个字节。,67,2.1.3 信息的抗干扰编码（数据校验码）,数据在计算机系统内形成、存取和传送过程中，可能会因为某种原因而产生错误。为减少和避免这类错误，一是尽可

30、能采取多种措施提高机器本身的抗干扰 能力和可靠性，另一方面是在数据编码上采取检错纠错的措施。 数据校验码：具有检测某些错误或带有自动纠正错误能力的数据编码方式。 常用的数据校验码有奇偶校验码、海明校验码、循环校验码。,编码与校验过程,有效 信息,校验码 编码器,校 验 码,校验位,校 验 码,发送 /写 /存,接收 /读 /取,有 效 信 息,校 验 位,有 效 信 息,校 验 位,校验码 译码器,正确,错误,输出,69,1. 奇偶校验码的编码,奇偶校验码是一种最简单、最常用的校验码，广泛用于主存的读写校验或ASCII码字符传送过程中的检查。 基本原理：在n位有效信息位上增加一个二进制位作为校

31、验位，构成n十1位的奇偶校验码。校验位P的取值（0或1）使nl位的奇偶校验码中“1”的个数为奇数（称为奇校验Odd）或为偶数（称为偶校验Even）。 校验位的位置在有效信息位的最高位之前或者在最低位之后。,70,例：A6A5A4A3A2A1A0为7位有效信息，加一个校验位P，构成8位的奇偶校验码为 A6A5A4A3A2A1A0P 或 PA6A5A4A3A2A1A0 若采用偶校验，则： PevenA6A5A4A3A2A1A0 若采用奇校验，则 Podd Peven,71,例：求7位信息码1100111的奇校验码和偶校验码（设校验位在最低位）。 解： (1)1100111的奇校验码 因为11001

32、11中“1”的个数为奇，所以奇校验位P0，1100111的奇校验码为11001110。 (2)1100111的偶校验码 因为1100111中“1”的个数为奇，所以偶校验位P1，1100111的偶校验码为11001111。,72,奇偶校验码的编码电路,73,奇偶校验码的校验,若接到一奇校验码中“1”的个数为偶数，或接到一偶校验码中“1”的个数为奇数，则表示有一位出错。 以上面的七位有效信息的奇偶校验码为例： 偶校验错： EA6A5A4A3A2A1A0Peven 奇校验错： EA6A5A4A3A2A1A0Podd E0，表示无错； E1，表示校验出错,74,奇偶校验码的校验电路,75,奇偶校验码的

33、校错能力,奇偶校验码只能发现奇数位个错误，而无法发现偶数位个错误，而且即使发现奇数位个错误也无法确定出错的位置；因而无法自动纠正错误。 但由于现代计算机可靠性比较高，出错概率很低，而出错中只有一位出错的概率最高，因此用奇偶校验检测一位出错，能够满足一般可靠性要求。 在CPU与主存的信息传送过程中，奇偶校验被广泛应用。,76,2.6.2 海明校验码,海明校验码的实质 在奇偶校验的基础上，增加校验位的位数，构成多组的偶校验，以便发现错误并自动纠正错误。 海明校验码校验位数的选择 设有效信息位的位数为n，校验位数为k，则能够检测一位出错并能自动纠正一位错误的海明校验码应满足下面关系： 2k-1n+k

34、 由此式可计算出具有检1纠1错能力的海明校验码中n与k的关系，如表2.6所示。,77,有效信息位与校验位的关系,78,海明校验码的编码规则,(1) n 位有效信息选择k个校验位，构成n+k位的海明校验码。若海明校验码位号从右向左（或从左向右）按从1到n+k排列，则校验位的位号分别为2i-1，i1，2k，有效信息位按原排列次序安排在其它位号中。 例：一个字符的BCD码为A4A3A2A1，根据表2.6选择k3。构成4+37位的海明校验码。 位号 H7 H6 H5 H4 H3 H2 H1 编码 A4 A3 A2 P3 A1 P2 P1 P1、P2、P3、分别为三个校验位，其Pi下标的2i-1是它们在

35、海明码中的位号，即20、21、22、的位置 。,79,(2)分组的方法和原则： k个校验位构成k组奇偶校验，每个有效信息位都被2个或2个以上的校验位校验。被校验的位号等于校验它的校验位位号之和。 如上例中，A3的位号为6，62+4，所以A3被P2 、 P3 校验。A4位号为7，71+2+4，所以A3被P1、P2、P4校验。以此方法可知每个信息位分别被哪些校验位校验。 A1（H3）：P1、P2 A2 （H5） ：P1、P3 A3（H6）：P2、P3 A4 （H7） ：P1、P2、P3,80,由此可得形成k个校验位的校验组 P1：A1、A2、A4 (第一组) P2：A1、A3、A4、 (第二组)

36、P3：A2、A3、A4 (第三组) (3)分组的偶校验：由已知的有效信息位按偶校验方法求出各个校验位，进而形成海明校验码。,81,例如，按偶校验求出各个校验位的方法是： P1A1A2A4 P2A1A3A4 P3A2A3A4,82,例：编制BCD字符“6”的海明校验码。 解：“6”的BCD码为A4A3A2A10110 P1A1A2A40101 P2A1A3A40101 P3A2A3A41100 因此得到BCD码字符“6”的海明校验码为： 位号 H7 H6 H5 H4 H3 H2 H1 编码 A4 A3 A2 P3 A1 P2 P1 0 1 1 0 0 1 1 海明校验码产生后，将信息位和校验位一

37、起存入内存。,83,海明校验码的校验方法,校验时， k个校验位进行k组偶校验，校验结果形成k位的“指误字” EkEk-1E2E1。 若某组校验结果正确，指误字相应位为0；若校验结果错误，指误字相应位为1。若校验结果 EkEk-1E2E1全0，则表示无错； EkEk-1E2E1全0，则表示有错， 并且指误字代码所对应的十进制值就是出错位的位号。将该位取反，错误码即得到自动纠正。 例： E1P1A1A2A4 = 0 1 0 1 0 1 0 1 E2P2A1A3A4 = 0 0 1 1 0 0 1 1 E3P3A2A3A4 = 0 0 0 0 1 1 1 1,84,指误字指示出错的前提是代码中只存在

38、一个错。若有多个错，可能查不出来。 所以只有在只存在一个错的前提下，海明码才能实现检1纠1错。 例：BCD字符“6”的偶校验码为0110011，其指误字为 E1P1A1A2A4 E2P2A1A3A4 E3P3A2A3A4,85,若接收正确，即接收到的代码是0110011 ，则 E110100 E210100 E301100 若接收出错，即接收到的代码是0010011 ，则 E110100 E210001 E301001 得到的指误字为 E3E2E1110，表示第6位上的数码出错。将第6位上的数码A3取反，即可得到正确结果。,86,2.6.3 循环冗余校验码,循环冗余校验码(Cyclic Red

39、undancy Check)简称为CRC码。是一种具有很强检错纠错能力的校验码。 CRC码广泛用于磁盘、磁带等辅助存储器的校验，在计算机网络和通信中亦被广泛采用。 循环冗余校验码是通过除法运算来建立有效信息和校验位之间的约定关系。,87,CRC码的基本原理,对于多项式M(x)和G(x)有 如果对于一个M(x)，事先按某一G(x)求得Q(x)和R(x)。传送时，把M(x)R(x)作为编好的校验码传送。 当收到该校验码后仍用原约定的多项式G(x)去除，若能整除，即余数为0，则表示该校验码正确；若余数不为0，表明有错，并可根据余数值确定出错位号，进行自动纠正。,88,CRC码的编码方法,(1) 把待

40、编码的n位有效信息表示为多项式M(x)，并选择一个k+1位约定多项式G(x)作为约定除数（又称生成多项式） M(x)Cn1Xn1Cn2Xn2C1X1C0 Ci0 或 1 对应M中第i位的信息 G(x)GkXkGk1Xk1G1X1G0,89,(2) 把M(x)左移k位，得到M(x) Xk。然后按模2除法，用M(x) Xk除以G(x)得到k位余数R(x)。即： (3)将M(x) Xk与余数R(x)作模2相加，即形成循环冗余校验码。 M(x) XkR(x)Q(x) G(x)R(x)R(x) Q(x) G(x) （模2加）,90,由于M(x) XkR(x)可被G(x)整除，所以可作为循环冗余码。 因为

41、M(x)左移k位后空出k位，所以与R(x)模2加可由简单的拼装来实现。 例：将4位有效信息1101编成7位CRC码。其中生成多项式为4位多项式，G(x)X3+X1+1。 解： M(x)1101X3+X2+1，M(x)左移3位，得： M(x) X31101000， G(x)X3+X1+11011 将M(x) X3 模2除以 G(x)得：,91,M(x) X3R(x)11010000011101001 所以M(x)的7位CRC码为1101001。 在该编码中，由于n4，n+k7，故称(7、4)码。,92,CRC码的校验方法,把接收到的CRC码用原约定的生成多项式G(x)作模2除，若除得余数为0，表

42、示没有错误；若除得余数不为0，表示有一位出错。根据余数值可确定出错的位置。 上例中的(7，4)CRC码的出错模式如表所示。,93,(7，4)码的出错模式(G(x)1011),94,以表中第一行错误码为例，把余数001补0再除以G(x)1011，第二次余数为010，再补0除以1011，得余数为100，按此继续除下去，得余数依次为011，110，111，101，然后又回到001，反复循环，这就是循环码的来历。,95,生成多项式G(x)的选择,在循环冗余校验中，并非任何一个k+l位的多项式都可作为生成多项式使用。生成多项式应满足下列要求： (1)任何一位发生错误都应使余数不为0； (2)不同位发生错误应当使余数不同； (3)对余数作模2除法，应能使余数循环。 选择不同的生成多项式，CRC码的码距不同，因而检错、校错能力也不同。 生成多项式不同，CRC码的出错模式也不同。,96,常用的生成多项式,Thank you!,