版权所有，引用请注明出处 第二章、计算机数据表示方法 原著 谭志虎 主讲(改编) 蒋文斌

Outline 2.1 非数值数据表示法 2.2 数值数据表示法 2.3 数据信息的校验

Data Representation Qualitative Quantitative Integers Signed Unsigned Non-integers (Real)

2.1 非数值数据表示法 字符表示法 characters 汉字表示法 Chinese characters

2.1.1 Character representation … 如何使用数值表示字符数据 Standards ASCII-American Standard Code for Information Interchange (ANSI 7bits) EBCDIC-Extended Binary-Coded Decimal Interchange Code (IBM 8bits) Unicode

128 Standard ASCII codes 52 Letters 10 Digits 34 Symbols a-z, A-Z 10 Digits 0-9 34 Symbols ! @ # $ % ^ & * ( ) … 32 Control characters <CR> <BEL> <ESC> <LF> …

ASCII 使用7bit表示128个字符 注意：ASCII中的数字字符和数字本身不相等 几乎所有计算机均支持该代码集 From 000 0000 to 111 1111 27=128 注意：ASCII中的数字字符和数字本身不相等 几乎所有计算机均支持该代码集 但不是所有语言都能用128个字符表示 8Bit??? MSF=0

Terminology 计算机利用寄存器存储数据 寄存器中每个位称bit (Binary DigiT) 最高有效位 (MSB) 最低有效位 (LSB) 1 7 6 5 4 3 2 MSB Most significant bit LSB Least significant bit

2.1.2 汉字表示法 8 bit数据仅能表示256个字符，常用汉字6000多个，故其无法表示汉字 GB2312国家标准采用16位表示 与ASCII字符的区别，最高有效位MSB=1 内码，外码(输入法)，字模码(显示用)

GB2312-80国家标准 1981年，GB2312-80国家标准，包括6763个汉字/682个非汉字字符，称为国标码或国际交换码 一级常用汉字3755个，按汉语拼音排列 二级常用汉字3008个，按偏旁部首排列 非汉字字符682个

汉字标准 GB2312-1980(GB0)(简体) GB13000-1993 汉字扩展规范GBK1.0 标准1995（非国家标准） 6763个汉字 GB13000-1993 20902个汉字 (Unicode 1.1版本) 汉字扩展规范GBK1.0 标准1995（非国家标准） 21003个字符（兼容GB2312） GB18030-2000(1/2/4字节编码) 27484汉字 （向下兼容GB2312 GBK，GB13000）

字模码介绍 字模码是用点阵表示的汉字字型代码，是汉字的输出形式。 字模点阵的信息量是很大的，所占存储空间也很大。以16*16为例，每个汉字要占用32个字节， 因此字模点阵只能用来构成汉字库，而不能用于机内存储。

Charset <META content="text/html; charset=gb2312" … http-equiv=Content-Type> 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多语言

Unicode www.unicode.org 用于克服字符数字的限制 为所有语言中的字符分配唯一的代码 16 bit 字符集，65536 Unicode 字符 提供唯一的代码 不论任何平台 不论任何程序 不论任何语言

Universal Character Set ISO UCS ISO 10646 UCS-2 UCS-4 UTF (Unicode Transform format) UTF-7 UTF-8 UTF-16

Terminology UUEncode/Uudecode MIME (Multipurpose Internet Mail Extensions )

2.2 数值数据表示方法 计算机数值数据表示的特点 进位制数 数的定点、浮点表示 机器数

