第二章数据编码和数据运算1

1、第二章 数据编码和数据运算n2.1数据与文字的编码数据与文字的编码n 数字计算机中采用二进制的数据表示方式，因为二进制数能方便可靠地用数字电路的逻辑电平表示。n 在计算机中表示的二进制数据称为机器数。它是一系列位数固定而且数量有限的二进制代码，表示的数值范围也是有限的。计算机中表示的机器数是一系列离散的数据。一个机器数所代表的实际数值称为真值 2.1.1 数制的转换n十进制数采用十个计数符号计数规则n逢十进一一个n位的十进制数x0 x1xn-2 xn-1代表的数值为：x0*10n-1 + x1 * 10n-2 + + xn-2 * 101 + xn-1 * 100二进制数n采用2个计数符号n逢

2、2进1n一个n位的二进制数x0 x1xn-2 xn-1代表的数值为：x0*2n-1 + x1 * 2n-2 + + xn-2 * 21 + xn-1 * 20r进制数n采用r个计数符号n逢r进1n一个n位的r进制数x0 x1xn-2 xn-1代表的数值为：x0*rn-1 + x1 * rn-2 + + xn-2 * r1 + xn-1 * r00 xi r-1 (0in-1)n有小数的情形数制转换n将二进制数转换成八进制数从小数点的位置开始每三位一组分别转换成相应的八进制数的计数符号不足三位时补0n将二进制数转换成十六进制数四位一组进行转换n例0010101102=1268=5616数制转换n

3、将八进制数转换成二进制数从小数点的位置开始每一位八进制数分别转换成三位二进制数n将八进制数转换成二进制数n十进制数转换成二进制数整数部分采用除2取余法小数部分采用乘2取整法x02n-1 + x12n-2 + + xn-221 + xn-120【例例1 1】 将十进制整数将十进制整数100100转换成二进制整数。转换成二进制整数。解：用解：用2 2连续除连续除100100，直至商小于，直至商小于2 2，算式如下：，算式如下： 运算结果：运算结果：100=1100100B100=1100100B【例例2 2】 将十进制小数将十进制小数0.6180.618转换成二进制小数。转换成二进制小数。解：用解

4、：用2 2连续乘以连续乘以0.6180.618，小数部分为，小数部分为0 0或保留或保留4 4位小数，算式如位小数，算式如下：下： 运算结果：运算结果：0.6180.1001B0.6180.1001B。 不同数制之间的转换规则：n二进制数转换成十六进制数二进制数转换成十六进制数采用采用“四位合一位四位合一位”法法 n十六进制数转换成二进制数十六进制数转换成二进制数采用采用“一位分四位一位分四位”法法 n二进制数转换成十进制数二进制数转换成十进制数按按权展开后相加权展开后相加 n十六进制数转换成十进制数十六进制数转换成十进制数按按权展开后相加权展开后相加 n十进制整数转换成二进制整数十进制整数转

5、换成二进制整数采用采用“除以除以2 2取余取余”法法n十进制整数转换成十六进制整数十进制整数转换成十六进制整数采用采用“除以除以1616取余取余”法法n十进制小数转换成二进制小数十进制小数转换成二进制小数采用采用“乘乘2 2取整取整”法法 n十进制小数转换成十六进制小数十进制小数转换成十六进制小数采用采用“乘乘1616取整取整”法法 2.1.2 定点数的编码n 定点数是指小数点位置固定不变的数据。在计算机中，通常采用两种类型的定点数表示。一种定点数把小数点定在最低位数的右面，这种定点数称为定点整数，因为它实际没有小数。另一种定点数把小数点固定在最高位数的后面，即纯小数表示，称为定点小数，它只保

6、留小数点后面的数据，小数点前面的一位数据固定为零。这种二进制定点数的表示可以直接在计算机中表示，计算机中表示无符号数就直接用这种二进制的表示作为数据的编码 n机器数机器数计算机中表示的二进制数据n真值真值一个机器数所代表的实际数值n定点数定点数定点整数定点小数(b) 定点小数(a) 定点整数xxxxxxxxx xxxxxxx2.1.2 定点数的编码机器数n无符号数半字、字、双倍字、四倍字n有符号数原码、反码、补码、移码1位符号位无符号数的编码无符号数的编码n定点整数定点整数数值表示x = x0 x1x2xnxi=0,1, 0inx02n + x12n-1 + + xn-121 + xn数值范围

