错误检测和校正课件

《错误检测和校正课件》由会员分享，可在线阅读，更多相关《错误检测和校正课件（39页珍藏版）》请在装配图网上搜索。

1、错误检测和校正PPT课件16 错误检测和校正错误检测和校正错误检测和校正PPT课件为什么要做错误检测与校正为什么要做错误检测与校正l光盘、磁盘和磁带一类的数据记录媒体一样，由于盘的制作材料的性能、盘制造生产技术水平的限制、驱动器的性能以及使用不当等诸多原因，从盘上读出的数据不可能完全正确。据有关厂家的测试和统计，一片未使用过的只读光盘，其原始误码率约为310-4；沾有指纹的盘的误码率约为610-4；有伤痕的盘的误码率约为510-3。错误检测和校正PPT课件采用的具体对策采用的具体对策l激光盘存储器采用了功能强大的错误码检测和纠正措施。采用的具体对策归纳起来有三种：l(1)错误检测：采用CRC(

2、Cyclic Redundancy Code)检测读出数据是否有错。l(2)错误校正码：采用里德索洛蒙码(ReedSolomon Code)，称为RS码，进行纠错。RS码被认为是性能很好的纠错码。l(3)交叉交插里德索洛蒙码CIRC(Cross Interleaved ReedSolomon Code),这个码的含义可理解为在用RS编译码前后，对数据进行交插处理和交叉处理。错误检测和校正PPT课件检错与纠错的基本原理检错与纠错的基本原理l检错与纠错是指允许在通信过程中产生错误的前提下，能有效的检测出错误并进行纠正，从而提高通信质量。检错与纠错统称为差错控制。l差错控制的主要目的是为了减少传输中

3、的错误，可采取两种方案：l让每个传输的数据单元仅带有足以使接收端发现差错的冗余信息，但不能确定错误位置，因而不能纠正错误，只能发现错误，这是一种检错编码方案。l让每个传输的数据单元带有足够的冗余信息，以便在接收端发现并自动纠正传输错误，这是一种纠错编码方案。错误检测和校正PPT课件性能参数性能参数-效率效率l效率l定义编码效率R来度量有效性：l Rk/nl其中，k是信息元的个数，n为码长。错误检测和校正PPT课件性能参数性能参数-检错和纠错能力检错和纠错能力l检错和纠错能力l两个等长码组之间相应位取值不同的数目称为这两个码组的码距。码组集中任意两个码字之间距离的最小值称为最小码距，用d0表示。

4、l最小码距d0直接关系着码的检错和纠错能力，任一(n，k)分组码，若要在码字内：l(1)检测e个随机错误，则要求码的最小距离d0=e+1；l(2)纠正t个随机错误，则要求码的最小距离d0=2t+1;错误检测和校正PPT课件检错纠错码举例检错纠错码举例l奇偶校验码l重复码l等比码l循环冗余校验（CRC）l.错误检测和校正PPT课件分组码分组码l简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字，在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字末被选用，称为禁用码组。l分组码一般可用(n，k)表示。其中，k是每

5、组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。错误检测和校正PPT课件循环码循环码l循环码是一类重要的分组码。l之所以称为循环码，是因为其循环性：即循环码组中任一码字循环移位所得的码字仍为该码组中的一个码字。l如：错误检测和校正PPT课件循环码的多项式描述循环码的多项式描述l对于任一矢量l都可用一个次数不超过n-1的多项式按下式（代码多项式）唯一确定：l它们之间具有相同的物理意义，只是描述方式不同而已121210().nnnnV xvxvxv xv1210(,.,)nnVvvv v错误检测和校正PPT课件多项式描述时的运算规则

6、多项式描述时的运算规则l模2运算l加l减l乘l除l取模l循环左移i位：()mod(1)inxV xx错误检测和校正PPT课件生成多项式生成多项式l定理：在一个(n,k)循环码中，一定存在唯一的次数最低的n-k次首一码多项式g(x):使所有的码多项式都是g(x)的倍数，即所有码字都可写成111().1n kn kn kg xxgxg x ()()()C xm x g x错误检测和校正PPT课件l若选 作为生成多项式，则（7，3）码多项式为：依此将(000).(111)代入，得到如下结果:432()1g xxxx2432210()()()()(1)C xm x g xm xm xmxxx错误检测和

