关于数据校验纠错算法

最近对于数据传输的噪音损耗问题的解决方案查了些资料

就此做一个总结:

  数据损坏

    因为网线被老鼠啃了或者硬盘摔地上了导致数据错了

    关于数据损坏的问题其实不限于网络传输方面,可以涉及到所有和数据相关的方面,比如文件解压,网络通讯,保密数据的校验(数据签名)等等

  错误校验

    即检验某一段数据是否有误。

    因为是不是有误光凭数据本身不可能知道,所以必须加上附加的认证方法

    当然最简单的认证方法就是再传一次数据,拿着数据一个个对着原本的数据对照一下。。。不过这样不说太麻烦,如果要实现这个方法,第二次传输这个数据的时候,难以保证这个数据是不是也出现了错误

    另一方面,显然数据越短,这段数据出现错误的概率越小,因为比特出错概率(BER)是不变的。所以如果可以把这个认证的数据(校验码)压缩成一段很短的数据就可以减少校验码出错的情况了

    比如奇偶校验(Parity Check)  或者说,数1校验

      奇偶校验制定了一个协议,规定数据中1的个数只能是偶数

      如果原始数据1是奇数,则加一个1在最前面;反之则加一个0在前面。

      如  0110101   和   11010010   都是符合规定的。  很显然这个第一位就是校验码。

      那么如果数据出了错误,某个0变成1或者1变成0,那么接收者数一遍1发现不是偶数个,那么就证明数据错了

    当然奇偶校验的缺陷十分明显,如果同时错了2个或者偶数个位,那么错误将无法被检测出来。。。

    所以我们需要更强的校验算法,使校验码尽可能简单的同时,让失误率尽可能小。

    具体实现方法就是加上hash算法,一个数据对应一个hash值,再用hash值代表原有数据的特征,作为校验码,从而达到一一对应的目的。

      例如把一段数据乘以10086再对23333取模,将这个hash结果作为校验码加在数据后面,然后接收者再做一遍hash得到他的hash值。

      如果两者相同,可以看做两组数据特征符合,于是数据得到验证。

    (本质上奇偶校验也是一种hash)

    当然另一方面,既然是hash那么就不可避免地会出现错误,比如数据出错了,然而接收者得到的hash值正好和校验码一样,或者说数据和校验码都错了然而也正好吻合。所以这要求hash函数足够强大。

             不过要指出的是,如果不幸校验码出错的话,只能重发一个数据包过来。。

    现今使用的MD5算法就是一种通过hash实现的校验算法,目前广泛运用于机密文件校验以及银行系统交易数据等等。

    类似的还有广泛使用的CRC循环冗余校验算法,被使用于TCP/IP协议中。

    另外LRC、BCC、SHA等等算法也可用于错误校验,只是hash函数大同小异,本质上差不多(吧)。还有个Nand ECC算法,没太看懂。。。

    

  错误纠偏

    即纠正某一段数据的错误。

    目前看到可以纠正错误的有以下几种算法:

      后向纠错:通过错误校验(数据不吻合校验码)知道数据错了以后,要求重新发一遍数据。包括数据错了和校验码错了两种情况(这也能叫算法??)(硬就是能了)

      前向纠错(FEC算法):发送端在发送数据之前,加了一些预处理之后的数据(冗余数据),以在出现错误之后可以反推回去纠正错误。

        零阶冗余:没有冗余,就是发原来的数据

        一阶冗余:在N包数据后面加一个冗余数据,这个数据按照某个方程生成(具体方程懒得打了有需要可以自行百度),插在数据块的最末尾。

              (注:一包数据里面带一个校验码,也就是一个整体)

                如果有一个数据坏了,找到这个数据的编号以后,通过其他好的数据将方程反推回去,可以反推回去这个数据。

        二阶冗余:在N包数据后面加两个冗余数据………………

              可以承受一个数据块中有两个数据坏了的情况(类比一下解方程组,两个未知数两个方程)

        三阶冗余:…………

      一般到了三阶冗余就已经可以保证很强的鲁棒性了

      汉明码(hamming code):https://blog.csdn.net/Yonggie/article/details/83186280不多bb贴链接,这位大神已经讲得很清楚了

        缺点是只能承受一个错误的情况

        优点……除此之外都是优点,目前见到的唯一做到错误校验和错误纠偏的算法了

      

    

原文地址:https://www.cnblogs.com/euphoria-eden/p/11374646.html