汉明码：错误检测与纠正示例

什么是错误？

传输的数据在通信过程中可能会损坏。它很可能受到外部噪声或其他物理故障的影响。在这种情况下，输入数据不可能与输出数据相同。这种不匹配称为“错误”。

数据错误可能会导致重要或安全数据的丢失。数字系统中的大多数数据传输都是以“位传输”的形式进行的。即使是很小的变化也会影响整个系统的性能。在数据序列中，如果 1 更改为 0 或 0 更改为 1，则称为“位错误”。

错误类型

数据从发送方到接收方的传输过程中，主要发生三种类型的比特错误。

• 单比特错误
• 多比特错误
• 突发错误

单比特错误

整个数据序列中一位的变化称为“单比特错误”。但是，单比特错误的发生并不常见。此外，这种错误仅发生在并行通信系统中，因为数据在单条线路上按位传输。因此，单条线路出现噪声的可能性更大。

多位错误

在数据序列中，如果发送器到接收器的数据序列中有两位或多位发生变化，则称为“多位错误”。

这种类型的错误主要发生在串行和并行类型的数据通信网络中。

突发错误

数据序列中一组比特的变化称为“突发错误”。这种类型的数据错误是从第一个比特变化到最后一个比特变化计算的。

什么是错误检测和错误纠正？

在数字通信系统中，错误会从一个通信系统传输到另一个通信系统。如果这些错误未被发现并纠正，则数据将丢失。为了实现有效通信，系统数据应以高精度传输。这将通过首先识别错误并纠正错误来实现。

错误检测是一种检测数据通信系统中从发送器传输到接收器的数据中存在的错误的方法。

在这里，你可以使用冗余代码来查找这些错误，方法是在数据从源传输时将其添加到数据中。这些代码称为“错误检测代码”。

三种类型的错误检测码是：

• 奇偶校验
• 循环冗余校验（CRC）
• 纵向冗余校验（LRC）

奇偶校验

• 它也被称为奇偶校验。
• 它具有一种经济有效的错误检测机制。
• 在这种技术中，冗余位称为奇偶校验位。它附加在每个数据单元上。单元中的 1 的总数应为偶数，这称为奇偶校验位。

纵向冗余检查

在这种错误检测技术中，位块以表格格式组织。LRC 方法可帮助您计算每列的奇偶校验位。此奇偶校验集也与原始数据一起发送。奇偶校验块可帮助您检查冗余。

循环冗余校验

循环冗余校验是必须附加到单元末尾的冗余序列。这就是为什么生成的数据单元应该可以被第二个预定的二进制数整除。

在目的地，传入的数据需要除以相同的数字。如果没有余数，则认为数据单元正确并被接受。否则，表明数据单元在传输过程中受损，因此必须拒绝。

在汉明码中，信源通过在消息中添加冗余位来对消息进行编码。这些冗余位大多是在消息的某些位置插入和生成的，以实现错误检测和纠正过程。

汉明码的历史

• 汉明码是由RWHamming创建的一种用于检测错误的技术。
• 汉明码适用于任意长度的数据单元，利用数据与冗余位之间的关系。
• 他致力于研究纠错方法问题，并开发出一种功能日益强大的算法，称为汉明码。
• 1950 年，他发表了汉明码，该码如今广泛应用于 ECC 内存等应用。

汉明码的应用

以下是使用汉明码的一些常见应用：

• 卫星
• 电脑内存
• 调制解调器
• 等离子CAM
• 打开连接器
• 屏蔽线
• 嵌入式处理器

汉明码的优点

• 汉明码方法对于数据流中单比特错误的网络很有效。
• 汉明码不仅可以检测位错误，还可以帮助您缩进包含错误的位，以便进行纠正。
• 汉明码的易于使用使其非常适合用于计算机内存和单纠错。

汉明码的缺点

