校验码：奇偶校验，汉明码，CRC循环冗余校验码

本文主要是介绍校验码：奇偶校验，汉明码，CRC循环冗余校验码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：http://blog.csdn.net/matrix_laboratory/article/details/12858049

大多数情况下，使用检错码，查错后请求重发；

只有在单工信道（没有反向反馈），才使用纠错功能

1. 奇偶校验

1.1 原理

有效数据：data_code

msg = data_code + check_code   

check_code一般是1位，使msg中“1”的个数为偶数（或奇数）

1.2 分类

水平校验：只检不纠

垂直校验：只检不纠

水平垂直校验：只能纠正1位错，（互补的错不行）

2. 海明码

2.1 海明距离（HD）

海明距离（HD）：两个码字的对应比特取值不同的比特数

检d个位查错：HD >= d + 1   （至少有一码代表无效）

纠d个位查错：HD >= 2d + 1   

2.2 原理

发送端在 k 比特信息上附加 r 比特冗余信息（即校验比特），构成 n=k+r 比特的码字，且满足条件：2^r≥n+1,即 2^r≥k+r+1。其中，每个校验比特和某几个特定的信息比特构成偶校验的关系。

eg:

P1 P2 D3P4D5D6D7P8D9D10D11
             其中，P1、P2、P4、P8 为插入的校验比特，D3D5D6D7D9D10D11 为原来ASCII码的信息比特。

如果把各信息比特的下标写成 2 的幂次之和，即下标3=1+2，5=1+4，6=2+4，7=1+2+4，9=1+8，10=2+8，11=1+2+8，这表示：信息比特 D3 要参与校验比特 P1、P2 的生成、信息比特 D5 要参与校验比特 P1、P4 的生成，……,等等。
            则各校验比特由下式决定： 
                P1 = D3+D5+D7+D9+D11       
                P2 = D3+D6+D7+D10+D11
                P4 = D5+D6+D7
                P8 = D9+D10+D11    

          S1 = P1+D3+D5+D7+D9+D11     
          S2 = P2+D3+D6+D7+D10+D11
          S4 = P4+D5+D6+D7
          S8 = P8+D9+D10+D11

if  S1＝ S2 ＝ S4 ＝ S8 ＝ 0， 则无错；
else  有错.
 错误位置在 S＝ S8 S4 S2 S1 处，

 ‘A’的 ASCII 码为1000001, 由于海明码为 
               P1P2D3P4D5D6D7P8D9D10D11的形式，
          即此处 D3=D11=1, D5=D6=D7=D9 =D10=0，
          则由 P1 = D3+D5+D7+D9+D11，P2 = D3+D6+D7+D10+D11，
                   P4 = D5+D6+D7，P8 = D9+D10+D11    
          得：P1=0，P2=0，P4=0，P8=1
              ∴发送端形成的海明码为 00100001001
          若接收方接收错误，收到：00100001011 (D10错误)
          则检/纠错过程如下：计算校正因子S1、S2、S4、S8，
          得： S1=0，S2=1，S4=0，S8=1
              ∵ S2= S8= 1          ∴ 检测有错，
          错误位置在 S＝1010 处即D10，将D10取反即可.

题目描述：

输入一个字符串，然后对每个字符进行奇校验，最后输出校验后的二进制数(如'3’，输出：10110011)。

输入：

输入包括一个字符串，字符串长度不超过100。

输出：

可能有多组测试数据，对于每组数据，
对于字符串中的每一个字符，输出按题目进行奇偶校验后的数，每个字符校验的结果占一行。

样例输入：

3
3a

样例输出：

10110011
10110011
01100001

3. CRC（循环冗余校验码）

3.1 原理

将位串看成系数为 0 或 1 的多项式。
         如位串1 0 1 0 0 1 1 1 即对应于多项式： x^7 + x^5 + x^2 + x + 1
收发双方约定一个多项式G(x)，发送方用位串及 G(x)进行某种运算得到校验和，并在帧的末尾加上校验和，使带校验和的帧的多项式能被 G(x) 整除; 接收方收到后，用 G(x) 除多项式，若有余数，则传输有错。

3.2 校验和计算

G(x)的最高阶和最低阶系数必须为1

设G(x)为n阶，待发送数据M = k (bits)

则校验和（冗余码）长度为r(bits)

M = 1010001101 ， n = 5, G(x) = P = 110101

将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2^n * M + R

常用的G(x)

N	K	码距d	G(x)多项式	G(x)
7	4	3	x3+x+1	1011
7	4	3	x3+x2+1	1101
7	3	4	x4+x3+x2+1	11101
7	3	4	x4+x2+x+1	10111
15	11	3	x4+x+1	10011
15	7	5	x8+x7+x6+x4+1	111010001
31	26	3	x5+x2+1	100101
31	21	5	x10+x9+x8+x6+x5+x3+1	11101101001
63	57	3	x6+x+1	1000011
63	51	5	x12+x10+x5+x4+x2+1	1010000110101
1041	1024		x16+x15+x2+1	11000000000000101

这篇关于校验码：奇偶校验，汉明码，CRC循环冗余校验码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---