首页 > 代码库 > 计算机系统知识(一)—海明码

计算机系统知识(一)—海明码

海明码校验

    当计算机存储或移动数据时,可能会产生数据位错误。这时能够利用汉明码来检測并纠错,简单的说,汉明码是一个错误校验码码集。

    了解海明码之前先了解一下异或:

    异或的数学符号为“⊕”。计算机符号为“xor”。其运算法则为:

    a⊕b = (?a ∧ b) ∨ (a ∧?b)

    假设二进制下用1表示真,0表示假。则异或的运算法则为:

    0⊕0=0,

    1⊕0=1,

    0⊕1=1。

   1⊕1=0(同为0,异为1)。

 

 海明码的编码步骤

  1. 依据信息位数,确定校验位数,2r -1>k+r。当中,k为信息位数,r为校验位。

求出满足不等式的最小r。即为校验位数。

计算校验位公式如表所看到的。

9

8

7

6

5

4

3

2

1

位数

I5

 

I4

I3

I2

 

I1

 

 

信息位

 

r3

 

 

 

 r2

 

 r1

r0

校验位

2.  求校验位。依据上面所说的计算公式求出校验位。

3.  求海明码。依据上面表格的填充。写出海明码。

我们以希塞视频中的样例来理解:

举例:若有效信息位为1101,求它的校验位

依据上面的步骤我们可知

1.  信息位为k=4位,那么2r -1≥k+r。求的r=3

2.  列表。

r位的校验位能够表示 2个数,和位数对齐后r0=1,r1=2,r2=4…等等。信息位即为我们上面的1101这4位信息。那么我们能够画出以下这张表

7

6

5

4

3

2

1

  位数

  I4(1)

  I3(1)

   I2(0)

 

  I1(1)

 

 

  信息位

 

 

 

   r2

 

  r1

  r0

  校验位

 我们知道r0=20,r1=21,r2=22

 而信息位与所相应的位数关系为3.中

  I4:7=22 +21+20

  I3: 6= 22 + 21

  I2: 5= 22+20

  I1:3 =21+20 

  r0就用具有出现20的信息位表示,因此

  r0=I4⊕I2⊕I1=1⊕0⊕1=0;

  r1=I4⊕I3⊕I1=1⊕1⊕1=1;

  r2=I4⊕I3⊕I2=1⊕1⊕0=0;

  注:异或的公式里面假设出现偶数的1。则结果为0,反之为1

 4. 将得到的校验码输入上表中,得出

  7

  6

  5

  4

  3

  2

  1

   位数

  1

  1

  0

 

  1

 

 

  信息位

 

 

 

   0

 

   1

  0

   校验位

  5.综上海明码结果为:1100110

关于纠错下篇介绍...

计算机系统知识(一)—海明码