多媒体技术基础 第4版讲稿pptchp17 错误检测和纠正

多媒体技术基础(第4版),林福宗 linfz 2017年3月,第17章 错误检测和纠正,第17章 错误检测和纠正,17.1 光盘的误码率 17.2 CRC错误检测 17.2.1 CRC错误检测原理 17.2.2 CD的错误检测码 17.3 RS编码和纠错原理 17.3.1 GF(2m)域 17.3.2 RS编码 17.3.3 RS解码 17.4 CIRC纠错技术 17.4.1 交插概念 17.4.2 交叉交插 17.5 RSPC码,2,2019年9月23日,多媒体技术基础 第4版,17.1 光盘的误码率,光盘作为数据存储器使用要求误码率小于10×10-12 光盘存储器需要纠错 由于光盘材料性能、光盘制造技术水平、驱动器性能和使用不当等诸多原因，从盘上读出的数据不可能完全正确 据有关厂家的测试和统计，一片未使用过的只读光盘，原始误码率约为3×10-4，沾有指纹的盘的误码率约为6×10-4，有伤痕的盘的误码率约为5×10-3 光盘存储器采用了三种错误检测和纠正措施 错误检测：循环冗余码(CRC)检测读出数据是否有错 错误校正： 里德索洛蒙码(RS)纠正 交叉交插里德-索洛蒙码 (CIRC)：在用RS编译码前后，对数据进行交插和交叉处理,2019年9月23日,3,多媒体技术基础 第4版,17.2 CRC错误检测原理,17.2.1 CRC错误检测原理 代码多项式 在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序列10101111，用多项式可以表示成 式中, xi表示代码的位置或某个二进制数位的位置 系数ai表示码的值，取值为0或1 M(x)称为信息代码多项式,4,2019年9月23日,多媒体技术基础 第4版,17.2 CRC错误检测原理与检测码(续1),模2多项式代数运算规则 例如，模2多项式的加法和减法 代码多项式的模2加法和模2减法运算所得的结果相同，可用加法来代替减法,5,2019年9月23日,多媒体技术基础 第4版,17.2 CRC错误检测原理与检测码(续2),模2多项式的除法用长除法,6,2019年9月23日,多媒体技术基础 第4版,17.2 CRC错误检测原理与检测码(续3),代码多项式的结构 如果一个k位的二进制信息代码多项式为M(x) ，增加(nk)位的校验码后，信息代码多项式在新的数据块中表示成xn-kM(x)，见图17-1,7,2019年9月23日,图17-1 消息代码结构,多媒体技术基础 第4版,17.2 CRC错误检测原理与检测码(续4),错误检测原理 如果用一个校验码G(x)生成多项式去除代码多项式M(x) ，得到的商假定为Q(x)，余式为R(x)，则可写成 模2多项式的加法和减法运算结果相同，可把上式写成,8,2019年9月23日,多媒体技术基础 第4版,代表新的代码多项式，它能够被校验码生成多项式G(x)除尽，即它的余项为0 在盘上写数据时，将xn-kM(x)表示的信息代码和表示的余数R(x)代码一起写到盘上 从盘上读数据时，将信息代码和余数代码一起读出，用相同的校验码生成多项式G(x)去除 通过判断余数是否为0来确定数据是否有误,9,2019年9月23日,多媒体技术基础 第4版,17.2 CRC错误检测原理与检测码(续6),17.2.2 CD的错误检测码 CD-DA盘上的q通道使用的CRC校验码生成多项式 若用二进制表示，则为,10,2019年9月23日,假定要写到盘上的信息代码M(x)为,由于增加了2个字节的校验码，所以信息代码变成,多媒体技术基础 第4版,17.2.2 CD的错误检测码 1. 激光唱盘(CD-DA) CD-DA盘的q通道使用的CRC校验码生成多项式， 若用二进制数表示，则为 【例】假定要写到盘上的消息代码M(x)为 M(x)= 4D6F746F 增加2个字节(16位)的校验码，消息代码就变成, x16M(x)= 4D6F746F0000(H),11,2019年9月23日,多媒体技术基础 第4版,17.2 CRC错误检测原理与检测码(续7),两数相除结果 其商可不必关心，其余数为B994(H)，这就是CRC校验码 将信息代码和CRC码一起写到盘上 写到盘上的信息代码和CRC码是4D6F746FB994，能被 错误检测 从盘上读出的这块数据用同样的CRC码生成多项式去除，其结果是：(1) 余数为0：读出没有错误；(2) 余数不为0：读出有错,除尽,2019年9月23日,12/43,多媒体技术基础 第4版,17.2 CRC错误检测原理与检测码(续8),2. 只读光盘(CD-ROM) 在CD-ROM扇区方式1中，有一个4字节的EDC域用来存放CRC码。CRC校验码生成多项式是一个32阶的多项式 计算CRC码时用的数据块是从扇区的开头到用户数据区结束的数据字节，即字节02063 CRC码在EDC中存放的次序如下,13,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理,RS编码和纠错原理 RS码是Irving S. Reed和Gustave Solomon在1960年介绍的纠错码(error-correcting codes，ECC)，在许多领域都有重要应用，如 光盘存储器(如CD，DVD，蓝光盘)，数据传输系统(如xDSL，WiMAX)、电视广播系统(如DVB)，卫星通信。 RS码尤其适合纠正突发错误(burst errors)，不管一个符号中出现多少位错误，都把它作为单个符号错误 由于RS码、RS编码(Reed Solomon encoding)、RS解码(Reed Solomon decoding) 都是在伽罗瓦域(Galois Field，GF)中进行的，因此先对GF域作简单介绍,14,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),17.3.1 GF(2m)域 在数学上，伽罗瓦域(Galois Field)是以法国数学家Évariste Galois(1811-1832)名字命名的有限域(finite field) 有限域是元素数目有限的一组元素，这些元素的加减乘除运算都有一套规则，运算的结果仍然是这组元素中的元素 在错误检测和编码技术中，元素(element)通常指符号(symbol)或代码(code)。,15,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),1. 域元素的表示方法 伽罗瓦域用符号GF(2m)表示，其中的2m表示域中的元素数目，m表示元素由几位(bit)组成。生成GF域元素的元素称为本原元素(primitive element)，并用表示。 2m 个域元素的值用表示为 其中，N=2m-1，的值通常选为2 除用的幂的形式表示外，式(17-4)的每个域元素也可用多项式表示,16,2019年9月23日,多媒体技术基础 第4版,17,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),18,2019年9月23日,多媒体技术基础 第4版,19,2019年9月23日,以上建立了GF(23)域中的元素与3位二进制数之间的对应关系。使用同样的方法，可建立GF(24)域元素的各种表示方法，见表17-2,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),20,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),21,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),22,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),17.3.2 RS编码 RS编码是求解剩余多项式系数的过程，剩余多项式是消息多项式除以校验码生成多项式的余式 先要了解RS码的表示方法，RS码的生成多项式，再介绍RS编码 1. RS码的表示方法 RS码用RS(n, k)表示，符号的含义见图17-2 【例】RS (28，24)码：码块长度为28个符号，其中消息代码长度为24个符号，检验码4个符号，可纠正2个分散或连续的符号错误，但不能纠正3个错误符号,23,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),24,2019年9月23日,图17-2 RS(n, k )码中的符号,多媒体技术基础 第4版,25,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),3. RS码的编码方法 RS编码：计算消息码多项式M(x)除以校验码生成多项式G(x)的过程，得到剩余多项式R(x) RS码：R(x)的系数 R(x)的系数：可用多项式长除法得到，或用其他方法计算 下面举例说明，用解方程组的方法求解剩余多项式的系数,26,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),27,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),28,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),29,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(续),17.3.3 RS解码 RS 解码是检测和纠正错误符号的过程 RS解码过程分三步 (1) 使用与编码相同的RS码生成多项式计算校正子 (2) 计算错误位置和错误值 (3) 纠正错误,30,2019年9月23日,多媒体技术基础 第4版,31,2019年9月23日,多媒体技术基础 第4版,17.3 RS编码和纠错原理(end),32,2019年9月23日,多媒体技术基础 第4版,17.4 CIRC纠错技术,光盘存储器和数据通信信道经常遇到两种错误 (1) 随机错误：由随机干扰造成的错误，其特点是随机的和孤立的，干扰过后再读一次光盘，错误就可能消失 (2) 突发错误：连续多位或连续多个符号出错，如盘片划伤、沾污或盘的缺陷造成的错误。 CIRC(Cross Interleaved Reed Solomon)纠错码 综合了交叉、交插、交叉交插的RS编码技术 能够纠正随机错误 对纠正突发错误特别有效,33,2019年9月23日,多媒体技术基础 第4版,17.4 CIRC纠错技术(续),17.4.1 交插技术 纠正分散错误比较容易，纠正连续错误比较麻烦 我们读书看报，如果文中在个别地方出错，根据前后文就容易判断是什么错。如果连续错的字较多，就较难判断该处写的是什么 【例】用X表示出现的错字，两种错误形式 “独在异乡XXX，每逢佳节倍思亲”，这是连续出现的错误 “独在异乡X异客，每X佳节倍思X”，这是分散出现的错误 哪种错误形式更容易纠正？ 在数字记录系统中，对纠正突发错误很有效 在光盘上记录数据时，把本该连续存放的数据错开放，当出现一片错误时，这些错误就分散到各处，错误就容易得到纠正，这种技术就称为交插(interleaving)技术,2019年9月23日,34,多媒体技术基础 第4版,17.4 CIRC纠错技术(续),35,2019年9月23日,【例】,多媒体技术基础 第4版,17.4 CIRC纠错技术(续),从该例可以看到 对连续排列，每个码块中只能出现一个错误才能纠正 交插记录后，读出的3个连续错误经还原后可把它们分散到3个码块中，每个码块可以纠正1个错误，总计可以纠正3个连续错误 纠错能力 如果有r个 (n，k)码，每个(n，k)码能纠正t个错误，排成r×n矩阵，按列交插后存储或传送，读出或接收时恢复成原来的排列，那么可纠正t×r个突发错误,36,2019年9月23日,多媒体技术基础 第4版,17.4 CIRC纠错技术(续),17.4.2 交叉交插 交叉交插(crossinterleaving)编码是交插的一种变型，有实际的应用价值 【例】 假