本文主要是介绍校验码：奇偶校验，汉明码，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循环冗余校验码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
