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

1、2-1 数据与文字的表示方法 计算机组成原理计算机组成原理数据与文字表示2Outline数据与文字表示32.1 非非数值数数值数据表示法据表示法v字符表示法 charactersv汉字表示法 Chinese characters数据与文字表示42.1.1 Character representation v 如何使用数值表示字符数据v StandardsASCII-American Standard Code for Information Interchange (ANSI 7bits)EBCDIC-Extended Binary-Coded Decimal Interchange Code

2、 (IBM 8bits)Unicode数据与文字表示5128 Standard ASCII codesv 52 Letters a-z, A-Z v 10 Digits 0-9v 34 Symbols ! # $ % & * ( ) v 32 Control characters 数据与文字表示6ASCIIv使用7bit表示128个字符 From 000 0000 to 111 1111 27=128v注意：ASCII中的数字字符和数字本身不相等v几乎所有计算机均支持该代码集v但不是所有语言都能用128个字符表示v8Bit=1字节 ，MSB=0数据与文字表示7Terminologyv计算机利用

3、寄存器存储数据v寄存器中每个位称bit (Binary DigiT)v最高有效位 (MSB) 最低有效位 (LSB) MSBMost significant bit LSBLeast significant bit数据与文字表示82.1.2 汉汉字表示法字表示法v英文键盘输入汉字-输输入入编码编码： 数字编码：国标区位码，区码和位码各用两位十进制数字表示，例如“中” 区位码为5448。GB2312-80信息交换用汉字编码字符集国标码是四位十六进制数，区位码则是四位的十进制数特点：无重码，但难记。 拼音码：重码率高，需要会读拼音： 犇 猋 骉 蟲 麤 毳 淼 掱 垚 烜 屾 字形编码：五笔字型输

4、入法数据与文字表示92.1.2 汉汉字表示法字表示法v汉字信息在计算机中的存储、交换、检索等-汉汉字字内码内码v8 bit数据仅能表示256个字符，常用汉字6000多个，故其无法表示汉字vGB2312国家标准采用16位表示,2个字节v与ASCII字符的区别，最高有效位MSB=1数据与文字表示10GB2312-80国国家家标标准准v1981年，GB2312-80国家标准，包括6763个汉字/682个非汉字字符，称为国标码vGB2312字符集的构成：一级常用汉字3755个，按汉语拼音排列二级常用汉字3008个，按偏旁部首排列非汉字字符682个数据与文字表示11汉汉字字标标准准v GB2312-19

5、80(GB0)(简体)6763个汉字 v GB13000-199320902个汉字 (Unicode 1.1版本)v 汉字扩展规范GBK1.0 标准1995（非国家标准） 21003个字符（兼容GB2312）v GB18030-2000(1/2/4字节编码) 27484汉字 （向下兼容GB2312 GBK，GB13000）宋体 隶书 微软雅黑 华文琥珀 数据与文字表示12字模字模码码介介绍绍v 字模码是用点阵表示的汉字字型代码，是汉汉字的字的输输出形式出形式。 v 字模点阵的信息量是很大的，所占存储空间也很大。以16*16为例，每个汉字要占用32个字节，v 因此字模点阵只能用来构成汉字库，而不

6、能用于机内存储。数据与文字表示13Charsetv v charset=gb2312 简体中文 charset=big5 繁体中文 charset=EUC_KR 韩语 charset=Shift_JIS 或 EUC_JP 日语 charset=KOI8-R/Windows-1251俄语 charset=iso-8859-2 中欧语系charset=utf-8 unicode多语言数据与文字表示14Unicode v用于克服字符数字的限制v为所有语言中的字符分配唯一的代码v 16 bit 字符集, 17个平面，一共有17*65536=1114112个码位 (每个平面

7、有216=65536个码位 )v提供唯一的代码 不论任何平台 不论任何程序 不论任何语言 Unicode目前定义的99089个字符，其中包括71226个汉字,平面2的43253个字符都是汉字。平面0上定义了27973个汉字 数据与文字表示15Universal Character Set ISOUCS通用字符集 ISO 10646 包含了用于表达所有已知语言的字符UTF (UCS Transformation Format ) UCS的实际表现形式，即怎样将Unicode定义的数字转换成程序数据 UTF-8：以字节为单位对Unicode进行编码 UTF-16：编码以16位无符号整数为单位 UT

