Digital-electronics 简明教程

Error Detection & Correction Codes

我们知道，0 和 1 位对应于两个不同的模拟电压范围。因此，在从一个系统向另一个系统传输二进制数据期间，也可能添加噪声。由于这个原因，在另一个系统中接收到的数据中可能存在错误。

We know that the bits 0 and 1 corresponding to two different range of analog voltages. So, during transmission of binary data from one system to the other, the noise may also be added. Due to this, there may be errors in the received data at other system.

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

That means a bit 0 may change to 1 or a bit 1 may change to 0. We can’t avoid the interference of noise. But, we can get back the original data first by detecting whether any error(s) present and then correcting those errors. For this purpose, we can use the following codes.

  1. Error Detection Codes

  2. Error Correction Codes

Error Detection Codes

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

Error detection codes are used to detect the error(s) present in the received data (bit stream). These codes contain some bit(s), which are included (appended) to the original bit stream. These codes detect the error, if it is occurred during transmission of the original data (bit stream).

Example - 奇偶校验码，汉明码。

Example − Parity code, Hamming code.

Error Correction Codes

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

Error correction codes are used to correct the error(s) present in the received data (bit stream) so that, we will get the original data. Error correction codes also use the similar strategy of error detection codes.

Example - 汉明码。

Example − Hamming code.

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

Therefore, to detect and correct the errors, additional bit(s) are appended to the data bits at the time of transmission.

Parity Code

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

It is easy to include (append) one parity bit either to the left of MSB or to the right of LSB of original bit stream. There are two types of parity codes, namely even parity code and odd parity code based on the type of parity being chosen.

Even Parity Code

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

The value of even parity bit should be zero, if even number of ones present in the binary code. Otherwise, it should be one. So that, even number of ones present in even parity code. Even parity code contains the data bits and even parity bit.

下表显示了对应于每个 3 位二进制码的 even parity codes 。在此，偶校验位包含在二进制码的 LSB 右侧。

The following table shows the even parity codes corresponding to each 3-bit binary code. Here, the even parity bit is included to the right of LSB of binary code.

Binary Code

Even Parity Bit

Even Parity Code

000

0

0000

001

1

0011

010

1

0101

011

0

0110

100

1

1001

101

0

1010

110

0

1100

111

1

1111

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

Here, the number of bits present in the even parity codes is 4. So, the possible even number of ones in these even parity codes are 0, 2 & 4.

  1. If the other system receives one of these even parity codes, then there is no error in the received data. The bits other than even parity bit are same as that of binary code.

  2. If the other system receives other than even parity codes, then there will be an error(s) in the received data. In this case, we can’t predict the original binary code because we don’t know the bit position(s) of error.

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

Therefore, even parity bit is useful only for detection of error in the received parity code. But, it is not sufficient to correct the error.

Odd Parity Code

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

The value of odd parity bit should be zero, if odd number of ones present in the binary code. Otherwise, it should be one. So that, odd number of ones present in odd parity code. Odd parity code contains the data bits and odd parity bit.

下表显示了 odd parity codes 与每个 3 位二进制代码对应的关系。此处，奇偶校验位包含在二进制代码 LSB 的右侧。

The following table shows the odd parity codes corresponding to each 3-bit binary code. Here, the odd parity bit is included to the right of LSB of binary code.

Binary Code

Odd Parity Bit

Odd Parity Code

000

1

0001

001

0

0010

010

0

0100

011

1

0111

100

0

1000

101

1

1011

110

1

1101

111

0

1110

此处，奇偶校验代码中存在的位数为 4。因此，这些奇偶校验代码中可能出现的奇数字为 1 和 3。

Here, the number of bits present in the odd parity codes is 4. So, the possible odd number of ones in these odd parity codes are 1 & 3.

  1. If the other system receives one of these odd parity codes, then there is no error in the received data. The bits other than odd parity bit are same as that of binary code.

  2. If the other system receives other than odd parity codes, then there is an error(s) in the received data. In this case, we can’t predict the original binary code because we don’t know the bit position(s) of error.

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

Therefore, odd parity bit is useful only for detection of error in the received parity code. But, it is not sufficient to correct the error.

Hamming Code

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

Hamming code is useful for both detection and correction of error present in the received data. This code uses multiple parity bits and we have to place these parity bits in the positions of powers of 2.

