【教学课件】第2章数据的表示和运算.ppt

上传人:wuy****n92 文档编号:69867493 上传时间:2023-01-10 格式:PPT 页数:199 大小:2.24MB
返回 下载 相关 举报
【教学课件】第2章数据的表示和运算.ppt_第1页
第1页 / 共199页
【教学课件】第2章数据的表示和运算.ppt_第2页
第2页 / 共199页
点击查看更多>>
资源描述

《【教学课件】第2章数据的表示和运算.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第2章数据的表示和运算.ppt(199页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算第第2章章 数据的表示和运算数据的表示和运算2.1数制与编码数制与编码2.2定点数的表示和运算定点数的表示和运算2.3浮点数的表示和运算浮点数的表示和运算2.4算术逻辑单元算术逻辑单元ALU2023/1/91计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换当使用汇编语言或者高级语言编写程序时,一般都采用十进制形式;有时出于某种需要也采用十六进制形式或者二进制形式来表示。但是在计算机内部,数据的表示、存储和运算均采用二进制形式。

2、进位计数制:又称为数制,即按进位制的原则进行计数。数制由两大要素组成:基数R和各数位的权W。基数R决定了数制中各数位上允许出现的数码个数,基数为R的数制称为R进制数。权W则表明该数位上的数码所表示的单位数值的大小,权W与数位的位置有关。计算机中常用的进位计数制有二进制、八进制、十进制和十六进制。2023/1/92计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换假设 任意数值N 用 R进制数 来表示,表示形式为n+k个自左向右排列的符号来表示:N=(Dn-1Dn-2D0.D-1D-2D-k)R 式中Di(-k

3、in-1)为该数制采用的基本符号,可取值0,1,2,R-1,小数点隐含在D0与D-1之间,整数部分有n位,小数部分有k位,数值N的实际值为:2023/1/93计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换十进制(Decimal):基数为10,允许使用的数字有10个(0-9)。主要特点是逢十进一。任意一个十进制数可以表示为:例如十进制数例如十进制数135.26可以表示为:可以表示为:2023/1/94计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1

4、.1 进位计数制及其相互转换二进制(Binary):基数为2,可使用的数字只有0和1,逢二进一。任意一个二进制数可以表示为:例如例如二进制数二进制数(1100.1011)2可以表示可以表示为:为:2023/1/95计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换计算机中数据主要以二进制数的形式存储,原因有以下几点:二进制数易于表示,比较容易找到具有二值状态的物理器件来表示数据和实现存储。比如脉冲有无、电压高低等。二进制数运算规则简单,运算过程中的输入状态和输出状态较少,便于使用电子器件和线路加以实现。二进制

5、数的0和1与逻辑推理中的“真”和“假”相对应,为实现逻辑运算和逻辑判断提供了便利。2023/1/96计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换八进制(Octal):基数为8,可使用的数字有0-7,逢八进一。任意一个八进制数可以表示为:十六进制(Hexadecimal):基数为16,可使用的数码有0-9和A-F(代表10-15),逢十六进一。任意一个十六进制数可表示为:2023/1/97计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位

6、计数制及其相互转换非十进制转化为十进制:非十进制数转为十进制数时将非十进制数按权展开,然后求和。【例2.1】将下列非十进制数转化为十进制。(1207)8=183282081780=512+128+0+7=(647)10 (A7)16=(10161+7160)10=(160+7)10=(167)102023/1/98计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算例:39转换成二进制数(39)10=(100111)22 39 1 (b0)2 19 1 (b1)2 9 1 (b2)2 4 0 (b3)2 2 0 (b4)2 1 1 (b5)02.1 数制与编码 2

7、.1.1 进位计数制及其相互转换十进制转化为非十进制:十进制数转换为非十进制数时需将十进制数整数部分和小数部分分别转换,再将结果写到一起。十进制整数转换为非十进制整数:除R取余法。十进制整数不断除以R,直至商为0。每除一次取一个余数,从低位排向高位。例:208转换成十六进制数(208)10=(D0)1616 208 余 0 16 13 余 13=DH 02023/1/99计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换十进小数转换为非十进制小数:乘R取整法。用转换进制的基数乘以小数部分,直至小数为0或达到转

8、换精度要求的位数。每乘一次取一次整数,从最高位排到最低位。例:例:0.625转换成二进制数转换成二进制数0.62521.251(b-1)0.2520.500(b-2)0.5021.001(b-3)所以所以(0.625)10=(0.101)22023/1/910计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换【例2.2】将(12.6875)10转化为二进制数。整数部分整数部分(12)10=(1100)22023/1/911计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1

9、 数制与编码 2.1.1 进位计数制及其相互转换【例2.2】将(12.6875)10转化为二进制数。小数部分小数部分(0.6875)10=(0.1011)2.所以所以(12.6875)10=(1100.1011)2 2023/1/912计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换【课堂练习】将(105.3125)10转化为二进制数。(105.3125)10=(1101001.0101)22023/1/913计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编

10、码 2.1.1 进位计数制及其相互转换二进制、八进制与十六进制的转换:3位二进制数组成1位八进制数,4位二进制数组成1位十六进制数二进制转换为八进制:从小数点开始,向两边每3位为一组,整数部分不足3位在前面补“0”,小数部分不足3位在后面补“0”。八进制转换为二进制:过程相反,每一位八进制数转换为3位二进制编码。二进制转换为十六进制:从小数点开始,向两边每4位为一组,整数部分不足4位在前面补“0”,小数部分不足4位在后面补“0”。十六进制转换为二进制:只需将每一位十六进制数写成它的4位二进制编码即可。八进制与十六进制的转换先转换成二进制,然后再转换为所求的进制数2023/1/914计算机组成与

11、结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.1 进位计数制及其相互转换【例2.3】将(11011.11001)2转化为八进制、十六进制,将(751)8转化为十六进制。(11011.11001)2=(011011.110010)2=(33.62)8(11011.11001)2=(00011011.11001000)2=(1B.C8)16(751)8=(111101001)2=(000111101001)2=(1E9)162023/1/915计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2

12、.1.2 真值和机器数计算机中的数据可分两类:无符号数和有符号数。无符号数:即没有符号的数,在寄存器中的每一位均可存放数值。有符号数:即带有符号的数,存放时需要留出位置存放符号。符号“正”、“负”需要数字化,一般用“0”表示正号,用“1”表示负号,并将它放在有效数字前面。机器数:符号“数字化”的数真 值:带“+”或“-”符号的数例如,真值是+0.11001,机器数为0.11001;真值为0.11001,机器数为1.110012023/1/916计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.3 BCD码BCD码:使用二进制数编码来表

13、示十进制数的方法,又叫做二-十进制码。一般用4位二进制编码来表示一个十进制数。常用的BCD码分为有权码和无权码。有权码:每一位都有固定的权值,加权求和的值即为它所表示的十进制数。常用的有权码有8421码、2421码、5211码等,8421码的4位二进制数的权从高到低依次是8、4、2、1。一般提到的BCD码就是指8421码。这种编码的优点是这4位二进制数之间满足二进制的进位规则。2023/1/917计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.3 BCD码在计算机内部实现BCD码算术运算,要对运算结果进行修正。BCD码加法运算修正规

14、则:如果两个一位BCD码相加之和小于或等于(1001)2,即(9)10,不需修正;如相加之和大于或等于(10)10,要进行加6修正,并向高位进位,进位可在首次相加或修正时产生。例如 1+8=9 4+9=13 7+9=16 0 0 0 1 0 1 0 0 0 1 1 1 +1 0 0 0 +1 0 0 1 +1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 不需修正 加6修正 加6修正2023/1/918计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.3 BCD码其它几种有权码:2421、5211、4311码都采用4

15、位有权的二进制码表示1个十进制数,但这4位二进制之间不符合二进制规则。这几种有权码有一特点:任何两个相加之和等于(9)10的二进制码互为反码。如2421码中,0(0000)与9(1111)、1(0001)与8(1110),互为反码。表 2.1给出了十进制数的几种常见的4位有权码。2023/1/919计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.3 BCD码十进制数8421码2421码5211码4311码00000000000000000100010001000100012001000100011001130011001101010

16、100401000100011110005010110111000011160110110010101011701111101110011008100011101110111091001111111111111表表2.14位有权码位有权码2023/1/920计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.3 BCD码无权码:4位二进制编码的每一位没有固定的权。在采用的无权码的一些方案中,采用的比较多的是余3码,格雷码余3码:把原二进制的每个代码都加0011值得到的。优点是执行十进制数位相加时,能正确产生进位信号,还给减法运算带来了方

17、便。余3码的执行加法运算的规则:当两个余3码相加不产生进位时,应从结果中减去0011;产生进位时,应将进位信号送入高位余3码,同时本位加0011的修正操作。格雷码:它的任何两个相邻的编码之间只有1个二进制位的状态不同,其余3个二进制位必须具有相同状态。优点:从一个编码变成下一个相邻编码时,只有1位的状态发生变化,有利于得到更好的译码波形,在模拟/数字转换的电路中得到更好的运行结果。2023/1/921计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.3 BCD码表表2.24位无权码位无权码十进制数余3码格雷码(1)格雷码(2)0001

18、1000000001010000010100201010011011030110001000104011101101010510001110101161001101000117101010000001810111100100191100010010002023/1/922计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.4 字符和字符串字符:字母、数码、运算符号、标点符号等,汉字也属于字符。使用计算机的过程必然要涉及字符。由于计算机只能识别0和1两种数码,所以字符也应采用二进制编码。目 前 经 常 用 的 是 美 国 国 家 信 息

19、交 换 标 准 字 符 码,简 称ASCII(American Standard Code for Information Interchange)码。ASCII码:7位二进制代码表示一个字符,称为标准或基本ASCII码,如表 2.3所示。2023/1/923计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算0000100120103011410051016110711100000NULDLESP0P、p00011SOHDC1!1AQaq00102STXDC2”2BRbr00113ETXDC3#3CScs01004EOTDC4$4DTdt01015ENQNAK%

20、5EUeu01106ACKSYN&6FVfv01117BELETB7GWgw10008BSCAN(8HXhx10019HTEM)9IYiy1010ALFSUB*:JZjz1011BVTESC+;Kk1100CFFFS,Nn1111FSIUS/?OoDEL高位高位b6b5b4低位低位b3b2b1b07位位ASCII码码编编码码表表2023/1/924计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.4 字符和字符串标准ASCII码:有128种的组合,每种组合可代表一个字符。包括所有大写和小写字母,数字 0 到 9、标点符号,及在美式英语

21、中使用的特殊控制字符。扩充ASCII码:在标准ASCII码前面增加一个二进制位,用8位二进制数来给字符编码。共有256种组合,可给256个字符编码。前128个字符的最高位为0,用于表示标准ASCII码。后128个字符的最高位为1,用于表示128种特殊符号,如制表符等。2023/1/925计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.4 字符和字符串汉字编码:计算机的汉字处理技术必须解决3个问题:汉字的输入、存储与交换和汉字的输出,它们分别对应于汉字的输入码、内码、交换码和字形码。汉字输入码:将汉字输入到计算机中多用的编码。数字输入

22、法:对每个汉字采用一个数字串进行编码,例如区位码、国标码等。优点是无重复码,缺点是难以记忆。字形分解法:将汉字按其规则和笔画划分成若干部件,用字母或者数字进行编码。如五笔字型输入法、郑码输入法等。拼音输入法:是以汉字拼音为基础的输入方法。如全拼输入法、智能ABC输入法等。优点是无须记忆,缺点是重码率较高。音形输入法:利用拼音输入法和字形分解法的各自优点,兼顾汉字的音和形,将两者混合使用。如自然码输入法。2023/1/926计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.4 字符和字符串汉字内码:是计算机系统内部处理、存储汉字所使用的

23、统一代码,一般采用两个字节表示一个汉字。汉字的输入码可以有多种,但内码在计算机中是唯一的。汉字交换码:不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所用的代码标准。目前常用的是国标码,即国家标准化信息用汉字编码。国标汉字共有6763个,分两级,一级汉字为常用汉字,共3755个;二级汉字是非常用汉字,共3008个。每个汉字对应4位十六进制数(两个字节)。2023/1/927计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.4 字符和字符串汉字字形码:目前的汉字处理系统中,字形信息的表示可以分为两大类:一类是用活字或文字版的母体字

24、形形式,另一类是用点阵表示法、矢量表示法等形式,其中最基本应用最广泛的是后者。2023/1/928计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.4 字符和字符串字符串:连续的一串字符,通常方式下,它们占用主存中连续的多个字节,每个字节存一个字符。当主存字由2个或4个字节组成时,在同一个主存字中,既可以按从低位字节向高位字节的顺序存放字符串的内容,也可以按从高位字节向低位字节的次序顺序存放字符串的内容。这两种存放方式都是常用方式。如,1F AB THEN READ(C)就可有两种不同存放方式。假定每个主存字由4个字节组成,图 2.1

25、(a)是按从高位字节向低位字符的次序存放,图 2.1(b)按从低位字节向高位字节的次序存放。主存中每个字节存放的是相应字符的ASCII编码值。2023/1/929计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.4 字符和字符串IFABTHENREAD(C)AF ITB N E HD A E R)C(a)(b)2023/1/930计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码 计算机系统中的数据,在读写、存取和传送的过程中可能产生错误(随机错误或突发错误)。

