12 错误检测和校正.ppt

16错误检测和校正 为什么要做错误检测与校正 光盘 磁盘和磁带一类的数据记录媒体一样 由于盘的制作材料的性能 盘制造生产技术水平的限制 驱动器的性能以及使用不当等诸多原因 从盘上读出的数据不可能完全正确 据有关厂家的测试和统计 一片未使用过的只读光盘 其原始误码率约为3 10 4 沾有指纹的盘的误码率约为6 10 4 有伤痕的盘的误码率约为5 10 3 采用的具体对策 激光盘存储器采用了功能强大的错误码检测和纠正措施 采用的具体对策归纳起来有三种 1 错误检测 采用CRC CyclicRedundancyCode 检测读出数据是否有错 2 错误校正码 采用里德 索洛蒙码 Reed SolomonCode 称为RS码 进行纠错 RS码被认为是性能很好的纠错码 3 交叉交插里德 索洛蒙码CIRC CrossInterleavedReed SolomonCode 这个码的含义可理解为在用RS编译码前后 对数据进行交插处理和交叉处理 检错与纠错的基本原理 检错与纠错是指允许在通信过程中产生错误的前提下 能有效的检测出错误并进行纠正 从而提高通信质量 检错与纠错统称为差错控制 差错控制的主要目的是为了减少传输中的错误 可采取两种方案 让每个传输的数据单元仅带有足以使接收端发现差错的冗余信息 但不能确定错误位置 因而不能纠正错误 只能发现错误 这是一种检错编码方案 让每个传输的数据单元带有足够的冗余信息 以便在接收端发现并自动纠正传输错误 这是一种纠错编码方案 性能参数 效率 效率定义编码效率R来度量有效性 R k n其中 k是信息元的个数 n为码长 性能参数 检错和纠错能力 检错和纠错能力两个等长码组之间相应位取值不同的数目称为这两个码组的码距 码组集中任意两个码字之间距离的最小值称为最小码距 用d0表示 最小码距d0直接关系着码的检错和纠错能力 任一 n k 分组码 若要在码字内 1 检测e个随机错误 则要求码的最小距离d0 e 1 2 纠正t个随机错误 则要求码的最小距离d0 2t 1 检错纠错码举例 奇偶校验码重复码等比码循环冗余校验 CRC 分组码 简单地说 分组码是对每段k位长的信息组以一定的规则增加r个监督元 组成长为n的码字 在二进制情况下 共有2k个不同的信息组 相应地可得到2k个不同的码字 称为许用码组 其余2n 2k个码字末被选用 称为禁用码组 分组码一般可用 n k 表示 其中 k是每组二进制信息码元的数目 n是编码码组的码元总位数 又称为码组长度 简称码长 n k r为每个码组中的监督码元数目 循环码 循环码是一类重要的分组码 之所以称为循环码 是因为其循环性 即循环码组中任一码字循环移位所得的码字仍为该码组中的一个码字 如 循环码的多项式描述 对于任一矢量都可用一个次数不超过n 1的多项式按下式 代码多项式 唯一确定 它们之间具有相同的物理意义 只是描述方式不同而已 多项式描述时的运算规则 模2运算加减乘除取模循环左移i位 生成多项式 定理 在一个 n k 循环码中 一定存在唯一的次数最低的n k次首一码多项式g x 使所有的码多项式都是g x 的倍数 即所有码字都可写成 若选作为生成多项式 则 7 3 码多项式为 依此将 000 111 代入 得到如下结果 系统循环码 所谓的系统循环码 要求码字的前k位原封不动地照搬信息位 而后面n k位为校验位 也就是说 希望码多项式具有如下形式 这里 r x 是与码字中n k个校验元相对应的n k 1位多项式 构成系统多项式的方法 1 将信息多项式m x 预乘xn k 即左移n k位2 将xn km x 除以g x 得余式r x 3 系统循环码多项式写成C x xn km x r x CRC码 举例 求m 011 的 7 3 系统循环码 其中生成多项式为 CRC检错 用同样的CRC码生成多项式去除码多项式数据 相除后得到的两种可能结果是 余数为0 表示读出没有出现错误 余数不为0 表示读出有错 CRC校验可以100 的检测出所有的奇数个随机错误和小于等于r g x 的阶数 的突发错误 所以CRC的生成多项式次数越高 误判的概率就越小 CRC生成多项式的一点说明 CRC生成多项式G x 的结构与检错效果是经过严格的数学分析和实验后确定的 有相应的国际标准 例如 软磁盘存储器中使用的CRC校验码生成多项式是CD ROM采用的CRC校验码生成多项式是一个32阶的多项式 CD ROM的EDC字域 计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节 即字节0 2063共2064个字节 在EDC中存放的CRC码的次序如下 RS 里德 索洛蒙 码 RS码是一种分组码 其码字分为k mbit为一组 每组包括k个符号 每个符号由mbit组成 而不是1bit 也就是说 在RS码中是以一个符号为单位处理的 RS码一般表示为 n k 或 n k m RS码的编码方法 已知生成多项式G x 求k个mbit的符号mk 1 m1 m0的 n k m RS码的编码步骤如下 构造信息码符多项式M x mk 1xk 1 m1x m0求剩余多项式R x Qr 1Xr 1 Q1x Q0 r n k 即的余数 如何用mbit符号作为M x 的系数 引入概念 假设每个符号有m个bit 则存在最高次数为m的多项式P x 本原多项式 这里我们不介绍什么叫本原多项式 因为这里牵扯到太多的数学问题 我们假设本原多项式是已知的 其本原元素为 为本原多项式的根 即P 0 则有 2m个符号都可以用 的幂来表示 同样这里我们也不介绍为什么 如果有兴趣的同学可以参阅近世代数相关理论 如何用mbit符号作为M x 的系数 mbit符号可用本原元素 的幂进行表示 方法如下 对元素 0 2 q 1 其中q 2m 2 分别求其模P 的值 得到的系数即为 i所对应的二进制代码 举例 如3bit符号的本原多项式为P x x3 x 1 其本原元为 则 对应的运算 生成多项式G X 的一般形式 对一个信息码符多项式 RS校验码生成多项式的一般形式为式中 K0是偏移量 通常取K0 0或K0 1 而K n k 2t t为要校正的错误符号数 举例 求 6 4 3 RS码 假设已知m3 001m2 101m1 011m0 100本原多项式已知为P x x3 x 1 RS码纠错算法 RS码的错误纠正过程分三步 1 计算校正子 syndrome 2 计算错误位置 3 计算错误值 参见书本P299 举例 16 3CIRC纠错技术 光盘存储器和其它的存储器一样 经常遇到的错误有两种 一种是由于随机干扰造成的错误 这种错误称随机错误 它的特点是随机的 孤立的 干扰过后再读一次光盘 错误就可能消失 另一种错误是连续多位出错 或连续多个符号出错 如盘片的划伤 沾污或盘本身的缺陷都可能出现这种错误 一错就错一大片 这种错误称为突发错误 CIRC CrossInterleavedReedSolomon 纠错码综合了交插 延时交插 交叉交插等技术 不仅能纠随机错误 而且对纠突发错误特别有效 16 3 1交插技术 同样多的错误 人们更容易纠正分散的错误 例如 用X表示出现的错字 一种错误形式为 掩XXX 雪中送炭 鸡犬不宁 这是连续出现的错误 另一种错误形式为 掩X盗铃 雪中X炭 鸡犬不X 这是分散出现的错误 这两种错误形式相比 同样是3个错误 但人们更容易更正后一种形式的错误 这个道理很简单 把这种思想用在数字记录系统中对突发错误的更正非常有效 在光盘上记录数据时 如果把本该连续存放的数据错开放 那么当出现一片错误时 这些错误就分散到各处 错误就容易得到纠正 这种技术就称为交插 interleaving 技术 举例 3个 5 3 码块 B1 a2 a1 a0 P1 P0 B2 b2 b1 b0 Q1 Q0 B3 c2 c1 c0 R1 R0 交插排列 a2b2c2a1b1c1a0b0c0P1Q1R1P0Q0R0连续错3个 a2b2c2a1b1c1a0XXXQ1R1P0Q0R0读出后重新排列 a2a1a0XP0b2b1XQ1Q0c2c1XR1R0 从这个例子中可以看到 对连续排列 每个码块中只能出现一个错误才能纠正 而交插记录后 读出的3个连续错误经还原后可把它们分散到3个码块中 每个码块可以纠正1个错误 总计可以纠正3个连续的错误 一般来说 如果有r个 n k 码 排成r n矩阵 按列交插后存储或传送 读出或接收时恢复成原来的排列 若 n k 码能纠正t个错误 那么这样交插后就可以纠正rt个突发错误 16 3 2交叉交插技术 交叉交插 cross interleaving 编码是交插的一种变型 在实际应用中 也是一种重要的技术 现仍以简单的例子说明这种技术思想 例子见书本P300 CIRC首先应用在激光唱盘系统中 音频信号的采样率为44 1kHz 而每次采样有两个16比特的样本 一个来自左声道 一个来自右声道 每个样本用两个8bit的符号表示 因此每次采样共有4个符号 为了纠正可能出现的错误 每6次采样共24个符号构成1帧 称为F1帧 F1 Frame 用一个称为C2的编码器对这24个符号产生4个Q校验符号 Q0 Q1 Q2和Q3 24个声音数据加上4个Q校验符号共28个符号 用称为C1编码器对这28个符号产生4个P校验符号 P0 P1 P2和P3 28个符号加上4个P校验符号共32个符号构成的帧称为F2帧 F2 Frame F2帧加上1个字节 即1个符号 的子码共33个符号构成的帧称为F3帧 F3 Frame 16 4里德 索洛蒙盛积码 RSPC 按ISO IEC10149的规定 CD ROM扇区中的ECC码采用RSPC码产生172个字节的P校验符号和104个字节的Q校验符号 RS码采用本原多项式和本原元 00000010 编码步骤 步骤 1 CD ROM的每个扇区中从字节12开始到字节2075共2064个字节组成