概述

介绍如下内容:

  • 什么是汉明码(海明码)
  • 汉明码(海明码)的计算(配置)
  • 汉明码(海明码)的纠错
  • 一个有意思的情况

什么是汉明码(海明码)

汉明码是一种奇偶校验码,特点是能够检验一位错误,纠正一位错误,并且相对于传统的奇偶校验非常节省空间。

汉明码(海明码)的计算(配置)

汉明码(海明码)的前提:数据在传输中只会有一位二进制位出现错误

基本步骤是:

  1. 对等待配置的数据进行分组。
  2. 选择每一个校验位的位置。
  3. 计算每个校验位。

校验位数量计算公式

校验位的数量=需要分成多少个组

\( 2^k \geq n + k + 1 \)

  • \( k \):校验位的数量,取最小值。
  • \( n \):需要配置汉明码的数据的位数。

这个公式很容易理解,可以这么分析:

  1. \( k \)个二进制校验位一共可以表示\( 2^k\)种状态。
  2. \( n + k \)是配置完汉明码后的数据的位数。
  3. 显然\( 2^k \)个状态中要能表示某一位是否出错,共\( n + k \)种情况。
  4. \( 2^k \)个状态也要能表示数没有出错这一情况。
  5. 所以\( 2^k \geq n + k + 1 \)

校验位的位置

第\( i \)组的校验位所在的位置是\( 2^i \space (i = 0, 1, 2, 3, ……) \)

确定每个组的包含的数据

确认了校验位的位置后即可确认每个分组所包含哪些数据。如我要对0011配置海明码,可以列如下表格

  1. 填入校验位
    图片加载失败
  2. 从左到右依次地将待配置的数据的高位,次高位……填入表格的空位中
    图片加载失败
  3. 各个校验码\( C_i \)所承担的检测小组为:
    • \( C_1承担检测第1,3,5,7,9,11,……位 \),即对应位的二进制表示为\( XX…XX1 \)
    • \( C_2承担检测第2,3,6,7,10,11,……位 \),即对应位的二进制表示为\( XX…X1X \)
    • \( C_4承担检测第4,5,6,7,12,13,……位 \),即对应位的二进制表示为\( XX…1XX \)
    • \( C_8承担检测第8,9,10,11,12,13,……位 \),即对应位的二进制表示为\( XX…1XXX \)
    • 以此类推

校验位的取值

校验位\( C_i \)的取值和采用的是奇校验还是偶校验有有关。

  • 采用偶校验:\( C_i = 第i组内所有的数进行异或的结果 \)
  • 采用奇校验:\( C_i = 第i组内所有的数进行异或的结果然后取反 \)

举例

则对于数据\(0011\)配置海明码,可以列如下表格

图片加载失败

汉明码(海明码)的纠错

数据接收方需要知道发送方采用的是奇校验还是偶校验,以及是否采用的汉明码。

确定数据中含有多少个校验位

同时也是确定数据被分为的几组,因为组和校验位是一一对应的。

  1. 我们拿到了长度\(m\)的二进制数据。
  2. 根据公式\( 2^k \geq n + k + 1 \)可以知道,\(n + k = m \)。
  3. 可以通过简单的枚举得出\(k\)的数值。

验证每个校验位的值是否准确

就是将每个检测位和检测位对应数据进行异或运算,如果为0则代表该组中出现错误。

纠正出错的数据

将每个检测位按下标从高到低排列组成一个二进制数,这个二进制数的十进制就对应了哪一位出错,如果检测位均为0则数据没有出错。

举例

例子一

  1. 接收到一个数据为\(100_0011\),采用的是偶校验
  2. 共有7位,根据公式\( 2^k \geq n + k + 1 \)可以直到数据中包含有3个校验位
  3. 分别计算3个校验位的值
    • \(P_1 = 1 \oplus 0 \oplus 0 \oplus 1 \ = 0,无错\)
    • \(P_2 = 0 \oplus 0 \oplus 1 \oplus 1 \ = 0,无错\)
    • \(P_4 = 0 \oplus 0 \oplus 1 \oplus 1 \ = 0,无错\)
  4. 将每个检测位按下标从高到低排列组成一个二进制数,这个二进制数的十进制就对应了哪一位出错,如果检测位均为0则数据没有出错。
    • \( P_4 P_2 P_1 = 000 ,没有出错\)

例子二

图片加载失败

一个有意思的情况

汉明码的配置和纠错过程可以用矩阵运算来表示,如果我们依旧对0011按照奇校验配置海明码如何用矩阵运算来表示呢?

图片加载失败

是不是很神奇?不要问我为什么,我也不知道,如果有大佬知道还请在评论回复一下。