错误检测和纠正代码

---

我们知道位0和位1对应于两个不同范围的模拟电压。因此，在二进制数据从一个系统传输到另一系统的过程中，也可能会添加噪声。因此，其他系统接收到的数据可能会出现错误。

这意味着比特0可能会变成1，或者比特1可能会变成0。我们无法避免噪声的干扰。但是，我们可以首先通过检测是否存在任何错误来恢复原始数据，然后纠正这些错误。为此，我们可以使用以下代码。

• 错误检测代码
• 纠错码

错误检测代码- 用于检测接收到的数据（比特流）中存在的错误。这些代码包含一些位，这些位被包含（附加）到原始位流中。如果错误发生在原始数据（比特流）的传输过程中，这些代码就会检测到该错误。示例- 奇偶校验码、汉明码。

纠错码- 用于纠正接收到的数据（比特流）中存在的错误，以便我们得到原始数据。纠错码也采用与检错码类似的策略。示例- 汉明码。

因此，为了检测和纠正错误，在传输时将附加位附加到数据位。

奇偶校验码

在原始比特流的 MSB 左侧或 LSB 右侧包含（附加）一个奇偶校验位很容易。根据所选择的奇偶校验类型，奇偶校验码有两种类型，即偶校验码和奇奇偶校验码。

偶校验码

如果二进制代码中存在偶数个，则偶校验位的值应为零。否则，应该是一。因此，偶校验码中存在偶数个。偶校验码包含数据位和偶校验位。

下表列出了每个 3 位二进制码对应的偶校验码。这里，偶校验位包含在二进制代码的LSB右侧。

这里，偶校验码中存在的位数是 4。因此，这些偶校验码中可能的偶数个是 0、2 和 4。

• 如果其他系统接收到这些偶校验码之一，则接收到的数据没有错误。除偶校验位外的其他位与二进制码相同。

• 如果其他系统接收到奇偶校验码以外的数据，则接收到的数据中将会出现错误。在这种情况下，我们无法预测原始二进制代码，因为我们不知道错误的位位置。

因此，偶校验位仅对于检测接收到的奇偶校验码中的错误有用。但是，这还不足以纠正错误。

奇校验码

如果二进制代码中存在奇数个奇数奇偶校验位，则奇数奇偶校验位的值应为零。否则，应该是一。因此，奇数奇偶校验码中存在奇数个。奇校验码包含数据位和奇校验位。

下表列出了每个 3 位二进制码对应的奇数奇偶校验码。这里，奇校验位包含在二进制代码的LSB右侧。

这里，奇数奇偶校验码中存在的位数为 4。因此，这些奇数奇偶校验码中可能的奇数个为 1 和 3。

• 如果其他系统接收到这些奇数奇偶校验码之一，则接收到的数据没有错误。除奇校验位外的其他位与二进制码相同。

• 如果其他系统接收到非奇数奇偶校验码，则接收到的数据中存在错误。在这种情况下，我们无法预测原始二进制代码，因为我们不知道错误的位位置。

因此，奇校验位仅用于检测接收到的奇偶校验码中的错误。但是，这还不足以纠正错误。

汉明码

汉明码对于检测和纠正接收数据中存在的错误非常有用。该代码使用多个奇偶校验位，我们必须将这些奇偶校验位放置在 2 的幂的位置。

以下关系正确（有效）的“k”的最小值只不过是所需的奇偶校验位的数量。

$$2^k\geq n+k+1$$

在哪里，

“n”是二进制代码（信息）中的位数

“k”是奇偶校验位的数量

因此，汉明码的位数等于n+k。

设汉明码为 $b_{n+k}b_{n+k-1}.....b_{3}b_{2}b_{1}$ 和奇偶校验位 $p_{k}, p_{k -1}，....p_{1}$。我们只能将“k”个奇偶校验位放置在 2 的幂位置上。在剩余的位位置中，我们可以放置“n”位二进制代码。

根据需要，我们在形成汉明码时可以使用偶校验或奇校验。但是，应该使用相同的奇偶校验技术来查找接收的数据中是否存在任何错误。

按照此过程查找奇偶校验位。

