校验码最终版.ppt

检错纠错码 数据在计算机系统内形成 存取和传送的过程中难免会产生错误 为减少和避免这类错误 一方面是精心设计各种电路 提高计算机硬件的可靠性 另一方面是在数据编码上找出路 即采用一点冗余的线路 在原有数据位之外再增加一到几位校验位 使新得到的码字带上某种特性 之后则通过检查该码字是否仍保持有这一特性 来发现是否出现了错误 甚至于定位错误后 自动改正这一错误 这就是我们这里说的检错纠错编码技术 数据校验码的实现原理 是在合法的数据编码之间 加入一些不允许出现的 非法的 编码 使合法数据编码出现某些错误时 就成为非法编码 码距 是指任意两个合法码之间至少有几个二进制位不相同 仅有一位不同 称其码距为1 例如用四位二进制表示16种状态 16种编码都用到了 此时码距为1 就是说 任何一个状态的四位码中的一位或几位出错 就变成了另一合法码 此时无查错能力 若用其中的8个状态编码 此时码距为2 一般来说 合理地增大合法码的码距 就能提高发现错误的能力 但表示一定数量的合法码所使用的二进制位数变多 增加了数据存储的容量或数据传输的数量 编码的纠错 检错能力与编码的最小距离有关 L 编码的最小距离 D 检测错误的位数 C 纠正错误的位数 几种常用的检错纠错码 我们只介绍三种常用的检错纠错码 奇偶检错码 用于并行数据传送中海明检错与纠错码 用于并行数据传送中循环冗余码 用于串行数据传送中 编码过程 译码过程 原始数据 码字 数据 校验 结果数据 形成校验位的值 加进特征 检查接收的码字 发现 改正错误 传送主存读 写 奇偶校验码 用于并行码检错原理 在k位数据码之外增加1位校验位 使K 1位码字中取值为1的位数总保持为偶数 偶校验 或奇数 奇校验 例如 0001100010000101010010110101 偶校验 奇校验 校验位 原有数字位两个新的码字 奇偶校验码的实现电路 奇较验偶校验偶校验出错指示 同左侧电路 编码电路 译码电路 P 校验位 八位数据位 D7D6D5D4D3D2D1D0 p 奇偶校验码常用于 存储器读写检查 ASCII字符 其他类型信息传送过程中的出错检查 缺点 只能发现有无差错 而不能确定发生差错的位置 只能发现奇数个二进位错 不能发现偶数个二进制错 海明校验码 用于多位并行数据检错纠错处理实现 为k个数据位设立r个校验位 使k r位的码字同时具有这样两个特性 1 能发现并改正k r位中任何一位出错 2 能发现k r位中任何二位同时出错 但已无法改正 要特性1成立 必须有如下关系 2r k r 1要特性1和2同时成立 k和r有如下关系 2r 1 k r 海明码的编码方法 合理地用k位数据位形成r个校验位的值 即保证用k个数据位中不同的数据位组合来形成每一个校验位的值 使任何一个数据位出错时 将影响r个校验位中不同的校验位组合起变化 换言之 通过检查是哪种校验位组合起了变化 就能确定是哪个数据位错 对该位求反则实现纠错 有时两位错与某种情况的一位错对校验位组合的影响相同 必须能区分一位或双位错 海明码的编码规律 假设海明码的最高位号为m 最低位号为1 即 HmHm 1 H2H1 1 校验位与数据位之和为m 每个校验位Pi在海明码中被分在位号2i 1的位置 其余各位为数据位 并按照从低到高逐位依次排列的关系分配各数据位 2 海明码的每一位码Hi 包括数据位和校验位本身 由多个校验位校验 其关系是被校验的每一位位号要等于校验它的各校验位的位号之和 这样安排的目的 是希望校验的结果能反映出出错位的位号 3 在增大合法码码距时 使所有码的码距尽量均匀的增大 以保证对所有码的检错能力平衡提高 用一个校验码和形成这个校验码的编码方程执行异或 又一次执行偶校验运算 通过检查五个S的结果 可以实现检错纠错的目的 偶数个数出错 S5一定为0 因此S5可区分两位错或一位出错 任何一位 含数据位 校验位 均不错 则S4 S1都应为0 S4 S1不全为0 说明有错 例如若为1100或1011 则分别表示H12或H11位错 由检验线路直接纠正 海明码常用于 大中型计算机存储器的校验 中科院98年试题 请写出数据10110100110的海明码 用4位校验位 采用偶校验 P1 D2 D1P2 D3 D1P3 D3 D2 海明码的实现方案 如何确定数据位和校验位的对应关系 例如 k 3 r 4 D3D2D1P4P3P2P11111111110010010100100110001 P4 P3 P2 P1 D3 D2 D1 S1 P1 D2 D1S2 P2 D3 D1S3 P3 D3 D2S4 P4 P3 P2 P1 D3 D2 D1 异或 编码方案 译码方案 海明码的实现方案 如何确定数据位和校验位的对应关系 例如 k 3 r 4 D3D2D1P4P3P2P1 1 排列好码字的每一位 3个数据位D3D2D14个校验位P4P3P2P12 在P4 P1列不同行写13 在P4 P1列其他处写04 看P4 P1列3位码的值04215 定D3 D1列3位码的值653 1 1 1 1 0 0 0 0 0 0 0 0 0 0421 653 写D3 D1列3位码的值在顶行各空闲位置写18 写P4 P1的编码表达式9 写S4 S1的编码表达式 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 P1 D2 D1P2 D3 D1P3 D3 D2 海明码的实现方案 如何确定数据位和校验位的对应关系 例如 k 3 r 4 D3D2D1P4P3P2P11111111110010010100100110001 P4 P3 P2 P1 D3 D2 D1 S1 P1 D2 D1S2 P2 D3 D1S3 P3 D3 D2S4 P4 P3 P2 P1 D3 D2 D1 异或 8 写编码表达式 9 写译码表达式 如何实现检错与纠错 D3D2D1P4P3P2P11111111110010010100100110001 S1 P1 D2 D1S2 P2 D3 D1S3 P3 D3 D2S4 P4 P3 P2 P1 D3 D2 D1 译码表达式 P4是总校验位 区别一位还是双位错 纠错 对比出错模式表S4 S1都是0 无错误S4 S1非全0 有错误 与哪一列同值 哪位错对出错数据位求反以纠正 S4 0 但S3 S1非全0表明是双位错 无法纠正 否则属于更多位同时错 循环冗余码 用于多位串行数据传送中的检错纠错处理 在k位数据位串行移位输出的过程中 用带有异或门控制的移位寄存器形成r个校验位的值 跟随在数据位之后传送走 在接收端再对k r位的码字进行合法与出错检查 若可能则自动改错 循环冗余码的实现原理 循环冗余码是在k位数据位串行移位输出过程中求出r个校验位的值 其数学原理用的是模2除 即对由k个数据位后跟r个取值为0的位构成的数 除以从数学表中查来的一个生成多项式 对应一个特定的r 1位的二进制数 求出的r位的余数就是校验位的结果 为了描述不断移位操作过程中的数据 引进伪变量X和它的的不同的幂 以表示一个二进制数取值为1的那些位的值 此时原来说的k位数据 k r位码字 r位的余数均可以用一元多项式表示 模2除时作除数用的二进制数也表现为多项式的形式 叫做生成多项式 CRC码工作原理 用多项式M x xr除以生成多项式 产生检验码的多项式 所得余数作为校验位 为了得到r位余数 校验位 G x 必须是r 1位 M x xr R x Q x G x R x R x Q x G x R x R x Q x G x 因此 所得CRC码可被G x 表示的数码除尽 模2除与移位寄存器 模2除类似于正常二进制除法 区别有两点 上商只看被除数的最高位 其值为1则上商1 其值为0则上商0 求余数用本位相减 上商为1时 求余数只用本位相减 位间无借位 模2除运算 可以用带有异或门控制的移位寄存器实现 不用加法电路 简单又速度快 且可与串行数据移位输出用同一电路 循环冗余码的实现的数学原理 10111100000010111011100000011100101111011 101 k 3数据为100r 4求出的校验值为1011100可写成X 2 为求四位校验位 可用X X X 1去模2除 4 2 X X X 1叫做生成多项式 由查表得到 4 2 码字为1001011 循环冗余码的实现电路 线性分组 7 3 码 即3位数据加4位校验查表得到生成多项式 G X X4 X2 X 1T4T3T2T1T0CP 1011100000 串行数据D 上商1上商0 循环冗余校验码常用于 磁介质存储和计算机之间通信方面 课堂练习 已知M x 100101 生成多项式G x x3 x 1 1 试计算CRC校验的校验位 写出M x 的校验码 2 说明CRC码校验出错的方法 检错纠错码小结 1 K位码有2K个编码状态 全用于表示合法码 则任何一位出错 均会变成另一个合法码 不具有检错能力 2 从一个合法码变成另一个合法码 只少要改变几位码的值 称为最小码距 码距 3 K 1位码 只用其2K个状态 可使码距为2 如果一个合法码中的一位错了 就成为非法码