8、F-32编码以32位无符号整数为单位包括拉丁语，希腊语，斯拉夫语，希伯来语，阿拉伯语，亚美尼亚语和乔治亚语的描述，还包括中文，日文和韩文这样的象形文字，以及 平假名，片假名，孟加拉语，旁遮普语果鲁穆奇字符(Gurmukhi),泰米尔语，印.埃纳德语（Kannada),Malayalam，泰国语，老挝语，汉语拼音（Bopomofo),Hangul,Devangari,Gujarati,Oriya,Telugu 以及其他数也数不清的语. 对于还没有加入的语言，由于正在研究怎样在计算机中最好地编码它们，因而最终它们都将被加入. 这些语言包括 Tibetian，高棉语，Runic（古代北欧文字），埃塞

9、俄比亚语，其他象形文字，以及各种各样的印-欧语系的语言，还包括挑选出来的艺术语言比如 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等方式去处理数据与文字表示举举

10、例例16在Unicode中：汉字“字”对应的数字是23383（十进制），十六进制表示为5B57。在Unicode中，我们有很多方式将数字23383表示成程序中的数据，包括：UTF-8、UTF-16、UTF-32。UTF是怎样将Unicode定义的数字转换成程序数据。例如，“汉字”对应的数字是0 x6c49和0 x5b57，而编码的程序数据是：char data_utf8 = 0 xE6, 0 xB1, 0 x89, 0 xE5, 0 xAD, 0 x97; / UTF-8编码 char16_t data_utf16 = 0 x6C49, 0 x5B57; / UTF-16编码 char32_t

11、 data_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 标准，请改用 unsigned short 和 unsigned long。）“汉字”的UTF-8编码需要6个字节。“汉字”的UTF-16编码需要两个char16_t，大

12、小是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计计算机算

13、机数数据据编码编码特点特点v少量简单的基本符号表示大量复杂的信息v状态简单v电路实现简单v运算方便v硬件成本数据与文字表示20Human vs. Computerv人们日常生活采用10进制 天生10个手指v计算机采用二进制 计算机采用电子开关 开关仅仅包括两个状态 ON OFF数据与文字表示21十十进进制制编码编码特点特点v 0123456789共10种状态，状态过多v 运算组合状态过多v 加法组合数= 55=36=3八进制：二进制：结论结论：二：二进进制的制的组组合合状态状态最少最少对R进制数进行算术求和或求积运算，其运算规则各有R(R+1)/2种数据与文字表示22二二进进制制编码编码特点特

