纠错码的新领域

纠错码是信息时代的荣耀之一:它们保证了数字信息在无线电波或铜线上的完美传输，即使是在工程师们称之为“噪音”的有害影响存在的情况下。

但传统的纠错码在处理大数据块时效果最好:数据块越大，它的传输速率就越高。然而，在互联网时代，分布式计算正变得越来越普遍，设备在很长一段时间内反复交换小块数据。

因此，在过去的20年里，研究人员一直在研究交互编码方案，它解决了短交换的长序列问题。与传统的纠错码一样，交互式码也根据三个标准进行评估:它们能容忍多大的噪音?他们能承受的最大传输速率是多少?编码和解码过程有多耗时?

在本月的IEEE计算机科学基础研讨会上，麻省理工学院的毕业生将描述第一个在所有三个方面都达到最佳的交互式编码方案。

“在这项工作之前，人们知道如何使三分之二的东西达到最佳状态，”电子工程和计算机科学研究生、论文的两位合著者之一莫森·加法里(Mohsen Ghaffari)说。“这篇论文实现了这三个目标。”

邪恶的噪音

此外，1948年克劳德·香农(Claude Shannon)对纠错码的开创性分析考虑了随机噪声的情况，在这种情况下，传输的每一位数据都有同样的被破坏的机会，而加法里和他的合作者伯恩哈德·哈普勒(伯恩哈德·哈普勒在麻省理工学院完成研究生工作，现在是卡内基梅隆大学的助理教授)考虑了更严格的“对抗性噪声”的情况。在这种情况下，拮抗剂试图以最具破坏性的方式干扰传播。

“我们不知道哪种类型的随机噪音会真正捕捉到现实，”加法里解释说。“如果我们知道最好的方法，我们就会使用它。但总的来说，我们不知道。所以你要尽量生成一种通用的编码。”一个能够阻止活跃对手的编码方案也会阻止任何类型的随机噪声。

纠错码——无论是经典的还是交互式的——都是通过向要传输的消息中添加一些额外的信息来起作用的。例如，它们可能附加一些描述消息位之间算术关系的位。消息位和额外的位都容易损坏，所以解码消息——从到达接收者的序列中提取消息位的真实序列——通常是一个在消息位和额外位之间来回迭代的过程，试图消除差异。

在交互式通信中，最大可容忍错误率是四分之一:如果对手可以破坏发送的四分之一以上的比特，那么完全可靠的通信是不可能的。Ghaffari解释说，一些先前的交互编码方案可以在不需要太多额外比特的情况下处理错误率。但解码过程极其复杂。

列个清单

为了降低复杂性，Ghaffari和Haeupler采用了一种称为列表解码的技术。他们的算法不是在消息位和额外位之间来回迭代，直到出现最可能的解释，而是迭代足够长的时间来创建一个可能的候选列表。在相互计算结束时，每个相互作用的设备可能有一个包含数百个条目的列表。

但是，虽然两台设备对另一台设备发送的信息只有不完全的了解，但对自己发送的信息却有完全的了解。因此，如果在计算结束时，设备只是交换列表，每个设备都有足够的额外信息来确定最佳解码。

交互编码方案的最大可容忍错误率- 1 / 4是一个理论结果。另一方面，编码消息的最小长度和最小解码复杂度是基于观察的猜测。

但是Ghaffari和Haeupler的解码算法几乎是线性的，这意味着它的执行时间大致与交换信息的长度成正比。

但线性关系仍然由常数定义:y = x是线性关系，但y = 1,000,000,000x也是线性关系。对于考虑的每一个额外的数据位，需要额外一秒计算的线性算法不如需要额外一微秒计算的线性算法好。

麻省理工学院(MIT)

www.mit.edu

- CFE Media编辑。查看更多控制工程网络安全故事．

您是否具有本内容中提到的主题的经验和专业知识?您应该考虑为我们的CFE媒体编辑团队做出贡献，并获得您和您的公司应得的认可。点击在这里开始这个过程。