计算机数据编码需要考虑的因素: 数的类型(小数、整数、实数和复数） 数值范围 数值精确度 数值存储和处理所需的硬件代价

计算机数据编码特点 少量简单的基本符号表示大量复杂的信息 状态简单 电路实现简单 运算方便 硬件成本

Human vs. Computer 人们日常生活采用10进制 计算机采用二进制 天生10个手指 计算机采用电子开关 开关仅仅包括两个状态 ON OFF

十进制编码特点 0123456789共10种状态，状态过多 运算组合状态过多 加法组合数= C102+10 =10*9/2!+10 =55 八进制： C82+8=8*7/2!+8=36 四进制： C42+4=4*3/2!+4=10 二进制： C22+2=2*1/2!+2=3 结论：二进制的组合状态最少

二进制编码特点 符号个数最少，“0、1” 物理上容易实现 用数字电路的两个状态表示(如电压高低） 与二值逻辑的 真 假 两个值对应简单 与二值逻辑的 真 假 两个值对应简单 二进制位可以表示任何对象(字符，数值，逻辑值) 用二进制码表示数值数据运算规则简单 0+1=1+0=1 1+1=0 0+0=0 仅仅三种运算规则(10进制有55种) 一个异或门即可完成该运算

一位全加器 输入: 加数Ai 、Bi 低位进位输入Ci 输出: 和数Si ，进位输出Ci+1 进位Ci+1 和数Si 加数Bi 加数Ai 进位Ci+1 和数Si 加数Bi 加数Ai 低位进位Ci

二进制加法器基本电路

进制表示 N 代表一个数值 r 是这个数制的基(Radix) i 表示这些符号排列的位号 Di 是位号为i的位上的一个符号 ri 是位号为i的位上的 1 代表的值 Di*ri 是第i位的所代表的实际值  表示m+k+1位的值求累加和

例子 (10456)10＝1×104＋0×103 ＋4×102＋5×101＋6×100 (0xF96)16＝F×162＋9×161 ＋6×100 (10010001)2＝1×27＋0×26 ＋0×25 ＋1×24 ＋0×23 ＋0×22 ＋0×21 ＋1×20

进制转换 二进制数转八进制 二进制数转十六进制 二进制数转十进制 十进制数转二进制

二到八或十六进制转换 二进制转到八进制 二进制转十六进制 说明：整数部分不足位数对转换无影响， 小数部分不足位数要补零凑足，则出错。 从小数点向左右三位一分组 (10 011 100 . 01)2 = ( 234 . 2 )8 010 二进制转十六进制 从小数点向左右四位一分组 (1001 1100 . 01)2 = ( 9C . 4 )16 0100 说明：整数部分不足位数对转换无影响， 小数部分不足位数要补零凑足，则出错。

从二进制数求其十进制的值，逐位码权累加求和 二进制转十进制 从二进制数求其十进制的值，逐位码权累加求和 10010001＝1×27＋0×26 ＋0×25 ＋1×24 ＋0×23 ＋0×22 ＋0×21 ＋1×20

十进制转二进制 整数部分除2取余 小数部分乘2取整 求得位数满足要求为止 除尽为止 1011 2 1 1 1 0.625 * 2 2 5 1 整数部分除2取余 小数部分乘2取整 2 1 1 1 低 0.625 * 2 2 5 高 低 1 0.25 * 2 1 0.5 * 2 2 2 1 1 1 2 高 0.0 除尽为止 1011 求得位数满足要求为止

进制转换的简单运算方法 MEMORIZE! －17/128的二进制表示方法??? 大数的转换方法，记住几个常用的2的幂 25＝32 26＝64 27＝128 28＝256 29＝512 210＝1024(1Kilo) 211＝2048 212＝4096 213＝8182 214＝16364 215＝32728 216＝65536 220＝1048576(1Mega) 230＝1073741824(1Giga) 240＝1Tera 更大的单位是多少？ 250＝1 Peta 260＝1 Exa 270＝1 Zetta 280＝1 Yotta MEMORIZE!

Kilo, Mega, Giga, Tera, Peta, Exa, Zetta, Yotta physics. nist Kilo, Mega, Giga, Tera, Peta, Exa, Zetta, Yotta physics.nist.gov/cuu/Units/binary.html 30GB=???Byte 1Mbits=??? 30 GB drive＝30 x 109 ＝28 x 230 bytes 1 Mbit/s = 106 bps 硬盘厂商及通讯行业是计算机行业唯一使用SI因子的

1999 New IEC Standard Prefixes http://en. wikipedia SI (International System of Units )仅指10进制 234可以访问多少存储单元? 2.5 TiB存储空间需要多少地址线进行译码？ MEMORIZE!

几个简化运算的例子 130=128+2=10000010 65539=65536+3=10000000000000011 2003=2047-44=111111111111-32-8-4 MEMORIZE! 111111110111＝212-1-8 111111111110=111111111111-1 =212-1-1=4046 -17/128=-0.0010001

2.2 数值数据表示方法 计算机数值数据表示的特点 进位制数 数的定点、浮点表示 机器数

2.2.1 数的定点、浮点表示方法 定点表示 (小数点位置固定的数) 浮点表示 Signed & Unsigned 定点小数 定点整数 定点表示 (小数点位置固定的数) 定点小数 定点整数 仅能表示纯小数及纯整数 浮点表示 Signed & Unsigned

定点小数 X0 X1 X2 X3 Xn 符号位 小数点位置 数值部分 2-n ≦ |X|≦1-2-n 下溢/上溢 最高有效位 最低有效位 … Xn 符号位 小数点位置 数值部分 X0 1 … 2-n ≦ |X|≦1-2-n 下溢/上溢 X0 … 1

定点小数的编码 数值表示 X = X 0 . X1 X 2… X n X i={0,1}, 0≤i≤n =X 12-1 + … + X n-12-n+1 + X n 2-n 数值范围 0≤|x| ≤1-2-n

定点整数 X0 X1 X2 X3 Xn 符号位 数值部分 小数点位置 1 ≦|X|≦2n-1 上溢 最高有效位 最低有效位 X0 1 X0 … Xn 符号位 数值部分 小数点位置 X0 1 … 1 ≦|X|≦2n-1 上溢 X0 … 1

定点整数的编码 数值表示 数值范围 X = X1X2…Xn Xi={0,1}, 0≤i≤n =X12n-1 + … + Xn-121 + Xn 数值范围 0≤|x|≤2n-1

浮点数如何表示 ????? 参与运算的数据通常既包括整数也包括小数部分。 如何表示？如何运算？？ 将数据按照一定比例因子缩小成定点小数或扩大成定点整数进行表示和运算 运算完毕后再根据比例因子还原成实际数值 计算机中浮点运算有专门的器件

浮点数如何表示… 电子的质量 9×10-28g 太阳的质量2×1033g＝0.2×1034 科学记数法N=10E×M N=Re×m M称为尾数，是一个纯小数，e是比例因子的阶数，称为浮点数的指数，是一个整数，R为基数

浮点数的表示 将比例因子以适当形式表示在数据中即可表示浮点数 可有效提高数字表示范围，也保持了数字有效精度 N=Re×m=2E×M … Em M0 M1 M2 … Mn 阶符 阶值 尾符 尾数值

浮点数的表示范围 负下溢 正下溢 负上溢 正上溢 -  负数 正数 + N=2E×M |N|→∞ 产生正上溢或者负上溢 正数 + N=2E×M |N|→∞ 产生正上溢或者负上溢 阶码正上溢 E →+∞ 阶码负上溢 E → - ∞ |N|→0 产生正下溢或者负下溢

Range & precision 机器字长一定时，阶码越长，表示范围越大，精度越低 浮点数表示范围比定点数大，精度高 阶符 阶值 尾符 … Em M0 M1 M2 … Mn 阶符 阶值 尾符 尾数值 机器字长一定时，阶码越长，表示范围越大，精度越低 浮点数表示范围比定点数大，精度高

Example 8位定点小数可表示的范围 设阶码2位，尾数4位 设阶码3位，尾数3位 0.0000001 --- 0.1111111 1/128 --- 127/128 设阶码2位，尾数4位 可表示2-11*0.0001 --- 211*0.1111 0.0000001 --- 111.1 设阶码3位，尾数3位 可表示2-111*0.001 --- 2111*0.111 0.0000000001 --- 1110000

浮点数的规格化问题normalization 0.05*101 50*10-2 5*10-1 0.01*21 1*2-2 1*2-1 尾数最高有效位为1的数称为规格化数。 为了在尾数中表示最多的有效数据位 为了数据表示的唯一性。 两种规格化数 1.XXXXX 0.1XXXXX 机器零：全部为0，特殊的数据编码

浮点数标准 IEEE754 构成：阶码E，尾数M，符号位S， N = (-1)SX M X 2E 32/64位浮点数（Float/Double） S(1bit) E(23~30共8bit) M(0~22共23bit) S(1bit) E(52~62共11bit) M(0~51共52bit) 构成：阶码E，尾数M，符号位S， N = (-1)SX M X 2E

浮点数标准 IEEE754… (-1)s×1.m×2e-127 (-1)s×0.m×2-126 规格化数(Normal)： 非规格化数(Subnormal)(e=0) (-1)s×0.m×2-126 尾数部分采用原码表示，故表示范围对称 emin=1, emax=254/2046 最高数字位总是1，该标准将这个1缺省存储(隐藏位implicit)，使得尾数表示范围比实际存储多一位

单精度浮点数编码格式 符号位 阶码 尾数 表示 0/1 255 非零1xxxx NaN Not a Number 0/1 255 sNaN Signaling NaN 255 +∞ 1 255 - ∞ 0/1 1~254 f (-1)S× (1.f) ×2(e-127) 0/1 f(非零) (-1)S× (0.f) ×2(-126) 0/1 +0/-0

IEEE754 规格化浮点数表示范围 格式 最小值 最大值 单精度 Emin=1, M=0, 1.0×21-127 = 2-126 Emax=254, f=1.1111…, 1.111…1×2254-127 = 2127×(2-2-23) 双精度 Emin=1, M=0, 1.0×21-1023 =2-1022 Emax=2046, f=1.1111…,1.111…1×22046-1023 =21023×(2-2-52)

一个奇怪的程序 3.000000,2 Really?3.0!=a ?????????? 二进制存储 浮点数不是精确数 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 ?????????? 二进制存储 浮点数不是精确数

一个奇怪的程序 3.000000,2 main() { float a,b,c; int d; b=3.3; c=1.1; a=b/c; printf("%f,%d",a,d); if (3.0!=a) printf("\nYeah!"); } 3.000000,2

2.2 数值数据表示方法 计算机数值数据表示的特点 进位制数 数的定点、浮点表示 机器数

2.2.2 机器数/机器码 真值 (书写用) 机器不能识别书写格式，计算机如何表示负数？ 机器码 (机器内部使用) 真值 (书写用) 将用+ -表示正负的二进制数称为符号数的真值 机器不能识别书写格式，计算机如何表示负数？ 机器码 (机器内部使用) 将符号和数值一起编码表示的二进制数称为机器码 原码 Signed magnitude 反码 One’s complement 补码 Two’s complement 移码 Biased notation

原码表示法（Signed magnitude） 计算机如何表示数的正负? 增加符号位 Add a sign bit 最高位为符号位，0为正，1为负，数值位不变

原码表示示例 [+0]原=0.000…0 [-0]原=1. 000…0 [-0.1111]原 = 1.1111 [ 0.1111]原 = 0.1111 [ 1110]原 = 01110 [-1110]原 = 11110

原码表示法 求值方法 x = (-1)X0( x12n-1 + … + xn-12 +Xn) 求值方法 x = (-1)X0( x12-1 + … + xn-12-(n-1) +Xn2-n)

原码在数轴上的表示 -7~+7 7个正数，7个负数，两个零 -(2(n-1) -1) ~2(n-1) -1

Signed Magnitude Both positive and negative zero Equal number of positives and negatives Easy to interpret First bit is the sign Remaining bits are number Sounds ideal? But… 01011001+11001101=???

Signed Magnitude? 010110012 = 8910 + 110011012 = -7710 001001102 = 3210 If signs are different sign of result will be sign of larger operand

Shortcomings of signed magnitude? Arithmetic circuit complicated Also, two zeros 0x00000000 = +0ten 0x80000000 = –0ten What would two 0s mean for programming? Therefore sign and magnitude abandoned

反码表示法 所谓反码,就是二进制的各位数码取反 符号位表示方法与原码相同 Example: 710 = 001112 ； -710 =110002 Called One’s Complement

反码0的表示 [+0]反=0.000…0 [-0]反=1.111…1 [0.1111]反=0.1111 [-0.1111]反=1.0000 [1110]反=01110 [-1110]反=10001

反码公式证明 -1<x<=0时 [x]反=2-2-n-|x|=2-2-n+x 假设 x=-0.x1x2…xn =1.11…1+0.00…1-0.00…1 =10.00…0-0.00…1 =2-2-n [x]反=2-2-n-|x|=2-2-n+x

反码公式证明 -2n<x<=0时 [x]反= 2n+1-1 -|x|= 2n+1-1 +x 假设 x= -x1x2…xn = 111…1+000…1-000…1 = 1000…0-000…1 = 2n+1-1 [x]反= 2n+1-1 -|x|= 2n+1-1 +x

反码表示法… 求值方法([X]反= x0x1 … xn-1 Xn) 2n+1－1+X -2n < X ≤ 0 求值方法([X]反= x0x1 … xn-1 Xn) x = -x0（2n -1）+ x12n-1 + … + xn-12 +Xn [X] 反= X 0≤X<1 2 - 2－n+X -1 < X ≤ 0

反码在数轴上的表示 -7~+7 正数7个，负数7个，零两个 -(2n -1) ~2n -1

原码&反码

Shortcomings of One’s complement? Arithmetic still a somewhat complicated. Still two zeros 0x00000000 = +0ten 0xFFFFFFFF = -0ten Although used for awhile on some computer products, one’s complement was eventually abandoned because another solution was better.

有趣的时钟 3与15、-9等效 12 9 3 6 12 3 6 9 12 3 6 9

同余的概念 a≡b (mod m) Z≡Y (mod X) Y≡Z (mod X) 假定有两个数a和b，若用某一个整数m去除，所得的余数相同，就称a,b两个数对m同余,记作：              a≡b  (mod m) 假设X,Y,Z三个数，满足下列关系：Z=nX+Y (n为整数),则称Z和Y对模X是同余的，记作：        Z≡Y (mod X)      Y≡Z (mod X)

例子 Z=nX+Y X为模数 以12为模 3=12+3=24+3=36+3 3，15，27，39 都是相等的 -9=12-9=3 -9与3是相等的 0=12

例子（减法变成加法） 7+(-4) =7+(12-4) =7+8 =15=3

3. 补码表示法 求值方法([X]补= x0x1 … xn-1 Xn) x = -x02n + x12n-1 + … + xn-12 +Xn 例如：10000100的真值为-128+4=-124 [X] 补= X 0≤X<1 2+X -1≤X<0

补码在数轴上的表示 -8~+7 正数7个，负数8个，零1个 -2n ~2n -1

反码、补码数轴表示比较

补码编码的简便方法 正值直接取其原来的二进制码，对于负数是在对其逐位取反之后再在最低位LSB加1。 [-10101010]补 =1 01010101+1 =1 01010110 [-0.010101]补=1.101011

证明 定点小数时 整数时 [x]反=2-2-n+x [x]反=2n+1-1+x [x]补=2+x [x]补=2n+1+x =(2-2-n+x)+2-n =[x]反+2-n 整数时 [x]反=2n+1-1+x [x]补=2n+1+x =(2n+1-1+x)+1 = [x]反+1

例子 X=+0.11111111 [X]补 =??? [X]补 =0.11111111 X=-0.11111111 [X]补 =1.00000000 +0.00000001 =1.00000001 X=-0.00000000 [X]补 =??? [X]补 =1.11111111 +0.00000001 =10.00000000 =0.00000000

32 bit MIPS signed numbers 0000 0000 0000 0000 0000 0000 0000 0000two = 0ten 0000 0000 0000 0000 0000 0000 0000 0001two = + 1ten 0000 0000 0000 0000 0000 0000 0000 0010two = + 2ten ... 0111 1111 1111 1111 1111 1111 1111 1110two = + 2,147,483,646ten 0111 1111 1111 1111 1111 1111 1111 1111two = + 2,147,483,647ten 1000 0000 0000 0000 0000 0000 0000 0000two = – 2,147,483,648ten 1000 0000 0000 0000 0000 0000 0000 0001two = – 2,147,483,647ten 1000 0000 0000 0000 0000 0000 0000 0010two = – 2,147,483,646ten ... 1111 1111 1111 1111 1111 1111 1111 1101two = – 3ten 1111 1111 1111 1111 1111 1111 1111 1110two = – 2ten 1111 1111 1111 1111 1111 1111 1111 1111two = – 1ten maxint minint

模4补码 例： 00.1010110 11.0101001 又称 双符号位补码，变形补码 X 0≤X<2n 2n+2+X -2n≤X<0 例： 00.1010110 11.0101001 又称 双符号位补码，变形补码 [X] 补= X 0≤X<1 4+X -1≤X<0

补码的性质 零有唯一的表示方式 负一的补码 [＋0.0000]补= [-0.0000]补= 0.0000 [－1.0000]补= 1.0000

补码加减法的实现 [X + Y]补= [X]补+ [Y]补 [X-Y]补= [X]补+ [-Y]补

补码特点 唯一的零 符号位可以直接参与运算 减法可以变成加法 负数比整数多一个

4. 移码表示法 Biased/Excess Notation 定义 [x]移 = 2n+x -2n ≤ x < 2n 保持数据原有大小顺序，便于进行比较操作。 通常仅用于表示整数，表示浮点数的阶码。 与补码的符号位相异，数据位相同

移码表示 X=+10101 [X]移 =25+10101=110101 X=-10101 [X]移 =25-10101 ＝01010＋00001 ＝001011

移码在数轴上的表示 定点小数没有移码定义 平行移动

各种编码 Binary Number Stored Number Represented 000 +0 +0 -4 001 +1 +1 +1 原码 反码 补码 移码 000 +0 +0 -4 001 +1 +1 +1 -3 010 +2 +2 +2 -2 011 +3 +3 +3 -1 100 3 -4 101 1 2 -3 +1 110 2 1 -2 +2 111 3 -1 +3 Number Stored Number Represented

定点小数机器码表示范围 X0.X1X2X3…Xn-1Xn n+1位定点数，数据位n位 原码，反码表示区间一致 补码 (-1,1) 补码 [-1, 1-2-n] [-1,1) 2+x

定点整数数机器码表示范围 X0X1X2X3…Xn-1Xn n+1位定点数，数据位n位 原码，反码表示区间一致 补码 [1-2n, 2n-1] [-2n, 2n) 2n +x

几种编码的应用 移码主要用于表示浮点数的阶码 补码加减法运算方便，得到了广泛的应用。 目前计算机中广泛采用补码表示方法。 少数机器采用原码进行存储和传送，运算的时候改用补码。

几种机器编码简便方法对比 真值为负数 真值为正数 机器码 原码 符号位为零,等于真值本身 符号位为一,数值位为真值本身 简便编码方法：加符号位 补码 符号位为零,等于真值本身 符号位为一,逐位取反,末位加一 反码 符号位为零,等于真值本身 符号位为一,逐位取反 移码 符号为一,数值位为真值本身 符号位为零,数值位逐位取反,末位加一

例子 机器码 +00001111 -00001111 +0.00001111 -0.00001111 原码 000001111 100001111 0.00001111 1.00001111 补码 000001111 111110001 0.00001111 1.11110001 反码 000001111 111110000 0.00001111 1.11110000 移码 100001111 011110001 小数无移码 小数无移码

2.2.3 十进制数的表示 BCD码 Binary coded decimal二进制编码的十进制 几种BCD码 8421码 (8*X3+4*X2+2*X1+1*X0) 2421码 (2*X3+4*X2+2*X1+1*X0) 余三码 (8*X3+4*X2+2*X1+1*X0)+0011 BCD码运算的问题(编码校正)

BCD码运算问题 8421码的校正 余三码的校正 相对而言运算比较复杂 8＋7＝1000＋0111＝1111 非法编码 8＋7＝1000＋0111＝1111 非法编码 余三码的校正 0＋0＝0011＋0011＝0110 ＝3 非法编码 4＋4＝0111＋0111＝1110 ＝？非法编码 相对而言运算比较复杂

2.3 数据信息的校验 解决编码传输问题 在编码中引入一定冗余，增加代码的最小码距，使编码出现一个错误时就成为非法代码 奇偶信息的校验 海明校验 CRC 循环冗余校验

2.3.1 奇偶校验 奇校验： 偶校验: 奇校验: 检错码: 校验码（数据＋校验位）中1的个数为奇数 0000  00001 0001  00010 偶校验: 奇校验: 检错码: G=0表示数据正常，否则表示出错

奇偶校验… + + 检测码不为零表示错误发生 同时发个多个错误时的情况？ d7d6d5d4d3d2d1d0 p g 检测码不为零表示错误发生 同时发个多个错误时的情况？

奇偶校验性能 00001 00001 00001 00001 00001 00000 01111 11111 正确传输 正常检错 正常检错 不能检错 仅能识别奇数个错误，不能纠正错误

2.3.2 海明校验Hamming Codes 奇偶校验 一个校验位 只能检错，无法纠错 1950海明码 多个奇偶校验组 既能检错，也能纠错

可检测一位错海明码… 分组交叉奇偶校验法 全部检错码为0表示数据正常 不为零时检错码的值表示编码中出错数据位 可检错，也可纠错 将编码中的数据位分成r个校验组，组内采取奇偶校验，每组一个校验位，可构成r位检错码。r>1 全部检错码为0表示数据正常 不为零时检错码的值表示编码中出错数据位 可检错，也可纠错 每一数据位至少参加2个校验组，一位出错，可引起多个检错码的变化。

可检测一位错海明码… 设海明码N位，其中数据位k位，校验位r位 校验位r位表示共r个校验组 N=k+r≤2r－1 (4,3)编码 D4D3D2D1P3P2P1 H7H6H5H4H3H2H1 包含G3G2G1个校验组，P3P2P1分属其中一组

可检测一位错海明码… G3G2G1 出错位 备注 000 数据正常 001 H1出错 G3G2=0 表示仅仅P1位出错 P1存放在H1位置 010 H2出错 G3G1=0 表示仅仅 P2位出错 P2存放在H2位置 100 H4出错 G2G1=0 表示仅仅 P3位出错 P3存放在H4位置 011 H3出错 H3参与G2 G1两校验组 101 H5出错 H5参与G3 G1两校验组 110 H6出错 H6参与G3 G2两校验组 111 H7出错 H7参与G3 G2 G1三校验组

可检测一位错海明码… G1(P1,H3,H5,H7) G2(P2,H3,H6,H7) G3(P3,H5,H6,H7) P1=D1⊕D2⊕D4 H7参与G3 G2 G1校验组 H6参与G3 G2校验组 H5参与G3 G1校验组 H3参与G2 G1校验组 H7出错 111 H6出错 110 H5出错 101 H3出错 011 备注 出错位 G3G2G1 G1(P1,H3,H5,H7) G2(P2,H3,H6,H7) G3(P3,H5,H6,H7) P1=D1⊕D2⊕D4 P2=D1⊕D3⊕D4 P3=D2⊕D3⊕D4 H1 H2 H3 H4 H5 H6 H7 D4 D3 D2 P3 D1 P2 P1

指错、纠错原理 G1=P1⊕D1⊕D2⊕D4 G2=P2⊕D1⊕D3⊕D4 G3=P3⊕D2⊕D3⊕D4 检错码G3G2G1 !=000表示出错，具体值表示出错位置 将对应位置上的数位取反即可纠错 假设D1D2同时出错，则G3G2G1=110 ？？？ 引入总校验位 P4=H1⊕H2⊕H3⊕H4⊕H5⊕H6⊕H7 G4=P4⊕H1⊕H2⊕H3⊕H4⊕H5⊕H6⊕H7 判断一位错两位错

CRC循环冗余校验码 检错，纠错码 数据位k位，校验位r位 N=k+r≤2r－1

模2运算规则 加法：按位加不考虑进位 减法：按位减不考虑借位 乘法：部分积之和按模2加法计算 除法：余数首位为1，商上1 ,否则上0 异或运算，不考虑进位 乘法：部分积之和按模2加法计算 除法：余数首位为1，商上1 ,否则上0 10000÷101 =101*101+01

多项式 将待编码的k位有效信息位组表达为多项式M(x) M(x)=bk-1Xk-1 + bk-2Xk-2 +… b1X1 + b0 将数据左移r位，以便空出r位校验位，多项式变成M(x)·X r 将M(x)·X r除以生成多项式G(x) 商为Q(x) 余数R(x) M(x)·X r=Q(X)·G(x)+R(X) 将余数拼接在空出的校验位上 M(x)·X r+R(X)=(Q(X)·G(x)+R(X))+R(x) ＝Q(X)·G(x) CRC编码可被G(x)表示的编码整除

(7,4)循环码出错模式G(x)=1011 余数 出错位 1100010 000 无 1100011 001 7 1100000 010 6 A1~A7 余数 出错位 1 1 1 1 1100010 000 无 1 1100011 001 7 1 1 - 1100000 010 6 1 1100110 100 5 1 1 - 1101010 011 4 1 1110010 110 3 1 - 1000010 111 2 1 1 - 0100010 101 1 1

生成多项式 任何一位发生错误都应使余数不为0 不同位发生错误应当使得余数不同 对余数继续作模2除，应使余数循环 (n,k)码，将Xn-1分解为若干质因子 根据编码要求的码距选择其中的因式或若干因式的乘积为生成多项式

生成多项式 x7-1=(x+1)(x3+x+1)(x3+x2+1) G(x)=x+1=11 (7,6)码，判一位错 G(x)= x3+x+1 G(x)＝(x3+x2+1) (7,4)码，判两位错或纠一位错 G(x)=(x+1)(x3+x+1)=11101 (7,3)码，判两位错并纠一位错

Example 现有一个(7,3)循环冗余校验码，其中3位为信息位，求信息位M(x)=110的CRC码，其中生成多项式为G(x)=11101。

(7,3)循环码出错模式G(x)=11101 余数 出错位 余数 出错位 1101001 0000 无 1101010 0011 6+7 A1~A7 余数 出错位 A7~A1 余数 出错位 1101001 0000 无 1101010 0011 6+7 1101000 0001 7 1101111 0110 5+6 1101011 0010 6 1100101 1100 4+5 1 1110 0101001 2 0111 1001001 3 1101 1111001 4 1000 1100001 5 0100 1101101 1110001 0101 3+4 1011001 1010 2+3 0101011 1100 1+6 1101110 0111 5+6+7 0010001 0100 1+2+3

CRC(Cyclic Redundancy Check 可检测出所有的双错、奇数位错 可检测所有小于、等于校验位长度的突发错 突发错是指几乎连续发生的一串错，突发长度就是指从出错的第一位到出错的最后一位的长度(但是，中间并不一定每一位都错) 广泛运用于通信传输领域，磁存储领域

本章重点内容 二进制表示以及进制转换运算 2X、X/2 、X/64的求解方法 真值、原码、补码、 移码、 反码的编码方法。 纠错码和检错码 熟练掌握 纠错码和检错码 奇偶校验熟练掌握 海明，CRC会计算 BCD码 机器数 有权码 校验码概念

Example（清华大学1998年试题） 写出数据-11.4的规格化浮点数形式表示，阶码采用4位移码,尾数用12位原码，含符号位。 写出上述格式的规格化浮点数所能表示的最大正数和最小正数。 说明上述格式中浮点数的机器零 说明浮点数中隐藏位含义和用法

解答 -11.4=-1011.01100111 -11.4=-0.101101100111*24 -11.4=-1.01101100111*23 -11.4=-01101100111*23 -11.4=1,01101100111*23 M=1,01101100111 E=3=1,011

解答… (-1)s×1.m×2e 最大整数 1.11111111111×27 最小整数 1.00000000000×2-8 =(2-2-11) ×27 最小整数 1.00000000000×2-8 = 2-8