如何使用汉明码纠正消息

Question

所以我想在今年夏天的项目中使用汉明码来纠正消息传输中的错误,但我无法弄清楚它是如何工作的.我在网上看了很多文章,但我真的不懂算法.有人能用简单的方法解释一下吗？

谢谢.

Answer 1

这一切都与汉明距离有关.

两个base-2值之间的汉明距离是它们不同的位数.因此,如果您发送A,但我收到B,则必须在传输中切换的位数是A和B之间的汉明距离.

当每个代码字中的位以某种方式单独传输时,汉明码很有用.我们不关心它们是串行还是并行,但它们不会组合成代表几位的模拟值,或者在编码后压缩/加密.

因此,每个比特独立地(随机地具有一些固定的概率),正确地接收或翻转.假设传输相当可靠,则正确接收大多数位.因此,更有可能出现少量比特中的错误,并且不可能在大量比特中同时出现错误.

因此,汉明码通常旨在纠正1位错误,和/或检测2位错误(有关两种主要类型的详细信息,请参阅维基百科文章).可以构建纠正/检测更大错误的代码,但AFAIK的使用不会那么多.

该代码通过均匀地间隔"汉明空间"中的代码点来工作,其在数学术语中是由相关字大小的所有值组成的度量空间,其中汉明距离作为度量.想象一下,每个代码点都被一些无效值的"缓冲区"所包围.如果收到的值不是代码点,则必须发生错误,因为只传输有效的代码点.

如果接收到缓冲区中的值,则假设发生1位错误,则发送的值必须与接收的值相距1.但由于代码点是分散的,因此只有一个代码点可以关闭.因此它被"纠正"到该代码点,理由是1位错误比任何其他代码点产生接收值所需的更大错误更可能.在概率方面,您发送附近代码点的条件概率大于您发送任何其他代码点的条件概率,因为我收到了我所做的值.所以我猜你发送了附近的一个,基于传输的可靠性和每个字的位数有一定的信心.

如果收到与两个代码点等距的无效值,那么我不能说一个比另一个更可能是真值.所以我检测到错误,但我无法纠正它.

显然,SECDED汉明码不会纠正3位错误.接收到的值远离实际发送的值,而不是某个其他代码点,并且我错误地将其"纠正"为错误的值.因此,您需要足够可靠的传输而不关心它们,否则您也需要更高级别的错误检测(例如,整个消息的CRC).