一、奇偶校验码
数据校验码,是数据传输时,一种常用的发现某些错误,甚至带有一些纠错功能的数据编码方法
（一）奇校验码
- 实现原理:
将原来合法的编码距由1增加到2
- 具体实现过程:
将原有的合法二进制数据增加一位标志位,标志这串二进制所含'1'的个数,奇数个标志位记0,偶数个标志位记1,这样的做法能保证处理过后的'1'的总数为奇数(因此称之为奇校验).
- 出错检测:
如果得到的编码中'1'的数量不是奇数,则要么数据传输错误,要么数据发生偶数次错误(2,4...)
（二）偶校验码
实现过程:
偶校验与奇校验相反
（三）示例:
| 数据(二进制) | 奇校验码 | 偶校验码 |
|---|---|---|
| 00000000 | 100000000 | 000000000 |
| 01010100 | 001010100 | 101010100 |
| 01111111 | 001111111 | 101111111 |
| 11111111 | 111111111 | 011111111 |
注:粗体为校验位
二、海明(汉明)校验码
海明码,Richard Hamming
- 实现原理
复杂,不理解
-
实现过程
-
确定校验码位数量
在k个数据位之基础上再插入r个校验位,从而形成k+r位新的编码,并且k与r满足如右所示的数量关系 : 2^r >= k + r + 1
-
确定校验码位置
-
确定校验码的值
-
校验码植入完成,开始数据传输
-
接收数据,进行数据校验
-
-
出错检测
往后看吧 4. 例,写出一个含八位数据01010111的汉明码,若接收到的数据位最低位由1变为0,求新汉明码
-
确定校验码位置
2^r >= k+r+1 => r = 4 设四个汉明校验码分别为p1,p2,p3和p4,数据码分别为D1...D8
得出汉明编码数据为:
| more | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|
| more | D5 | P4 | D4 | D3 | D2 | P3 | D1 | P2 | P1 |
| more | ~ | 2^3 | ~ | ~ | ~ | 2^2 | ~ | 2^1 | 2^0 |
- 确定校验码的值
数据D拆分所得到的子集为:
| D | 位置 | 拆分 |
|---|---|---|
| D1 | 3 | 2+1 |
| D2 | 5 | 4+1 |
| D3 | 6 | 4+2 |
| ... | ... | ... |
| D8 | 12 | 8+4 |
P的值为所有D中,子集包含有i(角标)的D相互异或
P1 = D7 xor D5 xor D4 xor D2 xor D1 =0
P2 = D7 xor D6 xor D4 xor D3 xor D1 = 0
P3 = D8 xor D4 xor D3 xor D2 = 1
P4 = D8 xor D7 xor D6 xor D5 = 0
注释:xor,异或
- 校验码植入
| 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| D8 | D7 | D6 | D5 | P4 | D4 | D3 | D2 | P3 | D1 | P2 | P1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
数据最后一位变位后,新校验码S为
| S1 | S2 | S3 | S4 |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
- 收到错误数据,处理得错误码位置
当发送和接收的两套汉明码进行异或运算,结果全为零,则传输正确,否则错误
S1 xor P1 = 1
S2 xor P2 = 1
S2 xor P2 = 0
S2 xor P2 = 0
由于(1100)2 != 0
故,发生错误,查表可得错误位置
三、CRC循环冗余校验码
此为海明码改进,解决海明校验码需要插入到数据当中,难以分离的问题(k位信息码直接拼接r位校验码)
TODO: 例,把10101011转换成循环冗余码,且其生成多项式10011 将数据10101011补四个零,然后除10011,获得其余数,不考虑借位的方式除. 得余数1010,冗余码为10101011 1010
<!--上传-->