满足下面等式 (有效) 的 minimum value of 'k' 即所需奇偶校验位的数量。

The minimum value of 'k' for which the following relation is correct (valid) is nothing but the required number of parity bits.

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

其中，

Where,

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

'n' is the number of bits in the binary code (information)

'k' 是奇偶校验位的数量

'k' is the number of parity bits

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

Therefore, the number of bits in the Hamming code is equal to n + k.

设 Hamming code 为 $\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”位。

Let the Hamming code is $\mathrm{b_{n+k}b_{n+k-1} \: …​.. \: b_{3}b_{2}b_{1}}$ & parity bits $\mathrm{p_{k}, \: p_{k-1}, \: …​. \: p_{1}}$. We can place the 'k' parity bits in powers of 2 positions only. In remaining bit positions, we can place the ‘n’ bits of binary code.

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

Based on requirement, we can use either even parity or odd parity while forming a Hamming code. But, the same parity technique should be used in order to find whether any error present in the received data.

请按照以下步骤查找 parity bits 。

Follow this procedure for finding parity bits.

  1. Find the value of p1, based on the number of ones present in bit positions b3, b5, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 20.

  2. Find the value of p2, based on the number of ones present in bit positions b3, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 21.

  3. Find the value of p3, based on the number of ones present in bit positions b5, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 22.

  4. Similarly, find other values of parity bits.

请按照以下步骤查找 check bits 。

Follow this procedure for finding check bits.

  1. Find the value of c1, based on the number of ones present in bit positions b1, b3, b5, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 20.

  2. Find the value of c2, based on the number of ones present in bit positions b2, b3, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 21.

  3. Find the value of c3, based on the number of ones present in bit positions b4, b5, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 22.

  4. Similarly, find other values of check bits.

接收数据中的校验位的十进制等效值提供了存在错误的二进制位的值。只需对该二进制位中的值取反即可。因此，在移除奇偶校验位后，我们将获得原始二进制代码。

The decimal equivalent of the check bits in the received data gives the value of bit position, where the error is present. Just complement the value present in that bit position. Therefore, we will get the original binary code after removing parity bits.

Example 1

让我们为二进制代码 d4d3d2d1 = 1000 找出海明码。考虑偶校验位。

Let us find the Hamming code for binary code, d4d3d2d1 = 1000. Consider even parity bits.

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

The number of bits in the given binary code is n=4.

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

We can find the required number of parity bits by using the following mathematical relation.

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

在上述数学关系中替换 n=4。

Substitute, n=4 in the above mathematical relation.

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

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

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

The minimum value of k that satisfied the above relation is 3. Hence, we require 3 parity bits p1, p2, and p3. Therefore, the number of bits in Hamming code will be 7, since there are 4 bits in binary code and 3 parity bits. We have to place the parity bits and bits of binary code in the Hamming code as shown below.

7-bit Hamming code 为 -

The 7-bit Hamming code is −

\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}}

通过替换二进制代码的位，海明码将为

By substituting the bits of binary code, the Hamming code will be

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

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

Now, let us find the parity bits.

\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}

P3:=b7⊕b6⊕b5=1⊕0⊕0=1

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

通过替换这些奇偶校验位，s0将为 −

By substituting these parity bits, the Hamming code will be −

b7b6b5b4b3b2b1:=1001011

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

Example 2

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

In the above example, we got the Hamming code as −

b7b6b5b4b3b2b1=1001011。

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

现在，让我们找出接收到的码的错误位置 −

Now, let us find the error position when the code received is −

b7b6b5b4b3b2b1=1001111

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

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

Now, let us find the check bits.

c1:=b7⊕b5⊕b3⊕b1:=1⊕0⊕1⊕1:=1

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

c2:=b7⊕b6⊕b3⊕b2:=1⊕0⊕1⊕1:=1

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

c3:=b7⊕b6⊕b5⊕b4:=1⊕0⊕0⊕1:=0

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

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

The decimal value of check bits gives the position of error in received Hamming code.

c3c2c1:=（011）@s1{10}

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

因此，汉明码存在于第三位（b3）中。只要对该位上的当前值求补，然后移除奇偶校验位，就能获得原始二进制码。

Therefore, the error present in third bit (b3) of Hamming code. Just complement the value present in that bit and remove parity bits in order to get the original binary code.