Day 42:汉明码
18年10月17日 · 吴超 1051 人阅读
汉明码的意义
无论何时传输或存储数据,都可能会发生错误,从而导致数据损坏。在计算机内存、磁盘、以太网、Wi-Fi 传输中随处可见。使用汉明码就是高效解决这个问题的一个解决方案。
为了识别错误,我们可以把每一位都双写。比如1010,我们可以存储成11001100。如果一对连续位不相同,则数据被损坏。这就是所谓的奇偶性。
显然,双写是不够的。虽然我们可以识别出一个错误,但是我们无法把这个错误的字符流恢复。因此,我们必须把数据增加三倍。有了111000111000,我们就可以认出是哪个部分损坏,并且用三个中剩下的两个来推算出第三个。当然这样我们每一个 bit 的数据就变成了三个 bit,这个空间浪费是比较大的。
汉明码的原理
每 255 个 bit 中,有 8 个 bit 用做空间地址和奇偶校验,这时就可以存储 247 bit 的数据。汉明码示意图如下:
每个奇偶校验位覆盖在其地址中特定位设置为1的位置上。例如奇偶校验位 P1 只检查带有掩码 xxx1 的地址,P2 只检查地址 xx1x ,P4 只检查地址 x1xx 等。如果出现数据错误,则可以根据校验位将出错的地方发现并还原。
汉明码的实现
Python3Turtle