错误纠正码 – 汉明码

错误和错误纠正码

当比特在计算机网络上传输时，由于干扰和网络问题，它们容易受到损坏。损坏的比特导致接收方接收到伪数据，即错误。

错误纠正码 （ECC）是由特定算法生成的一系列数字，用于检测和纠正在嘈杂信道上传输的数据中的错误。错误纠正码确定已损坏的比特数量以及在算法限制内已损坏的比特位置。

ECC可以广泛分为两种类型−

• 块码 − 将消息分成固定大小的比特块，为了错误检测或纠正，在块中添加冗余比特。

• 卷积码 − 消息包括任意长度的数据流，通过对数据流应用滑动的布尔函数生成奇偶符号。

汉明码

汉明码是一种块码，能够检测两个同时出现的比特错误并纠正单个比特错误。它由R.W. Hamming开发用于错误纠正。

在这种编码方法中，源将冗余比特插入消息中。这些冗余比特是额外生成并插入到消息中特定位置的比特，以实现错误检测和纠正。当目标接收到该消息时，它将进行重新计算以检测错误并找到出错的比特位置。

用汉明码编码消息

发送方用于编码消息的过程包括以下步骤−

• 步骤1 − 计算冗余比特的数量。

• 步骤2 − 定位冗余比特。

• 步骤3 − 计算每个冗余比特的值。

一旦冗余比特嵌入消息中，就会发送给用户。

步骤1 − 计算冗余比特的数量。

如果消息包含 m M个数据位， r r个冗余位被添加到它上面，以便 m r能够表示至少( m + r + 1)个不同的状态。这里，( m + r )表示(𝑚 + 𝑟)位位置中的一个错误位置，而一个额外的状态表示没有错误。因为， r r位可以表示2 r r个状态，而2 r r必须至少等于( m + r + 1)。因此以下方程式应成立 2 r ≥ m+r+1

第2步-定位冗余位。

即放置在2的幂位的r个冗余位，即1, 2, 4, 8, 16等处。在本文的其余部分中称为 _r 1 _ (位于位置1), _r 2 _ (位于位置2), _r 3 _ (位于位置4), _r 4 _ (位于位置8)等等。

第3步-计算每个冗余位的值。

冗余位是奇偶校验位。奇偶校验位是一个额外的位，使得1的数量要么是偶数，要么是奇数。两种类型的奇偶校验位是−

• 偶校验 - 此时消息中的位数变为偶数。

• 奇校验 - 此时消息中的位数变为奇数。

每个冗余位r i ，通常是根据其位位置计算奇偶校验位（通常为偶校验位）。它涵盖了其二进制表示中包含第i位为1的所有位位置，除了r i 位的位置。因此−

• 1 位是所有二进制表示中，最低位排除 1 后包含 1 的数据位的奇偶校验位（3、5、7、9、11 等）

• 2 位是从右边算起，位置为 2 的二进制表示中排除 2 的数据位的奇偶校验位（3、6、7、10、11 等）

• 3 位是从右边算起，位置为 3 的二进制表示中排除 4 的数据位的奇偶校验位（5-7、12-15、20-23 等）

解码汉明码消息

接收器接收到传入消息后，执行重新计算以检测并纠正错误。重新计算的步骤如下：

• 第一步 − 计算冗余位的数量。

• 第二步 − 定位冗余位。

• 第三步 − 奇偶校验。

• 第四步 − 错误检测和纠正

第一步 − 计算冗余位的数量

使用与编码中相同的公式确定冗余位的数量。

2 r ≥ m + r + 1，其中 m 是数据位的数量，而 r 是冗余位的数量。

第二步 − 定位冗余位

冗余位放在 2 的幂位置，即 1、2、4、8、16 等。

第三步 − 奇偶校验

奇偶校验位是根据数据位和冗余位使用与生成码中的 c 的相同规则计算的。

c = parity(1, 3, 5, 7, 9, 11 等)

c = parity(2, 3, 6, 7, 10, 11 等)

c = parity(4-7, 12-15, 20-23 等)

第四步 − 错误检测和纠正

计算奇偶校验位的二进制值的十进制等价值。如果为0，则没有错误。否则，十进制值表示出现错误的位位置。例如，如果c 1 c 2 c 3 c 4 = 1001，则表示在位置9上的数据位（十进制等价值为1001）出现错误。将该位翻转以获取正确的消息。