7、校正PPT课件系统循环码系统循环码l所谓的系统循环码，要求码字的前k位原封不动地照搬信息位，而后面n-k位为校验位，也就是说，希望码多项式具有如下形式：l这里，r(x)是与码字中n-k个校验元相对应的n-k-1位多项式()()()n kC xxm xr x错误检测和校正PPT课件构成系统多项式的方法构成系统多项式的方法l1、将信息多项式m(x)预乘xn-k，即左移n-k位l2、将xn-k m(x)除以g(x)，得余式r(x)l3、系统循环码多项式写成C(x)=xn-k m(x)+r(x)错误检测和校正PPT课件CRC码码-举例举例l求m=（011）的（7，3）系统循环码，其中生成多项式为432

8、()1g xxxx错误检测和校正PPT课件CRC检错检错l用同样的CRC码生成多项式去除码多项式数据，相除后得到的两种可能结果是：l余数为0，表示读出没有出现错误；l余数不为0，表示读出有错。lCRC校验可以100%的检测出所有的奇数个随机错误和小于等于r（g(x)的阶数）的突发错误，所以CRC的生成多项式次数越高，误判的概率就越小错误检测和校正PPT课件CRC生成多项式的一点说明生成多项式的一点说明l CRC生成多项式G(x)的结构与检错效果是经过严格的数学分析和实验后确定的，有相应的国际标准，例如：l软磁盘存储器中使用的CRC校验码生成多项式是lCD-ROM采用的CRC校验码生成多项式是一

9、个32阶的多项式：16152162()(1)(1)P xxxxxxx16125()1G xxxx错误检测和校正PPT课件CD-ROM的的EDC字域字域l计算CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节02063共2064个字节。在EDC中存放的CRC码的次序如下：EDC：x24x31x16x23x8x15x0 x7字节号：2064206520662067错误检测和校正PPT课件RS（里德（里德-索洛蒙）码索洛蒙）码lRS码是一种分组码，其码字分为km bit为一组，每组包括k个符号，每个符号由m bit组成，而不是1bit，也就是说，在RS码中是以一个符号为单位处理

10、的。lRS码一般表示为（n，k）或（n，k，m）错误检测和校正PPT课件RS码的编码方法码的编码方法l已知生成多项式G（x），求k个mbit的符号mk-1,.m1,m0的（n，k，m）RS码的编码步骤如下：l构造信息码符多项式M(x)=mk-1xk-1+.+m1x+m0l求剩余多项式R(x)=Qr-1Xr-1+Q1x+Q0 (r=n-k)，即 的余数()()n kM x xG x错误检测和校正PPT课件如何用如何用mbit符号作为符号作为M(x)的系数的系数l引入概念：l假设每个符号有m个bit，则存在最高次数为m的多项式P(x)（本原多项式，这里我们不介绍什么叫本原多项式，因为这里牵扯到太多

11、的数学问题，我们假设本原多项式是已知的）。其本原元素为（为本原多项式的根，即P（）=0），则有：2m个符号都可以用的幂来表示（同样这里我们也不介绍为什么，如果有兴趣的同学可以参阅近世代数相关理论）。错误检测和校正PPT课件如何用如何用mbit符号作为符号作为M(x)的系数的系数lmbit符号可用本原元素的幂进行表示，方法如下：l对元素（0,2.q-1)(其中q=2m-2)，分别求其模P（）的值，得到的系数即为i所对应的二进制代码。错误检测和校正PPT课件举例：举例：l如3bit符号的本原多项式为P(x)=x3+x+1，其本原元为，则：错误检测和校正PPT课件对应的运算对应的运算错误检测和校正P

12、PT课件生成多项式生成多项式G（X）的一般形式）的一般形式l对一个信息码符多项式，RS校验码生成多项式的一般形式为 l式中，K0是偏移量，通常取K0=0或K0=1，而K=(n-k)2t(t为要校正的错误符号数)。010()()KKiiG xx错误检测和校正PPT课件举例：举例：l求（6，4，3）RS码，假设已知lm3=001m2=101m1=011m0=100l本原多项式已知为P(x)=x3+x+1 错误检测和校正PPT课件RS码纠错算法码纠错算法lRS码的错误纠正过程分三步：l(1)计算校正子(syndrome)l(2)计算错误位置l(3)计算错误值。l（参见书本P299）l举例错误检测和校

