文章目录海明码从编码到纠错一篇讲透一、确定校验位数量二、编码过程第 1 步确定校验位和数据位的位置第 2 步确定每个校验位负责检查哪些位第 3 步计算每个校验位的值偶校验第 4 步得到最终编码三、纠错过程第 1 步重新计算每个校验组的奇偶性第 2 步拼出错误位置编号第 3 步纠正错误四、如果没有错误呢五、总结海明码从编码到纠错一篇讲透海明码Hamming Code是纠错编码中最经典、最基础的方案由理查德·海明于 1950 年提出。它的核心能力是自动检测并纠正 1 位错误。今天我们就用 4 位数据1011作为例子完整走一遍海明码的编码和纠错过程。一、确定校验位数量校验位数量 r 需满足2 r ≥ d r 1 2^r \geq d r 12r≥dr1其中 d 为数据位数。对于 4 位数据2 3 8 ≥ 4 3 1 8 2^3 8 \geq 4 3 1 8238≥4318所以 r 3。总共 7 位编码即(7, 4) 海明码。二、编码过程第 1 步确定校验位和数据位的位置校验位固定放在位置编号为 2 的幂次的位上其余位置放数据位位置1234567类型P₁P₂D₁P₃D₂D₃D₄P 校验位第 1、2、4 位D 数据位第 3、5、6、7 位将数据1011依次填入数据位位置1234567类型P₁P₂D₁P₃D₂D₃D₄值??1?011第 2 步确定每个校验位负责检查哪些位规则位置编号的二进制表示中第 i 位为 1 的那些位置归 Pᵢ 检查。P₁第 1 位检查位置编号二进制末位为 1 的位 → 第 1、3、5、7 位P₂第 2 位检查位置编号二进制倒数第 2 位为 1 的位 → 第 2、3、6、7 位P₃第 4 位检查位置编号二进制倒数第 3 位为 1 的位 → 第 4、5、6、7 位第 3 步计算每个校验位的值偶校验让每个校验位负责的那些位中1 的个数为偶数P₁检查第 1、3、5、7 位 → P₁ D₁ D₂ D₄ P₁ 1 0 1 P₁ 2要使总和为偶数 → P₁ 0P₂检查第 2、3、6、7 位 → P₂ D₁ D₃ D₄ P₂ 1 1 1 P₂ 3要使总和为偶数 → P₂ 1P₃检查第 4、5、6、7 位 → P₃ D₂ D₃ D₄ P₃ 0 1 1 P₃ 2要使总和为偶数 → P₃ 0第 4 步得到最终编码位置1234567类型P₁P₂D₁P₃D₂D₃D₄值0110011最终编码为0110011三、纠错过程假设传输过程中第 5 位出错接收方收到的编码为0 1 1 0 1 1 1第 5 位从 0 变成了 1第 1 步重新计算每个校验组的奇偶性P₁ 组第 1、3、5、7 位0 1 1 1 3 → 奇数 →校验失败记为 1P₂ 组第 2、3、6、7 位1 1 1 1 4 → 偶数 →校验通过记为 0P₃ 组第 4、5、6、7 位0 1 1 1 3 → 奇数 →校验失败记为 1第 2 步拼出错误位置编号将校验结果按 P₃P₂P₁ 排列P₃P₂P₁ 101101二进制5十进制→ 第 5 位出错第 3 步纠正错误将第 5 位翻转1 → 0纠正后的编码0110011与原始编码完全一致。四、如果没有错误呢如果接收到的编码完全正确那么所有校验组的奇偶性都会通过P₃P₂P₁ 000000 0表示没有错误。五、总结步骤内容确定校验位数量2 r ≥ d r 1 2^r \geq d r 12r≥dr1放置校验位放在 2 的幂次位置上计算校验位让每个校验组中 1 的个数为偶数纠错定位用 P₃P₂P₁ 拼出错误位置编号纠错操作翻转对应位置的那一位海明码的精妙之处在于校验位的位置设计和覆盖规则天然保证了每个位置出错时产生的校验结果都是唯一的。所以只要错 1 位就一定能精确定位并纠正。