• _{根据位位置 b 3}、b ₅、b ₇等中存在的 1 的数量查找p ₁的值。所有这些位位置（后缀）在其等效二进制中的位置值 2 ⁰中都有“1” 。

• _{根据位位置 b 3}、b ₆、b ₇等中存在的 1 的数量查找p ₂的值。所有这些位位置（后缀）在其等效二进制中的位置值 2 ¹中都有“1” 。

• _{根据位位置 b 5}、b ₆、b ₇等中存在的 1 的数量查找p ₃的值。^{所有这些位位置（后缀）在其等效二进制中的 2 2}位置值中都有“1” 。

• 同理，求出其他奇偶校验位的值。

按照此过程查找校验位。

• _{根据位位置 b 1}、b ₃、b ₅、b ₇等中存在的 1 的数量查找 c ₁的值。所有这些位位置（后缀）在其等效二进制中的位置值 2 ⁰中都有“1” 。

• _{根据位位置 b 2}、b ₃、b ₆、b ₇等中存在的 1 的数量查找 c ₂的值。所有这些位位置（后缀）在其等效二进制中的位置值 2 ¹中都有“1” 。

• _{根据位位置 b 4}、b ₅、b ₆、b ₇等中存在的 1 的数量查找 c ₃的值。^{所有这些位位置（后缀）在其等效二进制中的 2 2}位置值中都有“1” 。

• 同理，求出其他校验位的值。

接收到的数据中校验位的十进制等效值给出了出现错误的位位置的值。只需补充该位位置中存在的值即可。因此，去掉奇偶校验位后，我们就得到了原始的二进制码。

实施例1

让我们找到二进制代码的汉明码，d ₄ d ₃ d ₂ d ₁ = 1000。考虑偶校验位。

给定二进制代码中的位数为n=4。

我们可以使用以下数学关系找到所需的奇偶校验位数量。

$$2^k\geq n+k+1$$

代入上述数学关系式中，n=4。

$$\右箭头 2^k\geq 4+k+1$$

$$\右箭头 2^k\geq 5+k$$

满足上述关系的k的最小值为3。因此，我们需要3个奇偶校验位p ₁、p ₂和p ₃。因此，汉明码的位数将为 7，因为二进制码有 4 位和 3 个奇偶校验位。我们必须将奇偶校验位和二进制码位放入汉明码中，如下所示。

7位汉明码为 $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}=d_{4}d_{3}d_{2}p_ {3}d_{1}p_{2}bp_{1}$

通过替换二进制码的位，汉明码将是 $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} = 100p_{3}Op_{2 }p_{1}$。现在，让我们找到奇偶校验位。

$$p_{1}=b_{7}\oplus b_{5}\oplus b_{3}=1 \oplus 0 \oplus 0=1$$

$$p_{2}=b_{7}\oplus b_{6}\oplus b_{3}=1 \oplus 0 \oplus 0=1$$

$$p_{3}=b_{7}\oplus b_{6}\oplus b_{5}=1 \oplus 0 \oplus 0=1$$

通过替换这些奇偶校验位，汉明码将为 $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011$。

实施例2

在上面的示例中，我们得到的汉明码为 $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011$。现在，让我们找到当收到的代码为 $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001111$ 时的错误位置。

现在，让我们找到校验位。

$$c_{1}=b_{7}\oplus b_{5}\oplus b_{3}\oplus b_{1}=1 \oplus 0 \oplus 1 \oplus1 =1$$

$$c_{2}=b_{7}\oplus b_{6}\oplus b_{3}\oplus b_{2}=1 \oplus 0 \oplus 1 \oplus1 =1$$

$$c_{3}=b_{7}\oplus b_{6}\oplus b_{5}\oplus b_{4}=1 \oplus 0 \oplus 0 \oplus1 =0$$

校验位的十进制值给出了接收到的汉明码中的错误位置。

$$c_{3}c_{2}c_{1} = \left ( 011 \right )_{2}=\left ( 3 \right )_{10}$$

因此，错误出现在汉明码的第三位(b _{3 )中。}只需补充该位中存在的值并删除奇偶校验位即可获得原始二进制代码。