UID51981
威望56
金钱62644
交易诚信度0
主题141
帖子2319
注册时间2003-11-7
QQ
最后登录2020-5-2
特级会员
交易诚信度0
注册时间2003-11-7
|
转一篇网上的文章来了解下数字纠错：
长久以来，人们并不了解 CD 光盘真正的革命之处在哪里，以为激光和超大容量才是 CD 光盘真正的特征，其实这些都不是——CD 光盘开创了受市场广泛接受的可交换存储介质数字校验的先河，如果没有这一机制的参与，网络，多媒体乃至于如今的信息时代都无从谈起——因为一个非常可笑的原因，那就是你无法保证复制的文件再粘贴到另一个位置，二者还是一模一样。这个问题看似无聊，但却是模拟时代的介质所无法逾越的障碍——例如胶片唱盘和磁带都会磨损，AV 影碟和卫星电视信号中怎么也无法消除的雪花点。但是现如今的数字时代则不会存在这种问题，windows 系统的安装光盘不会出现因为复制错误而导致的系统安装崩溃，你从网上下载文档时也不会担心文档中出现莫名其妙的乱码甚至无法打开，这些都与数据纠错机制有着直接的联系。
接下来说说，CD 当中的数据是如何纠错的。但是在说数据纠错之前，不得不先提到数据校验。
数据校验简单来说就是在正常的数据之外，附加一小段数据，用这段数据来检测之前的数据是否有错误。数据校验与数据纠错的区别就是，数据校验所用的校验码体积可以很小，很多时候甚至只需要一个 1 或者 0 的数字就能发挥很大的作用。
举例：中国居民的身份证号是18位数字，但实际上真正记录你个人身份的数据应该只有17位，最后一个数字就是校验码。如果有人在电脑上输错了前面17位数字中的任意一位数字，则通过校验算法计算得到的校验码数字必然不等于身份证上的第18位数字（也就是真实的校验码），这时计算机就能够提醒：
「未能通过校验，请确认你的身份证号输入是否有误。」
具体算法可以参考链接[2]。
为了帮助大家理解该过程，这里可以使用一个更加简单的模型，即最常见的奇偶校验方法：
对于任意8个位的数据，例如 10010011 ，我们可以假设：
为了得到一个校验码，我们采用数数字的办法，即观察这 8 个数字中有多少个数字是 1 而不是 0 ?如果存在奇数个 1（1、3、5 或者 7 个），我们就将校验码记做 1 ，反之，如果出现了偶数个 1 （0、2、4、6、8 个），我们就将校验码记做 0 。
我保证这9个位（8个位的数据+1个位的校验码）的数据，绝对没有错误！即使有错，也只有1个错误，不可能出现2个以上。
那么我们就会有一个很有意思的结论，即——对于10010011来说，出现了4个1，故校验码为0（偶数个）。假如原数据是错的，根据第二个假设，只能有1个位有错误，即8个位中要么{有1个位从1变成了0}，要么{有1个位从0变成了1}，最后导致的结果是错误的数据当中肯定不会出现4个1——要么出现3个，要么出现5个，故一个错误的数据会导致我们再去数数字，最后得到的校验码只能是1（奇数个），如下图所示，被标记为红色的第四位由于从1变成了0，就导致实际校验码与我们的检验结果 1 相违背——此时就说明这个数据出现了错误。
此外，还有一个很有意思的结论——你肯定会说，如果错误不是出现在原始数据当中，而恰恰就是校验码！这时该怎么办？很简单，如果校验码出错了，那么正确的数据和错误的校验码——很显然，二者也不可能校验通过的，所以校验码在校验数据的同时，数据也在校验着校验码——于是校验失败，不管是原始数据还是校验码，通通作为错误数据一并丢弃掉。在数据传输过程中，校验码与完整的数据一起发出，如果打个比方的话，就像一个狱警押送着囚犯在两个监狱间转移，发送囚犯的监狱会通过了解每名囚犯的情况，然后派送一个特殊的狱警，而接受囚犯的监狱则会通过该狱警得知囚犯转移途中是否有人被掉了包。
将上面这个例子推广到若干长度的数据当中，我们就可以知道：假定若干个位中最多只出现1个错误，则我们可以通过一个位的数字来监视这一行所有的数字，从而知道这一行数据是否正确。当然，这个前提要求是无法始终被满足的。因为随着位数的增加，出错的几率也会增长，这就意味着这种方法所能检测的位数不能太多。那么如果一定要检测位数很多的数据，还有其它办法么？有，就是同样增加校验位的位数。但是此时，校验算法就显得更加复杂了。如果知友们对这个问题比较感兴趣的话，可以看看 CRC32 校验算法[3]的原理（奇偶校验就属于是 CRC 算法的一个特例）。当然，只要算法允许，理论上可以对任意体积的文件进行校验，例如 MD5 算法——而这时，这类校验码也会披上另一个名字，叫做「文件指纹」。
上面介绍了数据校验，那么数据纠错和数据校验有什么联系？
不妨将上面所举的奇偶校验码的例子展开一下，来继续我们的比喻：上一个监狱派出的警卫有个怪毛病，就是只有当这些囚犯到了新的监狱，然后排成一排时，他才能看自己这一排囚犯是否有人被掉了包，如果有囚犯被掉包的话，他就会大声呼叫——那么如何能够让我们知道被掉包的囚犯在什么位置呢？我们不妨将这群犯人编队，在派出这批囚犯前，在这支队伍的每行和每列各放置一个警卫，如下所示：这个时候就出现了一个非常有意思的情况，一旦其中有一个犯人被掉了包，则在接收囚犯的监狱，同时会有两个警卫大声呼叫：可以看到，当第 4 行第 4 位数据发生错误时，这两个校验码分别指向了错误所在的行和列，这时，我们的校验码就不仅能够发现这 5 个字节的数据是否有错误，甚至能够将错误找出，并将其纠正！当然，这还是多亏数据的二进制属性——正是因为数据不是 0 就是 1 ，所以只要我们能找出错误的具体位置，就肯定能将其纠错。
以上就是奇偶校验方法的一种简单扩展，叫做方正码算法。看似很简单，而漏洞也大，但威力却依然强劲——因为针对少数随机误码，其纠错效果极佳。光盘数据纠错所使用的里德所罗门码，即采用了该方案的变种。
那么问题来了，这个纠错方法看似只能对付一串连续数据中的少数随机错误，但是人们日常使用的光盘，常见的问题就是划伤，一划就是连续的一片，甚至是一块，这时你的纠错方法漏洞就暴露出来了——一段连续的数据中会同时出现多处错误，这时这种对少数随机错误纠错效果好的方法立马就不顶事儿了——遇到天灾，囚犯群起闹事，少数的警卫如何看管得住呢？
所以说还是得想办法——我们注意到，其实把这个问题想细了，就会发现，里德所罗门码真正无力处理的是在一段连续数据上发生了多个错误的对象 ，但是划伤造成的问题是在一段连续存储位置上发生了多个错误——那么，一段连续存储位置上就非得存储一段连续的数据么？这个很显然不一定，比如说你的电脑只要 D 盘还有 2GB 的空间的话，总是能塞下一个 1GB 的文件的，电脑不会，也不可能提醒你说：「由于连续存储空间不足，您的文件无法被存储」电脑的做法是哪儿有空位就塞到哪儿，只要能标明这个文件被拆成了几部分，每个部分分别位于硬盘的哪个位置就可以了。
换句话说——那么既然在这里，警卫的双眼是没有地理限制的，那么办法不就来了么？让一个警卫看管的一排囚犯中，同时有实际身在河北的囚犯，实际身在陕西的囚犯， 实际身在安徽的囚犯 ， 实际身在福建的囚犯 ，和实际身在内蒙古的囚犯......这时即便其中任何一个地方洪水滔滔，又能耐我何？......呃，至于具体是如何看管的？你就当警卫们人手一台卫星电视吧 XD
具体到光盘的 CIRC 纠错编码中，这一方法就演变成了「交织法」——即把原有的数据序列打乱，重新分配：原有的一段数据，是按照 -3，-2，-1，······ 14，15，16 这样顺序排列的，他们的存储也是按照同样的顺序依次排列。但是经过了交织法以后，它们的排列顺序被打乱成了 -3，-6，-1，-4，······ 13，10，15，12 这样一个散乱的顺序。
可以看到，经过交织法处理以后的数据，已经完全打乱了其原有的序列顺序，这时即使是光盘表面出现了轻微的划伤，本来也许是一处连续的损伤，经过解码时的反交织编码过程以后，就重新变回了一堆随机的少量的误码，此时我们的里德所罗门码又能够大显神威，令警卫们轻易地将各自队伍中趁当地遭逢天灾而掉包的囚犯一一识破。
最后我们来总结一下，CD 光盘当中的数据，能够实现自动纠错的核心方法就是 CIRC 编码，它的主要特色分为两部分，一部分叫做里德所罗门码，听上去有些恐怖，但实际上相当于是利用奇偶校验方法基本原理的一种变形，能够有效对付随机误码；另一部分叫做交织法，是通过打乱原有数据排序，使得光盘上最常出现的问题——划伤所导致的连续误码，变成随机误码，从而保证里德所罗门码能够有效工作。
但是需要指出的是，以上从严格意义上讲并不是一个「正确」的答案，因为真正的 CIRC 编码比上面所介绍的两个特色还要复杂，还有更多的细节被刻意忽略。但我个人认为如果一味追求正确地回答这个问题，只会导致知友看到一个不知所云的答案（例如参考来源[4]，但我对此问题最初的了解正是从该资料中得到的，所以强烈建议对此问题感兴趣的知友能够通读一遍这篇材料）。所以我仅在此抛砖引玉，希望能够令知友对此问题有一个大概的印象，明白纠错的大致含义即可。另：关于CD光盘的编码除了 CIRC 编码以外，还有 EFM 调制编码，但该编码与数据纠错无关，故不再介绍。
|
|
楼主: 棋盘子龙睛
[复制链接]
京公网安备 11010602010207号
( 京ICP证041102号，京ICP备09075138号-9 )
狗仔卡
楼主
发表于 2014-1-28 02:24
