Open nfssuzukaze opened 3 years ago
海明距离的值为：两个码字中不相同的个数的和
如果两个码字的海明距离为 d，则需要 d个 1位错误才能将一个码字转变为另一个码字**（如上表所示，码字1 在第 2,3,5,6,7 位出现 5个 1位错误，就会转化为 码字2）
2,3,5,6,7
如果给出一个计算校验位的算法，那么就可以构建出一个完整的合法码字列表，然后从这个列表中找出两个具有最小海明距离的码字。这个距离就是整个编码的海明距离
同样是上表，现将其看作为一个合法码字列表。假设发送端发送了一个 01 序列 0000 1111 ，但在途中被干扰
0000 1111
检错：
到接收端时的 01 序列已经变成了 1110 0011 ，这里出现了 5个 1位错误，但仍然是合法的码字（与码字2 完全相同），所以这就是海明距离为 5 的编码所不能检测到的
1110 0011
码字2
但如果到接收端的码字为 1110 0111 的话，则完全可以检测出来 01 序列出现了错误，此时的海明距离为 4。那么当然，如果出错位数更少的话，也依然能够成功检错
1110 0111
所以，海明距离为 d + 1 的编码只能检测到至多 d个的 1位错误
纠错：
到接收端时的 01 序列已经变成了 0010 0011 ，这里出现了 3个 1位错误，毋庸置疑可以检测出来，但是想要纠错的话，由于该错误码字与 码字2 的海明距离 2 比与 码字1 的海明距离 3 更小，其会被纠正为 码字2 ，我们知道，这样的纠错并不正确
0010 0011
码字1
但如果是到接收端的码字为 0000 0011 的话，其与 码字2 的海明距离 3 比与 码字1 的海明距离 2 更小，所以其会被纠正为 码字1 ，这才是正确的纠错。理所当然，如果出错位数更少的话，也依然能够纠正
0000 0011
所以，海明距离为 2d + 1 的编码只能至多纠正 d个 的 1位错误
在上面的例子中，解码的作用就是找到距离接收码字最近的合法码字。但是将所有的合法码字作为候选被评估，是一项非常耗时的工作。所以实际上的代码被设计成了允许使用快捷方式找到最有可能的原始码字
每个 n 位的码字有 m 个消息位与 r 个校验位，有着纠错 1 位的功能。（由纠错 1 位 可以推测出海明码可以检错 2 位）
则对于 2^m 个合法消息，每个合法消息有 n 位，则意味着其对应着 n 个非法的码字，加上原来那个合法的码字，有：一个合法消息对应 (n + 1) 个码字，然而总共只有 2^n 个位模式，所以有如下
2^m × (n + 1) <= 2^n 因为 n = m + r 所以 m + r + 1 <= 2^r
在给定 m 的情况下，可以根据该公式得出拥有纠正 1位错误所需的最少校验位
现假定需要传送 8 位数据 0000 1111 ，根据公式可算出，所需的校验位有 4 位。在海明码中，码字的位被连续编号，其中，校验码存在于 2^i ( i = 0, 1, 2, ... )，信息码存在于其他位，如下表格所示
现对校验位进行计算
P1 = M3 ^ M5 ^ M7 ^ M9 ^ M11 P2 = M3 ^ M6 ^ M7 ^ M10 ^ M11 ……
如此计算，可得 P1 = 1，P2 = 1，P4 = 1，P8 = 0。可以得到 12 位码字如下，由发送端发送
当接收端接收到该码字时，会进行如下检测
S1 = P1 ^ M3 ^ M5 ^ M7 ^ M9 ^ M11 ……
在这个码字中会有 S1, S2, S3, S4 四个位（与校验位的个数相对应）
现假设发送端发送过来的第 7 位（信息位）出现了错误
S1 = 1，S2 = 1，S3 = 1，S4 = 0。将这四位组合起来就是 0111 ，也就是 7，表示第七位出错
0111
若第 4 位出现错误（校验位）
S1 = 0，S2 = 0，S3 = 1，S4 = 0。组合起来是 0100 ，也就是 4，表示第四位出错
0100
若未出现差错
S1 = 0，S2 = 0，S3 = 0，S4 = 0。组合起来是 0000 ，也就是 0，表示没有出错
0000
海明码
海明距离
海明距离的值为：两个码字中不相同的个数的和
如果两个码字的海明距离为 d，则需要 d个 1位错误才能将一个码字转变为另一个码字**（如上表所示，码字1 在第
2,3,5,6,7位出现 5个 1位错误，就会转化为 码字2）如果给出一个计算校验位的算法，那么就可以构建出一个完整的合法码字列表，然后从这个列表中找出两个具有最小海明距离的码字。这个距离就是整个编码的海明距离
块码的纠错与检错
同样是上表，现将其看作为一个合法码字列表。假设发送端发送了一个 01 序列
0000 1111，但在途中被干扰检错：
到接收端时的 01 序列已经变成了
1110 0011，这里出现了 5个 1位错误，但仍然是合法的码字（与码字2完全相同），所以这就是海明距离为 5 的编码所不能检测到的但如果到接收端的码字为
1110 0111的话，则完全可以检测出来 01 序列出现了错误，此时的海明距离为 4。那么当然，如果出错位数更少的话，也依然能够成功检错所以，海明距离为 d + 1 的编码只能检测到至多 d个的 1位错误
纠错：
到接收端时的 01 序列已经变成了
0010 0011，这里出现了 3个 1位错误，毋庸置疑可以检测出来，但是想要纠错的话，由于该错误码字与码字2的海明距离 2 比与码字1的海明距离 3 更小，其会被纠正为码字2，我们知道，这样的纠错并不正确但如果是到接收端的码字为
0000 0011的话，其与码字2的海明距离 3 比与码字1的海明距离 2 更小，所以其会被纠正为码字1，这才是正确的纠错。理所当然，如果出错位数更少的话，也依然能够纠正所以，海明距离为 2d + 1 的编码只能至多纠正 d个 的 1位错误
在上面的例子中，解码的作用就是找到距离接收码字最近的合法码字。但是将所有的合法码字作为候选被评估，是一项非常耗时的工作。所以实际上的代码被设计成了允许使用快捷方式找到最有可能的原始码字
海明码的规则
计算校验位个数
每个 n 位的码字有 m 个消息位与 r 个校验位，有着纠错 1 位的功能。（由纠错 1 位 可以推测出海明码可以检错 2 位）
则对于 2^m 个合法消息，每个合法消息有 n 位，则意味着其对应着 n 个非法的码字，加上原来那个合法的码字，有：一个合法消息对应 (n + 1) 个码字，然而总共只有 2^n 个位模式，所以有如下
2^m × (n + 1) <= 2^n 因为 n = m + r 所以 m + r + 1 <= 2^r
在给定 m 的情况下，可以根据该公式得出拥有纠正 1位错误所需的最少校验位
计算各校验位的值
现假定需要传送 8 位数据
0000 1111，根据公式可算出，所需的校验位有 4 位。在海明码中，码字的位被连续编号，其中，校验码存在于 2^i ( i = 0, 1, 2, ... )，信息码存在于其他位，如下表格所示现对校验位进行计算
P1 = M3 ^ M5 ^ M7 ^ M9 ^ M11 P2 = M3 ^ M6 ^ M7 ^ M10 ^ M11 ……
如此计算，可得 P1 = 1，P2 = 1，P4 = 1，P8 = 0。可以得到 12 位码字如下，由发送端发送
接收端的检验
当接收端接收到该码字时，会进行如下检测
S1 = P1 ^ M3 ^ M5 ^ M7 ^ M9 ^ M11 ……
在这个码字中会有 S1, S2, S3, S4 四个位（与校验位的个数相对应）
现假设发送端发送过来的第 7 位（信息位）出现了错误
S1 = 1，S2 = 1，S3 = 1，S4 = 0。将这四位组合起来就是
0111，也就是 7，表示第七位出错若第 4 位出现错误（校验位）
S1 = 0，S2 = 0，S3 = 1，S4 = 0。组合起来是
0100，也就是 4，表示第四位出错若未出现差错
S1 = 0，S2 = 0，S3 = 0，S4 = 0。组合起来是
0000，也就是 0，表示没有出错