7、n0 x2n+1-1无符号数的编码无符号数的编码n定点小数定点小数数值表示x = x0 . x1x2xn x0=0,xi=0,1, 0in x12-1 + + xn-12-n+1 + xn2-n数值范围n0 x1-2-n有符号数的编码有符号数的编码n计算机中的数据编码都是有一定的表示范围的，离散的；而不像数学中的数可以是任意大的，连续的。n在数据编码中，如果数据值超过了编码所能表示的数值范围，则称为数值溢出。n计算机中表示一个带符号数的方法有：原码表示法、反码表示法、补码表示法和移码表示法四种。1. 原码表示法特点：简便编码方法（加符号位）例：3原 = 00000011-3原= 1000001

8、11. 原码表示法n零有两种表示方式例例 设x=101010，y= -101010，求x原和y原解：解： x原=00101010y原=10101010例例 设x=0.1010，y= -0.1010，求x原和y原解：解： x原=0.101010y原=1.1010102. 补码表示法特点：便于运算例：3补 = 00000011-3补= 111111012s complement coding2. 补码表示法n方法方法1正数：直接取其原来的二进制码（加符号位正数：直接取其原来的二进制码（加符号位0）负数：对其二进制码按位取反之后再在最低位加负数：对其二进制码按位取反之后再在最低位加1例：例：0101

9、01补补=00010101-010101补补=11101010+1=11101011n方法方法2正数：直接取其原来的二进制码正数：直接取其原来的二进制码负数：从二进制码的最低位开始，对遇到的负数：从二进制码的最低位开始，对遇到的0和第一和第一个个1取其原来的二进制编码，从第一个取其原来的二进制编码，从第一个1以后开始直以后开始直到最高位均取其相反编码。到最高位均取其相反编码。例：例：101010补补=0101010-101010补补=1010110定点小数的补码编码nx= x0.x1xnn数值范围：-1 x 1 - 2-n例例 设x=0.101010，y=-0.101010， 求x补和y补。解

10、：解：x补=0.101010y补=1.010110补码求值的方法补码求值的方法n公式法x = -x02n + x12n-1 + + xn-12 + xn例如：10000100的真值为-128+4=-124n求补法x补与-x补的关系例: x补=11111100 -x补=00000100 -x=4 x=-43. 反码表示法例：例：1010反反 = 01010 -1010反反= 101011s complement codingn反码的表示法是用对负值的各位取反的表示方法.对于给定的反玛x反的代码，其数值：3. 反码表示法n编码方法正数的反码与原码相同负数的反码是将二进制位按位取反n数值范围-2n

11、+1 x 2n -1定点小数-1 + 2-n x 1-2-nn零有两个编码：0000和11114. 移码表示法n编码方法x移 = 2n +xn数值范围-2n x 2n - 1符号位：1表示正号，0代表负号0有惟一的编码保持了数据原有的大小顺序定点小数没有移码定义4. 移码表示法例例 设x=101010，y= -101010，求x移和y移。解：解： x移=1000000+101010=10101010y移=1000000+(-101010) =10000000-0101010=01010110四种编码的例子数据真值与数据编码n数据的真值中可以把最高位的0省略n数据编码中不能忽略任何位置上的0或1

12、n数据编码的最高位代表数据的符号n数据真值的最高位则不代表符号nx表示真值nxxx表示编码2.1.3 浮点数的编码构成：阶码E，尾数M，符号位S，基数RN = (-1)SMRESEM E的编码：移码或补码 S与M的编码：原码或补码 R进制的含义：多个二进制位构成一组，代表一个R进制位例：0 00111 1100000000 或 00111, 1.1100000000浮点数的编码n规格化0.12 = 0.120 = 0.0121要求数值中小数点后第一位为非零为了在尾数中表示最多的有效数据位为了数据表示的唯一性n机器零全部为0特殊的数据编码规格化的编码n基数为2的浮点数规格化尾数的绝对值在1/2到