26、为减少和避免这类错误,一方面精心设计各种电路,提高计算机硬件的可靠性;另一方面是在数据编码上找出路,即采用某种编码法,通过少量附加电路,使之能发现某些错误,甚至能确定出错位置,进而实现自动改错的能力。2023/1/931计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码 数据校验码是一种常用的带有发现某些错误或自动改错能力的数据编码方法。实现原理:加进一些冗余码,使合法数据编码出现某些错误时,就成为非法编码。这样就可以通过检测编码的合法性来达到发现错误的目的。码距:一个编码系统中任意两个合法编码(码字)之间不同的二进数位

27、(bit)数叫这两个码字的码距,而整个编码系统中任意两个码字的最小距离就是该编码系统的码距。2023/1/932计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码 图2.4所示编码系统,用三个bit表示8个码字。两个码字之间不同的bit数最少为1,故该系统码距为1。如任何码字中一位或多位被颠倒,这个码字不能与其它有效信息区分开。如传送信息001,而被误收为011,因011仍是合法码字,接收机将认为011是正确信息。信息序号二进码字a2a1a000001001201030114100510161107111图图2.4用三个

28、用三个bit来表示来表示8个码字个码字2023/1/933计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码 图2.5所示编码系统,用4个bit表示8个码字,码字间的最小距离增加到2,码距为2。8个码字相互间最少有两bit的差异。如果任何信息的一个数位被颠倒,就成为一个非法码字。如信息是1001,误收为1011,接收机知道发生了一个差错,因为1011不是一个合法码字。但差错不能被纠正,偶数个差错也无法发现。图图2.5用用4个个bit来表示来表示8个码字个码字信息序号二进码字a3a2a1a00000011001210103

