计算机网络中的汉明码

在计算机网络中，汉明码用于表示一组纠错码，当数据从发送方移动到接收方时可能会发生这种情况。汉明方法通过查找发生错误的状态来纠正错误。

冗余位

冗余位是额外的二进制位，它们被生成并添加到数据传输的信息承载位中，以确保在数据传输过程中不会丢失任何位。冗余位被放置在某些计算位置以消除错误，两个冗余位之间的距离称为"汉明距离"。

纠错码 − 这是数据位和冗余位之间的关系，用于纠正单比特错误。一个帧由M个数据位和R个冗余位组成，设该帧的总长度为N(N=M+R)。包含数据和校验位的 N 位单元通常称为 N 位码字。

以下公式用于查找冗余位数。

单比特错误数 = M + R

无错误的状态数 = 1

因此，代表所有状态 (M+R+1) 的冗余位数 (R) 必须满足 −

2^𝑅 ≥ 𝑀 + 𝑅 + 1

其中 R = 冗余位，M = 数据位。

查找汉明码的步骤

汉明方法使用额外的奇偶校验位来识别单比特错误。

• 步骤 1 - 首先以二进制形式从 1 开始写入位位置(1、10、11、100 等)
• 步骤 2 - 将所有 2 的幂的位位置标记为奇偶校验位(1、2、4、8、16、32、64 等)
• 步骤 3 - 所有其他位位置用于要编码的数据(3、5、6、7、9、10 和 11 等)

每个奇偶校验位计算代码字中某些位的奇偶校验。奇偶校验的位置决定了它交替检查和跳过的位序列。

• 位置 1 - 检查 1 位，然后跳过 1 位，检查 1 位，然后跳过 1 位，依此类推(例如 - 1,3,5,7,11 等)
• 位置 2 - 检查 2 位，然后跳过 2 位，检查 2 位，然后跳过 2 位(例如 - 2,3,6,7,10,11,14,15 等)
• 位置 4 - 检查 4 位，然后跳过 4 位，检查 4 位，然后跳过 4 位(例如 - 4、5、6、7、12、13、14、15 等)
• 位置 8 - 检查8 位，然后跳过 8 位，检查 8 位，然后跳过 8 位(例如 - 8、9、10、11、12、13、14、15、24、25、26、27、28、29、30、31)。

注意 - 如果检查的位置中的 1 的总数为奇数，则将奇偶校验位设置为 1;如果检查的位置中的 1 的总数为偶数，则将奇偶校验位设置为 0。

示例

为数据字节 1001101 构造偶校验汉明码字。

位数(1001101)为 7。

r 的值计算为 -

2^𝑅 ≥ 𝑀 + 𝑅 + 1

⇒ 2⁴ ≥ 7 + 4 + 1

因此，冗余位数 = 4

现在，让我们计算所需的奇偶校验位数。

我们取 𝑃 = 2， 然后 2^𝑃 = 2² = 4 和 𝑛 + 𝑃 + 1 = 4 + 2 + 1 = 7

2 个奇偶校验位不足以容纳 4 位数据。

现在，我们取 𝑃 = 3，然后 2^𝑃 = 2³ = 8 和 𝑛 + 𝑃 + 1 = 4 + 3 + 1 = 8

因此，3 个奇偶校验位足以容纳 4 位数据。

代码字中的总位数为 − 4 + 3 = 7

位置 1:检查位 1、3、5、7、9 和11.

? _1_0 0 1_1 0 1 0.在位置 1 中为偶校验，因此将位置 1 设置为 0:0_1_0 0 1_1 0 1 0.

位置 2:检查位 2、3、6、7、10、11。

0 ? 1_0 0 1_1 0 1 0。在位置 2 奇校验，因此将位置 2 设置为 1:0 1 1_0 0 1_1 0 1 0

位置 4 检查位4,5,6,7,12。

0 1 1 ? 0 0 1_1 0 1 0。在位置 4 奇校验，因此将位置 4 设置为 1:0 1 1 1 0 0 1_1 0 1 0

位置 8 检查位8,9,10,11,12。

0 1 1 1 0 0 1 ? 1 0 1 0. 在位置 8 中为偶校验，因此将位置 8 设置为 1:0 1 1 1 0 0 1 0 1 0 1 0

代码字 = 011100101010