数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究纠错码 - 海明码
错误和纠错码
当比特在计算机网络上传输时，由于干扰和网络问题，它们可能会被损坏。损坏的比特会导致接收方收到伪数据，这些数据被称为错误。
纠错码 (ECC) 是一系列由特定算法生成的数字，用于检测和消除通过噪声信道传输的数据中的错误。纠错码能够确定已损坏的比特的确切数量以及损坏比特的位置，但在算法的限制范围内。
ECC 可以广泛地分为两种类型 -
分组码 - 消息被分成固定大小的比特块，并在其中添加冗余比特以进行错误检测或纠正。
卷积码 - 消息包含任意长度的数据流，奇偶校验符号是通过对数据流进行布尔函数的滑动应用生成的。
海明码
海明码是一种分组码，能够检测多达两个同时发生的比特错误并纠正单个比特错误。它由 R.W. 海明开发用于纠错。
在这种编码方法中，源通过在消息中插入冗余比特来对消息进行编码。这些冗余比特是在消息本身的特定位置生成并插入的额外比特，用于启用错误检测和纠正。当目标收到此消息时，它会执行重新计算以检测错误并找到出错的比特位置。
海明码编码消息
发送方用于编码消息的过程包括以下步骤 -
步骤 1 - 计算冗余比特的数量。
步骤 2 - 安排冗余比特的位置。
步骤 3 - 计算每个冗余比特的值。
一旦冗余比特嵌入到消息中，它就会发送给用户。
步骤 1 - 计算冗余比特的数量。
如果消息包含 *m*𝑚 个数据比特，则向其添加 *r*𝑟 个冗余比特，以便 *m*𝑟 能够指示至少 (*m* + *r*+ 1) 种不同的状态。这里，(*m* + *r*) 表示在每个 (*𝑚* + *𝑟*) 比特位置中错误的位置，而一个额外的状态表示没有错误。由于，*r*𝑟 个比特可以指示 2r𝑟 个状态，因此 2r𝑟 必须至少等于 (*m* + *r* + 1)。因此，以下等式应该成立 2r ≥ m+r+1
步骤 2 - 安排冗余比特的位置。
将 *r* 个冗余比特放置在 2 的幂次方比特位置，即 1、2、4、8、16 等。在本文的其余部分，它们被称为 *r1*（在位置 1）、*r2*（在位置 2）、*r3*（在位置 4）、*r4*（在位置 8）等等。
步骤 3 - 计算每个冗余比特的值。
冗余比特是奇偶校验比特。奇偶校验比特是一个额外的比特，它使 1 的数量为偶数或奇数。两种类型的奇偶校验是 -
偶校验 - 这里消息中的总比特数变为偶数。
奇校验 - 这里消息中的总比特数变为奇数。
每个冗余比特 ri 是基于其比特位置计算的奇偶校验，通常是偶校验。它涵盖所有比特位置，这些位置的二进制表示在其 ith 位置包含 1，除了 ri 的位置。因此 -
r1 是所有数据比特的奇偶校验比特，这些数据比特的位置的二进制表示在最低有效位包含 1，不包括 1（3、5、7、9、11 等）
r2 是所有数据比特的奇偶校验比特，这些数据比特的位置的二进制表示在从右数起的第 2 位包含 1，不包括 2（3、6、7、10、11 等）
r3 是所有数据比特的奇偶校验比特，这些数据比特的位置的二进制表示在从右数起的第 3 位包含 1，不包括 4（5-7、12-15、20-23 等）
海明码解码消息
接收方一旦收到传入的消息，就会执行重新计算以检测错误并纠正错误。重新计算的步骤如下 -
步骤 1 - 计算冗余比特的数量。
步骤 2 - 安排冗余比特的位置。
步骤 3 - 奇偶校验检查。
步骤 4 - 错误检测和纠正
步骤 1 - 计算冗余比特的数量
使用与编码相同的公式，确定冗余比特的数量。
2r ≥ m + r + 1 其中 *m* 是数据比特的数量，*r* 是冗余比特的数量。
步骤 2 - 安排冗余比特的位置
将 *r* 个冗余比特放置在 2 的幂次方比特位置，即 1、2、4、8、16 等。
步骤 3 - 奇偶校验检查
基于数据比特和冗余比特计算奇偶校验比特，使用与生成 c1、c2、c3、c4 等相同的规则。因此
c1 = 奇偶校验(1、3、5、7、9、11 等)
c2 = 奇偶校验(2、3、6、7、10、11 等)
c3 = 奇偶校验(4-7、12-15、20-23 等)
步骤 4 - 错误检测和纠正
计算奇偶校验比特二进制值的十进制等效值。如果为 0，则没有错误。否则，十进制值给出出错的比特位置。例如，如果 c1c2c3c4 = 1001，则表示位置 9（1001 的十进制等效值）处的比特有错误。翻转该比特以获取正确的消息。
51K+ 次查看