14、点v “0、1” 物理上容易实现 具有两种稳定状态的物理器件很多 用数字电路的两个状态表示(门电路的导通与截止、电压的高低）v 机器可靠性高 电压的高低、电流的有无，两种物理状态稳定、分明，抗干扰能力强，鉴别信息的可靠性高v 逻辑判断方便 与二值逻辑的 真 假 两个值对应简单v 二进制位可以表示任何对象(字符，数值，逻辑值)v 运算规则简单 0+1=1+0=1 1+1=0 0+0=0 仅有3种运算规则 大大简化运算器等物理器件的设计，一个异异或或门门即可完成该运算数据与文字表示23一位全加器：如何一位全加器：如何计计算算0,1的加法的加法111111001110101010011000进位Ci

15、+10110和数Si110010100000加数Bi加数Ai低位进位CiiiiiCBAS数据与文字表示24二二进进制加法器基本制加法器基本电电路路iiiiCBASiiiiiiiiiiiCBABACBABAC)()(1数据与文字表示25进进制表示制表示mkiiirDN* N 代表一个数值 r 是这个数制的基基(Radix) i 表示这些符号排列的位号 Di 是位号为i的位上的一个符号 ri 是位号为i的位上的 1 代表的值 Di*ri 是第第i位的所代表的位的所代表的实际值实际值 表示m+k+1位的值求累加和累加和数据与文字表示26例子例子v(10456)1011040103 410251016

16、100v(0 xF96)16v (10010001)2mkiiirDN*-按权展开按权展开位权的大小是以基数为底，数字符号所处的位置的序号为指数的整数次幂。二进制数就是2的n次幂 。127026 025 124 023022 021 120=145F1629161 6100=3990数据与文字表示27进进制制转换转换v二进制数转八进制v二进制数转十六进制v二进制数转十进制v十进制数转二进制数据与文字表示28二到八或十六二到八或十六进进制制转换转换v 二进制转到八进制 从小数点向左右三位一分三位一分组组 (10 011 100 . 01)2 = v 二进制转十六进制 从小数点向左右四位一分四位一

17、分组组 (1001 1100 . 01)2 = 注意：注意：整数部分不足位数对转换无影响，整数部分不足位数对转换无影响， 小数部分不足位数要补零凑足小数部分不足位数要补零凑足，否则出错。，否则出错。( 234 . 2 )8010( 9C . 4 )160100数据与文字表示29二二进进制制转转十十进进制制从二进制数求其十进制的值，逐位码权累加求和-按按权权展展开开v 10010001127026 025 124 023 022 021 120mkiiirDN*数据与文字表示30十十进进制制转转二二进进制制整数部分除2取余 小数部分乘2取整2 1 122252101 11 10 01 10.62

18、5 * 21 10.25 * 20 00.5 * 21 1 0.0 除尽为止 1011低低高高高高低低求得位数满足要求为止（11.625）10= （ ？ ）21011.101数据与文字表示31进进制制转换转换的的简单运简单运算方法算方法v 17/12817/128的二进制表示?v 记住几个常用的2的幂：2532 2664 27128 28256 29512 2101024(1Kilo) 2112048 21240962138182 21416364 2153272821665536 2201048576(1Mega)2301073741824(1Giga) 2401Tera更大的单位是多少？2

19、501 Peta 2601 Exa 2701 Zetta 2801 YottaMEMORIZE!数据与文字表示321999 New IEC Standard Prefixes /wiki/Binary_prefixv SI (International System of Units )仅指10进制v 234可以访问多少存储单元?v 2.5 TiB存储空间需要多少地址线进行译码？MEMORIZE!硬盘厂商及通讯行业是计算机行业唯一使用SI因子的数据与文字表示33几几个简个简化化运运算的例子算的例子MEMORIZE!.数据与文字表示342.2 数值数数

20、值数据表示方法据表示方法v计算机数值数据表示的特点v进位制数v数的定点、浮点表示v机器数数据与文字表示352.2.1 数数的定点、浮点表示方法的定点、浮点表示方法v定点表示 (小数点位置固定的数) 定点小数 定点整数 表示纯小数及纯整数v浮点表示vSigned & Unsigned数据与文字表示36定点小定点小数数-纯纯小小数数符号位小数点位置数值部分数据与文字表示37v 数值表示 X = X 0 . X1 X 2 X n X i=0,1, 0in =X 12-1 + + X n-12-n+1 + X n 2-nv 数值范围 0|x| 1-2-n 定点小定点小数数的的编码编码 0.000000

21、00 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原码表示时原码表示时,正数和负数的范围是对称的正数和负数的范围是对称的,故绝对值最大的负数等故绝对值最大的负数等于正数值加上于正数值加上”

22、 ”号号,其真值为其真值为(1 2-n)数据与文字表示39定点整定点整数数符号位小数点位置数值部分0 |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原码表示的绝

23、对值最大负数= (2n 1)数据与文字表示42浮点浮点数数如何表示如何表示v小数点的位置可按需浮动小数点的位置可按需浮动v 将数据按照一定比例因子缩小成定点小数或扩大成定点整数进行表示和运算v 运算完毕后再根据比例因子还原成实际数值v 计算机中浮点运算有专门的器件电子的质量 910-28g太阳的质量21033g定点表示方法无法直接表示该数值范围电子的质量 0.910-27g太阳的质量0.21034g数据与文字表示43浮点浮点数数如何表示如何表示v 电子的质量 910-28gv 太阳的质量21033g0.21034v 科学记数法N=10EMvN=ReMM:称为称为尾尾数数，是一个纯纯小小数数（原

24、码或补码表示） e:是比例因子的阶数、指数，称为浮点数的阶码阶码、指数，是一个整数（移码或补码）R:为为基基数数，是常，是常数数数据与文字表示44浮点浮点数数的表示的表示v 机器中表示浮点数，需要：v N=ReM=2EM =2e (m)v m:尾数，定点小数表示，给出有效数字位数，决定精度；v e：指数，整数形式表示，称为阶码，给出小数点位置，决定浮点数的表示范围。M1M2Mn尾数值 阶值阶阶符符尾符尾符数据与文字表示45浮点浮点数数的表示范的表示范围围- +负数正数0负上溢正上溢负下溢正下溢v N=2EMv |N| 产生正上溢或者负上溢v |N|0 产生正下溢或者负下溢注意：下溢时，浮点数值

25、趋于零，故机器不做溢出处理，仅把它作为机器零。注意：下溢时，浮点数值趋于零，故机器不做溢出处理，仅把它作为机器零。 上溢时才是浮点数真正溢出，机器需停止运算，作溢出中断处理。上溢时才是浮点数真正溢出，机器需停止运算，作溢出中断处理。 一般所说的浮点溢出，均是指上溢。一般所说的浮点溢出，均是指上溢。机器零机器零:当一个浮点数的当一个浮点数的尾数为尾数为0(不论阶码是何值不论阶码是何值)，或或阶码的值比能在机器中表示的最小值还小时，计算阶码的值比能在机器中表示的最小值还小时，计算机都把该浮点数看成零值，称为机器零。机都把该浮点数看成零值，称为机器零。数据与文字表示46v机器字长一定时，阶码越长，表

26、示范围越大，精度越低v浮点数表示范围比定点数大，精度高尾数值 阶值阶符尾符Range & precision字长共8位： 阶码7位，尾数1位，不考虑符号位，最大表示0.5*27 阶码6位，尾数2位，不考虑符号位，最大表示0.75*26数据与文字表示47Example v 8位定点小数可表示的范围n 0.0000001 - 0.1111111 n 1/128 - 127/128v 设阶码2位，尾数4位n 可表示2-11*0.0001 - 211*0.1111n 0.0000001 - 111.1v 设阶码3位，尾数3位n 可表示2-111*0.001 - 2111*0.111n 0.000000

27、0001 - 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

28、)M(022共23bit)v 32/64位浮点数（Float/Double）S(1bit)E(5262共11bit)M(051共52bit) 浮点浮点数标数标准准 IEEE754尾数值 阶值阶符尾符数据与文字表示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)