13、1之间n基数为R的浮点数规格化尾数的绝对值在1/R到1之间n原码数据位的最高位为1n补码小数点前后两位互不相同尾数0.1010和1.0101是规格化的尾数0.0101和1.1010是非规格化的x.1xxxxxx0.1xxxxxx1.0 xxxxxx规格化的编码例例2-1 对数据12310作规格化浮点数的编码，假定1位符号位，基数为2，阶码5位，采用移码，尾数10位，采用补码。解：12310 = 11110112 = 0.1111011000227 7移=10000+00111 = 101110.1111011000补=0.1111011000123浮=0 10111 1111011000浮点数

14、的表示范围n浮点数的溢出表现为阶码的溢出n浮点数的上溢(overflow)数据大于阶码所能表示的数据n浮点数的下溢(underflow)数据小于阶码所能表示的数值时 负上溢 负下溢 正下溢 正上溢图 2-2 浮点数的表示范围- +负数正数02.1.4文字的编码n1. 西文字符的编码ASCII码n2. 汉字的编码输入码n数字编码、拼音码和字形码机内码n用于汉字信息存储、交换、检索等操作n3. 十进制数的编码汉字的存放n汉字的表示方法（一级汉字3755个，二级汉字3008个）输入码n国标码一级（1655）*94二级（5687）*94图形符号（682个）（0109）*94n拼音、五笔汉字内码：汉字信

15、息的存储，交换和检索的机内代码，两个字节组成，每个字节高位都为1（区别于英文字符）汉字字模码：汉字字形n点阵n汉字库十进制数的编码n编码的方法字符串形式nASCII码的高位置0压缩的十进制数串形式n对每一位十进制数用四个二进制位编码表示nBCD码(binary coded decimal)n用4位编码中的剩余6个代码表示符号2.1.5 检错码和纠错码n能够发现某些错误或具有自动纠错能力的数据编码n在代码中增加冗余位以使代码具有某种特征n分组码n卷积码1.奇偶校验码n奇校验：xk+1 = x1 + x2 + + xk + 1 mod 2n偶校验：xk+1 = x1 + x2 + + xk mod

16、 2n例：偶校验0000 000000001 000110010 00101奇偶校验码的原理n码距两个合法代码对应位上编码不同的位数海明距离n在编码中引入一定的冗余，增加代码的最小码距，使得编码中出现一个错误时就成为非法代码。合法代码合法代码非法代码合法代码合法代码非法代码非法代码问题n某一个检错码具有以下4个码字，指出各码字之间的码距：0000000000000001111111111000001111111111如果码距更大.合法代码合法代码非法代码非法代码非法代码非法代码非法代码合法代码?2. 海明码海明码n海明码：（n, k）码长n=2m - 1信息位数k=2m - m - 1校验位数

17、m= n - k最小码距d = 3(7,4)海明码的例子c1 = x1 + x2 + x3c2 = x2 + x3 + x4c3 = x1 + x2 + x4将这些信息位和校验位构成码字将这些信息位和校验位构成码字w，即即w = x1,x2,x3,x4,c1,c2,c3=w1,w2,w3,w4,w5,w6,w7校验方程：校验方程：w1 + w2 + w3 + w5 = 0 w2 + w3 + w4 +w6 = 0w1 + w2 + w4 + w7 = 0(7,4)海明码的例子例例 用上述定义的海明码对数据1010进行编码。解解：根据上述海明码定义，得c1 = x1 + x2 + x3 = 0

18、(mod 2)c2 = x2 + x3 + x4 = 1 (mod 2)c3 = x1 + x2 + x4 = 1 (mod 2)所以编码的结果为1010011。练习n对于海明码校验方程w1 + w2 + w3 + w5 = 0 w2 + w3 + w4 +w6 = 0w1 + w2 + w4 + w7 = 0假如出现了码字 w1,w2,w3,w4,w5,w6,w7=0,1,0,1,0,1,0问该码字是否合法？如果不合法，是哪一位发生了错误？应该纠正成什么码字？3. 循环码n定义线性码中若一个n位编码V = vn-1 , vn-2 , , v1, v0是码C的一个码字，那么V向右循环移动一位后的n位编码V1 = v0, vn-1