错误检测和校正代码

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

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

• 错误检测代码
• 错误校正代码

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

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

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

奇偶校验码

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

偶校验码

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

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

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

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

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

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

奇校验码

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

下表显示了与每个 3 位二进制代码相对应的奇校验码。这里，奇校验位包含在二进制代码的 LSB 右侧。

这里，奇校验码中存在的位数为 4。因此，这些奇校验码中可能的奇数个 1 为 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₃、b₅、b₇ 等中存在的 1 的数量，查找 p₁ 的值。所有这些位位置（后缀）在其等效二进制中，在 2⁰ 的位置值中都有"1"。

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

• 根据位位置 b₅、b₆、b₇ 等中存在的 1 的数量，查找 p₃ 的值。所有这些位位置（后缀）在其等效二进制中，在 2² 的位置值中都有"1"。

• 类似地，找到奇偶校验位的其他值。

按照此过程查找校验位。

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

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

• 根据位位置 b₄、b₅、b₆、b₇ 等中存在的 1 的数量，找到 c₃ 的值。所有这些位位置（后缀）在其等效二进制中的位置值 2² 都是"1"。

• 类似地，找到校验位的其他值。

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

示例 1

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

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

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

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

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

$$\Rightarrow 2^k\geq 4+k+1$$

$$\Rightarrow 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 ight )_{2}=\left ( 3 ight )_{10}$$

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