关于海明码的原理和计算

海明（汉明）码是广泛采用的一种有效的校验码，它实际上是一种多重奇偶校验码。

海明码的原理就是在有效信息位中加入几个校验位形成海明码，并把海明码的每一个二进制分配到几个奇偶校验中。当某一位出错的时候，不仅能检错，还能发现出错位的位置。
   假设校验位有k位，那么校验码最多有2^k个，显然其中有一个校验码是正确的，那么就能校验出2^k-1个错位。所以，如果能满足一个n位数n+k<=2^k-1,则在理论上即可判断出哪一位数出错。

编码步骤

1. 首先确定需要几位校验位，2^k= k+n+1,其中k为校验位，n为数据位。求出最小的k即为校验位的位数。
2. 确认校验位的分布
   规定校验位K_i在海明码位号为2^i-1上

例如若有信息为1011的数，则海明码的校验码的分布为：101K₃1K₂K₁

3. 分组以形成校验关系
   每个数据位由多个校验位进行校验，但是需要满足被校验数据的海明码位号等于校验该数据位的各校验码海明码位号的和。（PS:校验码不需要被校验）
   接上例：在海明码中第三位的D1，需要有K₁,K₂进行校验，D2由K₁,K₃，D3由K₂,K₃，D4由K₁,K₂,K₃检验
4. 校验位取值
   校验位的取值由分组决定。
   K₁=D1⊕D2⊕D4
   K₂=D1⊕D3⊕D4
   K₃=D2⊕D3⊕D4
   注：⊕为异或运算

K₁=1
K₂=0
K₃=0
所以，1011的海明码为1010101

5. 海明码的校验原理
   每个校验组分别利用校验位和参与该校验位的数据位进行奇偶校验检查，构成K个校验方程。
   接上例
   S₁=K₁⊕D1⊕D2⊕D4
   S₂=K₂⊕D1⊕D3⊕D4
   S₃=K₃⊕D2⊕D3⊕D4
   若S_i =1，表示覆盖了海明码中所有位置号二进制表示里倒数第i位为1的数据。如S₃=1，则表示着位置号为100，110，101，111等数据。
   例如：若S₃S₂S₁=000表示这无错，S₃S₂S₁=101，表示着海明码中第五位数据有错误，只需取反即可改正。

【例】使用海明码进行纠错，7位码长（x7x6x5x4x3x2x1），其中4位数据，监督关系式为： C0 = x1+x3+x5+x7 C1 = x2+x3+x6+x7 C2 = x4+x5+x6+x7 如果接收到的码字为1000101，那么纠错后的码字是（）
解：由题可得：
C0=1,C1=0,C2=1,即C2C1C0=101。所以海明码中第五位数据出错，取反可得，10#1#0101

因为在网上查阅汉明码资料的时候，发现网上部分题和博客对汉明码的解释千奇百怪，我认为其中有些错误，所以就照着百科自己理解梳理了一遍。

有的博客里加校验位是从左开始算位数，有的直接添加在末尾。所以，要是有大佬能解释一下为什么不统一，麻烦请私信我。