29、f12540/1- 02551+02550sNaN Signaling NaN非零非零0 xxxx2550/1NaN Not a Number非零非零1xxxx2550/1表示表示尾尾数数阶码阶码符符号号位位数据与文字表示52Emax=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一一个个奇

30、怪的程序奇怪的程序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);

31、结果如下：0.0600000000000000050.5800000000000001401.499999999999941.232999999999999954数据与文字表示1.01 + 2.01 = 3.02 v 64位浮点表示：v 1.01 为：v 0 0111111 1111 0000 00101000 11110101 11000010 10001111 01011100 00101001v 2.01 为：v 0 1000000 0000 0000 00010100 01111010 11100001 01000111 10101110 00010100v 3.02 表示为： v 0

32、 1000000 0000 1000 00101000 11110101 11000010 10001111 01011100 00101001v 2.01+1.01 在编程语言中的计算结果 表示为：v 0 1000000 0000 1000 00101000 11110101 11000010 10001111 01011100 0010100055数据与文字表示v结论：因为浮点数在计算机内的存储存在偏差，导致运算时，与实际期望的结果不同。v双精度数的表示法：尾数一共有52个bit，也就是最小能表示的数是 2-52，取对数可得出，约是在小数点后16位，那也就是说小数点后15位是可以精确表示的

