海明校验码学习卡片

海明校验码发明者
📜 海明校验码发明者
  • 由理查德·汉明(Richard Hamming)发明
  • 因其对信息纠错领域的贡献获得1968年图灵奖
  • 中文名称音译差异：海明码/汉明码
💡 记忆提示

"汉"字代表发明者姓氏，"明"代表编码的明确纠错能力

海明码核心思想
💡 海明码核心思想
  • 将信息位分组进行偶校验
  • 通过多个校验位标注出错位置
  • 相比传统奇偶校验只能检测奇数位错误，海明码能定位错误位置
🔍 对比传统奇偶校验

奇偶校验：只能发现奇数位错误
海明码：能定位具体错误位置

校验位数计算
🧮 校验位数计算
  • 必须满足不等式：2k ≥ n + k + 1
  • 其中：
    - n = 信息位数
    - k = 校验位数
  • 例如：4个信息位时，k=3才能满足该不等式
📝 示例计算

n=4时：
23=8 ≥ 4+3+1=8 → k=3

位置分配规则
📍 位置分配规则
  • 校验位Pi放在海明位号为2i-1的位置
  • 位置序列：1, 2, 4, 8, 16...
  • 信息位按顺序填充剩余位置
📌 示例

P1在位置1
P2在位置2
P3在位置4
P4在位置8

分组规则
🔗 分组规则
  • 将信息位位置序号转为k位二进制表示
  • 校验位Pi与二进制表示第i位为1的信息位归为同一组
  • 对每个分组内的信息位进行异或运算(偶校验)
📊 示例分组

信息位D1(位置3=011)归P1,P2组
异或规则：相同为0，不同为1

检错与纠错能力
✅ 检错与纠错能力
  • 1位纠错能力：可精确定位并纠正单个错误位
  • 2位检错能力：能检测出两位错误但无法定位
  • 改进方案：添加"全校验位"对整体进行偶校验
🔧 改进方案判断

S1-Sk全0且全校验成功→无错误
S1-Sk非全0且全校验失败→1位错
S1-Sk非全0且全校验成功→2位错需重传

6张卡片