13、正PPT课件16.3 CIRC纠错技术纠错技术l光盘存储器和其它的存储器一样，经常遇到的错误有两种:l一种是由于随机干扰造成的错误，这种错误称随机错误。它的特点是随机的、孤立的，干扰过后再读一次光盘，错误就可能消失。l另一种错误是连续多位出错，或连续多个符号出错，如盘片的划伤、沾污或盘本身的缺陷都可能出现这种错误，一错就错一大片。这种错误称为突发错误。lCIRC(Cross Interleaved Reed Solomon)纠错码综合了交插、延时交插、交叉交插等技术，不仅能纠随机错误，而且对纠突发错误特别有效。错误检测和校正PPT课件16.3.1交插技术交插技术 l同样多的错误，人们更容易纠正

14、分散的错误。l例如，用X表示出现的错字，一种错误形式为“掩X X X，雪中送炭，鸡犬不宁”，这是连续出现的错误，另一种错误形式为“掩X盗铃，雪中X炭，鸡犬不X”，这是分散出现的错误。这两种错误形式相比，同样是3个错误，但人们更容易更正后一种形式的错误。l这个道理很简单，把这种思想用在数字记录系统中对突发错误的更正非常有效。在光盘上记录数据时，如果把本该连续存放的数据错开放，那么当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术。错误检测和校正PPT课件举例举例l3个(5，3)码块：lB1=(a2，a1，a0，P1，P0)lB2=(b2

15、，b1，b0，Q1，Q0)lB3=(c2，c1，c0，R1，R0)l交插排列：la2 b2 c2 a1 b1 c1 a0 b0 c0 P1 Q1 R1 P0 Q0 R0l连续错3个：la2 b2 c2 a1 b1 c1 a0 X X X Q1 R1 P0 Q0 R0l读出后重新排列：la2 a1 a0 X P0 b2 b1 X Q1 Q0 c2 c1 X R1 R0错误检测和校正PPT课件l从这个例子中可以看到，对连续排列，每个码块中只能出现一个错误才能纠正。而交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续的错误。l一般来说，如果

16、有r个(n，k)码，排成rn矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，若(n，k)码能纠正t个错误，那么这样交插后就可以纠正rt个突发错误。错误检测和校正PPT课件16.3.2 交叉交插技术交叉交插技术 l交叉交插(crossinterleaving)编码是交插的一种变型。在实际应用中，也是一种重要的技术。现仍以简单的例子说明这种技术思想。l例子见书本P300 错误检测和校正PPT课件lCIRC首先应用在激光唱盘系统中。音频信号的采样率为44.1 kHz，而每次采样有两个16比特的样本，一个来自左声道，一个来自右声道，每个样本用两个8bit的符号表示，因此每次采样共有4个符号。

17、l为了纠正可能出现的错误，每6次采样共24个符号构成1帧，称为F1帧(F1Frame)。用一个称为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帧(F2Frame)。F2帧加上1个字节(即1个符号)的子码共33个符号构成的帧称为F3帧(F3Frame)。错误检测和校正PPT课件16.4里德里德-索洛蒙盛积码（索洛蒙盛积码（RSPC）l按ISO/IEC10149的规定，CD-ROM扇区中的ECC码采

18、用RSPC码产生172个字节的P校验符号和104个字节的Q校验符号。RS码采用本原多项式 和本原元=(00000010)错误检测和校正PPT课件编码步骤编码步骤l步骤：l1、CD-ROM的每个扇区中从字节12开始到字节2075共2064个字节组成的数据块排列成2443的矩阵 l2、P校验符号用(26，24)RS码产生 l3、Q校验符号用(45，43)RS码产生 l(26，24)RS码和(45，43)RS码可以纠正出现在任何一行和任何一列上的一个错误，并且能相当可靠地检测出行、列中的多重错误。如果在一个阵列中出现多重错误，Reference Technology公司提供有一种名叫Layered ECC的算法，它可以取消多重错误。它的核心思想是交替执行行纠错和列纠错。错误检测和校正PPT课件P校验校验错误检测和校正PPT课件Q校验校验错误检测和校正PPT课件举例举例