33、，加上前置的默认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数据与文字表示浮点数的IEEE 754存储格式为（41360000）16求该浮点数的真值（十进制数值）v（41360

34、000）16展开为二进制580100 0001 0011 0110 0000 0000 0000 0000e=10000010 127(01111111)=00000011=31.M=1.01101100000000000000000=1.011011x=+(1.011011)x23=+1011.011 = 11.375数据与文字表示十进制20.59375的32位浮点数的二进制存储表示十进制20.59375转为二进制表示5910100.10011 2-1=0.5, 2-2=0.25, 2-3=0.125 10100.10011= 1.010010011 x 24 S=0, M=01001001

35、1, E=e+127=131 0 10000011 010010011 00000000000000数据与文字表示602.2 数值数数值数据表示方法据表示方法v计算机数值数据表示的特点v进位制数v数的定点、浮点表示v机器数数据与文字表示612.2.2 机器机器数数/机器机器码码v 真值 (书写用) 将用+ -表示正负的二进制数称为符号数的真值 +10010，-0.101v 机器不能识别书写格式v 机器码 (机器内部使用) 将将符符号号和和数值数值一起一起编码编码表示表示的二的二进进制制数称为数称为机器机器码码v 原码 Signed magnitude 反码 Ones complementv 补

36、码 Twos complement 移码 Biased notation数据与文字表示62原原码码表示法（表示法（Signed magnitude）v计算机如何表示数的正负?v增加符号位 Add a sign bitv最高位为符号位，0为正，1为负，数值位不变数据与文字表示63原原码码表示示例表示示例v-0.1111原 = 1.1111v 0.1111原 = 0.1111v 1110原 = 01110v-1110原 = 11110符号位：+用0表示，- 用1表示数值位不变数据与文字表示64原原码码表示法表示法定点整数：定点小数：零？+0原=0.0000-0原=1. 0000原码中的零有+0和-

37、0之分数据与文字表示65p -7+7 7个正数，7个负数，两个零p -(2n -1) 2n -1 数据位共n位二进制编码的按权展开对应的原码表示数据与文字表示66Signed Magnitudev Both positive and negative zero两个0？v Equal number of positives and negatives正负对称v Easy to interpret容易理解 First bit is the sign Remaining bits are numberv Sounds ideal? Butv01011001+11001101=?数据与文字表示67Si

38、gned Magnitude? 010110012 = 8910 + 110011012 = -7710 001001102 = 3810数据与文字表示68Shortcomings of signed magnitude?v Arithmetic circuit complicatedv Also, two zeros 0 x00000000 = +0ten 0 x80000000 = 0ten What would two 0s mean for programming?v Therefore signed magnitude abandoned数据与文字表示69反反码码表示法表示法v所谓反

39、码，就是二进制的各位数码取反v符符号号位位表示方法与原码相同v Example: 710 = 001112 -710 = 110002v Called Ones Complement符号位：+用0表示，- 用1表示负数的数值位 需要逐位取反正数的数值位不变数据与文字表示70反反码码的表示的表示v+0反=0.0000v-0反=1.1111v0.1111反=0.1111v-0.1111反=1.0000v1110反=01110v-1110反=10001符号位：+用0表示，- 用1表示负数的数值位 需要逐位取反正数的数值位不变数据与文字表示71反反码码表示法表示法定点小数：定点小数：定点整数：定点整数

