《计算机组成原理》第二章 计算机中的数据显.ppt

2020年2月14日 第1页 第2章计算机中的数据表示 计算机组成原理 第二版 清华大学出版社 教学目标教学重点教学过程 2020年2月14日 第2页 教学目标 数据在计算机中的表示方法及编码形式掌握进位计数制和数制之间的转换掌握数与字符的表示方法及校验方法 2020年2月14日 第3页 教学重点 进位计数制和数制之间的转换定点数和浮点数带符号数的表示方法字符编码数据校验码 2020年2月14日 第4页 教学过程 2 1数据 信息和媒体2 2进位计数制2 3定点数和浮点数2 4带符号数的表示方法2 5十进制数据表示2 6字符编码2 7数据校验码2 8例题解析 2020年2月14日 第5页 2 1数据 信息和媒体 1 4 数据 是对事实 概念或指令的一种特殊表达形式 可以用人工方式或自动化装置进行通信 翻译转换或加工处理 数值型数据 具有特定值的一类数据 可用来表示数量的多少 可比较其大小 非数值型数据 包括字符数据 逻辑数据 图画 声音和活动图像数据等 2020年2月14日 第6页 2 1数据 信息和媒体 2 4 信息 对人有用的数据 这些数据可能影响到人们的行为和决策 信息处理 通过数据的采集和输入 有效地把数据组织到计算机中 由计算机系统对数据进行相应的处理加工 如 存储 建库 转换 合并 分类 计算 统计 汇总 传送等操作 最后向人们提供有用的信息的全过程 2020年2月14日 第7页 2 1数据 信息和媒体 3 4 媒体 承载信息的载体 与计算机信息处理有关的媒体 感觉媒体 能使人听觉 视觉 嗅觉 味觉和触觉器官直接产生感觉的一类媒体 如声音 文字 图画 气味等 它们是人类使用信息的有效形式 表示媒体 为了使计算机有效地加工 处理 传输感觉媒体而在计算机内部采用的特殊表示形式 即声 文 图 活动图像的二进制编码表示 存储媒体 用于存放表示媒体以便计算机随时加工处理的物理实体 如磁盘 光盘 半导体存储器等 表现媒体 用于把感觉媒体转换成表示媒体进而转换为感觉媒体的物理设备 如计算机的输入 输出设备传输媒体 用来将表示媒体从一台计算机传递到另一台计算机的通信载体 如同轴电缆 光纤 电话线等 2020年2月14日 第8页 2 1数据 信息和媒体 4 4 数字化编码 用少量最简单的基本符号 对大量复杂多样的信息进行一定规律的组合 一切信息编码的两大要素基本符号的种类组合规则 2020年2月14日 第9页 计算机内部采用的二进制表示方式的原因 1 二进制只有两个数码 0 和 1 易于用物理器件表示 这些物理状态都是不同的质的变化 形象鲜明 易于区别 并且数的存储 传送和处理可靠性高 2 运算规则简单 操作实现容易3 二进制加 减 乘 除运算 可以归结为加 减 移位三种操作 4 理论和实践证明 采用R e 2 71828进制时 存储设备最省 取3比取2更节省设备 但二进制比三进制易于表示5 二进制中的 1 和 0 与逻辑命题中的 真 假 相对应 为计算机实现逻辑运算和程序中的逻辑判断创造了良好条件 2020年2月14日 第10页 2 2进位计数制 2 2 1进位基数和位的权数2 2 2二进制数制2 2 3八进制数制2 2 4十六进制数制2 2 5数制之间的相互转换 2020年2月14日 第11页 2 2 1进位基数和位的权数 基数 计数制中用到的数码的个数 用R表示 位权 以基数为底的指数 指数的幂是数位的序号 对一个数S 其基数为R 则 2020年2月14日 第12页 计算机常用各种进制数的表示 2020年2月14日 第13页 2 2 5数制之间的相互转换 二 八 十六进制数转换为十进制数十进制数转换为二 八 十六进制数十进制数转换为二进制十进制数转换为八进制 十六进制数二进制数和八进制数 十六进制数的转换二进制数转换为八 十六进制数八 十六进制数转换为二进制数 2020年2月14日 第14页 二 八 十六进制数转换为十进制数 1 2 例2 1将 11011 11 2转换为十进制数解 11011 11 2 1 24 1 23 0 22 1 21 1 20 1 2 1 1 2 2 27 75 10 2020年2月14日 第15页 二 八 十六进制数转换为十进制数 2 2 例2 2将 732 6 8转换为十进制数解 732 6 8 7 82 3 81 2 80 6 8 1 474 75 10例2 3将 A5C B2 16转换为十进制数解 A5C B2 16 10 162 5 161 12 160 11 16 1 2 16 2 2652 6953125 10 2020年2月14日 第16页 十进制转换为二进制数 1 3 任一十进制数N N N整 N小 将这两部分分开转换 整数部分的转换 采用 除2求余法 转换方法为 连续用2除 求得余数 1或0 分别为K0 K1 K2 直到商为0 所有余数排列Kn 1Kn 2 K2K1K0即为所转换的二进制整数部分 小数部分的转换 采用 乘2取整法 转换方法为 连续用2乘 依次求得各整数位 0或1 K 1 K 2 K m 直到乘积的小数部分为0 在小数转换过程中 出现Fi恒不为0时 可按精度要求确定二进制小数的位数 2020年2月14日 第17页 十进制转换为二进制数 2 3 例2 4求 43 10的二进制表示解 除以2商Qi余数Ki43 221K0 121 210K1 110 25K2 05 22K3 12 21K4 01 20K5 1 43 10 101011 2 2020年2月14日 第18页 十进制转换为二进制数 3 3 例2 5求 0 6875 20的二进制值解 乘以2小数Fi整数Ki0 6875 20 3750K 1 10 3750 20 7500K 2 00 7500 20 5000K 3 10 5000 20 0000K 4 1 0 6875 10 0 1011 2 2020年2月14日 第19页 十进制数转换为八进制数 十六进制数 将十进制数转换为八进制数 十六进制数时 使用的方法与十进制数转换成二进制数的方法基本相同 只是求整数部分时是用商除以8或16 取其余数 小数部分改用乘以8或16 取其整数即可 2020年2月14日 第20页 二进制数与八进制 十六进制数间的转换 二进制转化成八 十六 进制整数部分 从右向左按三 四 位分组 不足补零小数部分 从左向右按三 四 位分组 不足补零 例2 9 001011010110 101011100 2 1326 534 81326534例2 10 01011101 01011010 2 5D 5A 165D5A 2020年2月14日 第21页 八进制 十六进制数与二进制数间的转换 八 十六 进制转化成二进制一位八进制数对应三位二进制数一位十六进制数对应四位二进制数例2 11 247 63 8 010100111 110011 2例2 12 F5A 6B 16 1111010110100110 01101011 2 2020年2月14日 第22页 2 3定点数和浮点数 数据的表示定点表示法浮点表示法任何一个二进制数N都可以表示为N 2E S其中E是一个二进制整数 称为数N的阶码 2为阶码的基数 S是二进制小数 称为数N的尾数 E和S可正可负 尾数S表示数N的全部有效数据 阶码E指明该数的小数点位置 表示数据的大小范围 2020年2月14日 第23页 2 3 1定点数表示法 阶码E保持不变若E 0 小数点固定在最高位之前 则该数是一个纯小数或定点小数 例如N 20 0 110101001 0 110101001若E n n为尾数的位数 则把小数点定在尾数最末位之后 表示一个纯整数 定点整数 例如N 27 0 1011010 01011010 2020年2月14日 第24页 2 3 2浮点数的表示 浮点数的格式阶码位数m与尾数位数n之间有如下关系 2m 1 n即表示阶码的值应保证实际的小数点可以在整个尾数的位格中移动 2020年2月14日 第25页 2 3 2浮点数的表示 规格化浮点数所谓浮点数的规格化 就是通过移动尾数 使尾数S的最高位数字为1 即S满足1 2 S 1时 这个浮点数就是规格化的数 否则就不是 在字长一定的情况下 规格化的浮点数精度最高 2020年2月14日 第26页 2 3 3定点数表示法和浮点数表示法的比较 表示的数据范围不同定点表示法 8位小数 能表示的数据范围 0 0000001 0 1111111 2 7 1 2 7 浮点表示法 2位阶码 1位阶符 4位尾数 1位尾符 能表示的范围 0 0001 2 11 0 1111 211溢出情况不同定点表示法 小数 带符号n 1位数时 小于2 n时 当0 大于1 2 n时 溢出 停机 浮点表示法 规格化后 从阶码上分析溢出 阶码很小时 下溢 当0 阶码超出最大值时 上溢 停机 运算规则的复杂性不同定点数 较简单 浮点数 较复杂 精度不同 规格化浮点数的精度远远大于定点数 2020年2月14日 第27页 2 3 4计算机中数的表示单位和机器字长 数的表示单位 位 Bit 表示数的最基本单位 对二进制只有 0 和 1 字节 Byte 8位二进制数字 Word 机器字长 参加运算的寄存器所含的二进制位数 代表机器的精度固定长度可变字长 2020年2月14日 第28页 2 4带符号数的表示 一个数的表示方法 是它们在计算机中的组成格式和编码规则 当一个数送入计算机进行运算处理时 首先将其转换为二进制数 同时还要解决以下几个问题 1 怎样表示数的符号2 怎样确定小数点的位置 2020年2月14日 第29页 2 4 1机器数的原码表示 1 3 规则 机器数的最高一位表示符号 0 表示正号 1 表示负号 后面各位用数的绝对值表示 整数原码的定义为 X 原为机器数的原码 X为真值 n为整数的位数 例2 13 求X 1011和Y 1011的原码解 X 1011时 原 01011Y 1011时 Y 原 24 1011 11011 2020年2月14日 第30页 2 4 1机器数的原码表示 2 3 小数原码的定义为 X 原为机器数的原码 X为真值 例2 14 求X 0 1011和Y 0 1011的原码解 X 0 1011时 原 0 1011Y 0 1011时 Y 原 1 0 1011 1 1011 2020年2月14日 第31页 2 4 1机器数的原码表示 3 3 性质 原码最高位表示数的符号 0表示正号 1表示负号 对定点小数 有 0不唯一定点小数 0 原 0 0 0 0 原 1 0 0整数 0 原 00 0 0 原 10 0 2020年2月14日 第32页 2 4 2机器数的补码表示 1 8 整数的补码 X 补为整数X的补码 X为任意整数 n为整数的位数 小数的补码 X 补是小数X的补码 X为任意小数 2为模数 2020年2月14日 第33页 2 4 2机器数的补码表示 2 8 例2 15求正整数X 1011和负整数Y 1011的补码解 X 补 01011 Y 补 2n 1 X 24 1 X 100000 1011 10101例2 16求正小数X 0 1011和负小数Y 0 1011的补码解 X 补 0 1011 Y 补 2 X 2 0 1011 1 0101 2020年2月14日 第34页 2 4 2机器数的补码表示 3 8 性质0的补码唯一整数0 0 补 00 0 0 补 2n 1 00 0 2n 1 00 0 mod2n 1 小数0 0 补 0 00 0 0 补 2 0 00 0 2 0 00 0 mod2 设 X 补 XSXn 1Xn 2 X1X0 XS是补码的符号位 标志整数X的符号 XS 0时 X为正数 XS 1时 X为负数 补码的表示范围是 正整数2n X 0负整数0 X 2n整数X的补码可以写成 X 补 2n 1 XS X 2020年2月14日 第35页 性质整数的补码与真值之间的关系补码与真值的关系设 X 补 XSXn 1Xn 2 X1X0 X 补 2n 1 XS X 可以证明 X X 补 2n 1 XS 2n Xs Xn 1Xn 2 X1X0补码的一项算术运算特性 X 2 补是把 X 补中各位连同符号位一起都右移一位 符号位保持不变 2 4 2机器数的补码表示 4 8 2020年2月14日 第36页 2 4 2机器数的补码表示 5 8 补码的求法当0 X 2n时 数X的补码是 符号位为1 数值位是其真值X的数值位取反加1 也可由X的原码 X 原求得补码 X 补 X 补等于 X 原除符号位外求反加1 反过来可由X的补码 X 补求得原码 X 原 X 原等于 X 补除符号位外求反加1 当X为小数时 若X为负数 则X的补码是 符号位为1 数值位是其真值X的数值位取反末位加1 也可由X的原码 X 原求得补码 X 补 X 补等于 X 原除符号位外求反末位加1 反过来可由X的补码 X 补求得原码 X 原 X 原等于 X 补除符号位外求反末位加1 2020年2月14日 第37页 2 4 2机器数的补码表示 6 8 由 X 补求 X 补 X Y 补 X 补 Y 补 X Y 补 X 补 Y 补假设 X 补 XSXn 1Xn 2 X1X0 可由 X 补按下式求得 X 补把对 X 补连同符号位在内的各位求反运算称为对 X 补 求反 运算 记为 X 补 这样对 X 补的 求补 运算可看成对 X 补 求反 运算再加1 X 补 X 补 1 且两者有以下关系 X 补 X 补 2n 1 1 11 1 n个1 2020年2月14日 第38页 2 4 2机器数的补码表示 7 8 变形补码小数 模4补码 的定义为 或 X 补 X mod4 1 当 1 X 1时 数X的 模4补码 的两个符号位相同 00表示正号 11表示负号 其数值位与补码相同 当符号位为01或10时 表示数值溢出 为01时表示两正数之和大于等于1的情况 称为数值 上溢 为10时表示两负数之和小于等于 1的情况 称为数值 下溢 2 模4补码 表示中 0有唯一的补码 根据 模4补码 的性质1 可以判断数的溢出 两个同符号数相加时 有可能出现溢出 2020年2月14日 第39页 2 4 2机器数的补码表示 8 8 补码的符号位扩展若 X 补 XSXn 1Xn 2 X1X0为8位 需要扩展为16位时 要按下面的规则进行扩展 用符号位XS填满扩展的高8位 若X 0 XS 0 扩展后高8位全为0 低8位包括符号位仍为原来的数码位 若X 0 XS 1 扩展后高8位全为1 低8位包括符号位仍为原来的数码位 2020年2月14日 第40页 2 4 3机器的反码表示 1 3 定义 整数反码的数学定义为 或 X 反 X mod2n 1 1 例2 20X 1011 则 X 反 01011 1011 则 反 25 1 X 10100 2020年2月14日 第41页 2 4 3机器的反码表示 2 3 定义 小数反码的数学定义为 或 X 反 X mod2 2 n 2020年2月14日 第42页 2 4 3机器的反码表示 3 3 性质 1 0的反码不唯一 整数0 0 反 00 0 0 反 2n 1 1 00 0 11 1 mod2n 1 1 小数0 0 反 0 00 0 0 反 2 2 n 0 00 0 1 1 1 mod2 2 n 2 设整数X的反码表示为 X 反 XSXn 1Xn 2 X1X0 XS是反码的符号位 它标志整数X的符号 XS 0时 X为正数 XS 1时 X为负数 3 反码与补码的关系根据补码和反码的定义 当X为正数时 X 补 X 反 当X为负整数时 X 补 X 反 1 当X为n位负小数时 X 补 X 反 2 n 2020年2月14日 第43页 2 4 4机器数的移 增 码表示法 1 2 定义 设阶码为n位整数 X 移 2n X2n X 2n即无论X是正还是负 一律加上2n 称2n为基数 移码与补码的关系 真值是正数时 移码是补码的最高位加1 真值是负数时 移码是补码的最高位减1 即若 X 补 XSXn 1Xn 2 X1X0 则 X 移 Xn 1Xn 2 X1X0例2 21X 1001 X 补 01001 可求得 X 移 11001X 1001 X 补 10111 可求得 X 移 00111 2020年2月14日 第44页 2 4 4机器数的移 增 码表示法 2 2 性质 1 0的移码唯一 整数0 0 移 2n 00 0 100 0 0 移 2n 00 0 100 0 2 机器0的形式为00 0 它表示的真值是 X 移所能表示的最小的数 3 移码的最高位是符号位 但表示的意义与原码和补码的意义相反 符号为0时 表示负数 符号为1 表示正数 4 移码一般只进行加减运算 运算后需要对结果进行修正 修正量为2n 即要对结果的符号位取反后 才能得到移码形式的结果 5 通过比较两个移码的大小 可得知其对应的真值大小 2020年2月14日 第45页 2 4 5各种编码的比较 相同点 1 三种编码 原码 反码 补码 的最高位都是符号位 2 当真值为正时 三种编码的符号位都用0表示 数值部分与真值相同 即它们的表示方法是相同的 3 当真值为负时 三种编码的符号位都用1表示 但数值部分的表示各不相同 数值部分存在这样的关系 补码是原码的 求反加1 整数 或者 求反末位加1 小数 反码是原码的 每位求反 4 它们所能表示的数据范围基本一样 2n X 2n 整数 或 1 X 1 小数 补码多表示一个数 2n 整数 或 1 小数 区别 在于对负数的表示方法有所不同 2020年2月14日 第46页 2 5十进制数据表示 人们习惯于用十进制表示数据 而计算机则采用二进制表示和处理数据 所以向计算机输入数据时 需要进行十进制数到二进制数的转换 输出数据时 则要进行二进制数到十进制数的转换处理 在数据量较小的情况下 这样的转换对机器运行效率的影响不是很大 但是 在某些应用领域 运算简单而数据量很大 进行这些转换所占用的时间比例比较大 所以为了提高机器的运行效率 计算机可以用十进制来表示和处理数据 一个十进制数位是用若干位二进制编码表示 用四位二进制代码的不同组合来表示一个十进制数码的编码方法 称为二 十进制编码 也称BCD码 BinaryCodedDecimal 常用这种编码作为十进制数转换成二进制数的中间过渡 即先将一个十进制数用BCD码来表示 再把它们送入机器 计算机通过标准子程序使其转换成纯二进制数 2020年2月14日 第47页 2 5 1二 十进制编码原理 1 二 十进制的编码都采用压缩的十进制串的方法 即四个二进制位的值来表示一个十进制数码 2 各种编码的区别在于选用哪十个状态 选择的原则是 要考虑输入和输出时转换方便 内部运算时 加 减运算规则要尽量简单 在特定场合 可能有其它一些要求 3 从每个二进制位是否有确定的位权区分 可把二 十进制编码分为有权码和无权码 2020年2月14日 第48页 2 5 2二 十进制有权码 1 2 对于有权码 将每位的数码与相应的位权相乘 再求和 就可以得到它所代表的十进制数值 8421码实现加 减运算时的修正规则 1 4位一组二进制数 两个8421码表示的数相加之和等于或小于1001 即十进制的9时 不需要修正 在各组内 二进制代码相加 仍遵循 逢二进一 的规则 2 4位一组二进制数 两个8421码相加结果大于1001 即十进制9 时 则应该对该组的4位进行 加6修正 使它向高一组产生进位 3 4位一组二进制数 两个8421码相加结果大于或等于10000 即十进制16 而向高一组进位时 则应该对该4位进行 加6修正 2020年2月14日 第49页 2 5 2二 十进制有权码 2 2 编码方法 8421码 2421码 5211码 4311码和84 2 1码 四位二进制位的位权分别为8 4 2 1 等 其最方便使用的共同特点为 1 对于2421码 5211码 4311码 任何两个十进制数位 采用这三种编码的任何一种编码 它们相加之和等于或大于10时 其结果的最高位向左产生进位 小于10时则不产生进位 这一特点有利于实现 逢十进位 的计数和加法规则 2 对于2421码 5211码 4311码和84 2 1码 任何两个十进制数位 采用这四种编码的任何一种编码 它们相加其和等于9时 即它们的二进制编码位互为反码 则其结果的四个二进制位一定是1111 能较好地体现十进制的按9取补与二进制的按1取补的对应关系 这对减法很有用 2020年2月14日 第50页 2 5 3二 十进制无权码 1 2 无权码中 用的较多的是余3码 Excess 3code 和格雷码 Graycode 格雷码又称循环码 1 余3码 1 余3码是在8421码的基础上 把每个代码都加上0011而形成的 2 普通8421码的加法器仍能为余3码加法器直接利用 具体规则如下 A 若两个十进制数的余3码相加 如果结果不产生进位 则从所得和值去减0011 便得十进制位和的余3码 B 若两个十进制数的余3码相加 如果结果有进位 则其进位正确 但需将所得和值加上0011 才求得十进制数和的余3码 2020年2月14日 第51页 2 5 3二 十进制无权码 2 2 2 格雷码 1 格雷码的编码规则是使相邻的两个代码 只有一个二进制位的状态不同 其余三个二进制位必须有相同状态 2 优点 从一个编码变到下一个相邻编码时 只有一个位的状态发生变化 有利于保证代码变换的连续性 在模拟 数字转换和产生节拍电位等应用场合特别有用 2020年2月14日 第52页 2020年2月14日 第53页 2 6字符编码 2 6 1ASCII码2 6 2EBCDIC码 2020年2月14日 第54页 2 6 1ASCII码 美国标准信息交换代码 AmericanStandardCodeforInformationInterchange 简称ASCII码 7位二进制编码 可表示27 128个字符 ASCII码中 编码值0 31不对应任何可印刷 或称有字形 字符 通常称它们为控制字符 用于通信中的通信控制或对计算机设备的功能控制 编码值为32的是空格 或间隔 字符SP 编码值为127的是删除控制DEL码 其余的94个字符称为可印刷字符 2020年2月14日 第55页 2 6 2EBCDIC码 EBCDIC码 ExtendedBinaryCodedDecimalInterchangeCode 扩展BCD码 是8位二进制编码 可以表示256个编码状态 但只选用其中一部分 主要用在IBM公司生产的各种机器中 2020年2月14日 第56页 2 6 3汉字的表示 特点 1 汉字是一种象形文字 据统计 从甲骨文至今约有六万左右的汉字 目前常见的汉字有约七千个 2 汉字字形结构复杂 笔划繁多 3 汉字同音字多 多音字多 涉及多种编码 汉字编码输入方案可以归纳为四类 即数字编码 如区位码 字音编码 如拼音码 字形编码 如五笔字型 汉字混合编码等 1981年我国制定了 信息交换用汉字编码字符集基本集GB2312 80 国家标准 每个二进制编码用两个字节表示 共收录一级汉字3755个 二级汉字3008个 各种符号682个 共计7445个 2020年2月14日 第57页 2 7数据校验码 2 7 1奇偶校验码2 7 2海明校验码2 7 3循环冗余校验码 2020年2月14日 第58页 2 7数据校验码 1 数据校验的实现原理 数据校验码是在合法的数据编码之间 加进一些不允许出现的 非法的 编码 使合法的数据编码出现错误时成为非法编码 这样就可以通过检测编码的合法性达到发现错误的目的 2 码距 指任何一种编码的任两组二进制代码中 其对应位置的代码最少有几个二进制位不相同 2020年2月14日 第59页 2 7 1奇偶校验码 1 码距 22 奇偶校验码 它是在被传送的n位信息组上 加上一个二进制位作为校验位 使配置后的n 1位二进制代码中1的个数为奇数 奇校验 或偶数 偶校验 例 数据奇校验编码偶校验编码0000000010000000000000000001110101001110101101110101其中 最高一位为校验位 其余低八位为数据位 3 奇偶校验码只能检测出数据代码中一位出错的情况 但无法判断差错所发生的位置 常用于存储器读写检查 或ASCII字符传送过程中的检查 2020年2月14日 第60页 2 7 2海明校验码 1 8 1 原理在数据位中加入几个校验位 将数据代码的码距均匀地拉大 并把数据的每个二进制位分配在几个奇偶校验组中 当某一位出错后 就会引起有关的几个校验位的值发生变化 不但可以发现错误 还能指出是哪一位出错 为进一步自动纠错提供依据 2 编码规则若海明码最高位号为m 最低位号为1 即HmHm 1 H2H1 则海明码的编码规则是 1 校验位与数据位之和为m 每个校验位Pi在海明码中被分在位号2i 1的位置上 其余各位为数据位 并按从低向高逐位依次排列的关系分配各数据位 2 海明码的每一位位码Hi 包括数据位和校验位 由多个校验位校验 其关系是被校验的每一位位号要等于校验它的各校验位的位号之和 2020年2月14日 第61页 2 7 2海明校验码 2 8 3 增添校验位假设欲检测的有效信息为n位 需增加的校验位为k位 则校验码的长度为n k位 校验位的状态组合 应当具有指出n k位中任一位有错或无错的能力 即需要区别出n k 1种状态 应满足以下关系式 2k n k 1这个关系式称为海明不等式 若信息位长度n确定后 由此可得到校验位k的最短长度 确定校验位后 就可以与信息位组成海明校验位 假设数据位是7位二进制编码 据上所述 校验位的位数k为4 故海明码的总位数为11 它们的排列关系可表示为 海明码位号 H11H10H9H8H7H6H5H4H3H2H1海明码 D7D6D5P4D4D3D2P3D1P2P1可知 每个校验位由其本身校验 每个数据位由若干校验位校验 2020年2月14日 第62页 2 7 2海明校验码 3 8 4 校验位校验任务的分配 根据海明码的编码规则 每一位海明码都有多个校验位 且被校验的每一位的位号等于参与校验的几个校验位的位号之和 占据各权位上的校验位按权组成的8421码 正好等于海明码的位号 即海明码的位号Hi正好等于要校验它的校验位所占权位权值之和 例如 H11 P4 23 P2 22 P1 21这说明了H11位将由P4 P2 P1进行校验 校验位P1可以校验 H1 H3 H5 H7 H9 H11 H13 H15校验位P2可以校验 H2 H3 H6 H7 H10 H11 H14 H15校验位P3可以校验 H4 H5 H6 H7 H12 H13 H14 H15校验位P4可以校验 H8 H9 H10 H11 H12 H13 H14 H15根据校验时采用奇校验或偶校验 可以写出相应的校验方程 2020年2月14日 第63页 2 7 2海明校验码 4 8 例2 23设有一个7位信息码位0110001 求它的海明码 解 n 7 根据海明不等式 可求得校验位最短长度k 4 其海明码先表示如下 海明码位号 H11H10H9H8H7H6H5H4H3H2H1海明码 011P4000P31P2P1按偶校验写出校验方程为 H1 H3 H5 H7 H9 H11 0 P1 H1 H2 H3 H6 H7 H10 H11 0 P2 H2 H4 H5 H6 H7 0 P3 H4 H8 H9 H10 H11 0 P4 H8 由此可得 P1 0 P2 0 P3 0 P4 0 所以0110001的海明码为01100000100 2020年2月14日 第64页 2 7 2海明校验码 5 8 5 检错与纠错方法 将错了的码字重新代入校验方程校验一次即可 假设上面例子中的海明码01100000100传送后 若H6位发生了错误 变成了01100100100 这时把它们代入上面的偶校验校验方程 如下 H1 H3 H5 H7 H9 H11 0 1 0 0 1 0 0 E1H2 H3 H6 H7 H10 H11 0 1 1 0 1 0 1 E2H4 H5 H6 H7 0 0 1 0 1 E3H8 H9 H10 H11 0 1 1 0 0 E4可以把E4E3E2E1 0110看成一个 指误字 因为其二进制码为0110 说明H6出了错 是H6错成了1 所以要纠错 纠错时将H6位取反值 即让它恢复到正确值0 这样纠错后 即可得到正确的海明码01100000100 2020年2月14日 第65页 2 7 2海明校验码 6 8 6 讨论 设有效信息位n 4位 则根据海明不等式 可求得校验位最短长度k 3 则 海明码位号 H7H6H5H4H3H2H1海明码 D4D3D2P3D1P2P1可以得到 P1参与D1 D2 D4的校验 P2参与D1 D3 D4的校验 P3参与D2 D3 D4的校验 若采用偶校验 则 P1 D1 D2 D4P2 D1 D3 D4P3 D2 D3 D4上述编码中 两个正确码之间若有一位有效信息不同 则由于该位至少参加两组的奇偶校验 故至少会影响到两位校验位的不同 所以这种码距 3 可以检测两位错 或检测并纠正一位错 2020年2月14日 第66页 2 7 2海明校验码 7 8 若按下述关系对所得的海明码进行偶校验 S1 P1 D1 D2 D4S2 P2 D1 D3 D4S3 P3 D2 D3 D4则S3S2S1可以反映出错情况 1 若S3S2S1 000 无错 2 若欲传的海明码 0101101 收到0111101 则S1 P1 D1 D2 D4 1 1 1 0 1 S2 0 S3 1表明第5位 D2 出错 3 若欲传的海明码 0101101 收到0110101 则S1 1 S2 0 S3 0表明有错 但无法判断是第1位出错 还是4 5位同时出错 上述编码不能把两位出错和一位出错区分开来 2020年2月14日 第67页 2 7 2海明校验码 8 8 7 改进 增加一个校验位S4 P4 P1 P2 P3 D1 D2 D3 D4P4 P1 P2 P3 D1 D2 D3 D4 1 S4 0 S3S2S1 000 无错 2 S4 0 S3S2S1 0 表明有两位出错 3 S4 1 S3S2S1 0 可根据S3S2S1指出的值纠正一位错 在这种情况下 因多增加一位校验位 则前面的海明不等式改为 2k 1 n k称为扩展海明码 其码距 4 可发现两位错并纠正一位错 2020年2月14日 第68页 2 7 3循环冗余校验码 1 7 1 CRC的编码方法n是有效数据信息位位数 r是校验位位数 总长k n r位 称 k n 码 设待编码的有效信息以多项式M x 表示 将M x 左移r位得到多项式M x Xr 使低r位二进制位全为零 以便与r位校验位拼接 使用多项式M x Xr除以生成多项式G x 求得的余数即为校验位 为了得到r位余数 校验位 G X 必须是r 1位的 2020年2月14日 第69页 2 7 3循环冗余校验码 2 7 假设M x Xr除以生成多项式G x 求得的余数用表达式R x 表示 商的表达式用Q x 表示 它们之间的关系如下 这时将r位余数R X 与左移r位的M x Xr相加 就得到n r位的CRC编码 M x Xr R x Q