错误检测和校正代码

我们知道位 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' 的最小值只不过是所需的奇偶校验位数。

$$\mathrm{2^{k} \: \geq \: n \: + \: k \: + \: 1}$$

其中，

'n' 是二进制代码(信息)中的位数

'k' 是奇偶校验位数

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

让 汉明码 为$\mathrm{b_{n+k}b_{n+k-1} \: ..... \: b_{3}b_{2}b_{1}}$ & 奇偶校验位 $\mathrm{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。

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

$$\mathrm{2^{k} \: \geq \: n \: + \: k \: + \: 1}$$

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

$$\mathrm{\Rightarrow \: 2^{k} \: \geq \: 4+k+1}$$

$$\mathrm{\Rightarrow \: 2^{k} \: \geq \: 5+k}$$

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

7 位汉明码为 −

$$\mathrm{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}}$$

通过替换二进制码的位，汉明码将是

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} \: = \: 100p_{3}Op_{2}p_{1}}$$

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

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

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

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

通过替换这些奇偶校验位，汉明码将为 −

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} \: = \: 1001011}$$

示例 2

在上面的例子中，我们得到的汉明码为 −

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011}$$.

现在，让我们找出收到的代码为−

$$\mathrm{b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001111}$$

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

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

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

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

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

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

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