40、：-1110反=10001-0.1111反=1.0000数据与文字表示72反反码码公式公式证证明明v 定点小数 -1x=0时 p假设 x=-0.x1x2xn px反 = 1.x1x2 xnpx反+|x|=1.111 =1.111+0.001-0.001 =10.000-0.001 x反+|x|= =2-2-nvx反=2-2-n-|x|=2-2-n+x数据与文字表示73反反码码公式公式证证明明v定点整数 -2nx=0时 p假设 x= -x1x2xn p假设 x反= 1x1x2 xnpx反+|x|= 1111 = 1111+0001-0001 = 10000-0001 = 2n+1-1vx反= 2

41、n+1-1 -|x|= 2n+1-1 +x数据与文字表示74反反码码表示法表示法定点小数：定点小数：定点整数：定点整数：数据与文字表示75 数值 -7 15 7 7 0 0 编码 p -7+7 正数7个，负数7个，零两个p -(2n -1) 2n -1 数据位n位二进制编码的按权展开对应的反码表示的数据与文字表示76原原码码&反反码码 数值 -7 15 7 7 0 0 编码 二进制编码的按权展开对应的原码表示的二进制编码的按权展开对应的反码表示的数据与文字表示77Shortcomings of Ones complement?v Arithmetic still a somewhat comp

42、licated.v Still two zeros 0 x00000000 = +0ten 0 xFFFFFFFF = -0ten v Although used for awhile on some computer products, ones complement was eventually abandoned because another solution was better.数据与文字表示78有趣的有趣的时钟时钟123691236912369v 9点+9 = 6点v 9点- 3 = 6点v-3 与 +9 等价v 9是-3对12的补码数据与文字表示79同余的同余的概概念念v 假定

43、有两个数a和b，若用某一个整数m去除，所得的余数相同，就称a,b两个数对m同余,记作： ab (mod m) v 假设X,Y,Z三个数，满足下列关系：Z=nX+Y (n为整数),则称Z和Y对模X是同余的，记作： ZY (mod X) YZ (mod X) 数据与文字表示80例子例子v Z=nX+Y X为模数v 以12为模v 9=12+9=24+9=36+9v 9，21，33，45 都是相等的（同余）v -3=12-3=9v 9与-3是相等的（同余）v 0=12数据与文字表示81例子例子v 7+(-3)v =7+(12-3)v =7+9v =16v =4v 表示负数的时候如利用模的性质转换成正数

44、， 即可将原码运算中的减减法法转换成加法加法运算数据与文字表示82补码补码表示公式表示公式定点小数：定点小数：定点整数：定点整数：零？数据与文字表示83p -8+7 正数7个，负数8个，零1个p -2n 2n -1 数据位n位 数值 0 0 -8 7 15 7 编码 二进制编码的按权展开对应的补码表示的数据与文字表示84反反码码、补码数轴补码数轴表示比表示比较较 数值 0 0 -8 7 15 7 编码 数值 -7 15 7 7 0 0 编码 二进制编码的按权展开对应的反码表示的二进制编码的按权展开对应的补码表示的数据与文字表示85补码与补码与反反码码的的关关系系负定点小数时x反=2-2-n+x

45、x补=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数据与文字表示86v正值：与原码相同，符号位为0v负值负值：符：符号号位位为为1，数值数值位取反，末位加位取反，末位加1,v - 10101010补=1 01010101+1=1 01010110v -0.010101补=1.101011数据与文字表示87例子例子vX=+0.11111111 X补 =? vX=-0.11111111 X补 =? v X=-0.00000000 X补 =?X补 =0.11111111 X补 =1.11111111 +

46、 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.23

47、0.23/10=0.023 原符原符号号位位不变，符符号号位位与数值与数值位位均右移一位，例如， X补 =10010 则 X/2补 =11001不同位数的整数补码相加减时，如何运算? 数据与文字表示91补码补码表示中的符表示中的符号号位位扩扩展展不同位数的整数补码相加减时， 位数少的补码数的符号位向左扩展， 一直扩展到与另一数的符号位对齐。 数据与文字表示92变变形形补码补码例： 00.1010110 11.0101001又称 双符号位双符号位补码，变形补码数据与文字表示93补码补码加加减减法法运运算算实实例例x=0.1011 y= -0.0101 用模4补码 求x+y x-yx补 = 00

