计算机网络中的汉明码

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

冗余位

冗余位是额外生成的二进制位，添加到数据传输的信息位中，以确保在数据传输过程中没有丢失任何位。冗余位放置在某些计算出的位置以消除错误，两个冗余位之间的距离称为“汉明距离”。

纠错码 - 这是数据位和冗余位之间用于纠正单比特错误的关系。一个帧由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 - 将所有位位置标记为奇偶校验位（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

Urmila Samariya

更新于：2023年9月14日

35K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始