错误纠正码 – 汉明码

错误和错误纠正码

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

错误纠正码 （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的数量要么是偶数，要么是奇数。两种类型的奇偶校验位是−