48、1011, y补 = 11 1011 -y补 = 00 0101 数据与文字表示94补码补码特点特点v唯一的零v符号位可以直接参与运算v减法可以变成加法v负数比正数多一个数据与文字表示954. 移移码码表示法表示法 Biased/Excess Notationp 保持数据原有大小顺序，便于进行比较操作。p 通常仅用于表示整数，表示浮点数的阶码。定义x移 = 2n+x -2n x 9 +6修正 + 0110 =10011 BCD表示13106数据与文字表示1072.3 数数据信息的校据信息的校验验v计算机中的错误类型：1）固定性错误 -元器件故障元器件故障； 精心精心设计设计各各种电种电路，提高

49、路，提高计计算机硬件的可靠性；算机硬件的可靠性；2）突发性错误 -噪噪声声干干扰扰。 采用某种编码法，通过少量的附加电路，使之能发现某些错误，甚至能确定出错位置，进而实现自动改错的能力。v数据校验码：用以发现或同时能得出错误位置特征(自自动动改改错错能力能力)的数据编码。 数据与文字表示1082.3 数数据信息的校据信息的校验验v解决编码传输问题v在编码中引入一定冗余冗余，增加代码的最小码距，使编码编码出出现现一一个错误时个错误时就成就成为为非法代非法代码码 奇偶校验 海明校验 CRC 循环冗余校验数据与文字表示2.3.1 奇偶校奇偶校验验：v奇偶校验码是一种开销最小，能发现数据代码中奇奇数数

50、位出位出错错情况的编码。v常用于存储器读写检查，或ASCII字符传送过程中的检查。数据与文字表示奇偶校奇偶校验验编码编码方法方法 校验码（数数据校据校验验位位）中1的个数为奇/偶数 0000 00001 (奇校验) 0001 00011 (偶校验)编码方法编码方法：加一位校验位加一位校验位，使奇校验为奇数个1， 偶校验为偶数个1。数据与文字表示例：例：对对几几个个字字节值节值的奇偶校的奇偶校验编码验编码数据数据 奇校验的编码奇校验的编码 偶校码的编码偶校码的编码 00000000 100000000 000000000 010l0l00 0010l0100 101010l00 01111111

51、 001111111 10l111l1l校验位的值取O还是1，是由数据位中1的个数决定的设二进制数X=X0X1Xn-1，校验位为C，则o 奇校验码 X0 X1Xn-1 C=1o 偶校验码 X0 X1Xn-1 C=0数据与文字表示11287654321DDDDDDDDP87654321DDDDDDDDP偶校验:奇校验:876543211GDDDDDDDDP偶校验检错码:G=0表示数据正常， G=1表示出错奇偶奇偶校校验验位的生成位的生成 0001 偶校验P = 1 偶校验00011 传输为01011 检错码G= 1 出错！出错！ 传输为00011 检错码G= 0 正确！正确！ 1010 偶校验P

52、 = 0 奇校验P= 1 传输为11011 检错码G= 0 正确？正确？ 数据与文字表示113奇偶校验位的生成与检验的电路设计数据与文字表示114奇偶校奇偶校验码验码的的检错过检错过程程 v设检错码X0X1X2X3C存在内存中 设读出时为 X0 X1 X2 X3 C 由X0 X1 X2 X3 形成C*； 判C*与C相等？ 是：无错或无奇数位错否：奇数位出错数据与文字表示115例例: v甲方数据:X0X1X2X3C = 1011v本地生成奇校验编码： 10110v传输到乙方：X0X1X2X3C=11110v乙方要判断收到的数据是否正确？v根据X0X1X2X3生成校验位：C*=1 1 1 1=1v