29、0011411005010160110711112023/1/934计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码 为使一个系统能检查和纠正一个差错,码间最小距离必须至少是“3”。最小距离为3时,或能纠正一个错,或能检二个错,但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。表2.6概括了最小距离为1至7的码的纠错和检错能力。常用的数据校验码:奇偶校验码、海明校验码、循环冗余校验码码距码的检错与纠错能力检错纠错123456700102或12加12加23加23加32023/

30、1/935计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-奇偶校验码奇偶校验码:奇偶检验码是一种最简单、最直观、应用最广泛的检错码,它的码距为2,因此它只能检出一位错。实现方法:由若干位有效信息(如1个字节),再加上1个二进制位(校验位)组成校验码。检验位的取值(0或1)将使整个校验码中“1”的个数为奇数或偶数。当校验位的取值使整个校验码中“1”的个数为奇数时,称为奇校验;当“1”的个数为偶数时为偶校验。奇偶校验的编码和检验的电路:常见的有并行奇偶统计电路,如图2.2所示。2023/1/936计算机组成与结构计算机组

31、成与结构 第第2 2章章 数据的表示和运算数据的表示和运算PO=D1 D2 D3 D4 D5 D6 D7 D8 2.1 数制与编码 2.1.5 数据校验码-奇偶校验码图 2.2 奇偶校验位的形成及检验电路=2023/1/937计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-奇偶校验码下面以奇校验为例说明对主存信息进行奇偶校验的全过程:校验位形成:当要把一个字节的代码D7D0写入主存时,就将它们送往奇偶校验逻辑电路,该电路产生的“奇形成”信号就是校验位。它将与8位代码一起作为奇校验码写入主存。若D7D0中有偶数个“1”

