错误检测与纠正码

---

---

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

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

• 错误检测码
• 错误纠正码

错误检测码

错误检测码用于检测接收到的数据（比特流）中存在的错误。这些代码包含一些比特，这些比特被包含（附加）到原始比特流中。如果在原始数据（比特流）传输过程中发生错误，这些代码会检测到该错误。

示例 - 奇偶校验码，汉明码。

错误纠正码

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

示例 - 汉明码。

因此，为了检测和纠正错误，在传输时会在数据位后面附加额外的位。

奇偶校验码

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

偶校验码

如果二进制码中存在偶数个1，则偶校验位的取值为零。否则，它应该为一。这样，偶校验码中存在偶数个1。偶校验码包含数据位和偶校验位。

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

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

• 如果另一个系统接收了这些偶校验码之一，则接收到的数据中没有错误。除偶校验位之外的位与二进制码的位相同。
• 如果另一个系统接收到的不是偶校验码，则接收到的数据中存在错误。在这种情况下，我们无法预测原始二进制码，因为我们不知道错误的位位置。

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

奇校验码

如果二进制码中存在奇数个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₃) 中。只需对该位中存在的值取反，并删除奇偶校验位以获得原始的二进制代码。