《计算机组成原理》第二章计算机中的数据显.ppt

2023/9/17,第1页,第2章计算机中的数据表示,计算机组成原理(第二版)清华大学出版社,教学目标教学重点教学过程,2023/9/17,第2页,教学目标,数据在计算机中的表示方法及编码形式掌握进位计数制和数制之间的转换掌握数与字符的表示方法及校验方法,2023/9/17,第3页,教学重点,进位计数制和数制之间的转换定点数和浮点数带符号数的表示方法字符编码数据校验码,2023/9/17,第4页,教学过程,2.1 数据、信息和媒体2.2 进位计数制2.3 定点数和浮点数2.4 带符号数的表示方法2.5 十进制数据表示2.6 字符编码2.7 数据校验码 2.8 例题解析,2023/9/17,第5页,2.1 数据、信息和媒体(1/4),数据：是对事实、概念或指令的一种特殊表达形式，可以用人工方式或自动化装置进行通信、翻译转换或加工处理。数值型数据：具有特定值的一类数据，可用来表示数量的多少，可比较其大小。非数值型数据：包括字符数据、逻辑数据、图画、声音和活动图像数据等。,2023/9/17,第6页,2.1 数据、信息和媒体(2/4),信息：对人有用的数据，这些数据可能影响到人们的行为和决策。信息处理：通过数据的采集和输入，有效地把数据组织到计算机中，由计算机系统对数据进行相应的处理加工（如：存储、建库、转换、合并、分类、计算、统计、汇总、传送等操作），最后向人们提供有用的信息的全过程。,2023/9/17,第7页,2.1 数据、信息和媒体(3/4),媒体：承载信息的载体。与计算机信息处理有关的媒体：感觉媒体：能使人听觉、视觉、嗅觉、味觉和触觉器官直接产生感觉的一类媒体，如声音、文字、图画、气味等，它们是人类使用信息的有效形式。表示媒体：为了使计算机有效地加工、处理、传输感觉媒体而在计算机内部采用的特殊表示形式，即声、文、图、活动图像的二进制编码表示。存储媒体：用于存放表示媒体以便计算机随时加工处理的物理实体，如磁盘、光盘、半导体存储器等。表现媒体：用于把感觉媒体转换成表示媒体进而转换为感觉媒体的物理设备，如计算机的输入输出设备传输媒体：用来将表示媒体从一台计算机传递到另一台计算机的通信载体，如同轴电缆、光纤、电话线等,2023/9/17,第8页,2.1 数据、信息和媒体(4/4),数字化编码：用少量最简单的基本符号，对大量复杂多样的信息进行一定规律的组合。一切信息编码的两大要素 基本符号的种类组合规则,2023/9/17,第9页,计算机内部采用的二进制表示方式的原因,1、二进制只有两个数码“0”和“1”，易于用物理器件表示。这些物理状态都是不同的质的变化，形象鲜明、易于区别，并且数的存储、传送和处理可靠性高。2、运算规则简单，操作实现容易3、二进制加、减、乘、除运算，可以归结为加、减、移位三种操作。4、理论和实践证明，采用R=e=2.71828进制时，存储设备最省，取3比取2更节省设备，但二进制比三进制易于表示 5、二进制中的“1”和“0”与逻辑命题中的“真”、“假”相对应，为计算机实现逻辑运算和程序中的逻辑判断创造了良好条件。,2023/9/17,第10页,2.2 进位计数制,2.2.1 进位基数和位的权数2.2.2 二进制数制2.2.3 八进制数制2.2.4 十六进制数制2.2.5 数制之间的相互转换,2023/9/17,第11页,2.2.1 进位基数和位的权数,基数：计数制中用到的数码的个数，用R表示。位权：以基数为底的指数，指数的幂是数位的序号。对一个数S，其基数为R，则：,2023/9/17,第12页,计算机常用各种进制数的表示,2023/9/17,第13页,2.2.5 数制之间的相互转换,二、八、十六进制数转换为十进制数十进制数转换为二、八、十六进制数十进制数转换为二进制十进制数转换为八进制、十六进制数二进制数和八进制数、十六进制数的转换二进制数转换为八、十六进制数八、十六进制数转换为二进制数,2023/9/17,第14页,二、八、十六进制数转换为十进制数（1/2）,例2-1 将(11011.11)2转换为十进制数 解：(11011.11)2=124+123+022+121+120+12-1+12-2=(27.75)10,2023/9/17,第15页,二、八、十六进制数转换为十进制数（2/2）,例2-2 将(732.6)8转换为十进制数 解：(732.6)8=782+381+280+68-1=(474.75)10例2-3 将(A5C.B2)16转换为十进制数 解：(A5C.B2)16=10162+5161+12160+1116-1+216-2=(2652.6953125)10,2023/9/17,第16页,十进制转换为二进制数（1/3）,任一十进制数N，N=N整+N小。将这两部分分开转换整数部分的转换：采用“除2求余法”，转换方法为：连续用2除，求得余数（1或0）分别为K0、K1、K2、，直到商为0，所有余数排列Kn-1Kn-2K2K1K0 即为所转换的二进制整数部分。小数部分的转换：采用“乘2取整法”。转换方法为：连续用2乘，依次求得各整数位（0或1）K-1、K-2、K-m，直到乘积的小数部分为0。在小数转换过程中，出现Fi恒不为0时，可按精度要求确定二进制小数的位数。,2023/9/17,第17页,十进制转换为二进制数（2/3）,例2-4 求(43)10的二进制表示 解：除以2 商Qi 余数Ki 43/221 K0=1 21/210 K1=1 10/2 5 K2=0 5/2 2 K3=1 2/2 1 K4=0 1/2 0 K5=1(43)10=(101011)2,2023/9/17,第18页,十进制转换为二进制数（3/3）,例2-5 求(0.6875)20的二进制值解：乘以2小数Fi整数Ki 0.687520.3750K-1=1 0.375020.7500K-2=0 0.750020.5000K-3=1 0.500020.0000K-4=1(0.6875)10=(0.1011)2,2023/9/17,第19页,十进制数转换为八进制数、十六进制数,将十进制数转换为八进制数、十六进制数时，使用的方法与十进制数转换成二进制数的方法基本相同，只是求整数部分时是用商除以8或16，取其余数；小数部分改用乘以8或16，取其整数即可。,2023/9/17,第20页,二进制数与八进制、十六进制数间的转换,二进制转化成八(十六)进制整数部分：从右向左按三(四)位分组，不足补零小数部分：从左向右按三(四)位分组，不足补零,例2-9(001 011 010 110.101 011 100)2=(1326.534.)8 1 3 2 6 5 3 4例2-10(0101 1101.0101 1010)2=(5D.5A)16 5 D 5 A,2023/9/17,第21页,八进制、十六进制数与二进制数间的转换,八(十六)进制转化成二进制一位八进制数对应三位二进制数一位十六进制数对应四位二进制数例2-11(247.63)8=(010 100 111.110 011)2例2-12(F5A.6B)16=(1111 0101 1010 0110.0110 1011)2,2023/9/17,第22页,2.3 定点数和浮点数,数据的表示定点表示法浮点表示法任何一个二进制数N都可以表示为N=2ES其中E是一个二进制整数，称为数N的阶码，2为阶码的基数，S是二进制小数，称为数N的尾数。E和S可正可负。尾数S表示数N的全部有效数据，阶码E指明该数的小数点位置，表示数据的大小范围。,2023/9/17,第23页,2.3.1 定点数表示法,阶码E保持不变若E=0，小数点固定在最高位之前，则该数是一个纯小数或定点小数。例如 N=200.110101001=0.110101001若E=n(n为尾数的位数)，则把小数点定在尾数最末位之后，表示一个纯整数(定点整数)。例如 N=270.1011010=01011010,2023/9/17,第24页,2.3.2 浮点数的表示,浮点数的格式阶码位数m与尾数位数n之间有如下关系：2m-1n即表示阶码的值应保证实际的小数点可以在整个尾数的位格中移动。,2023/9/17,第25页,2.3.2 浮点数的表示,规格化浮点数所谓浮点数的规格化，就是通过移动尾数，使尾数S的最高位数字为1。即S满足1/2|S|1时，这个浮点数就是规格化的数，否则就不是。在字长一定的情况下，规格化的浮点数精度最高。,2023/9/17,第26页,2.3.3 定点数表示法和浮点数表示法的比较,表示的数据范围不同定点表示法，8位小数，能表示的数据范围：0.00000010.1111111（2-71-2-7）浮点表示法，2位阶码，1位阶符，4位尾数，1位尾符，能表示的范围：0.00012-11 0.1111211溢出情况不同定点表示法（小数）带符号n+1位数时：小于2-n时：当0；大于1-2-n时：溢出，停机。浮点表示法：规格化后，从阶码上分析溢出：阶码很小时，下溢：当0；阶码超出最大值时，上溢：停机。运算规则的复杂性不同定点数：较简单；浮点数：较复杂。精度不同：规格化浮点数的精度远远大于定点数。,2023/9/17,第27页,2.3.4 计算机中数的表示单位和机器字长,数的表示单位：位（Bit）：表示数的最基本单位，对二进制只有“0”和“1”字节（Byte）：8位二进制数字（Word）：机器字长：参加运算的寄存器所含的二进制位数，代表机器的精度固定长度可变字长,2023/9/17,第28页,2.4 带符号数的表示,一个数的表示方法，是它们在计算机中的组成格式和编码规则。当一个数送入计算机进行运算处理时，首先将其转换为二进制数，同时还要解决以下几个问题：1怎样表示数的符号 2怎样确定小数点的位置,2023/9/17,第29页,2.4.1 机器数的原码表示（1/3）,规则：机器数的最高一位表示符号，“0”表示正号；“1”表示负号，后面各位用数的绝对值表示。整数原码的定义为：X原为机器数的原码，X为真值，n为整数的位数。例2-13：求X=1011和Y=-1011的原码解：X=1011时，原=01011Y=-1011时，Y原=24-(-1011)=11011,2023/9/17,第30页,2.4.1 机器数的原码表示（2/3）,小数原码的定义为：X原为机器数的原码，X为真值。例2-14：求X=0.1011和Y=-0.1011的原码解：X=0.1011时，原=0.1011Y=-0.1011时，Y原=1-(-0.1011)=1.1011,2023/9/17,第31页,2.4.1 机器数的原码表示（3/3）,性质：原码最高位表示数的符号，0表示正号，1表示负号。对定点小数，有：0不唯一 定点小数+0原=0.00-0原=1.00 整数+0原=000-0原=100,2023/9/17,第32页,2.4.2 机器数的补码表示（1/8）,整数的补码X补为整数X的补码，X为任意整数，n为整数的位数。小数的补码：X补是小数X的补码，X为任意小数，2为模数。,2023/9/17,第33页,2.4.2 机器数的补码表示（2/8）,例2-15 求正整数X=1011和负整数Y=-1011的补码 解：X补=01011 Y补=2n+1+X=24+1+X=100000-1011=10101 例2-16 求正小数X=0.1011和负小数Y=-0.1011的补码解：X补=0.1011 Y补=2+X=2-0.1011=1.0101,2023/9/17,第34页,2.4.2 机器数的补码表示（3/8）,性质 0的补码唯一整数0+0补=000-0补=2n+1-000=2n+1=000(mod 2n+1)小数0+0补=0.000-0补=2-0.000=2=0.000(mod 2)设 X补=XSXn-1Xn-2X1X0，XS是补码的符号位，标志整数X的符号，XS=0时，X为正数；XS=1时，X为负数。补码的表示范围是：正整数 2nX0负整数 0X-2n 整数X的补码可以写成：X补=2n+1XS+X，,2023/9/17,第35页,性质整数的补码与真值之间的关系 补码与真值的关系设X补=XSXn-1Xn-2X1X0，X补=2n+1XS+X，可以证明：X=X补-2n+1XS=-2nXs+Xn-1Xn-2X1X0补码的一项算术运算特性 X/2补是把X补中各位连同符号位一起都右移一位，符号位保持不变。,2.4.2 机器数的补码表示（4/8）,2023/9/17,第36页,2.4.2 机器数的补码表示（5/8）,补码的求法当0X-2n时，数X的补码是：符号位为1，数值位是其真值X的数值位取反加1。也可由X的原码X原求得补码X补：X补等于X原除符号位外求反加1。反过来可由X的补码X补求得原码X原：X原等于X补除符号位外求反加1。当X为小数时，若X为负数，则X的补码是：符号位为1，数值位是其真值X 的数值位取反末位加1。也可由X的原码X原求得补码X补：X补等于X原除符号位外求反末位加1。反过来可由X的补码X补求得原码X原：X原等于X补除符号位外求反末位加1。,2023/9/17,第37页,2.4.2 机器数的补码表示（6/8）,由X补求-X补 X+Y补=X补+Y补 X-Y补=X补+-Y补 假设X补=XSXn-1Xn-2X1X0，可由X补按下式求得-X补把对X补连同符号位在内的各位求反运算称为对X补“求反”运算，记为X补。这样对X补的“求补”运算可看成对X补“求反”运算再加1：-X补=X 补+1，且两者有以下关系：X补+X补=2n+1-1=111(n个1),2023/9/17,第38页,2.4.2 机器数的补码表示（7/8）,变形补码小数“模4补码”的定义为：或X补=X(mod 4)(1)当-1X1时，数X的“模4补码”的两个符号位相同，00表示正号，11 表示负号，其数值位与补码相同。当符号位为01或10时，表示数值溢出：为01时表示两正数之和大于等于1的情况，称为数值“上溢”；为10 时表示两负数之和小于等于-1的情况，称为数值“下溢”。(2)“模4补码”表示中，0有唯一的补码：根据“模4补码”的性质1，可以判断数的溢出。两个同符号数相加时，有可能出现溢出。,2023/9/17,第39页,2.4.2 机器数的补码表示（8/8）,补码的符号位扩展若X补=XSXn-1Xn-2X1X0为8位，需要扩展为16位时，要按下面的规则进行扩展：用符号位XS填满扩展的高8位，若X0，XS=0，扩展后高8位全为0，低8 位包括符号位仍为原来的数码位。若X0，XS=1，扩展后高8位全为1，低8位包括符号位仍为原来的数码位。,2023/9/17,第40页,2.4.3 机器的反码表示（1/3）,定义：整数反码的数学定义为：或X反=X(mod 2n+1-1)例2-20 X=1011，则X反=01011=-1011，则反=25-1+X=10100,2023/9/17,第41页,2.4.3 机器的反码表示（2/3）,定义：小数反码的数学定义为：或X反=X(mod 2-2-n),2023/9/17,第42页,2.4.3 机器的反码表示（3/3）,性质：(1)0的反码不唯一，整数0+0反=000-0反=(2n+1-1)+(-000)=111(mod 2n+1-1)小数0+0反=0.000-0反=2-2-n-0.000=1.11(mod 2-2-n)(2)设整数X的反码表示为：X反=XSXn-1Xn-2X1X0，XS是反码的符号位，它标志整数X的符号，XS=0时，X为正数；XS=1时，X为负数。(3)反码与补码的关系 根据补码和反码的定义，当X为正数时，X补=X反；当X为负整数时，X补=X反+1；当X为n位负小数时，X补=X反+2-n,2023/9/17,第43页,2.4.4 机器数的移(增)码表示法（1/2）,定义：设阶码为n位整数，X移=2n+X 2nX-2n即无论X是正还是负，一律加上2n，称2n为基数。移码与补码的关系：真值是正数时，移码是补码的最高位加1；真值是负数时，移码是补码的最高位减1。即若 X补=XSXn-1Xn-2X1X0，则 X移=Xn-1Xn-2X1X0例2-21 X=1001，X补=01001，可求得X移=11001 X=-1001，X补=10111，可求得X移=00111,2023/9/17,第44页,2.4.4 机器数的移(增)码表示法（2/2）,性质：(1)0的移码唯一。整数0+0移=2n+000=1000-0移=2n-000=1000(2)机器0的形式为000，它表示的真值是X移所能表示的最小的数。(3)移码的最高位是符号位，但表示的意义与原码和补码的意义相反。符号为0时，表示负数；符号为1，表示正数。(4)移码一般只进行加减运算，运算后需要对结果进行修正，修正量为2n，即要对结果的符号位取反后，才能得到移码形式的结果。(5)通过比较两个移码的大小，可得知其对应的真值大小。,2023/9/17,第45页,2.4.5 各种编码的比较,相同点：1、三种编码（原码、反码、补码）的最高位都是符号位。2、当真值为正时，三种编码的符号位都用0表示，数值部分与真值相同。即它们的表示方法是相同的。3、当真值为负时，三种编码的符号位都用1表示，但数值部分的表示各不相同，数值部分存在这样的关系：补码是原码的“求反加1”(整数)，或者“求反末位加1”(小数)；反码是原码的“每位求反”。4、它们所能表示的数据范围基本一样，-2nX2n(整数)或-1X1(小数)，补码多表示一个数-2n(整数)或-1(小数)。区别：在于对负数的表示方法有所不同。,2023/9/17,第46页,2.5 十进制数据表示,人们习惯于用十进制表示数据，而计算机则采用二进制表示和处理数据。所以向计算机输入数据时，需要进行十进制数到二进制数的转换；输出数据时，则要进行二进制数到十进制数的转换处理。在数据量较小的情况下，这样的转换对机器运行效率的影响不是很大。但是，在某些应用领域，运算简单而数据量很大，进行这些转换所占用的时间比例比较大。所以为了提高机器的运行效率，计算机可以用十进制来表示和处理数据。一个十进制数位是用若干位二进制编码表示。用四位二进制代码的不同组合来表示一个十进制数码的编码方法，称为二十进制编码，也称BCD码（Binary Coded Decimal）。常用这种编码作为十进制数转换成二进制数的中间过渡。即先将一个十进制数用BCD码来表示，再把它们送入机器，计算机通过标准子程序使其转换成纯二进制数。,2023/9/17,第47页,2.5.1 二十进制编码原理,1、二十进制的编码都采用压缩的十进制串的方法，即四个二进制位的值来表示一个十进制数码。2、各种编码的区别在于选用哪十个状态。选择的原则是：要考虑输入和输出时转换方便；内部运算时，加、减运算规则要尽量简单；在特定场合，可能有其它一些要求。3、从每个二进制位是否有确定的位权区分，可把二十进制编码分为有权码和无权码。,2023/9/17,第48页,2.5.2 二-十进制有权码（1/2）,对于有权码，将每位的数码与相应的位权相乘，再求和，就可以得到它所代表的十进制数值。8421码实现加、减运算时的修正规则：（1）4位一组二进制数，两个8421码表示的数相加之和等于或小于1001，即十进制的9时，不需要修正，在各组内，二进制代码相加，仍遵循“逢二进一”的规则。（2）4位一组二进制数，两个8421码相加结果大于1001（即十进制9）时，则应该对该组的4位进行“加6修正”，使它向高一组产生进位。（3）4位一组二进制数，两个8421码相加结果大于或等于10000（即十进制16），而向高一组进位时，则应该对该4位进行“加6修正”。,2023/9/17,第49页,二-十进制有权码（2/2）,编码方法：8421码，2421码、5211码、4311码和84-2-1码(四位二进制位的位权分别为8、4、-2、-1)等。其最方便使用的共同特点为：(1)对于2421码、5211码、4311码，任何两个十进制数位，采用这三种编码的任何一种编码，它们相加之和等于或大于10时，其结果的最高位向左产生进位，小于10时则不产生进位。这一特点有利于实现“逢十进位”的计数和加法规则。(2)对于2421码、5211码、4311码和84-2-1码，任何两个十进制数位，采用这四种编码的任何一种编码，它们相加其和等于9时，即它们的二进制编码位互为反码，则其结果的四个二进制位一定是1111，能较好地体现十进制的按9 取补与二进制的按1取补的对应关系，这对减法很有用。,2023/9/17,第50页,2.5.3 二十进制无权码（1/2）,无权码中，用的较多的是余3码(Excess-3 code)和格雷码(Gray code)，格雷码又称循环码。1.余3码（1）余3码是在8421码的基础上，把每个代码都加上0011而形成的。（2）普通8421码的加法器仍能为余3码加法器直接利用，具体规则如下：（A）若两个十进制数的余3码相加，如果结果不产生进位，则从所得和值去减0011，便得十进制位和的余3码。（B）若两个十进制数的余3码相加，如果结果有进位，则其进位正确，但需将所得和值加上0011，才求得十进制数和的余3码。,2023/9/17,第51页,2.5.3 二十进制无权码（2/2）,2.格雷码（1）格雷码的编码规则是使相邻的两个代码，只有一个二进制位的状态不同，其余三个二进制位必须有相同状态。（2）优点：从一个编码变到下一个相邻编码时，只有一个位的状态发生变化，有利于保证代码变换的连续性。在模拟/数字转换和产生节拍电位等应用场合特别有用。,2023/9/17,第52页,2023/9/17,第53页,2.6 字符编码,2.6.1 ASCII码2.6.2 EBCDIC码,2023/9/17,第54页,2.6.1 ASCII码,“美国标准信息交换代码”(American Standard Code for Information Interchange)，简称ASCII码。7位二进制编码，可表示27=128个字符。ASCII码中，编码值031不对应任何可印刷（或称有字形）字符，通常称它们为控制字符，用于通信中的通信控制或对计算机设备的功能控制。编码值为32的是空格（或间隔）字符SP。编码值为127的是删除控制DEL码。其余的94个字符称为可印刷字符。,2023/9/17,第55页,2.6.2 EBCDIC码,EBCDIC码(Extended Binary Coded Decimal Interchange Code，扩展BCD码)，是8位二进制编码，可以表示256个编码状态，但只选用其中一部分。主要用在IBM公司生产的各种机器中。,2023/9/17,第56页,2.6.3 汉字的表示,特点：（1）汉字是一种象形文字，据统计，从甲骨文至今约有六万左右的汉字。目前常见的汉字有约七千个。（2）汉字字形结构复杂，笔划繁多。（3）汉字同音字多，多音字多。涉及多种编码：汉字编码输入方案可以归纳为四类，即数字编码，如区位码；字音编码，如拼音码；字形编码，如五笔字型；汉字混合编码等。1981年我国制定了信息交换用汉字编码字符集基本集GB2312-80国家标准。每个二进制编码用两个字节表示。共收录一级汉字3755个，二级汉字3008个，各种符号682个，共计7445个。,2023/9/17,第57页,2.7 数据校验码,2.7.1 奇偶校验码2.7.2 海明校验码2.7.3 循环冗余校验码,2023/9/17,第58页,2.7 数据校验码,1、数据校验的实现原理：数据校验码是在合法的数据编码之间，加进一些不允许出现的(非法的)编码，使合法的数据编码出现错误时成为非法编码。这样就可以通过检测编码的合法性达到发现错误的目的。2、码距：指任何一种编码的任两组二进制代码中，其对应位置的代码最少有几个二进制位不相同。,2023/9/17,第59页,2.7.1 奇偶校验码,1、码距=22、奇偶校验码：它是在被传送的n位信息组上，加上一个二进制位作为校验位，使配置后的n+1位二进制代码中1的个数为奇数(奇校验)或偶数(偶校验)。例：数据奇校验编码偶校验编码0000000010000000000000000001110101001110101101110101其中，最高一位为校验位，其余低八位为数据位。3、奇偶校验码只能检测出数据代码中一位出错的情况，但无法判断差错所发生的位置。常用于存储器读写检查，或ASCII字符传送过程中的检查。,2023/9/17,第60页,2.7.2 海明校验码（1/8）,1原理 在数据位中加入几个校验位，将数据代码的码距均匀地拉大，并把数据的每个二进制位分配在几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，不但可以发现错误，还能指出是哪一位出错，为进一步自动纠错提供依据。2编码规则 若海明码最高位号为m，最低位号为1，即HmHm-1H2H1，则海明码的编码规则是：（1）校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置上，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。（2）海明码的每一位位码Hi（包括数据位和校验位）由多个校验位校验，其关系是被校验的每一位位号要等于校验它的各校验位的位号之和。,2023/9/17,第61页,2.7.2 海明校验码（2/8）,3增添校验位 假设欲检测的有效信息为n位，需增加的校验位为k位，则校验码的长度为n+k位。校验位的状态组合，应当具有指出n+k位中任一位有错或无错的能力，即需要区别出n+k+1种状态。应满足以下关系式：2kn+k+1 这个关系式称为海明不等式，若信息位长度n确定后，由此可得到校验位k的最短长度。确定校验位后，就可以与信息位组成海明校验位。假设数据位是7位二进制编码，据上所述，校验位的位数k为4,故海明码的总位数为11。它们的排列关系可表示为：海明码位号：H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 海明码：D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 可知：每个校验位由其本身校验；每个数据位由若干校验位校验。,2023/9/17,第62页,2.7.2 海明校验码（3/8）,4校验位校验任务的分配：根据海明码的编码规则，每一位海明码都有多个校验位，且被校验的每一位的位号等于参与校验的几个校验位的位号之和。占据各权位上的校验位按权组成的8421码，正好等于海明码的位号，即海明码的位号Hi正好等于要校验它的校验位所占权位权值之和。例如：H11P423P222P121这说明了H11位将由 P4、P2、P1进行校验。校验位P1可以校验：H1、H3、H5、H7、H9、H11、H13、H15校验位P2可以校验：H2、H3、H6、H7、H10、H11、H14、H15校验位P3可以校验：H4、H5、H6、H7、H12、H13、H14、H15校验位P4可以校验：H8、H9、H10、H11、H12、H13、H14、H15根据校验时采用奇校验或偶校验，可以写出相应的校验方程。,2023/9/17,第63页,2.7.2 海明校验码（4/8）,例2-23 设有一个7位信息码位0110001，求它的海明码。解：n=7，根据海明不等式，可求得校验位最短长度k=4。其海明码先表示如下：海明码位号：H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1海明码：0 1 1 P4 0 0 0 P3 1 P2 P1按偶校验写出校验方程为：H1 H3H5 H7 H9H110（P1H1）H2 H3 H6H7 H10H110（P2H2）H4H5 H6H70（P3H4）H8H9 H10H110（P4H8）由此可得：P10、P20、P30、P40，所以0110001的海明码为。,2023/9/17,第64页,2.7.2 海明校验码（5/8）,5检错与纠错 方法：将错了的码字重新代入校验方程校验一次即可。假设上面例子中的海明码传送后，若H6位发生了错误，变成了，这时把它们代入上面的偶校验校验方程，如下：H1 H3H5 H7 H9H110 1 0 0 1 0=0=E1H2 H3 H6H7 H10H110 1 1 0 1 0=1=E2H4H5 H6 H70 0 1 0=1=E3H8H9 H10H110 1 1 0=0=E4可以把E4E3E2E1=0110看成一个“指误字”，因为其二进制码为0110，说明H6出了错，是H6错成了1，所以要纠错，纠错时将H6位取反值，即让它恢复到正确值0。这样纠错后，即可得到正确的海明码。,2023/9/17,第65页,2.7.2 海明校验码（6/8）,6讨论：设有效信息位n=4位，则根据海明不等式，可求得校验位最短长度k=3。则：海明码位号：H7 H6 H5 H4 H3 H2 H1 海明码：D4 D3 D2 P3 D1 P2 P1 可以得到：P1参与D1、D2、D4的校验；P2参与D1、D3、D4的校验；P3参与D2、D3、D4的校验。若采用偶校验，则：P1=D1 D2D4 P2=D1 D3D4 P3=D2 D3D4上述编码中，两个正确码之间若有一位有效信息不同，则由于该位至少参加两组的奇偶校验，故至少会影响到两位校验位的不同，所以这种码距=3（可以检测两位错，或检测并纠正一位错）,2023/9/17,第66页,2.7.2 海明校验码（7/8）,若按下述关系对所得的海明码进行偶校验：S1=P1 D1 D2D4S2=P2 D1 D3D4S3=P3 D2 D3D4则S3 S2 S1可以反映出错情况：（1）若S3 S2 S1=000，无错（2）若欲传的海明码=0101101，收到0111101，则S1=P1 D1 D2D4=1110=1，S2=0，S3=1表明第5位（D2）出错（3）若欲传的海明码=0101101，收到0110101，则S1=1，S2=0，S3=0表明有错，但无法判断是第1位出错，还是4、5位同时出错。上述编码不能把两位出错和一位出错区分开来。,2023/9/17,第67页,2.7.2 海明校验码（8/8）,7改进：增加一个校验位 S4=P4 P1 P2 P3 D1 D2 D3 D4 P4=P1 P2 P3 D1 D2 D3 D4（1）S4=0，S3S2S1=000，无错（2）S4=0，S3S2S10，表明有两位出错（3）S4=1，S3S2S10，可根据S3S2S1指出的值纠正一位错。在这种情况下，因多增加一位校验位，则前面的海明不等式改为：2k-1n+k 称为扩展海明码，其码距=4，可发现两位错并纠正一位错。,2023/9/17,第68页,2.7.3 循环冗余校验码（1/7）,1CRC的编码方法n是有效数据信息位位数，r是校验位位数。总长k=n+r 位，称（k，n）码。设待编码的有效信息以多项式M(x)表示，将M(x)左移r位得到多项式M(x)Xr，使低r位二进制位全为零，以便与r位校验位拼接。使用多项式M(x)Xr除以生成多项式G(x)，求得的余数即为校验位。为了得到r位余数(校验位)，G(X)必须是r+1位的。,2023/9/17,第69页,2.7.3 循环冗余校验码（2/7）,假设M(x)Xr除以生成多项式G(x)，求得的余数用表达式R(x)表示，商的表达式用Q(x)表示，它们之间的关系如下：这时将r位余数R(X)与左移r位的M(x)Xr相加，就得到n+r位的CRC编码：M(x)Xr+R(x)=Q(x)G(x)+R(x)+R(x)因为“两个相同数据的模2和为零”，即R(x)+R(x)=0，所以，M(x)Xr+R(x)=Q(x)G(x)可以看出，所求得的CRC码是一个可被G(X)表示的数码除尽的数码。,2023/9/17,第70页,2.7.3 循环冗余校验码（3/7）,例 2-24 设四位有效信息位是1100，选用生成多项式 G(X)=1011，试求有效信息位1100的CRC编码。解：(1)将有效信息位1100表示为多项式M(x)M(X)=X3+X2=1100(2)M(X)左移r=3位，得M(x)X3 M(x)X3=X6+X5=1100000(3)用r+1位的生成多项式 G(X)，对M(x)Xr作“模2除”1100000/1011=1110+010/1011(4)M(x)X3 与r位余数R(X)作“模2加”，即可求得它的CRC编码 M(x)X3+R(X)=1100000+010=1100010(模2加)因为k=7、n=4，所以编好的CRC码又称为(7，4)码。,2023/9/17,第71页,2.7.3 循环冗余校验码（4/7）,2模2运算：不考虑借位和进位（1）模2加减：可用异或门实现，即：0+0=0；0+1=1；1+0=1；1+1=0；0-0=0；0-1=1；1-0=1；1-1=0；（2）模2乘法：用模2加求部分积之和 例如：1011 x 11 1011+1011 11101,2023/9/17,第72页,2.7.3 循环冗余校验码（5/7）,（3）模2除法：按模2减求部分余数，每上一位商，部分余数要减少一位，上商规则是：只要余数最高位为1，则商1，否则为0。当部分余数的位数小于除数时，该余数为最后余数。例如：111.商11（除数）1000（被除数）11 10 11 10 11 1,2023/9/17,第73页,2.7.3 循环冗余校验码（6/7）,3CRC的译码及纠错CRC码传送到目标部件，用约定的多项式G(x)对收到的CRC码进行“模2除”，若余数为0，则表明该CRC校验码正确；否则表明有错，不同的出错位，其余数是不同的。由余数具体指出是哪一位出了错，然后加以纠正。可以证明：更换不同的有效信息位，余数与出错位的对应关系不会发生变化，只与码制和生成多项式G(X)有关。,2023/9/17,第74页,2.7.3 循环冗余校验码（7/7）,4关于生成多项式不是任何一个(k+1)位多项式都能作为生成多项式，从检错、纠错的要求来看，生成多项式应满足下列要求：(1)任何一位发生错误，都应使余数不为零；(2)不同位发生错误，都应使余数不同；(3)用余数补零，继续作“模2除”，应使余数循环。,2023/9/17,第75页,本章小结,数据可区分为数值型数据和非数值型数据。根据基数和位的权数可将数据表示成二进制数（基数R为2），八进制数（基数R为8），十六进制数（基数R为16）等。数制之间可根据基数和位的权数实现相互之间的转换。数的表示单位是位、字节和字。定点表示法和浮点表示法可实现数据的有效表示，可根据精度及表示范围的不同采用不同的表示方法。带符号数的表示要注意符号的表示方法和小数点的位置。计算机中数的表示方法有四种：原码表示法、补码表示法、反码表示法、移码表示法。十进制的数据表示方法有：有权码（2421码、4311码、8421码等）和无权码（余3码、格雷码等）英文字符采用ASCII码、EBCDIC码等，但最常用的还是ASCII码。汉字的编码有输入码、内码、字型码等。主要的数据校验码有：奇偶校验码、循环冗余校验码和海明校验码等。,