数据校验码-奇校验码-偶校验码-CRC循环冗余码-海明码-计算方法

一、奇偶校验码

数据校验码,是数据传输时,一种常用的发现某些错误,甚至带有一些纠错功能的数据编码方法

(一)奇校验码

  1. 实现原理:

    将原来合法的编码距由1增加到2

  2. 具体实现过程:

    将原有的合法二进制数据增加一位标志位,标志这串二进制所含'1'的个数,奇数个标志位记0,偶数个标志位记1,这样的做法能保证处理过后的'1'的总数为奇数(因此称之为奇校验).

  3. 出错检测:

    如果得到的编码中'1'的数量不是奇数,则要么数据传输错误,要么数据发生偶数次错误(2,4...)

(二)偶校验码

实现过程:

偶校验与奇校验相反

(三)示例:

数据(二进制) 奇校验码 偶校验码
00000000 100000000 000000000
01010100 001010100 101010100
01111111 001111111 101111111
11111111 111111111 011111111

注:粗体为校验位

二、海明(汉明)校验码

海明码,Richard Hamming

  1. 实现原理

    复杂,不理解

  2. 实现过程

    • 确定校验码位数量

      在k个数据位之基础上再插入r个校验位,从而形成k+r位新的编码,并且k与r满足如右所示的数量关系 : 2^r >= k + r + 1

    • 确定校验码位置

    • 确定校验码的值

    • 校验码植入完成,开始数据传输

    • 接收数据,进行数据校验

  3. 出错检测

    往后看吧

  4. 例,写出一个含八位数据01010111的汉明码,若接收到的数据位最低位由1变为0,求新汉明码
  • 确定校验码位置

    2^r >= k+r+1 => r = 4
    设四个汉明校验码分别为p1,p2,p3和p4,数据码分别为D1...D8

    得出汉明编码数据为:

... 9 8 7 6 5 4 3 2 1
... D5 P4 D4 D3 D2 P3 D1 P2 P1
... / 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

Pi的值为所有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

发表评论

电子邮件地址不会被公开。 必填项已用*标注