纠错

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

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

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

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

为了纠正错误，必须知道错误的精确位置。例如，如果我们想计算单比特错误，纠错码将确定七个比特中的哪一个出错。为了实现这一点，我们必须添加一些额外的冗余比特。

假设 r 是冗余比特的数量，d 是数据比特的总数。冗余比特 r 的数量可以通过以下公式计算

2r>=d+r+1

r 的值是通过使用上述公式计算的。例如，如果 d 的值为 4，那么满足上述关系的最小可能值为 3。

为了确定出错比特的位置，R.W Hamming 开发了一种名为 Hamming 码的技术，该技术可以应用于任何长度的数据单元，并利用数据单元和冗余单元之间的关系。

Hamming 码

奇偶校验位： 附加到原始二进制比特数据中的比特，以便 1 的总数是偶数或奇数。

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

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

Hamming 码算法

• 将“d”个信息比特与“r”个冗余比特组合形成 d+r。
• 为 (d+r) 个数字中的每一个分配一个十进制值作为其位置。
• r 个比特位于位置 1, 2, ..., 2^k-1。
• 在接收端，重新计算奇偶校验位。奇偶校验位的十进制值决定了错误的位置。

错误位置与二进制数之间的关系。

让我们通过一个例子来理解 Hamming 码的概念

假设原始数据是 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、2¹、2²。

添加奇偶校验位后的数据表示

确定奇偶校验位

确定 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。