53、根据C和C*生成检测码：G= C* C=1 0=1vG=1,传输错误 数据与文字表示116d7d6d5d4d3d2d1d0+pd7d6d5d4d3d2d1d0p+gv 检测码G不为零表示错误发生v 检测码为零时是否表示数据正确？奇偶校奇偶校验验数据与文字表示117奇偶校奇偶校验验性能性能0000100001000010000001111111110000100001正确传输正确传输正常检错正常检错正常检错正常检错不能检错不能检错仅能识别奇数个错误，不能纠正错误数据与文字表示118Two-dimensional Parityv若干数据一个校验位v整个数据包增加一个校验字节011010010110

54、100010110111010110010111011010001101数据与文字表示119v All 1-bit errors011010010110100000110111010110010111011010001101error bitodd number of 1sHow Many Errors Can you Detect?数据与文字表示120How Many Errors Can you Detect?v All 2-bit errors011010010110100000111 111010110010111011010001101error bitsodd number of

55、1s on columns数据与文字表示121v All 3-bit errors011010010110100000111 110010110010111011010001101error bitsodd number of 1s on columnHow Many Errors Can you Detect?数据与文字表示122How Many Errors Can you Detect?v Most 4-bit errors011010010110100000111 110010010010111011010001101error bits011010010110100000111 11

56、0010010010111011010001101error bits数据与文字表示123Checksumv Sender: add all words of a packet and append the result (checksum) to the packetv Receiver: add all words of a received packet and compare the result with the checksumv Example: Internet checksum数据与文字表示124二二维维奇偶校奇偶校验验的的启启示示v一个数据位参加多个校验组 一个数据位发生错

57、误可在多个检测码中反应 可有效提高检错能力数据与文字表示1252.3.2 海明校海明校验验Hamming Codesv奇偶校验 一个校验位 只能检错，无法纠错v海明码 多个奇偶校验组 既能检错，也能纠错数据与文字表示海明海明码码原理原理v特点：能检测出两位同时出错、亦能检测出一位出错并能自动纠错。v实现原理： k个数个数据位据位之外加上r个个校校验验位位，从而形成一个k十r位的新码字，当某一位出错后，就会引起相关的几个校验位的值发生变化，从而达到检错、纠错的目的。数据与文字表示数数据位据位k与与校校验验位位r的的对应关对应关系：系：v2rk+r+1： 一位出错并纠错（4，3）v2r-1k+r

58、：一位出错并纠错且发现两位错数据与文字表示128可可检测检测一位一位错错海明海明码码v 分组交叉奇偶校验法 将编码中的数据位分成r个校验组，组内采取奇偶校验，每组一个校验位，可构成r位检错码。r1v 全部检错码为0表示数据正常v 不为零时检错码的值表示编码中出错数据位v 可检错，也可纠错v 每一数据位至少参加2个校验组，一位出错，可引起多个检错码的变化。数据与文字表示129可可检测检测一位一位错错海明海明码码v 设海明码N位，其中数据位k位，校验位r位v 校验位r位表示共r个校验组v N=k+r2r1v (4,3)编码 D4D3D2D1P3P2P1 H7H6H5H4H3H2H1 包含G3G2G

59、1个校验组，P3P2P1分属其中一组数据与文字表示130H7参与G3 G2 G1三校验组H6参与G3 G2两校验组H5参与G3 G1两校验组H3参与G2 G1两校验组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可可检测检测一位一位错错海明海明码码D4 D3 D2 D1 P3 P2 P1H7 H6 H5 H4 H3 H2 H1数据与文字表示131P1P2D

60、1P3D2D3D4H1H2H3H4H5H6H7v G1(P1,H3,H5,H7)v G2(P2,H3,H6,H7)v G3(P3,H5,H6,H7)v P1=D1 D2 D4v P2=D1 D3 D4v P3=D2 D3 D4可可检测检测一位一位错错海明海明码码H7参与G3 G2 G1校验组H6参与G3 G2校验组H5参与G3 G1校验组H3参与G2 G1校验组H7出错111H6出错110H5出错101H3出错011备注出错位P3P2P1数据与文字表示1321234567positions001 010 011 100 101 110 111P1P2d1P3d2d3d4rolePosition