32、,则“奇形成”=1,若D7D0中有奇数个“1”,则“奇形成”=0。校验检测:校验检测是将读出的9位代码(8位信息位和1位校验位)同时送入奇偶校验电路检测。若读出代码没有错误,则“奇校验出错”=0;若读出代码中的某一位上出现错误,则“奇校验出错”=1,表示这个9位代码中一定有某一位出现了错误,但是具体的错误位置是不能确定的。2023/1/938计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-奇偶校验码水平垂直奇偶校验码:实际工作中还经常采用纵横都加校验奇偶校验位的编码系统水平垂直奇偶校验码。考虑传输若干个长度为m位的信

33、息。如果把这些信息编成每组n个信息的分组,则在这些不同的信息间,也能够作奇偶校验。下图中n个信息的一个分组排列成矩阵式样,并以水平奇偶(HP)及垂直奇偶(VP)的形式编出奇偶校验位。2023/1/939计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码【例】(2001年程序员试题):由 6 个字符的 7 位 ASCII 编码排列,加上水平垂直奇偶校验位构成下列矩阵(最后一列为水平奇偶校验位,最后一行为垂直奇偶校验位),则:X1X2X3X4处比特分别为?处比特分别为?X5X6X7X8处比特分别为?处比特分别为?X9X10XI1X12处比特分别为?