• 单比特错误检测和纠正码。但是，如果发现多个比特错误，则结果可能会导致另一个应该正确的比特被更改。这可能会导致数据进一步出错。
• 汉明码算法只能解决单个位的问题。

如何用汉明码对消息进行编码

发送方对消息进行编码的过程包括以下三个步骤：

• 计算冗余位的总数。
• 检查冗余位的位置。
• 最后计算这些冗余位的值。

当上述冗余位嵌入到消息中后，该消息就会发送给用户。

步骤1） 计算冗余位的总数。

假设该消息包含：

• n– 数据位数
• p – 添加的冗余位数，使得 np 可以指示至少 (n + p + 1) 个不同的状态。

这里，(n + p) 表示 (n + p) 个比特位置中错误的位置，一个额外的状态表示没有错误。由于 p 位可以表示 2^p 州，2^p 必须至少等于 (n + p + 1)。

步骤2） 将冗余位放置在正确的位置。

p 个冗余位应放置在 2 的幂的位位置上。例如，1、2、4、8、16 等。它们被称为 p₁ （在位置 1），p₂ （在位置 2），p₃ （在位置 4）等等。

步骤3） 计算冗余位的值。

冗余位应该是奇偶校验位，使得 1 的数量为偶数或奇数。

两种奇偶校验类型是？

• 消息中的位数总数为偶数称为偶校验。
• 消息中的位数总数为奇数称为奇校验。

这里，所有冗余位 p1 都必须计算为奇偶校验。它应覆盖除 p1 位置之外的所有二进制表示应在第 1 位包含 1 的位位置。

P1 是每个数据位的奇偶校验位，其二进制表示形式在较不重要的位置包含 1（不包括 1），例如（3、5、7、9、……）

P2 是二进制表示法中从右边起第 1 个位置为 2 的每个数据位的奇偶校验位，但不包括 2，例如（3、6、7、10、11、…）

P3 是二进制表示法中从右边开始第 1 位为 3 的位置（不包括第 4 位）的每个位的奇偶校验位，例如（5-7、12-15、…）

使用汉明码解密消息

接收方收到来电消息后需要重新计算以查找并纠正错误。

重新计算过程按以下步骤完成：

• 计算冗余位数。
• 正确定位所有冗余位。
• 奇偶校验

步骤1） 计算冗余位数

您可以使用相同的公式进行编码，冗余位数

2^p ?n+p+1

这里，p是数据位数，p是冗余位数。

步骤2） 正确定位所有冗余位

这里，p为冗余位，位于2的幂的位位置，例如1、2、4、8等。

步骤3） 奇偶校验

奇偶校验位需要根据数据位和冗余位来计算。

p1 = 奇偶校验（1、3、5、7、9、11…）

p2 = 奇偶校验（2、3、6、7、10、11…）

p3 = 奇偶校验（4-7、12-15、20-23…）

总结

• 传输的数据可能在通信过程中损坏
• 三种类型的位错误是 1) 单位错误 2) 多位错误 3) 突发位错误
• 整个数据序列中一位的改变称为“单一位错误”。
• 在数据序列中，如果发送器到接收器的数据序列中有两位或多位发生变化，则称为“多位错误”。
• 数据序列中比特集的变化称为“突发错误”。
• 错误检测是一种检测数据通信系统中从发送器传输到接收器的数据中存在的错误的方法
• 三种类型的错误检测码是 1）奇偶校验 2）循环冗余校验（CRC）3）纵向冗余校验（LRC）
• 汉明码是一种线性码，可用于检测最多两个直接位的错误。它能够检测单比特错误。
• 汉明码是由RWHamming创建的一种用于检测错误的技术。
• 使用汉明码的常见应用是卫星计算机内存、调制解调器、嵌入式处理器等。
• 汉明码方法的最大好处在于，它对给定单比特错误的数据流的网络有效。
• 汉明码方法最大的缺点是它只能解决单个位的问题。
• 我们可以借助汉明码执行加密和解码消息的过程。