数据与文字的表示方法(含数据校验)课件

2-1 数据与文字的表示方法 计算机组成原理计算机组成原理数据与文字表示2Outlinevv2.12.1非非数数值值数数据表示法据表示法vv2.22.2 数数值值数数据表示法据表示法vv2.32.3 数数据信息的校据信息的校验验数据与文字表示32.1 非非数数值数数据表示法据表示法v字符表示法charactersv汉字表示法Chinesecharacters数据与文字表示42.1.1 Character representation v如何使用数值表示字符数据vStandardsASCII-American Standard Code for Information Interchange(ANSI 7bits)EBCDIC-Extended Binary-Coded Decimal Interchange Code(IBM 8bits)Unicode数据与文字表示5128 Standard ASCII codesv52Lettersa-z,A-Zv10Digits0-9v34Symbols!#$%&*()v32Controlcharacters数据与文字表示6ASCIIv使用7bit表示128个字符From0000000to111111127=128v注意：ASCII中的数字字符和数字本身不相等v几乎所有计算机均支持该代码集v但不是所有语言都能用128个字符表示v8Bit=1字节，MSB=0数据与文字表示70 01 10 01 11 10 00 01 17 76 65 54 43 32 21 10 0Terminologyv计算机利用寄存器存储数据v寄存器中每个位称bit(BinaryDigiT)v最高有效位(MSB)最低有效位(LSB)MSBMostsignificantbit LSBLeast significant bit数据与文字表示82.1.2 汉字表示法字表示法v英文键盘输入汉字-输入入编码：数字编码：国标区位码，区码和位码各用两位十进制数字表示，例如“中”区位码为5448。GB2312-80信息交换用汉字编码字符集国标码是四位十六进制数，区位码则是四位的十进制数特点：无重码，但难记。拼音码：重码率高，需要会读拼音：犇猋骉蟲麤毳淼掱垚烜屾字形编码：五笔字型输入法数据与文字表示92.1.2 汉字表示法字表示法v汉字信息在计算机中的存储、交换、检索等-汉字字内内码v8bit数据仅能表示256个字符，常用汉字6000多个，故其无法表示汉字vGB2312国家标准采用16位表示,2个字节v与ASCII字符的区别，最高有效位MSB=1数据与文字表示10GB2312-80国国家家标准准v1981年，GB2312-80国家标准，包括6763个汉字/682个非汉字字符，称为国标码vGB2312字符集的构成：一级常用汉字3755个，按汉语拼音排列二级常用汉字3008个，按偏旁部首排列非汉字字符682个数据与文字表示11汉字字标准准vGB2312-1980(GB0)(简体)6763个汉字 vGB13000-199320902个汉字(Unicode 1.1版本)v汉字扩展规范GBK1.0标准1995（非国家标准）21003个字符（兼容GB2312）vGB18030-2000(1/2/4字节编码)27484汉字 （向下兼容GB2312 GBK，GB13000）宋体隶书微软雅黑华文琥珀数据与文字表示12字模字模码介介绍v字模码是用点阵表示的汉字字型代码，是汉字的字的输出形式出形式。v字模点阵的信息量是很大的，所占存储空间也很大。以16*16为例，每个汉字要占用32个字节，v因此字模点阵只能用来构成汉字库，而不能用于机内存储。数据与文字表示13Charsetvvcharset=gb2312简体中文charset=big5繁体中文charset=EUC_KR韩语charset=Shift_JIS或EUC_JP日语charset=KOI8-R/Windows-1251俄语charset=iso-8859-2中欧语系charset=utf-8unicode多语言数据与文字表示14Unicode www.unicode.orgv用于克服字符数字的限制v为所有语言中的字符分配唯一的代码v16bit字符集,17个平面，一共有17*65536=1114112个码位(每个平面有216=65536个码位)v提供唯一的代码不论任何平台不论任何程序不论任何语言Unicode目前定义的99089个字符，其中包括71226个汉字,平面2的43253个字符都是汉字。平面0上定义了27973个汉字数据与文字表示15Universal Character Set ISOUCS通用字符集ISO10646包含了用于表达所有已知语言的字符UTF(UCSTransformationFormat)UCS的实际表现形式，即怎样将Unicode定义的数字转换成程序数据UTF-8：以字节为单位对Unicode进行编码UTF-16：编码以16位无符号整数为单位UTF-32编码以32位无符号整数为单位包括拉丁语，希腊语，斯拉夫语，希伯来语，阿拉伯语，亚美尼亚语和乔治亚语的描述，还包括中文，日文和韩文这样的象形文字，以及平假名，片假名，孟加拉语，旁遮普语果鲁穆奇字符(Gurmukhi),泰米尔语，印.埃纳德语（Kannada),Malayalam，泰国语，老挝语，汉语拼音（Bopomofo),Hangul,Devangari,Gujarati,Oriya,Telugu以及其他数也数不清的语.对于还没有加入的语言，由于正在研究怎样在计算机中最好地编码它们，因而最终它们都将被加入.这些语言包括Tibetian，高棉语，Runic（古代北欧文字），埃塞俄比亚语，其他象形文字，以及各种各样的印-欧语系的语言，还包括挑选出来的艺术语言比如Tengwar,Cirth和克林贡语(Klingon).UCS还包括大量的图形的，印刷用的，数学用的和科学用的符号，包括所有由TeX,Postscript,MS-DOS2，MS-Windows,Macintosh,OCR字体，以及许多其他字处理和出版系统提供的字符.UTF-16VSUTF-8，好处在于大部分字符都以固定长度的字节(2字节)储存，但UTF-16却无法兼容于ASCII编码。c#中默认的就是UTF-16，所以在处理c#字符串的时候只能是byte,stream等方式去处理数据与文字表示举例例16在Unicode中：汉字“字”对应的数字是23383（十进制），十六进制表示为5B57。在Unicode中，我们有很多方式将数字23383表示成程序中的数据，包括：UTF-8、UTF-16、UTF-32。UTF是怎样将Unicode定义的数字转换成程序数据。例如，“汉字”对应的数字是0 x6c49和0 x5b57，而编码的程序数据是：chardata_utf8=0 xE6,0 xB1,0 x89,0 xE5,0 xAD,0 x97;/UTF-8编码char16_tdata_utf16=0 x6C49,0 x5B57;/UTF-16编码char32_tdata_utf32=0 x00006C49,0 x00005B57;/UTF-32编码这里用char、char16_t、char32_t分别表示无符号8位整数，无符号16位整数和无符号32位整数。UTF-8、UTF-16、UTF-32分别以char、char16_t、char32_t作为编码单位。（注：char16_t和char32_t是C+11标准新增的关键字。如果你的编译器不支持C+11标准，请改用unsignedshort和unsignedlong。）“汉字”的UTF-8编码需要6个字节。“汉字”的UTF-16编码需要两个char16_t，大小是4个字节。“汉字”的UTF-32编码需要两个char32_t，大小是8个字节。根据字节序的不同，UTF-16可以被实现为UTF-16LE或UTF-16BE，UTF-32可以被实现为UTF-32LE或UTF-32BE。数据与文字表示172.2 数数值数数据表示方法据表示方法v计算机数值数据表示的特点v进位制数v数的定点、浮点表示v机器数二进制表示数值数据的需要让计算机能够进行正确的运算数据与文字表示18计算机算机数数据据编码需要考需要考虑的因素的因素:v数的类型(小数、整数、实数和复数）v数值范围v数值精确度v数值存储和处理所需的硬件代价数据与文字表示19计算机算机数数据据编码特点特点v少量简单的基本符号表示大量复杂的信息v状态简单v电路实现简单v运算方便v硬件成本数据与文字表示20Human vs.Computerv人们日常生活采用10进制天生10个手指v计算机采用二进制计算机采用电子开关开关仅仅包括两个状态ONOFF数据与文字表示21十十进制制编码特点特点v0123456789共10种状态，状态过多v运算组合状态过多v加法组合数=55=36=3八进制：二进制：结论：二：二进制的制的组合合状状态最少最少对R进制数进行算术求和或求积运算，其运算规则各有R(R+1)/2种数据与文字表示22二二进制制编码特点特点v“0、1”物理上容易实现具有两种稳定状态的物理器件很多用数字电路的两个状态表示(门电路的导通与截止、电压的高低）v机器可靠性高电压的高低、电流的有无，两种物理状态稳定、分明，抗干扰能力强，鉴别信息的可靠性高v逻辑判断方便与二值逻辑的 真 假 两个值对应简单v二进制位可以表示任何对象(字符，数值，逻辑值)v运算规则简单0+1=1+0=1 1+1=0 0+0=0仅有3种运算规则大大简化运算器等物理器件的设计，一个异异或或门即可完成该运算数据与文字表示23一位全加器：如何一位全加器：如何计算算0,1的加法的加法输入输入:加数加数A Ai i 、B Bi i 低位进位输入低位进位输入C Ci i输出输出:和数和数S Si i ，进位输出，进位输出C Ci+1i+1111111001110101010011000进位Ci+10110和数Si110010100000加数Bi加数Ai低位进位Ci数据与文字表示24二二进制加法器基本制加法器基本电路路数据与文字表示25进制表示制表示N代表一个数值r是这个数制的基基(Radix)i表示这些符号排列的位号Di是位号为i的位上的一个符号ri是位号为i的位上的1代表的值Di*ri是第第i位的所代表的位的所代表的实际值表示m+k+1位的值求累加和累加和数据与文字表示26例子例子v(10456)1011040103 410251016100v(0 xF96)16v(10010001)2-按权展开按权展开位权的大小是以基数为底，数字符号所处的位置的序号为指数的整数次幂。二进制数就是2的n次幂。127026 025 124 023022 021 120=145F1629161 6100=3990数据与文字表示27进制制转换v二进制数转八进制v二进制数转十六进制v二进制数转十进制v十进制数转二进制数据与文字表示28二到八或十六二到八或十六进制制转换v二进制转到八进制 从小数点向左右三位一分三位一分组(10 011 100.01)2=v二进制转十六进制 从小数点向左右四位一分四位一分组 (1001 1100.01)2 =注意：注意：整数部分不足位数对转换无影响，整数部分不足位数对转换无影响，小数部分不足位数要补零凑足小数部分不足位数要补零凑足，否则出错。，否则出错。(234.2)8010(9C.4)160100数据与文字表示29二二进制制转十十进制制从二进制数求其十进制的值，逐位码权累加求和-按按权展展开开v10010001127026025124023022021120数据与文字表示30十十进制制转二二进制制整数部分除2取余小数部分乘2取整2 1 122252101 11 10 01 10.625*21 10.25 *20 00.5 *21 1 0.0 除尽为止 1011低低高高高高低低求得位数满足要求为止（11.625）10=（？）21011.101数据与文字表示31进制制转换的的简单运运算方法算方法v17/12817/128的二进制表示?v记住几个常用的2的幂：2532 2664 27128 28256 29512 2101024(1Kilo)2112048 21240962138182 21416364 2153272821665536 2201048576(1Mega)2301073741824(1Giga)2401Tera更大的单位是多少？2501 Peta 2601 Exa 2701 Zetta 2801 YottaMEMORIZE!数据与文字表示321999 New IEC Standard Prefixes http:/en.wikipedia.org/wiki/Binary_prefixvSI(International System of Units)仅指10进制v234可以访问多少存储单元?v2.5TiB存储空间需要多少地址线进行译码？MEMORIZE!硬盘厂商及通讯行业是计算机行业唯一使用SI因子的数据与文字表示33几几个个简化化运运算的例子算的例子-17/128=?65539=65539=1111 1111111111111110=11111110=1111111111111111-1=21111-1=21212-1-1=4094-1-1=4094130=130=1111111111111111011101112 21212-1-8-1-82003=2003=MEMORIZE!128+2=128+2=1000100000001 10 065536+3=1000000000000001165536+3=100000000000000112047-44=1112047-44=111111111111111-32-8-41111-32-8-4-0 0010001.数据与文字表示342.2 数数值数数据表示方法据表示方法v计算机数值数据表示的特点v进位制数v数的定点、浮点表示v机器数数据与文字表示352.2.1 数数的定点、浮点表示方法的定点、浮点表示方法v定点表示(小数点位置固定的数)定点小数定点整数表示纯小数及纯整数v浮点表示vSigned&Unsigned数据与文字表示36定点小定点小数数-纯小小数数符号位小数点位置数值部分X X0 0X X1 1X X2 2X X3 3X Xn n最低有效位最低有效位最高有效位最高有效位-17/128:1 0010001数据与文字表示37v数值表示 X=X0.X1X 2X n X i=0,1,0in =X 12-1+X n-12-n+1+X n 2-nv数值范围0|x|1-2-n 定点小定点小数数的的编码 0.00000000 0.11111111 +0.00000001 =1.00000000数据与文字表示38定点小定点小数数的表示范的表示范围0111120 2-1 2-2 2-(n-1)2-n 0000120 2-1 2-2 2-(n-1)2-n 最大正数最大正数最小正数最小正数最大正数最大正数=2-1+2-2+2-n=1-2-n 最小正数最小正数=2-n原码表示的绝对值原码表示的绝对值最大的负数最大的负数11111 20 2-1 2-2 2-(n-1)2-n原码表示时原码表示时,正数和负数的范围是对称的正数和负数的范围是对称的,故绝对值最大的负数等故绝对值最大的负数等于正数值加上于正数值加上”号号,其真值为其真值为(1 2-n)数据与文字表示39定点整定点整数数符号位小数点位置数值部分X X0 0X X1 1X X2 2X X3 3X Xn nX X0 01 11 11 11 1X X0 00 00 00 00 00|X|2n-1最高有效位最高有效位最低有效位最低有效位数据与文字表示40v数值表示X=X1X2Xn Xi=0,1,0in=X12n-1+Xn-121+Xnv数值范围0|x|2n-1定点整定点整数数的的编码数据与文字表示41定点整定点整数数的表示范的表示范围01111 2n 2n-1 2n-2 21 20最大正数最大正数=2n-100010最小正数最小正数=1 2n 2n-1 2n-2 21 2011111原码表示的绝对值原码表示的绝对值最大的负数最大的负数 2n 2n-1 2n-2 21 20原码表示的绝对值最大负数=(2n1)数据与文字表示42浮点浮点数数如何表示如何表示v小数点的位置可按需浮动小数点的位置可按需浮动v将数据按照一定比例因子缩小成定点小数或扩大成定点整数进行表示和运算v运算完毕后再根据比例因子还原成实际数值v计算机中浮点运算有专门的器件电子的质量910-28g太阳的质量21033g定点表示方法无法直接表示该数值范围电子的质量0.910-27g太阳的质量0.21034g数据与文字表示43浮点浮点数数如何表示如何表示v电子的质量910-28gv太阳的质量21033g0.21034v科学记数法N=10EMvN=ReMM:称称为尾尾数数，是一个纯小小数数（原码或补码表示）e:是比例因子的阶数、指数，称为浮点数的阶码、指数，是一个整数（移码或补码）R:为基基数数，是常，是常数数数据与文字表示44浮点浮点数数的表示的表示v机器中表示浮点数，需要：vN=ReM=2EM=2e(m)vm:尾数，定点小数表示，给出有效数字位数，决定精度；ve：指数，整数形式表示，称为阶码，给出小数点位置，决定浮点数的表示范围。E E0 0E E1 1E E2 2E EmmMM0 0M1M2Mn尾数值阶值阶符符尾符尾符数据与文字表示45浮点浮点数数的表示范的表示范围-+负数正数0负上溢正上溢负下溢正下溢vN=2EMv|N|产生正上溢或者负上溢v|N|0产生正下溢或者负下溢注意：下溢时，浮点数值趋于零，故机器不做溢出处理，仅把它作为机器零。注意：下溢时，浮点数值趋于零，故机器不做溢出处理，仅把它作为机器零。上溢时才是浮点数真正溢出，机器需停止运算，作溢出中断处理。上溢时才是浮点数真正溢出，机器需停止运算，作溢出中断处理。一般所说的浮点溢出，均是指上溢。一般所说的浮点溢出，均是指上溢。机器零机器零:当一个浮点数的当一个浮点数的尾数为尾数为0(不论阶码是何值不论阶码是何值)，或或阶码的值比能在机器中表示的最小值还小时，计算阶码的值比能在机器中表示的最小值还小时，计算机都把该浮点数看成零值，称为机器零。机都把该浮点数看成零值，称为机器零。数据与文字表示46v机器字长一定时，阶码越长，表示范围越大，精度越低v浮点数表示范围比定点数大，精度高E E0 0E E1 1E E2 2E EmmMM0 0MM1 1MM2 2MMn n尾数值阶值阶符尾符Range&precision字长共8位：阶码7位，尾数1位，不考虑符号位，最大表示0.5*27 阶码6位，尾数2位，不考虑符号位，最大表示0.75*26数据与文字表示47Example v8位定点小数可表示的范围n0.0000001-0.1111111n 1/128 -127/128v设阶码2位，尾数4位n可表示2-11*0.0001-211*0.1111n0.0000001-111.1v设阶码3位，尾数3位n可表示2-111*0.001-2111*0.111n0.0000000001-1110000数据与文字表示48浮点浮点数数的的规格化格化问题normalization v0.05*101=50*10-2 =5*10-1 v为了在尾数中表示最多的有效数据位，提高精度v为了数据表示的唯一性v尾尾数数最高有效位最高有效位为1 1的数称为规格化数。v两种规格化数:（补码情况下）正尾数：0.1XXXXX 负尾数：1.0XXXXv机器零：全部为0，特殊的数据编码尾数用纯小数形式给出，而且尾数绝对值应大于尾数用纯小数形式给出，而且尾数绝对值应大于1/R，即小数点后第一位不为，即小数点后第一位不为0。数据与文字表示49S(1bit)E(2330共8bit)M(022共23bit)v32/64位浮点数（Float/Double）S(1bit)E(5262共11bit)M(051共52bit)N=(-1)N=(-1)S SX MX M X X 2 2E E 构成：阶码构成：阶码E E，尾数，尾数M M，符号位，符号位S S，浮点浮点数数标准准 IEEE754E E0 0E E1 1E E2 2E EmmMM0 0MM1 1MM2 2MMn n尾数值阶值阶符尾符数据与文字表示50v规格化数(Normal)-32位浮点数：(-1)s1.M2E-127 e=E-127v1.M最高数字位总是1，该标准将这个1缺省存储vEmin=1,Emax=254浮点浮点数数标准准 IEEE754数据与文字表示51单精度浮点精度浮点数数编码格式格式+0/-0000/1(-1)S(0.f)2(-126)f(非零非零)00/1(-1)S(1.f)2(e-127)f12540/1-02551+02550sNaN Signaling NaN非零非零0 xxxx2550/1NaN Not a Number非零非零1xxxx2550/1表示表示尾尾数数阶码符符号号位位数据与文字表示52IEEE754 IEEE754 规格化格化浮点浮点数数表示范表示范围Emax=2046,f=1.1111,1.111122046-1023=21023(2-2-52)Emin=1,M=0,1.021-1023=2-1022双双精度精度Emax=254,f=1.1111,1.11112254-127=2127(2-2-23)Emin=1,M=0,1.021-127=2-126单单精度精度最大值最小值格式数据与文字表示53一一个个奇怪的程序奇怪的程序main()double a,b,c;int d;b=3.3;c=1.1;a=b/c;d=b/c;printf(%f,%d,a,d);if(3.0!=a)printf(nReally?3.0!=a);3.000000,2?Really?3.0!=a二进制存储浮点数不是精确数数据与文字表示运行代码：System.out.println(0.05+0.01);System.out.println(1.0-0.42);System.out.println(4.015*100);System.out.println(123.3/100);结果如下：0.0600000000000000050.5800000000000001401.499999999999941.232999999999999954数据与文字表示1.01+2.01=3.02 v64位浮点表示：v1.01为：v0011111111110000001010001111010111000010100011110101110000101001v2.01为：v0100000000000000000101000111101011100001010001111010111000010100v3.02表示为：v0100000000001000001010001111010111000010100011110101110000101001v2.01+1.01在编程语言中的计算结果表示为：v010000000000100000101000111101011100001010001111010111000010100055数据与文字表示v结论：因为浮点数在计算机内的存储存在偏差，导致运算时，与实际期望的结果不同。v双精度数的表示法：尾数一共有52个bit，也就是最小能表示的数是2-52，取对数可得出，约是在小数点后16位，那也就是说小数点后15位是可以精确表示的，加上前置的默认1，一共有16位数字是精确可靠的。v试验一下：VC调试器的显示值v2.01的显示值：2.0099999999999998v如果只取16位有效数字，那么将最后一位8四舍五入，得到正确的表示。56数据与文字表示57一一个个奇怪的程序奇怪的程序main()float a,b,c;int d;b=3.3;c=1.1;a=b/c;d=b/c;printf(%f,%d,a,d);if(3.0!=a)printf(nRight!);3.000000,2数据与文字表示浮点数的IEEE754存储格式为（41360000）16求该浮点数的真值（十进制数值）v（41360000）16展开为二进制5801000001001101100000000000000000ve=10000010127(01111111)=00000011=31.M=1.01101100000000000000000=1.011011x=+(1.011011)x23=+1011.011=11.375数据与文字表示十进制20.59375的32位浮点数的二进制存储表示十进制20.59375转为二进制表示59v10100.100112-1=0.5,2-2=0.25,2-3=0.125v10100.10011=1.010010011x24vS=0,M=010010011,E=e+127=131v01000001101001001100000000000000数据与文字表示602.2 数数值数数据表示方法据表示方法v计算机数值数据表示的特点v进位制数v数的定点、浮点表示v机器数数据与文字表示612.2.2 机器机器数数/机器机器码v真值(书写用)将用+-表示正负的二进制数称为符号数的真值+10010，-0.101v机器不能识别书写格式v机器码(机器内部使用)将将符符号号和和数数值一起一起编码表示表示的二的二进制制数称数称为机器机器码v原码Signedmagnitude反码Onescomplementv补码Twoscomplement移码Biasednotation数据与文字表示62原原码表示法（表示法（Signed magnitude）v计算机如何表示数的正负?v增加符号位Addasignbitv最高位为符号位，0为正，1为负，数值位不变数据与文字表示63原原码表示示例表示示例v-0.1111原=1.1111v0.1111原=0.1111v1110原=01110v-1110原=11110符号位：+用0表示，-用1表示数值位不变数据与文字表示64X X 原原原原=X 0X2X 0X2n n2 2n n-X=2-X=2n n+|X|-2+|X|-2n n X X 0 0X X 原原原原=X 0X1X 0X11-X -11-X -1 X X 0 0原原码表示法表示法定点整数：定点小数：零？+0原=0.0000-0原=1.0000原码中的零有+0和-0之分数据与文字表示65原原码在在数数轴上的表示上的表示p-7+77个正数，7个负数，两个零p-(2n-1)2n-1数据位共n位二进制编码的按权展开对应的原码表示数据与文字表示66Signed MagnitudevBothpositiveandnegativezero两个0？vEqualnumberofpositivesandnegatives正负对称vEasytointerpret容易理解FirstbitisthesignRemainingbitsarenumbervSoundsideal?Butv01011001+11001101=?数据与文字表示67Signed Magnitude?010110012=8910 +110011012=-7710 001001102=3810原码运算原码运算 符号相异时必须作减法符号相异时必须作减法。数据与文字表示68Shortcomings of signed magnitude?vArithmeticcircuitcomplicatedvAlso,twozeros0 x00000000=+0ten0 x80000000=0tenWhatwouldtwo0smeanforprogramming?vThereforesignedmagnitudeabandoned数据与文字表示69反反码表示法表示法v所谓反码，就是二进制的各位数码取反v符符号号位位表示方法与原码相同vExample:710=001112-710=110002vCalledOnesComplement符号位：+用0表示，-用1表示负数的数值位需要逐位取反正数的数值位不变数据与文字表示70反反码的表示的表示v+0反=0.0000v-0反=1.1111v0.1111反=0.1111v-0.1111反=1.0000v1110反=01110v-1110反=10001符号位：+用0表示，-用1表示负数的数值位需要逐位取反正数的数值位不变数据与文字表示71X X 反反反反=X 0X2X 0X2n n2 2n+1n+11+X -21+X -2n n X X 0 0X X 反反反反=X 0X1X 0X12-22-2n n+X -1+X -1 X X 0 0反反码表示法表示法定点小数：定点小数：定点整数：定点整数：-1110反=10001-0.1111反=1.0000数据与文字表示72反反码公式公式证明明v定点小数-1x=0时p假设x=-0.x1x2xnpx反=1.x1x2xnpx反+|x|=1.111=1.111+0.001-0.001=10.000-0.001x反+|x|=2-2-nvx反=2-2-n-|x|=2-2-n+x数据与文字表示73反反码公式公式证明明v定点整数-2nx=0时p假设x=-x1x2xnp假设x反=1x1x2xnpx反+|x|=1111=1111+0001-0001=10000-0001=2n+1-1vx反=2n+1-1-|x|=2n+1-1+x数据与文字表示74X X 反反反反=X 0X2X 0X2n n2 2n+1n+11+X -21+X -2n n X X 0 0X X 反反反反=X 0X1X 0X12-22-2n n+X -1+X -1 X X 0 0反反码表示法表示法定点小数：定点小数：定点整数：定点整数：数据与文字表示75反反码在在数数轴上的表示上的表示p-7+7正数7个，负数7个，零两个p-(2n-1)2n-1数据位n位二进制编码的按权展开对应的反码表示的数据与文字表示76原原码&反反码二进制编码的按权展开对应的原码表示的二进制编码的按权展开对应的反码表示的数据与文字表示77Shortcomings of Ones complement?vArithmeticstillasomewhatcomplicated.vStilltwozeros0 x00000000=+0ten0 xFFFFFFFF=-0tenvAlthoughusedforawhileonsomecomputerproducts,onescomplementwaseventuallyabandonedbecauseanothersolutionwasbetter.数据与文字表示78有趣的有趣的时钟123691236912369v9点+9=6点v9点-3=6点v-3与+9等价v9是-3对12的补码数据与文字表示79同余的同余的概概念念v假定有两个数a和b，若用某一个整数m去除，所得的余数相同，就称a,b两个数对m同余,记作：ab(modm)v假设X,Y,Z三个数，满足下列关系：Z=nX+Y(n为整数),则称Z和Y对模X是同余的，记作：ZY(modX)YZ(modX)数据与文字表示80例子例子vZ=nX+YX为模数v以12为模v9=12+9=24+9=36+9v9，21，33，45都是相等的（同余）v-3=12-3=9v9与-3是相等的（同余）v0=12数据与文字表示81例子例子v7+(-3)v=7+(12-3)v=7+9v=16v=4v表示负数的时候如利用模的性质转换成正数，即可将原码运算中的减减法法转换成加法加法运算数据与文字表示82补码表示公式表示公式X X 补补补补=X 0X2X 0X2n n2 2n+1n+1+X -2+X -2n nX0X0X X 补补补补=X 0X1X 0X12+X -1X02+X -1X0定点小数：定点小数：定点整数：定点整数：零？数据与文字表示83补码在在数数轴上的表示上的表示p-8+7正数7个，负数8个，零1个p-2n2n-1数据位n位二进制编码的按权展开对应的补码表示的数据与文字表示84反反码、补码数数轴表示比表示比较二进制编码的按权展开对应的反码表示的二进制编码的按权展开对应的补码表示的数据与文字表示85补码与与反反码的的关关系系负定点小数时x反=2-2-n+xx补=2+x=(2-2-n+x)+2-n=x反+2-n负整数时x反=2n+1-1+xx补=2n+1+x=(2n+1-1+x)+1=x反+1数据与文字表示86补码编码的的简便方法便方法v正值：与原码相同，符号位为0v负值：符：符号号位位为1，数数值位取反，末位加位取反，末位加1,v-10101010补=101010101+1=101010110v-0.010101补=1.101011数据与文字表示87例子例子vX=+0.11111111X补=?vX=-0.11111111X补=?vX=-0.00000000X补=?X补=0.11111111X补=1.11111111+0.00000001=10.00000000=0.00000000X补=1.00000000+0.00000001=1.00000001数据与文字表示88补码的性的性质v零有唯一的表示方式0.0000补=-0.0000补=0.0000v负1的补码1补=100001取反+00001=1111111数据与文字表示89补码加加减减法法的的实现vX+Y补=X补+Y补vX-Y补=X补+-Y补v-Y补=Y补补对Y补逐位取反,再在最低位加1数据与文字表示90补码表示中的符表示中的符号号位位扩展展由X补求X/2补的方法0.230.23/10=0.023原符原符号号位位不变，符符号号位位与数与数值位位均右移一位，例如，X补=10010则X/2补=11001不同位数的整数补码相加减时，如何运算?0 0101010111000011101010111000011+?1 100111000011100?0 0101010111000011101010111000011+?0 000111000011100?数据与文字表示91补码表示中的符表示中的符号号位位扩展展不同位数的整数补码相加减时，位数少的补码数的符号位向左扩展，一直扩展到与另一数的符号位对齐。0 0101010111000011101010111000011+11111111111111111 1001110000111000 0101010101011111101010101011111 0 0101010111000011101010111000011+00000000000000000 0001110000111000 0101010111011111101010111011111数据与文字表示92模模4补码，变形形补码例：00.1010110 11.0101001又称 双符号位双符号位补码，变形补码X X 补补补补=X 0X2X 0X2n n2 2n+2n+2+X -2+X -2n nX0X0X X 补补补补=X 0X1X 0X14+X -1X04+X -1X0数据与文字表示93补码加加减减法法运运算算实例例x=0.1011y=-0.0101用模4补码求x+yx-yx补=001011,y补=111011-y补=00010100 101100 1011+11 101111 1011 1 10000 0110 0110 x+yx+y 00 101100 1011+00 010100 0101 0101 0000 0000 x-yx-y 数据与文字表示94补码特点特点v唯一的零v符号位可以直接参与运算v减法可以变成加法v负数比正数多一个数据与文字表示954.移移码表示法表示法 Biased/Excess Notationp 保持数据原有大小顺序，便于进行比较操作。p 通常仅用于表示整数，表示浮点数的阶码。定义x移=2n+x -2n x 9+6修正+0110=10011BCD表示13106数据与文字表示1072.3 数数据信息的校据信息的校验v计算机中的错误类型：1）固定性错误-元器件故障元器件故障；精心精心设计各各种种电路，提高路，提高计算机硬件的可靠性；算机硬件的可靠性；2）突发性错误-噪噪声声干干扰。采用某种编码法，通过少量的附加电路，使之能发现某些错误，甚至能确定出错位置，进而实现自动改错的能力。v数据校验码：用以发现或同时能得出错误位置特征(自自动改改错能力能力)的数据编码。数据与文字表示1082.3 数数据信息的校据信息的校验v解决编码传输问题v在编码中引入一定冗余冗余，增加代码的最小码距，使编码出出现一一个个错误时就成就成为非法代非法代码奇偶校验海明校验CRC循环冗余校验数据与文字表示2.3.1 奇偶校奇偶校验：v奇偶校验码是一种开销最小，能发现数据代码中奇奇数数位出位出错情况的编码。v常用于存储器读写检查，或ASCII字符传送过程中的检查。数据与文字表示奇偶校奇偶校验编码方方法法校验码（数数据校据校验位位）中1的个数为奇/偶数000000001(奇校验)000100011(偶校验)编码方法编码方法：加一位校验位加一位校验位，使奇校验为奇数个1，偶校验为偶数个1。数据与文字表示例：例：对几几个个字字节值的奇偶校的奇偶校验编码数据数据 奇校验的编码奇校验的编码 偶校码的偶校码的编码编码 00000000 100000000 000000000 010l0l00 0010l0100 101010l00 01111111 001111111 10l111l1l校验位的值取O还是1，是由数据位中1的个数决定的设二进制数X=X0X1Xn-1，校验位为C，则o奇校验码X0X1Xn-1C=1o偶校验码X0X1Xn-1C=0数据与文字表示112偶校验:奇校验:偶校验检错码:G=0表示数据正常，G=1表示出错奇偶奇偶校校验位的生成位的生成 0001偶校验P=1偶校验00011传输为01011检错码G=1出错！出错！传输为00011检错码G=0 正确！正确！1010偶校验P=0奇校验P=1传输为11011检错码G=0 正确？正确？数据与文字表示113奇偶校验位的生成与检验的电路设计数据与文字表示114奇偶校奇偶校验码的的检错过程程 v设检错码X0X1X2X3C存在内存中设读出时为X0X1X2X3C由X0X1X2X3形成C*；判C*与C相等？是：无错或无奇数位错否：奇数位出错数据与文字表示115例例:v甲方数据:X0X1X2X3C=1011v本地生成奇校验编码：10110v传输到乙方：X0X1X2X3C=11110v乙方要判断收到的数据是否正确？v根据X0X1X2X3生成校验位：C*=1111=1v根据C和C*生成检测码：G=C*C=10=1vG=1,传输错误数据与文字表示116d7d6d5d4d3d2d1d0+pd7d6d5d4d3d2d1d0p+gv检测码G不为零表示错误发生v检测码为零时是否表示数据正确？奇偶校奇偶校验数据与文字表示117奇偶校奇偶校验性能性能0000100001000010000001111111110000100001正确传输正确传输正常检错正常检错正常检错正常检错不能检错不能检错仅能识别奇数个错误，不能纠正错误数据与文字表示118Two-dimensional Parityv若干数据一个校验位v整个数据包增加一个校验字节011010010110100010110111010110010111011010001101数据与文字表示119vAll1-biterrors011010010110100000110111010110010111011010001101error bitodd number of 1sHow Many Errors Can you Detect?数据与文字表示120How Many Errors Can you Detect?vAll2-biterrors011010010110100000111 111010110010111011010001101error bitsodd number of 1s on columns数据与文字表示121vAll3-biterrors011010010110100000111 110010110010111011010001101error bitsodd number of 1s on columnHow Many Errors Can you Detect?数据与文字表示122How Many Errors Can you Detect?vMost4-biterrors011010010110100000111 110010010010111011010001101error bits011010010110100000111 110010010010111011010001101error bits数据与文字表示123ChecksumvSender:addallwordsofapacketandappendtheresult(checksum)tothepacketvReceiver:addallwordsofareceivedpacketandcomparetheresultwiththechecksumvExample:Internetchecksum数据与文字表示124二二维奇偶校奇偶校验的的启启示示v一个数据位参加多个校验组一个数据位发生错误可在多个检测码中反应可有效提高检错能力数据与文字表示1252.3.2 海明校海明校验Hamming Codesv奇偶校验一个校验位只能检错，无法纠错v海明码多个奇偶校验组既能检错，也能纠错数据与文字表示海明海明码原理原理v特点：能检测出两位同时出错、亦能检测出一位出错并能自动纠错。v实现原理：k个数个数据位据位之外加上r个个校校验位位，从而形成一个k十r位的新码字，当某一位出错后，就会引起相关的几个校验位的值发生变化，从而达到检错、纠错的目的。数据与文字表示数数据位据位k与与校校验位位r的的对应关关系：系：v2rk+r+1：一位出错并纠错（4，3）v2r-1k+r：一位出错并纠错且发现两位错数据与文字表示128可可检测一位一位错海明海明码v分组交叉奇偶校验法将编码中的数据位分成r个校验组，组内采取奇偶校验，每组一个校验位，可构成r位检错码。r1v全部检错码为0表示数据正常v不为零时检错码的值表示编码中出错数据位v可检错，也可纠错v每一数据位至少参加2个校验组，一位出错，可引起多个检错码的变化。数据与文字表示129可可检测一位一位错海明海明码v设海明码N位，其中数据位k位，校验位r位v校验位r位表示共r个校验组vN=k+r2r1v(4,3)编码D4D3D2D1P3P2P1H7H6H5H4H3H2H1包含G3G2G1个校验组，P3P2P1分属其中一组数据与文字表示130H7参与G3G2G1三校验组H6参与G3G2两校验组H5参与G3G1两校验组H3参与G2G1两校验组G2G1=0表示仅仅P3位出错G3G1=0表示仅仅P2位出错G3G2=0表示仅仅P1位出错备注H7出错111H6出错110H5出错101H3出错011P3存放在H4位置H4出错100P2存放在H2位置H2出错010P1存放在H1位置H1出错001数据正常000出错位G3G2G1可可检测一位一位错海明海明码D4D3D2D1P3P2P1H7H6H5H4H3H2H1数据与文字表示131P1P2D1P3D2D3D4H1H2H3H4H5H6H7vG1(P1,H3,H5,H7)vG2(P2,H3,H6,H7)vG3(P3,H5,H6,H7)vP1=D1D2D4vP2=D1D3D4vP3=D2D3D4可可检测一位一位错海明海明码H7参与G3G2G1校验组H6参与G3G2校验组H5参与G3G1校验组H3参与G2G1校验组H7出错111H6出错110H5出错101H3出错011备注出错位P3P2P1数据与文字表示1321234567positions001 010 011 100 101 110 111P1P2d1P3d2d3d4rolePosition of error=C3C2C1Where Ci is parity of group i数据与文字表示133求信息求信息1011的海明码的海明码 v信息4位，所以校验位为3位，公式要成立！v3+4=7，这个海明码一共是7位。v用I代表信息位。R代表校验位7654321-I4I3I2I1-101R21R1R0数据与文字表示134求信息求信息1011的海明码的海明码7654321-I4I3I2I1-101R21R1R0R2=I4+I3+I2，R2=1+0+1=0R1=I4+I3+I1，R1=1+0+1=0R0=I4+I2+I1，R0=1+1+1=1求出校验位为001。因此信息1011的海明码为：1010101数据与文字表示135R2R1R0的的简单理解理解7654321-I4I3I2I1-R2R1R0vR2对应的位数为4，对应8421码，在4这个位上有1的，就异或。因此R2=I4+I3+I2vI4对应7，划为二进制为0111，对应8421码，在4这个位上有1，所以就要异或。数据与文字表示136指指错、纠错原理原理vG1=P1D1D2D4vG2=P2D1D3D4vG3=P3D2D3D4v检错码G3G2G1!=000表示出错，具体值表示出错位置v将对应位置上的数位取反即可纠错v假设D1D2同时出错，则G3G2G1=110？v引入总校验位P4=H1H2H3H4H5H6H7vG4=P4H1H2H3H4H5H6H7 判断一位错两位错数据与文字表示137文氏文氏图表示表示3 D15 D26 D3G1G2G3H4/P3H1/P1H2/P27 D4v检一位错v检两位错v大多数三位错数据与文字表示138码距距概概念念v任意两个合法编码之间不同的二进数位数为码距v码距越大，抗干扰能力越强，纠错能力越强，数据冗余也越大，即编码效率低。v选择码距必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。v奇偶校验将使最小码距由一增加到二v海明码最小码距为3数据与文字表示139码距距与与纠错性能性能v最小码距e+1可检测e个错误v最小码距2t+1可纠正t个错误v最小码距e+t+1et可纠正t个错误，同时检测e个错误加337加236加225加124或123012001纠错检错最小码距数据与文字表示140CRC循循环冗余校冗余校验码v检错，纠错码v数据位k位，校验位r位vN=k+r2r1数据与文字表示141模模2运运算算规则v加法：按位加不考虑进位v减法：按位减不考虑借位异或运算，不考虑进位v乘法：部分积之和按模2加法计算v除法：余数首位为1，商上1,否则上010000101=101*101+01数据与文字表示142多多项式式v将待编码的k位有效信息位组表达为多项式M(x)vM(x)=bk-1Xk-1+bk-2Xk-2+b1X1+b0v将数据左移r位，以便空出r位校验位，多项式变成M(x)X r v将M(x)X r除以生成多项式G(x)商为Q(x)余数R(x)M(x)X r=Q(X)G(x)+R(X)v将余数拼接在空出的校验位上vM(x)X r+R(X)=(Q(X)G(x)+R(X)+R(x)Q(X)G(x)CRC编码可被G(x)表示的编码整除数据与文字表示143(7,4)循循环码出出错模式模式G(x)=101111010100010211110000103110111001040111101010510011001106010110000070011100011无0001100010出错位余数A1A71101-01011001101-01111101-001101101101-0001001000110100010数据与文字表示144生成多生成多项式式v任何一位发生错误都应使余数不为0v不同位发生错误应当使得余数不同v对余数继续作模2除，应使