34、处比特分别为?Y1和和Y2处的字符分别为?处的字符分别为?0111000111102023/1/940计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码【解】从ASCII码左起第5列可知垂直为偶校验。则:从第1列可知X4=0;从第3行可知水平也是偶校验。从第2行可知X3=1;从第7列可知X8=0;从第8列可知X12=1;从第6列可知X10=0;从第6行可知X9=1;从第2列可知X1=1;从第1行可知X2=1;从第3列可知X5=1;从第4行可知X6=0;从第4列(或第5行)可知X7=0;从第7行可知X11=1;整理一下:X1X2X3X4=1110

35、,X5X6X7X8=1000X9X10X11X12=1011 由字符Y1的ASCII码1001001=49H知道,Y1即是“I”(由“D”的ASCII码是1000100=44H推得)由字符Y2的ASCII码0110111=37H知道,Y2即是“7”(由“3”的ASCII码是0110011=33H推得)假如你能记住“0”的ASCII码是0110000=30H;“A”的ASCII码是1000001=41H,则解起来就更方便了2023/1/941计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码这是由Richard

36、 Hamming于1950年提出的、目前还被广泛采用在网络传输等领域。实现原理:在有效信息位中加入几个校验位形成海明码,使码距比较均匀的拉大,并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错后,就会引起有关的几个校验组的值发生变化,这不但可以发现出错,还能指出是哪一位出错,为自动纠错提供了依据。2023/1/942计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码假设校验位的个数为r,则它能表示2r个信息,用其中的一个信息指出“没有错误”,其余的2r-1个信息指出错误发生在哪一位。然而错误也可能发

