字符编码（二）校验码

 

经典校验码： 奇偶校验码,海明校验码 和 循环冗余校验码(CRC) 

都是对二进制的bit流而言

设原来数据有n位,要加入k位校验码.

        1，奇偶校验码-奇校验码 和 偶校验码 的统称.

                k=1

                奇偶校验码最简单,但只能检测出“奇数”（比如3个，5个）位出错. 无法检测偶数位错误

                奇校验 

                        加上校验位后,编码中1的个数为 奇数个 

                偶校验

                        加上校验位后,编码中1的个数为 偶数个 

                例: 

                        原编码           奇校验           偶校验 

                        0000            0000 1           0000 0 

                        0010           0010 0          0010 1 

 

        2，海明校验码-多重奇偶校验检错码

                可以检测任何位出错，并能纠正1位错误

                必须满足：pow(2,k)-1 >= n+k //pow(2,k) (代表2的k次方) 

 

        3，CRC即 循环冗余校验码--广泛应用于数据通信领域和磁介质存储系统中.

                CRC码利用生成多项式为k个数据位产生r个校验位进行编码,其编码长度为n=k+r所以又称 (n,k)码. 

                CRC理论非常复杂,-关键是求“多项式g(x)”

 

                在k位信息码后接r位校验码,对于一个给定的(n,k)码 

                可以证明(数学高手自己琢磨证明过程)存在一个最高次幂为 n-k=r 的多项式g(x) 

 

                根据g(x)可以生成k位信息的校验码,g(x)被称为 生成多项式 

 

                用C(x)=C(k-1)C(k-2)...C0表示k个信息位 

                把C(x)左移r位,就是相当于 C(x)*pow(2,r) 

                给校验位空出r个位来了. 

 

                给定一个 生成多项式g(x),可以求出一个校验位表达式r(x) 

                C(x)*pow(2,r) / g(x) = q(x) + r(x)/g(x) 

 

                用C(x)*pow(2,r)去除生成多项式g(x)商为q(x)余数是r(x) 

                所以有C(x)*pow(2,r) = q(x)*g(x) + r(x) 

 

                在CRC运算过程中,四则运算采用 mod 2运算(后面介绍),即不考虑进位和借位. 

                所以上式等价于C(x)*pow(2,r) + r(x) = q(x)*g(x) 

 

                C(x)*pow(2,r) + r(x)就是所求的n位CRC码,由上式可以看出它是生成多项式g(x)的倍式. 

 

                所以如果用得到的n位CRC码去除g(x)如果余数是0,就证明数据正确. 

                否则可以根据余数知道 出错位 .