第2章数据的表示和运算.ppt

单击此处编辑母版标题样式,单击此处编辑母版副标题样式,第,2,章 数据的表示和运算,2.1,数制与编码,2.2,定点数的表示和运算,2.3,浮点数的表示和运算,2.4,算术逻辑单元,ALU,2026/10/23,1,2.1,数制与编码,2.1.1,进位计数制及其相互转换,当使用,汇编语言,或者,高级语言,编写程序时，一般都采用,十进制,形式；有时出于某种需要也采用十六进制形式或者二进制形式来表示。但是在,计算机内部,，数据的表示、存储和运算均采用,二进制,形式。,进位计数制：,又称为数制，即按进位制的原则进行计数。数制由两大要素组成：基数,R,和各数位的权,W,。,基数,R,决定了数制中各数位上允许出现的数码个数，基数为,R,的数制称为,R,进制数。,权,W,则表明该数位上的数码所表示的单位数值的大小，权,W,与数位的位置有关。,计算机中常用的进位计数制有二进制、八进制、十进制和十六进制,。,2026/10/23,2,2.1,数制与编码,2.1.1,进位计数制及其相互转换,假设,任意数值,N,用,R,进制数,来表示，表示形式为,n+k,个自左向右排列的符号来表示：,N=(D,n-1,D,n-2,D,0,.D,-1,D,-2,D,-k,),R,式中,Di(-kin-1),为该数制采用的基本符号，可取值,0,1,2,R-1,，小数点隐含在,D,0,与,D,-1,之间，整数部分有,n,位，小数部分有,k,位，数值,N,的实际值为,：,2026/10/23,3,2.1,数制与编码,2.1.1,进位计数制及其相互转换,十进制,(Decimal),：基数为,10,，允许使用的数字有,10,个（,0-9,）。主要特点是逢十进一。任意一个十进制数可以表示为：,例如十进制数,135.26,可以表示为：,2026/10/23,4,2.1,数制与编码,2.1.1,进位计数制及其相互转换,二进制,(Binary),：基数为,2,，可使用的数字只有,0,和,1,，逢二进一。任意一个二进制数可以表示为,：,例如,二进制数,(1100.1011),2,可以表示,为：,2026/10/23,5,2.1,数制与编码,2.1.1,进位计数制及其相互转换,非十进制转化为十进制,：非十进制数转为十进制数时将非十进制数按权展开，然后求和。,【,例,2.1】,将下列非十进制数转化为十进制。,(1207),8,=18,3,28,2,08,1,78,0,=512+128+0+7=(647),10,(A7),16,=(1016,1,+716,0,),10,=(160+7),10,=(167),10,2026/10/23,8,例：,39,转换成二进制数,(39),10,=(100111),2,2 39 1,（,b,0,）,2 19 1,（,b,1,）,2 9 1,（,b,2,）,2 4 0,（,b,3,）,2 2 0,（,b,4,）,2 1 1,（,b,5,）,0,2.1,数制与编码,2.1.1,进位计数制及其相互转换,十进制转化为非十进制,：十进制数转换为非十进制数时需将十进制数整数部分和小数部分分别转换，再将结果写到一起。,十进制整数转换为非十进制整数,：,除,R,取余法。十进制整数不断除以,R,，直至商为,0,。每除一次取一个余数，从低位排向高位。,例,：,208,转换成十六进制数,(208),10,=(D0),16,16,208,余,0,16,13,余,13=D,H,0,2026/10/23,9,2.1,数制与编码,2.1.1,进位计数制及其相互转换,十进小数转换为非十进制小数,：乘,R,取整法。用转换进制的基数乘以小数部分，直至小数为,0,或达到转换精度要求的位数。每乘一次取一次整数，从最高位排到最低位。,例：,0.625,转换成二进制数,0.625,2,1.25 1 (b-1),0.25,2,0.50 0 (b-2),0.50,2,1.00 1 (b-3),所以,(0.625),10,=(0.101),2,2026/10/23,10,2.1,数制与编码,2.1.1,进位计数制及其相互转换,【,例,2.2】,将,(12.6875),10,转化为二进制数。,整数部分,(12),10,=(1100),2,2026/10/23,11,2.1,数制与编码,2.1.1,进位计数制及其相互转换,【,例,2.2】,将,(12.6875),10,转化为二进制数。,小数部分,(0.6875),10,=(0.1011),2,.,所以,(12.6875),10,=(1100.1011),2,2026/10/23,12,2.1,数制与编码,2.1.1,进位计数制及其相互转换,【,课堂练习,】,将,(105.3125),10,转化为二进制数。,(105.3125),10,=(1101001.0101),2,2026/10/23,13,2.1,数制与编码,2.1.1,进位计数制及其相互转换,二进制、八进制与十六进制的转换：,3,位二进制数组成,1,位八进制数，,4,位二进制数组成,1,位十六进制数,二进制转换为八进制,：从小数点开始，向两边每,3,位为一组，整数部分不足,3,位在前面补“,0”,，小数部分不足,3,位在后面补“,0”,。,八进制转换为二进制,：过程相反，每一位八进制数转换为,3,位二进制编码。,二进制转换为十六进制,：从小数点开始，向两边每,4,位为一组，整数部分不足,4,位在前面补“,0”,，小数部分不足,4,位在后面补“,0”,。,十六进制转换为二进制,：只需将每一位十六进制数写成它的,4,位二进制编码即可。,八进制与十六进制的转换先转换成二进制，然后再转换为所求的进制数,2026/10/23,14,2.1,数制与编码,2.1.1,进位计数制及其相互转换,【,例,2.3】,将,(11011.11001),2,转化为八进制、十六进制，将,(751),8,转化为十六进制。,(11011.11001),2,=(,011,011,.,110,010,),2,=(33.62),8,(11011.11001),2,=(,0001,1011,.,1100,1000,),2,=(1B.C8),16,(751),8,=(,111,101,001,),2,=(,0001,1110,1001,),2,=(1 E 9),16,2026/10/23,15,2.1,数制与编码,2.1.2,真值和机器数,计算机中的数据可分两类：无符号数和有符号数。,无符号数,：即没有符号的数，在寄存器中的每一位均可存放数值。,有符号数,：即带有符号的数，存放时需要留出位置存放符号。符号“正”、“负”需要数字化，一般用“,0”,表示正号，用“,1”,表示负号，并将它放在有效数字前面。,机器数,：符号“数字化”的数,真 值,：带“,+”,或“,-”,符号的数,例如，真值是,+0.11001,，机器数为,0.11001,；真值为,0.11001,，机器数为,1.11001,2026/10/23,16,2.1,数制与编码,2.1.3 BCD,码,BCD,码,:,使用二进制数编码来表示十进制数的方法，又叫做二,-,十进制码。一般用,4,位二进制编码来表示一个十进制数。,常用的,BCD,码分为有权码和无权码。,有权码,:,每一位都有固定的权值，加权求和的值即为它所表示的十进制数。常用的有权码有,8421,码、,2421,码、,5211,码等，,8421,码的,4,位二进制数的权从高到低依次是,8,、,4,、,2,、,1,。一般提到的,BCD,码就是指,8421,码。这种编码的优点是这,4,位二进制数之间满足二进制的进位规则。,2026/10/23,17,2.1,数制与编码,2.1.3 BCD,码,在计算机内部实现,BCD,码算术运算，要对运算结果进行修正。,BCD,码加法运算修正规则,：如果两个一位,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,修正,2026/10/23,18,2.1,数制与编码,2.1.3 BCD,码,其它几种有权码：,2421,、,5211,、,4311,码都采用,4,位有权的二进制码表示,1,个十进制数，但这,4,位二进制之间不符合二进制规则。这几种有权码有一特点：任何两个相加之和等于,(9)10,的二进制码互为反码。,如,2421,码中，,0(0000),与,9(1111),、,1(0001),与,8(1110),，互为反码。,表,2.1,给出了十进制数的几种常见的,4,位有权码。,2026/10/23,19,2.1,数制与编码,2.1.3 BCD,码,十进制数,8421,码,2421,码,5211,码,4311,码,0,0 0 0 0,0 0 0 0,0 0 0 0,0 0 0 0,1,0 0 0 1,0 0 0 1,0 0 0 1,0 0 0 1,2,0 0 1 0,0 0 1 0,0 0 1 1,0 0 1 1,3,0 0 1 1,0 0 1 1,0 1 0 1,0 1 0 0,4,0 1 0 0,0 1 0 0,0 1 1 1,1 0 0 0,5,0 1 0 1,1 0 1 1,1 0 0 0,0 1 1 1,6,0 1 1 0,1 1 0 0,1 0 1 0,1 0 1 1,7,0 1 1 1,1 1 0 1,1 1 0 0,1 1 0 0,8,1 0 0 0,1 1 1 0,1 1 1 0,1 1 1 0,9,1 0 0 1,1 1 1 1,1 1 1 1,1 1 1 1,表,2.1 4,位有权码,2026/10/23,20,2.1,数制与编码,2.1.3 BCD,码,无权码：,4,位二进制编码的每一位没有固定的权。在采用的无权码的一些方案中，采用的比较多的是余,3,码，格雷码,余,3,码：,把原二进制的每个代码都加,0011,值得到的。优点是执行十进制数位相加时，能正确产生进位信号，还给减法运算带来了方便。余,3,码的执行加法运算的规则：当两个余,3,码相加不产生进位时，应从结果中减去,0011,；产生进位时，应将进位信号送入高位余,3,码，同时本位加,0011,的修正操作。,格雷码：,它的任何两个相邻的编码之间只有,1,个二进制位的状态不同，其余,3,个二进制位必须具有相同状态。优点：从一个编码变成下一个相邻编码时，只有,1,位的状态发生变化，有利于得到更好的译码波形，在模拟,/,数字转换的电路中得到更好的运行结果。,2026/10/23,21,2.1,数制与编码,2.1.3 BCD,码,表,2.2 4,位无权码,十进制数,余,3,码,格雷码,(1),格雷码,(2),0,0 0 1 1,0 0 0 0,0 0 0 0,1,0 1 0 0,0 0 0 1,0 1 0 0,2,0 1 0 1,0 0 1 1,0 1 1 0,3,0 1 1 0,0 0 1 0,0 0 1 0,4,0 1 1 1,0 1 1 0,1 0 1 0,5,1 0 0 0,1 1 1 0,1 0 1 1,6,1 0 0 1,1 0 1 0,0 0 1 1,7,1 0 1 0,1 0 0 0,0 0 0 1,8,1 0 1 1,1 1 0 0,1 0 0 1,9,1 1 0 0,0 1 0 0,1 0 0 0,2026/10/23,22,2.1,数制与编码,2.1.4,字符和字符串,字符,：,字母、数码、运算符号、标点符号等，汉字也属于字符。使用计算机的过程必然要涉及字符。由于计算机只能识别,0,和,1,两种数码，所以字符也应采用二进制编码。,目前经常用的是美国国家信息交换标准字符码，简称,ASCII,(American Standard Code for Information Interchange),码。,ASCII,码,:7,位二进制代码表示一个字符，称为标准或基本,ASCII,码，如,表,2.3,所示,。,2026/10/23,23,0,000,1,001,2,010,3,011,4,100,5,101,6,110,7,111,0000,0,NUL,DLE,SP,0,P,、,p,0001,1,SOH,DC1,!,1,A,Q,a,q,0010,2,STX,DC2,”,2,B,R,b,r,0011,3,ETX,DC3,#,3,C,S,c,s,0100,4,EOT,DC4,$,4,D,T,d,t,0101,5,ENQ,NAK,%,5,E,U,e,u,0110,6,ACK,SYN,&,6,F,V,f,v,0111,7,BEL,ETB,7,G,W,g,w,1000,8,BS,CAN,(,8,H,X,h,x,1001,9,HT,EM,),9,I,Y,i,y,1010,A,LF,SUB,*,:,J,Z,j,z,1011,B,VT,ESC,+,;,K,k,1100,C,FF,FS,N,n,1111,F,SI,US,/,?,O,o,DEL,高位,b,6,b,5,b,4,低位,b,3,b,2,b,1,b,0,7,位,ASCII,码编码表,2026/10/23,24,2.1,数制与编码,2.1.4,字符和字符串,标准,ASCII,码,：有,128,种的组合，每种组合可代表一个字符。包括所有大写和小写字母，数字,0,到,9,、标点符号，及在美式英语中使用的特殊控制字符。,扩充,ASCII,码,:,在标准,ASCII,码前面增加一个二进制位，用,8,位二进制数来给字符编码。共有,256,种组合，可给,256,个字符编码。前,128,个字符的最高位为,0,，用于表示标准,ASCII,码。后,128,个字符的最高位为,1,，用于表示,128,种特殊符号，如制表符等,。,2026/10/23,25,2.1,数制与编码,2.1.4,字符和字符串,汉字编码,：,计算机的汉字处理技术必须解决,3,个问题：汉字的输入、存储与交换和汉字的输出，它们分别对应于汉字的输入码、内码、交换码和字形码。,汉字输入码,:,将汉字输入到计算机中多用的编码,。,数字输入法,：,对每个汉字采用一个数字串进行编码，例如区位码、国标码等。优点是无重复码，缺点是难以记忆。,字形分解法,：,将汉字按其规则和笔画划分成若干部件，用字母或者数字进行编码。如五笔字型输入法、郑码输入法等。,拼音输入法,：,是以汉字拼音为基础的输入方法。如全拼输入法、智能,ABC,输入法等。优点是无须记忆，缺点是重码率较高。,音形输入法,：,利用拼音输入法和字形分解法的各自优点，兼顾汉字的音和形，将两者混合使用。如自然码输入法。,2026/10/23,26,2.1,数制与编码,2.1.4,字符和字符串,汉字内码,：,是计算机系统内部处理、存储汉字所使用的统一代码，一般采用两个字节表示一个汉字。汉字的输入码可以有多种，但内码在计算机中是唯一的。,汉字交换码：,不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所用的代码标准。目前常用的是国标码，即国家标准化信息用汉字编码。国标汉字共有,6763,个，分两级，一级汉字为常用汉字，共,3755,个；二级汉字是非常用汉字，共,3008,个。每个汉字对应,4,位十六进制数（两个字节）。,2026/10/23,27,2.1,数制与编码,2.1.4,字符和字符串,汉字字形码,：,目前的汉字处理系统中，字形信息的表示可以分为两大类：一类是用活字或文字版的母体字形形式，另一类是用点阵表示法、矢量表示法等形式，其中最基本应用最广泛的是后者。,2026/10/23,28,2.1,数制与编码,2.1.4,字符和字符串,字符串,：,连续的一串字符,通常方式下,它们占用主存中连续的多个字节,每个字节存一个字符。,当主存字由,2,个或,4,个字节组成时,在同一个主存字中,既可以按,从低位字节向高位字节的顺序存放,字符串的内容,也可以按,从高位字节向低位字节的次序顺序存放,字符串的内容。这两种存放方式都是常用方式。,如，,1F AB THEN READ(C),就可有两种不同存放方式。假定每个主存字由,4,个字节组成,图,2.1,(a),是按从高位字节向低位字符的次序存放,图,2.1,(b),按从低位字节向高位字节的次序存放。主存中每个字节存放的是相应字符的,ASCII,编码值。,2026/10/23,29,2.1,数制与编码,2.1.4,字符和字符串,I,F,A,B,T,H,E,N,R,E,A,D,(,C,),A,F,I,T,B,N,E,H,D,A,E,R,),C,(,(a)(b),2026/10/23,30,2.1,数制与编码,2.1.5,数据校验码,计算机系统中的数据，在读写、存取和传送的过程中可能产生错误（随机错误或突发错误）。,为减少和避免这类错误，,一方面精心设计各种电路,，提高计算机硬件的可靠性；,另一方面是在数据编码上找出路,，即采用某种编码法，通过少量附加电路，使之能发现某些错误，甚至能确定出错位置，进而实现自动改错的能力,。,2026/10/23,31,2.1,数制与编码,2.1.5,数据校验码,数据校验码,是一种常用的带有,发现,某些错误或自动,改错,能力的数据编码方法。,实现原理,：加进一些冗余码，使合法数据编码出现某些错误时，就成为非法编码。这样就可以通过检测编码的合法性来达到发现错误的目的。,码距,：一个编码系统中任意两个合法编码（码字）之间不同的二进数位（,bit,）数叫这,两个码字的码距，,而整个编码系统中任意两个码字的最小距离就是该,编码系统的码距,。,2026/10/23,32,2.1,数制与编码,2.1.5,数据校验码,图,2.4,所示编码系统，用,三个,bit,表示,8,个码字,。两个码字之间不同的,bit,数最少为,1,，故该系统,码距为,1,。如任何码字中一位或多位被颠倒，这个码字不能与其它有效信息区分开。如传送信息,001,，而被误收为,011,，因,011,仍是合法码字，接收机将认为,011,是正确信息,。,信息序号,二进码字,a,2,a,1,a,0,0,0,0,0,1,0,0,1,2,0,1,0,3,0,1,1,4,1,0,0,5,1,0,1,6,1,1,0,7,1,1,1,图,2.4,用三个,bit,来表示,8,个码字,2026/10/23,33,2.1,数制与编码,2.1.5,数据校验码,图,2.5,所示编码系统，用,4,个,bit,表示,8,个码字,，码字间的最小距离增加到,2,，,码距为,2,。,8,个码字相互间最少有两,bit,的差异。如果任何信息的一个数位被颠倒，就成为一个非法码字。如信息是,1001,，误收为,1011,，接收机知道发生了一个差错，因为,1011,不是一个合法码字。但差错不能被纠正，偶数个差错也无法发现,。,图,2.5,用,4,个,bit,来表示,8,个码字,信息序号,二进码字,a,3,a,2,a,1,a,0,0,0,0,0,0,1,1,0,0,1,2,1,0,1,0,3,0,0,1,1,4,1,1,0,0,5,0,1,0,1,6,0,1,1,0,7,1,1,1,1,2026/10/23,34,2.1,数制与编码,2.1.5,数据校验码,为使一个系统能检查和纠正一个差错，,码间最小距离必须至少是“,3”,。最小距离为,3,时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。表,2.6,概括了最小距离为,1,至,7,的码的纠错和检错能力,。,常用的数据校验码,：奇偶校验码、海明校验码、循环冗余校验码,码距,码的检错,与纠错能力,检错 纠错,1,2,3,4,5,6,7,0 0,1 0,2,或,1,2,加,1,2,加,2,3,加,2,3,加,3,2026/10/23,35,2.1,数制与编码,2.1.5,数据校验码,-,奇偶校验码,奇偶校验码,：奇偶检验码是一种最简单、最直观、应用最广泛的检错码，它的码距为,2,，因此它只能检出一位错。,实现方法,：由若干位有效信息,(,如,1,个字节,),，再加上,1,个二进制位,(,校验位,),组成校验码。检验位的取值,(0,或,1),将使整个校验码中“,1”,的个数为奇数或偶数。当校验位的取值使整个校验码中“,1”,的个数为奇数时，称为,奇校验,；当“,1”,的个数为偶数时为,偶校验,。,奇偶校验的编码和检验的电路：,常见的有,并行奇偶统计电路,，如图,2.2,所示,。,2026/10/23,36,PO=D,1,D,2,D,3,D,4,D,5,D,6,D,7,D,8,2.1,数制与编码,2.1.5,数据校验码,-,奇偶校验码,图,2.2,奇偶校验位的形成及检验电路,=,2026/10/23,37,2.1,数制与编码,2.1.5,数据校验码,-,奇偶校验码,下面以奇校验为例说明对主存信息进行奇偶校验的全过程：,校验位形成,:,当要把一个字节的代码,D7,D0,写入主存时，就将它们送往奇偶校验逻辑电路，该电路产生的“奇形成”信号就是校验位。它将与,8,位代码一起作为奇校验码写入主存。若,D7,D0,中有偶数个“,1”,，则“奇形成”,=1,，若,D7,D0,中有奇数个“,1”,，则“奇形成”,=0,。,校验检测,:,校验检测是将读出的,9,位代码,(8,位信息位和,1,位校验位,),同时送入奇偶校验电路检测。若读出代码没有错误，则“奇校验出错”,=0,；若读出代码中的某一位上出现错误，则“奇校验出错”,=1,，表示这个,9,位代码中一定有某一位出现了错误，但是具体的错误位置是不能确定的。,2026/10/23,38,2.1,数制与编码,2.1.5,数据校验码,-,奇偶校验码,水平垂直奇偶校验码,：,实际工作中还经常采用纵横都加校验奇偶校验位的编码系统,水平垂直奇偶校验码。,考虑传输若干个长度为,m,位的信息。如果把这些信息编成每组,n,个信息的分组，则在这些不同的信息间，也能够作奇偶校验。下图中,n,个信息的一个分组排列成矩阵式样，并以水平奇偶（,HP,）及垂直奇偶（,VP,）的形式编出奇偶校验位。,2026/10/23,39,2.1,数制与编码,【,例,】(2001,年程序员试题,),：由,6,个字符的,7,位,ASCII,编码排列，加上水平垂直奇偶校验位构成下列矩阵（最后一列为水平奇偶校验位，最后一行为垂直奇偶校验位），则,：,X1 X2 X3 X4,处比特分别为？,X5 X6 X7 X8,处比特分别为？,X9 X10 XI1 X12,处比特分别为？,Y1,和,Y2,处的字符分别为？,0,1,1,1,0,0,0,1,1,1,1,0,2026/10/23,40,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,，,X5X6X7X8=1000,X9X10X11X12=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,，则解起来就更方便了,2026/10/23,41,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,这是由,Richard Hamming,于,1950,年提出的、目前还被广泛采用在网络传输等领域。,实现原理,：在有效信息位中加入几个校验位形成海明码，使码距比较均匀的拉大，并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验组的值发生变化，这不但可以发现出错，还能指出是哪一位出错，为自动纠错提供了依据。,2026/10/23,42,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,假设校验位的个数为,r,，则它能表示,2,r,个信息，用其中的一个信息指出“没有错误”，其余的,2,r,-1,个信息指出错误发生在哪一位。然而错误也可能发生在校验位，因此只有,k=,2,r,-1-r,个信息能用于纠正被传送数据的位数，也就是说要满足关系,。,2,r,k+r+1(2.10),如要能,检测与自动校正一位错,，并,发现两位错,，则应在前一条件下,再增加,1,位总校验位,，此时校验位的位数,r,和数据位的位数,k,应满足下述关系：,2,r-1,k+r,(2.11),。,2026/10/23,43,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,可计算出数据位,k,与校验位,r,的对应关系，如表,2.7,所示。,表,2,.,7,k,与,r,之间的关系表,r,值,k,值,r,值,k,值,2,3,4,1,2,4,5,11,5,6,7,12,26,27,57,58,120,2026/10/23,44,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,海明码的编码规律：,数据位,k,位，校验位,r,位，假设海明码的最高位号为,m,，最低位号为,1,，即,H,m,H,m-1,H,2,H,1,(1),校验位与数据位之和为,m,，,每个校验位,Pi,在海明码中被分在位号,2,i-1,的位置,，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。,(2),海明码的每一位码,H,i,(,包括数据位和校验位本身,),由多个校验位校验，其关系是,被校验的每一位位号要等于校验它的各校验位的位号之和,。以便校验的结果能正确反映出出错位的位号。,2026/10/23,45,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,例如,:,校验位,r=5,，用,P,1,-P,5,表示，数据位,k=8,，用,D,1,-D,8,表示，,5,个校验位,P,5,P,1,对应的海明码位号应分别为,H,13,，,H,8,，,H,4,，,H,2,和,H,1,。,P,5,只能放在,H,13,一位上，它已经是海明码的最高位了,，,其他,4,位满足,P,i,的位号等于,2,i-1,的关系,。其余为数据位,D,i,，则有如下排列关系：,P,5,D,8,D,7,D,6,D,5,P,4,D,4,D,3,D,2,P,3,D,1,P,2,P,1,按照海明码的编码规律，,每个海明码的位号要等于参与检验它的几个检验位的位号之和的关系,，可以给出如表,2,.,8,所示的结果,2026/10/23,46,海明码位号,数据位,/,校验位,参与校验的校验位位号,被校验位的海明码位号,=,校验位位号之和,H,1,P,1,1,1=1,H,2,P,2,2,2=2,H,3,D,1,1,，,2,3=1+2,H,4,P,3,4,4=4,H,5,D,2,1,，,4,5=1+4,H,6,D,3,2,，,4,6=2+4,H,7,D,4,1,，,2,，,4,7=1+2+4,H,8,P,4,8,8=8,H,9,D,5,1,，,8,9=1+8,H,10,D,6,2,，,8,10=2+8,H,11,D,7,1,，,2,，,8,11=1+2+8,H,12,D,8,4,，,8,12=4+8,H,13,P,5,13,13=13,表,2.8,出错的海明码位号和校验位位号的关系,2026/10/23,47,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,由有关数据位形成,P,i,值的,偶,校验,的结果,:,P,1,=D,1,D,2,D,4,D,5,D,7,P,2,=D,1,D,3,D,4,D,6,D,7,P,3,=D,2,D,3,D,4,D,8,P,4,=D,5,D,6,D,7,D,8,若要分清是两位出错还是一位出错，还要,补充一位,P,5,总校验位,P,5,=D,1,D,2,D,3,D,4,D,5,D,6,D,7,D,8,P,4,P,3,P,2,P,1,每一位数据位，都至少出现在,3,个,P,i,值,的形成关系中。当任一位数据码发生变化时，必将引起,3,个或,4,个,P,i,值跟着变化，该海明码的,码距为,4,。,2026/10/23,48,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,按如下关系对所得到的海明码实现,偶校验,:,S,1,=P,1,D,1,D,2,D,4,D,5,D,7,S,2,=P,2,D,1,D,3,D,4,D,6,D,7,S,3,=P,3,D,2,D,3,D,4,D,8,S,4,=,P,4,D,5,D,6,D,7,D,8,S,5,=P,5,P,4,P,3,P,2,P,1,D,1,D,2,D,3,D,4,D,5,D,6,D,7,D,8,校验得到的结果值,S,5,S,1,能反应,13,位海明码的出错情况,任何奇数个数出错，,S,5,一定为,1,任何偶数个数出错，,S,5,一定为,0,图,3.11,是,H=12,，数据位,k=8,，校验位,r=4,的海明校验线路，记作,(12,，,8),分组码。,2026/10/23,49,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,图,2.3,是,H=12,，数据位,k=8,，校验位,r=4,的海明校验线路，记作,(12,，,8),分组码。,图中，,H,12,H,11,H,1,是被校验码，,D,8,D,7,D,1,是纠正后的数据，,S,4,S,3,S,2,S,1,是用奇偶形成线路得到的。,若,S,4,S,1,全,0,，说明代码无错；若为,1100,或,1011,，则分别表示,H,12,或,H,11,有错，通过相关译码线经异或电路纠正该位,。,2026/10/23,50,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,图,2.3 (12,，,8),分组码海明校验线路,2026/10/23,51,2.1,数制与编码,2.1.5,数据校验码,-,海明校验码,假如要进一步判别是,1,位错还是,2,位错，则再增加一个校验位,。并用图,2.4,来取代图,2.3,虚框中的内容，此时增加了一个奇偶形成线路,S,5,。如为,一位错，仍按图,2.3,来纠正数据位,；如为,两位错，则无法纠正错误,。,图,2.4,判,1,位,/2,位错的附加线路,2026/10/23,52,2.1,数制与编码,2.1.5,数据校验码,-,循环冗余校验码,CRC(cyclic redundancy check),码可以发现并纠正信息存储或传送过程中连续出现的多位错误，在磁介质存储和计算机之间通信方面得到广泛应用,;,在数据存储和数据通讯领域，,CRC,应用广泛,:,著名通讯协议,X.25,的,FCS(,帧检错序列,),采用,CRC.CCITT,，,ARJ,、,LHA,等压缩工具软件采用的是,CRC32,，磁盘驱动器的读写采用了,CRC16,，通用的图像存储格式,GIF,、,TIFF,等也都用,CRC,作为检错手段。欧洲交换机都使用,CRC4,。,2026/10/23,53,2.1,数制与编码,2.1.5,数据校验码,-,循环冗余校验码,CRC,码是基于,模,2,运算,而建立编码规律的校验码,;,模,2,运算特点：,运算不考虑进位和借位,，,规则,如下：,模,2,加和模,2,减规则相同，按位异或，相同得,0,，不同得,1,。即：,00=0,，,01=1,，,10=1,，,11=0,。,模,2,乘时按模,2,加求部分积之和。,模,2,除是按模,2,减求部分余数。每求一位商应使部分余数减少一位。,上商规则,是：当部分余数的首位为,1,时，商取,1,，当部分余数的首位为,0,时，商取,0,；当部分余数的位数小于除数位数时，该余数即为最后余数。,2026/10/23,54,2.1,数制与编码,2.1.5,数据校验码,-,循环冗余校验码,模,2,乘例子：模,2,除例子：,1 0 1 0,)1 0 1,1 0 1 0,0 0 0 0,1 0 1 0,1 0 0 0 1 0,1,0,1,1 0 1,1,0 0 0 0,1 0 1,0,1 0,0 0 0,1,0 0,1 0 1,0 1,-,商,-R,余数,2026/10/23,55,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,位信息码判断是否出错。,2026/10/23,56,2.1,数制与编码,2.1.5,数据校验码,-,循环冗余校验码,CRC,码的编码方法：,将待编码的,k,位有效信息位组表达为,多项式,M(x),：,M(x)=C,k-1,x,k-1,+C,k-2,x,k-2,+C,i,x,i,+C,1,x+C,0,将信息位组,左移,r,位,，则可表示为多项式,M(x)x,r,。可空出,r,位，以便拼接,r,位校验位。,CRC,码用多项式,M(x)x,r,除以,G(x),(,生成多项式,),所得余数作为校验位。为了得到,r,位余数,(,校验位,),，,G(x),必须是,r+1,位。,设所得余数表达为,R(x),，商为,Q(x),。将余数拼接在信息位组左移空出的,r,位上，构成有效信息的,CRC,码。多项式表达为：,M(x)x,r,+R(x)=,Q(x)G(x)+R(x),+R(x),=,Q(x)G(x),+,R(x)+R(x),=Q(x)G(x),2026/10/23,57,2.1,数制与编码,2.1.5,数据校验码,-,循环冗余校验码,CRC,码的编码方法：,因此所得,CRC,码可被,G(x),表示的数码除尽。,如果,CRC,码在传输过程中不出错，其余数必为,0,；,如果传输过程中出错，则余数不为,0,，由余数指出哪一位出错，即可纠正。,2026/10/23,58,2.1,数制与编码,2.1.5,数据校验码,-,循环冗余校验码,【,例,2.4】,已知有效信息为,011,，试用生成多项式为,G,(,x,)=10111,将其编码。,解：,有效信息,M,(,x,)=011=,x,+1,，,n,=3,由,G,(,x,)=10111=,x,4,+,x,2,+,x,+1,得,k,+1=5,，,k,=4,将有效信息左移,4,位后再被,G,(,x,),模,2,除，即,M,(,x,),x,4,=,x,5,+,x,4,对应的代码为,0110000,，用,G,(,x,),的二进制编码,10111,来除，如下：,所以，,M,(,x,),x,4,+R(,x,)=0110000+1001=0111001,为,CRC,码。,总信息位为,7,位，有效信息位为,3,位，上述,0111001,码称,(7,，,3),码,2026/10/23,59,2.1,数制与编码,2.1.5,数据校验码,-,循环冗余校验码,【,课堂练习,】,对,4,位有效信息,(1100),求循环校验编码，选择生成多项式,(1011),。,解：,M(x)=x,3,+x,2,=1100(k=4