汉明 Code错误检测与纠正示例
布莱斯利奥
什么是错误？
Transmit传输过程中数据可能会损坏，容易受到外部噪声或其他物理故障的影响。在这种情况下，输入数据与输出数据不可能相同。这种不匹配被称为“错误”。
数据错误可能导致重要或机密数据的丢失。数字系统中的大部分数据传输都采用“比特传输”的形式，即使单个比特的微小变化也会影响整个系统的性能。在数据序列中，如果1被更改为0，或者0被更改为1，则称为“比特错误”。
错误类型
数据丢失时主要会发生三种类型的比特错误 transmit从发送方到接收方的数据流。下图说明了每种类型如何影响数据序列：
- 单比特错误
- 多比特错误
- 突发错误
单比特错误
整个数据序列中一位发生改变称为“单比特错误”。单比特错误并不常见。它主要发生在并行通信系统中，因为数据在不同的线路上按位传输，所以一条线路出现噪声而其他线路保持干净的概率更高。
多位错误
当数据序列中的两个或多个比特位发生变化时 transmit如果终端和接收端都出现这种情况，则称为“多比特错误”。
这种类型的错误在串行和并行数据通信网络中都会发生。
突发错误
数据序列中一组连续比特的改变称为“突发错误”。突发错误的长度是从第一个改变的比特到最后一个改变的比特测量的。
什么是错误检测和错误纠正？
在数字通信系统中，数据在设备间传输过程中可能会出现错误。如果这些错误未能被检测和纠正，数据就会丢失。为了实现有效的通信，数据传输必须保证高精度，而这需要首先识别错误，然后进行纠正。
错误检测 是一种查找数据中存在错误的方法。 transmit来自泰德 transmitter 到接收器 数据通信 系统。
冗余码通过在数据出错时向数据添加额外的比特来查找这些错误。 transmit这些额外的比特位来自源数据。它们被称为“错误检测码”。三种最常见的错误检测码类型是：
- 奇偶校验
- 循环冗余校验（CRC）
- 纵向冗余校验（LRC）
奇偶校验
- 它也被称为奇偶校验。
- 它提供了一种经济高效的错误检测机制。
- 在这种技术中，添加到每个数据单元的冗余位称为奇偶校验位。它的设置使得单元中 1 的总数为偶数（偶校验）或奇数（奇校验）。
纵向冗余检查
在这种错误检测技术中，数据块被组织成一个表格。LRC 方法为每一列计算一个奇偶校验位，并将这组奇偶校验位与原始数据一起发送。奇偶校验位块帮助接收方检查冗余并检测错误。
循环冗余校验
循环冗余校验 (CR) 在数据单元的末尾附加一系列冗余位，使得生成的数据单元能够被第二个预定的二进制数整除。
到达目的地后，接收到的数据会除以同一个数。如果没有余数，则认为该数据单元正确并被接受。否则，表明该数据单元在传输过程中损坏，必须被拒绝。
什么是汉明效应 Code?
汉明码是一种线性码，可用于检测最多两个连续比特错误并纠正单个比特错误。这种纠错机制通常在数据链路层运行，对数据进行帧封装并检查相邻节点之间的数据完整性。
在汉明码中，信源通过添加冗余比特对消息进行编码。这些冗余比特被插入并生成在消息的特定位置，以执行错误检测和纠正过程。
汉明的历史 Code
- 汉明码是RW汉明发明的一种用于检测和纠正错误的技术。
- 它可以应用于任意长度的数据单元，并利用数据位和冗余位之间的关系。
- 汉明致力于纠错问题的研究，并开发了一系列功能日益强大的算法。
- 1950 年，他发表了汉明码，该码至今仍在 ECC 存储器等应用中广泛使用。
汉明的应用 Code
以下是汉明码的一些常见应用：
- 卫星
- 计算机内存（ECC RAM）
- 调制解调器
- 等离子CAM
- 打开连接器
- 屏蔽线
- 嵌入式处理器
汉明法的优势 Code
- 汉明码适用于数据流容易出现单比特错误的网络。
- 它不仅能检测出比特错误，还能帮助你识别出包含错误的比特，以便进行纠正。
- 汉明码易于使用，因此非常适合计算机内存和单错误纠错。
汉明定律的缺点 Code
- 它是一种单比特错误检测和纠错码。如果发现多个比特出错，结果可能会翻转另一个原本正确的比特，从而进一步破坏数据。
- 汉明码算法只能解决单比特问题。
如何用汉明编码方式对消息进行编码 Code
发送方对消息进行编码的过程包括以下三个步骤：
- 计算冗余比特的总数。
- 确定冗余位的位置。
- 计算每个冗余位的值。
当冗余比特嵌入到消息中时，完整的码字就会发送给接收方。
步骤 1）计算冗余比特的总数。
假设该消息包含 n 数据位和 p 添加冗余位，使得 2p 可以表示至少 (n + p + 1) 种不同的状态。
这里，(n + p) 表示每个 (n + p) 位位置上的错误位置，而额外的一个状态表示没有错误。因为 p 个奇偶校验位可以表示 2p 州，2p 必须至少等于（n + p + 1）。
步骤 2）将冗余位放置在正确的位置。
p 个冗余位位于 2 的幂次方位上，例如 1、2、4、8 和 16。它们被称为 p1 （在位置 1），p2 （在位置 2），p3 （在第 4 个位置），依此类推。
步骤 3）计算每个冗余位的值。
每个冗余位都是一个奇偶校验位，它决定了该组位中 1 的个数是偶数还是奇数。奇偶校验有两种类型：
- 均等： 覆盖位置中 1 的总数为偶数。
- 奇偶性： 覆盖位置中 1 的总数变为奇数。
每个奇偶校验位覆盖一组特定的位置，这些位置由位置编号的二进制表示确定：
- p1 检查每个最低有效位为 1 的位置——位置 1、3、5、7、9、11 等。
- p2 检查从右数第二个比特为 1 的每个位置——位置 2、3、6、7、10、11 等。
- p3 检查从右数第三位二进制值为 1 的每个位置——位置 4 到 7、12 到 15，依此类推。
示例 (7,4): 考虑以下四个数据位 1011需要三个奇偶校验位（23 = 8 ≥ 4 + 3 + 1），得到一个七位码字，布局为 p1 p2 d1 p3 d2 d3 d4放置数据后，位置 3、5、6、7 分别对应 1、0、1、1。使用偶校验：p1 涵盖位置 1、3、5、7（位 1、0、1 → p1 = 0）；p2 覆盖 2、3、6、7（位 1、1、1 → p2 = 1）；p3 覆盖 4、5、6、7（位 0、1、1 → p3 = 0）。 transmit因此，ted 代码是 0110011.
如何用汉明密码解码信息 Code
接收方接收消息后，会进行重新计算以查找并纠正错误。重新计算过程包含以下步骤：
- 计算冗余比特的数量。
- 正确放置所有冗余位。
- 执行奇偶校验。
步骤 1）计算冗余比特的数量。 使用与编码相同的公式：2p ≥ n + p + 1，其中 n 为数据位数，p 为冗余位数。
步骤 2）正确放置所有冗余位。 每个冗余位都位于 2 的幂位位置上——例如，1、2、4 和 8。
步骤 3）执行奇偶校验。 奇偶校验位由数据位和接收到的冗余位重新计算得出：
- p1 = parity(1, 3, 5, 7, 9, 11, …)
- p2 = parity(2, 3, 6, 7, 10, 11, …)
- p3 = parity(4–7, 12–15, 20–23, …)
重新计算后的奇偶校验位组成一个二进制数。如果该二进制数为零，则表示没有错误；否则，其值给出了单个错误位的确切位置，该错误位将被翻转以纠正消息。
