汉明码编码note

最近在学习计算机组成原理,看了清华的课程,关于汉明码老师
只是简单地带过,因此我又研究了一下这一神奇的编码原理,不得不感叹汉明的聪明才智!

编码目的

当传输数据时,有各种原因可能会使数据出错,导致高层程序无法运行,这时如果我们采用一种编码方式能够检测错误
并且纠正错误,就能在底层解决这一问题,使得高层程序能正确运行

检错原理

奇偶检验

我们约定一串编码里1的个数是偶数个,那么这串编码里携带的信息就是对的,否则就是错的。

我们可以在开头对这串编码加一位校验码实现奇偶校验。

我们想传输10010这串码,那么在传输的时候,就传010010,其中在开头的0就是校验位。

我们想传输10000这串码,那么在传输的时候,就传110000,其中在开头的1就是校验位。

两个例子的1的个数都是偶数。

流程

  1. 发送者对数字进行分组
  2. 按位填写校验码并发送
  3. 接收者使用分组检测确定哪一位出错
  4. 出错位取反改正结果

汉明码.png

本文主要对1.2.进行记录,汉明码的核心部分也在前两部分

确定总位数

假设校验码一共k位,原始数据一共n位,校验码必须满足

实际上计算时按第2的n次方位占据检验位,其余的都为原始数据即可

分组

将数据的位置索引转为二进制数

也就是

第1个位置,变成第0001个位置;

第2个位置,变成第0010个位置;

第3个位置,变成第0011个位置;

第4个位置,变成第0100个位置;

第5个位置,变成第0101个位置;

第6个位置,变成第0110个位置;

位置在1,3,5,7,9,11的数据进到P1组。(你转换一下这些位置的二进制,就知道他们的位置符合XXX1)

位置在2,3,6,7,10,11的数据进到P2组。(位置符合XX1X)

位置在4,5,6,7的数据进到P3组。(位置符合X1XX)

位置在8,9,10,11的数据进到P4组。(位置符合1XXX)

第1,2,4,8位按照奇偶检验填写

发送给接收方

接收方检测纠错

  1. 收到汉明码后首先按照P1,P2,P3分组
  2. 对每个组进行奇偶校验,正确的给0,错误的给1
  3. 把P按照从大到小排列起来,该串就是出错的数据的位置。
  4. 对该位数据取反完成改正

例子

汉明码例子.png


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!