37、生在校验位,因此只有k=2r-1-r个信息能用于纠正被传送数据的位数,也就是说要满足关系。2rk+r+1(2.10)如要能检测与自动校正一位错,并发现两位错,则应在前一条件下再增加1位总校验位,此时校验位的位数r和数据位的位数k应满足下述关系:2r-1k+r (2.11)。2023/1/943计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码可计算出数据位k与校验位r的对应关系,如表2.7所示。表2.7k与r之间的关系表r值k值r值k值23412451156712262757581202023/1/944计算

38、机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码海明码的编码规律:数据位k位,校验位r位,假设海明码的最高位号为m,最低位号为1,即HmHm-1H2H1(1)校验位与数据位之和为m,每个校验位Pi在海明码中被分在位号2i-1的位置,其余各位为数据位,并按从低向高逐位依次排列的关系分配各数据位。(2)海明码的每一位码Hi(包括数据位和校验位本身)由多个校验位校验,其关系是被校验的每一位位号要等于校验它的各校验位的位号之和。以便校验的结果能正确反映出出错位的位号。2023/1/945计算机组成与结构计算机组成与结构

39、 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码例如:校验位r=5,用P1-P5表示,数据位k=8,用D1-D8表示,5个校验位P5P1对应的海明码位号应分别为H13,H8,H4,H2和H1。P5只能放在H13一位上,它已经是海明码的最高位了,其他4位满足Pi的位号等于2i-1的关系。其余为数据位Di,则有如下排列关系:P5D8D7D6D5P4D4D3D2P3D1P2P1 按照海明码的编码规律,每个海明码的位号要等于参与检验它的几个检验位的位号之和的关系,可以给出如表2.8所示的结果2023/1/946计算机组成与结构计算机组成与结构 第

40、第2 2章章 数据的表示和运算数据的表示和运算海明码位号数据位/校验位参与校验的校验位位号被校验位的海明码位号=校验位位号之和H1P111=1H2P222=2H3D11,23=1+2H4P344=4H5D21,45=1+4H6D32,46=2+4H7D41,2,47=1+2+4H8P488=8H9D51,89=1+8H10D62,810=2+8H11D71,2,811=1+2+8H12D84,812=4+8H13P51313=13表表2.8出错的海明码位号和校验位位号的关系出错的海明码位号和校验位位号的关系 2023/1/947计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算

41、数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码由有关数据位形成Pi值的偶校验的结果:P1=D1 D2 D4 D5 D7 P2=D1 D3 D4 D6 D7 P3=D2 D3 D4 D8 P4=D5 D6 D7 D8若要分清是两位出错还是一位出错,还要补充一位P5总校验位 P5=D1 D2 D3 D4 D5 D6 D7 D8 P4 P3 P2 P1 每一位数据位,都至少出现在3个Pi值的形成关系中。当任一位数据码发生变化时,必将引起3个或4个Pi值跟着变化,该海明码的码距为4。2023/1/948计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示

42、和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码按如下关系对所得到的海明码实现偶校验:S1=P1 D1 D2 D4 D5 D7 S2=P2 D1 D3 D4 D6 D7 S3=P3 D2 D3 D4 D8 S4=P4 D5 D6 D7 D8 S5=P5 P4 P3 P2 P1 D1 D2 D3 D4 D5 D6 D7 D8校验得到的结果值S5 S1能反应13位海明码的出错情况任何奇数个数出错,S5一定为1任何偶数个数出错,S5一定为0图3.11是H=12,数据位k=8,校验位r=4的海明校验线路,记作(12,8)分组码。2023/1/949计算机组成与结构计算机组成与结构 第第2

