交互式编码方案是第一个接近最优的方案

在一项新的研究论文中，麻省理工学院的工程师在三种经典方法上描述了第一种接近最优的交互式编码方案：他们可以忍受多少噪音？他们承受的最大传输速率是多少？编码和解码过程又如何？

纠错码是信息时代的荣耀之一：它们可以确保即使在受到工程师称之为“噪声”的破坏性影响的情况下，也可以通过无线电波或通过铜线完美地传输数字信息。

但是经典的纠错代码最适合处理大块数据：块越大，无错误传输的速率越高。但是，在Internet时代，随着设备在很长一段时间内反复交换小块数据，分布式计算正变得越来越普遍。

因此，在过去的20年中，研究人员一直在研究交互式编码方案，该方案解决了短交换的长序列问题。像传统的纠错码一样，交互式代码将根据以下三个标准进行评估：他们可以忍受多少噪音？他们承受的最大传输速率是多少？编码和解码过程又如何？

在本月举行的IEEE计算机科学基础专题讨论会上，麻省理工学院的过去和现在的研究生将描述第一个交互式编码方案，以在所有这三种方法上实现最佳效果。

电气工程和计算机科学专业的研究生Mohsen Ghaffari说：“在进行这项工作之前，已经知道如何从三分之二中获得最佳。”“本文实现了这三个目标。”

恶性噪音

此外，在克劳德·香农（Claude Shannon）于1948年进行的开创性的纠错码分析考虑了随机噪声的情况下，在这种情况下，传输的每一位数据都有相同的被破坏的机会，加法里（Ghaffari）和他的合作者Bernhard Haeupler在麻省理工学院做研究生。现在是卡耐基梅隆大学的助理教授-考虑一下“对抗性噪音”这一更为严格的案例，在这种情况下，反对者试图以最具破坏性的方式来干扰传播。

Ghaffari解释说：“我们不知道真正捕获现实的是哪种类型的随机噪声。”“如果我们知道最好的，我们就会使用它。但总的来说，我们不知道。因此，您尝试生成尽可能通用的编码。”可能会挫败积极对手的编码方案也将挫败任何类型的随机噪声。

纠错码（传统的和交互式的）都通过在要发送的消息中添加一些额外的信息来工作。例如，它们可能附加一些描述消息位之间的算术关系的位。消息位和额外位都易于损坏，因此对消息进行解码（从到达接收器的序列中提取消息位的真实序列）通常是在消息位和额外位之间来回迭代的过程。位，试图消除差异。

在交互式通信中，最大容许错误率是四分之一：如果对手破坏了发送的比特数的四分之一以上，则不可能实现完全可靠的通信。Ghaffari解释说，某些现有的交互式编码方案可以处理该错误率，而无需太多额外的位。但是解码过程非常复杂。

列出清单

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

但是，每个设备虽然对对方发送的消息只有不完善的知识，但对它所发送的消息却拥有完备的知识。因此，如果在计算的最后，这些设备只是交换列表，则每个设备都有足够的附加信息可以将最佳解码归零。

交互式编码方案的最大容许错误率（四分之一）是理论结果。另一方面，基于观察结果推测编码消息的最小长度和最小解码复杂度。

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

普林斯顿大学计算机科学助理教授马克·布雷弗曼（Mark Braverman）说：“从线性的角度来说，它是最佳的。”他还从事交互式编码工作。“这是一个重要的基准。”

但是线性关系仍然由常量定义：y = x是线性关系，但是y = 1,000,000,000x。线性算法对它认为的每增加一个数据位额外花费一秒钟的计算时间，不如线性算法花费一微秒的时间。

“我们仍然需要担心常量，” Braverman说。“但是在担心常数之前，您必须知道有一个恒定速率方案。这是非常不错的进步，是提出下一个问题的先决条件。”

研究报告的PDF副本：交互式编码II的最佳错误率：效率和列表解码

图像：荷西-路易斯·奥利瓦雷斯/麻省理工学院