解法
1947年,贝尔实验室的理查德·汉明,这位教同事使用计算机的人,走进办公室,期待着一台大型继电器机器的结果,这台机器周末无人值守运行。它很早就出了故障,结果什么也没交出来。他提出了那个引发一切的问题:如果机器能发现错误,为什么不能定位错误并修复它呢?
他使用的机器采用奇偶校验,能检测错误但不能纠正,所以任何单个比特翻转都意味着工作停止,必须重做。汉明增加了重叠的奇偶校验位,使每个数据比特被多个校验覆盖,这样翻转的比特会产生独特的模式,指向其自身的位置。
这让计算机可以纠正单个错误,甚至能检测两个错误并纠正一个,而无需停止。该方法发表于1950年他在《贝尔系统技术期刊》上的论文中,并成为以他命名的码族,用于计算机、电话交换,后来还用于从太空探测器遥测到音频光盘等一切领域。
取得了什么结果
添加能定位错误的比特,而不只是标记错误的比特
为什么有效
重叠校验使每个比特的故障模式独一无二,从而可以定位错误。
自我纠正的机器避免了停止和重跑长时间任务。
随着数据块增大,冗余开销下降,修复变得更便宜。
它将错误保护从检测工具转变为纠正工具。
可以借鉴什么
检测错误成本低,但纠正错误才能消除浪费;通过设计校验位来精确指出问题所在,就能免费获得修复。
后续
汉明码成为编码理论的起点,并为后来更强大的码提供了模型,这些码现在保护着内存、磁性和光学存储以及数据线路。汉明于1980年获得IEEE计算机学会先锋奖,IEEE还以他的名字命名了信息科学奖章。
从这里,追溯依据
参考来源
- Richard Wesley Hamming — Computer Pioneers IEEE Computer Society · history.computer.org
- Algebraic Coding Theory / Error Detection and Correction University of Puget Sound · math.pugetsound.edu