43、2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码图2.3是H=12,数据位k=8,校验位r=4的海明校验线路,记作(12,8)分组码。图中,H12,H11,H1是被校验码,D8,D7,D1是纠正后的数据,S4,S3,S2,S1是用奇偶形成线路得到的。若S4 S1全0,说明代码无错;若为1100或1011,则分别表示H12 或 H11有错,通过相关译码线经异或电路纠正该位。2023/1/950计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码图2.3 (12,8)分

44、组码海明校验线路2023/1/951计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-海明校验码假如要进一步判别是1位错还是2位错,则再增加一个校验位。并用图2.4来取代图2.3虚框中的内容,此时增加了一个奇偶形成线路S5。如为一位错,仍按图2.3来纠正数据位;如为两位错,则无法纠正错误。图图2.4判判1位位/2位错的附加线路位错的附加线路2023/1/952计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-循环冗余校验码CRC(cyclic

45、redundancy check)码可以发现并纠正信息存储或传送过程中连续出现的多位错误,在磁介质存储和计算机之间通信方面得到广泛应用;在数据存储和数据通讯领域,CRC应用广泛:著名通讯协议X.25的FCS(帧检错序列)采用CRC.CCITT,ARJ、LHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。欧洲交换机都使用CRC4。2023/1/953计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-循环冗余校验码CRC码是基于模2运算而建

46、立编码规律的校验码;模2运算特点:运算不考虑进位和借位,规则如下:模2加和模2减规则相同,按位异或,相同得0,不同得1。即:00=0,01=1,10=1,11=0。模2乘时按模2加求部分积之和。模2除是按模2减求部分余数。每求一位商应使部分余数减少一位。上商规则是:当部分余数的首位为1时,商取1,当部分余数的首位为0时,商取0;当部分余数的位数小于除数位数时,该余数即为最后余数。2023/1/954计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-循环冗余校验码模2乘例子:模2除例子:1010)101101000001

47、010100010 1011011000010101000010010101-商商-R余数余数2023/1/955计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-循环冗余校验码CRC码基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式;CRC码的关键是如何从K位信息位简便地得到r位校验位(编码),及如何从K+R位信

48、息码判断是否出错。2023/1/956计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-循环冗余校验码CRC码的编码方法:将待编码的k位有效信息位组表达为多项式M(x):M(x)=Ck-1xk-1+Ck-2xk-2+Cixi+C1x+C0将信息位组左移r位,则可表示为多项式M(x)xr。可空出r位,以便拼接r位校验位。CRC码用多项式M(x)xr除以G(x)(生成多项式)所得余数作为校验位。为了得到r位余数(校验位),G(x)必须是r+1位。设所得余数表达为R(x),商为Q(x)。将余数拼接在信息位组左移空出的r位上,

49、构成有效信息的CRC码。多项式表达为:M(x)xr+R(x)=Q(x)G(x)+R(x)+R(x)=Q(x)G(x)+R(x)+R(x)=Q(x)G(x)2023/1/957计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1 数制与编码 2.1.5 数据校验码-循环冗余校验码CRC码的编码方法:因此所得CRC码可被G(x)表示的数码除尽。如果CRC码在传输过程中不出错,其余数必为0;如果传输过程中出错,则余数不为0,由余数指出哪一位出错,即可纠正。2023/1/958计算机组成与结构计算机组成与结构 第第2 2章章 数据的表示和运算数据的表示和运算2.1

50、数制与编码 2.1.5 数据校验码-循环冗余校验码【例2.4】已知有效信息为011,试用生成多项式为G(x)=10111将其编码。解:有效信息M(x)=011=x+1,n=3由G(x)=10111=x4+x2+x+1 得k+1=5,k=4将有效信息左移4位后再被G(x)模2除,即M(x)x4=x5+x4对应的代码为0110000,用G(x)的二进制编码10111来除,如下:所以,M(x)x4+R(x)=0110000+1001=0111001为CRC码。总信息位为7位,有效信息位为3位,上述0111001码称(7,3)码 2023/1/959计算机组成与结构计算机组成与结构 第第2 2章章 数

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 大学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