计算机网络：纠错

本文概述

• 海明码
• 关系b / w错误位置和二进制数。
• 确定冗余位的位置
• 确定奇偶校验位

当数据从发送方发送到接收方时, 纠错码用于检测和纠正错误。

纠错可以通过两种方式处理：

• 向后纠错：发现错误后, 接收方会请求发送方重新传输整个数据单元。
• 前向纠错：在这种情况下, 接收器使用纠错码自动纠正错误。

单个附加位可以检测到错误, 但无法纠正。

为了纠正错误, 必须知道错误的确切位置。例如, 如果我们要计算一位错误, 则纠错码将确定错误的七位中的哪一位。为此, 我们必须添加一些额外的冗余位。

假设r是冗余位数, d是数据位数。冗余位数r可以使用以下公式计算：

2r>=d+r+1

r的值通过使用以上公式来计算。例如, 如果d的值为4, 则满足上述关系的可能的最小值将为3。

为了确定错误的位的位置, R.W Hamming开发的技术是Hamming码, 可以将其应用于任何长度的数据单元, 并使用数据单元和冗余单元之间的关系。

海明码

奇偶校验位：附加到二进制位原始数据的位, 以使总数为1的数为偶数或奇数。

偶数奇偶校验：要检查偶数奇偶校验, 如果1的总数为偶数, 则奇偶校验位的值为0。如果1的总数为奇数, 则奇偶校验位的值为1。

奇数奇偶校验：要检查奇数奇偶校验, 如果1的总数为偶数, 则奇偶校验位的值为1。如果1的总数为奇数, 则奇偶校验位的值为0。

海明码算法：

• 将“ d”位的信息添加到冗余位“ r”以形成d + r。
• 每个（d + r）位的位置都分配了一个十进制值。
• “ r”位放置在位置1, 2, ….. 2k-1中。
• 在接收端, 重新计算奇偶校验位。奇偶校验位的十进制值确定错误的位置。

关系b / w错误位置和二进制数。

让我们通过一个例子来理解汉明代码的概念：

假设要发送的原始数据是1010。

Total number of data bits 'd' = 4
Number of redundant bits r : 2r >= d+r+1
                           2r>= 4+r+1
Therefore, the value of r is 3 that satisfies the above relation.
Total number of bits = d+r = 4+3 = 7;

确定冗余位的位置

冗余位数为3。这三个位数分别由r1, r2, r4表示。计算冗余位的位置对应于提升的功率2。因此, 它们的对应位置是1、21、22。

The position of r1 = 1
The position of r2 = 2
The position of r4 = 4

附加奇偶校验位的数据表示：

确定奇偶校验位

确定r1位

通过对在第一位置中二进制表示为1的位位置执行奇偶校验来计算r1位。

从上图中我们观察到, 在第一个位置包含1的位位置是1、3、5、7。现在, 我们在这些位位置执行偶校验。在这些对应于r1的位位置上的总数1为偶数, 因此r1位的值为0。

确定r2位

通过对二进制位置在第二位置中包含1的位位置执行奇偶校验来计算r2位。

从上图可以看出, 在第二个位置包含1的位位置是2、3、6、7。现在, 我们在这些位位置执行偶校验。在与r2对应的这些位位置上的总数1为奇数, 因此r2位的值为1。

确定r4位

通过对二进制位置在第三位置中包含1的位位置执行奇偶校验来计算r4位。

从上图中我们观察到, 在第三位置包含1的位位置是4、5、6、7。现在, 我们在这些位位置执行偶校验。在这些对应于r4的位位置上的总数1为偶数, 因此r4位的值为0。

传输的数据如下：

假设在接收端将第4位从0更改为1, 然后重新计算奇偶校验位。

R1位

r1位的位位置是1, 3, 5, 7

从上图可以看出, r1的二进制表示为1100。现在, 我们执行偶校验检查, r1位中出现的1的总数为偶数。因此, r1的值为0。

R2位

r2位的位位置是2、3、6、7。

从上图可以看出, r2的二进制表示为1001。现在, 我们执行偶校验检查, 出现在r2位中的1的总数为偶数。因此, r2的值为0。

R4位

r4位的位位置是4, 5, 6, 7。

从上图可以看出, r4的二进制表示为1011。现在, 我们执行偶校验检查, r4位中出现的1的总数为奇数。因此, r4的值为1。

• 冗余位的二进制表示形式, 即r4r2r1为100, 其对应的十进制值为4。因此, 在第4位位置发生错误。该位值必须从1更改为0以纠正错误。