“神奇”的纠错方案被证明本质上效率低下广达杂志

如果您曾经发送过短信、播放过 CD 或在云中存储过文件，那么您就会从纠错中受益。这一革命性的想法可以追溯到 1940 世纪 XNUMX 年代，当时研究人员首次意识到可以以某种形式重写任何消息，以便以后的损坏可以轻松逆转。

多年来，研究人员开发了许多巧妙的方案，称为纠错码，它们以不同的方式对数据进行编码，并使用不同的程序来修复错误。但对于理论计算机科学家来说，很少有比所谓的本地可纠正代码更引人注目的了。这些代码具有两个听起来几乎矛盾的同时属性：任何错误都可以通过读取少数位置的编码数据来纠正，但没有攻击者可以通过有选择地篡改代码来挫败此纠正过程。就好像你只需看一眼其他几页就可以恢复从书中撕下的任何一页。

“这是一个非常神奇的现象，”说 汤姆·古尔，剑桥大学计算机科学家。 “先验地，这样的数学对象是否存在根本不明显。”

但这种魔法的代价是高昂的。唯一已知的本地可纠正代码的例子效率极低——对任何消息进行编码也会使其长度呈指数级增长。以这种方式编码的整本书太笨重了。

计算机科学家长期以来一直想知道是否可能有更好的本地可校正代码。他们特别关注仅使用三个查询来纠正任何错误的代码，希望这种严格的限制可以使这些代码更容易理解。但即使是这个简单的案例也困扰了研究人员 20 多年。

现在是计算机科学家 普拉韦什·科塔里 卡内基梅隆大学教授和他的研究生 彼得·马诺哈尔 终于有 证明 不可能构建一个三查询本地可校正代码来避免指数成本。这可能是一个负面的结果，但任何澄清纠错局限性的事情都会让研究人员感到兴奋，特别是因为本地可纠正代码的数学出现在远离通信的地区。

“这个结果令人惊讶，” 舒邦吉·萨拉夫，多伦多大学计算机科学家。 “这是一个巨大的突破。”

人多力量大

要了解纠错，请将您想要保护的数据想象为一系列位或 0 和 1。在此模型中，错误可能是任何不需要的 0 翻转为 1，反之亦然，无论是由于随机波动还是故意篡改。

假设您想向朋友发送消息，但您担心错误可能会改变消息的含义。一种简单的策略是将消息中的每个 0 替换为 000，将每个 1 替换为 111。如果您的朋友看到​​消息的一部分不包含连续的三个相同位，他们就会知道发生了错误。如果错误是随机的且相对罕见，那么任何 110 字符串都更有可能是损坏的 111，而不是损坏的 000。每个三元组内的简单多数投票足以纠正大多数错误。

这种方案称为重复码，具有简单的优点，但没有什么值得推荐的。一方面，它需要将每条消息的长度增加两倍，只是为了处理相对不常见的错误，如果很可能出现两个相邻的错误，我们将需要更多的冗余。更糟糕的是，如果错误不是随机的，例如当攻击者积极尝试破坏代码时，它很快就会变得毫无用处。在重复码中，纠正给定位所需的所有信息仅存储在其他几个位中，使其容易受到有针对性的攻击。

幸运的是，许多纠错码的表现更好。一个著名的例子叫做 里德-所罗门码，通过将消息转换为多项式来工作——数学表达式，例如 x² + 3x + 2 由不同的项加在一起组成，每个项都有一个变量（例如 x) 提升到不同的幂。使用里德-所罗门码对消息进行编码涉及为消息中的每个字符构建一个多项式，然后将多项式绘制为图形上的曲线并存储位于曲线上的点的坐标（至少再取一个）点比字符数）。错误可能会将其中一些点推离曲线，但如果错误不多，则只有一条多项式曲线会通过大多数点。这条曲线几乎肯定对应于真实的信息。

里德-所罗门码非常高效——您只需要存储一些额外的点来纠正错误，因此任何编码的消息只比原始消息稍长一些。它们也不太容易受到那种会给重复代码带来灾难的有针对性的破坏，因为用于纠正任何地方的错误的信息分布在整个编码消息中。

放眼全球，本土化行动

里德-所罗门码的力量源于互连性。但正是由于这种相互关联性，如果不阅读整个内容，就无法修复编码消息中的单个错误。在通信环境中，这听起来可能不是问题：如果您要发送消息，您可能希望收件人阅读全部内容。但这可能是数据存储中的一个负担——这是纠错的另一个主要应用。

考虑一家将用户电子邮件存储在云中（即存储在大量服务器上）的公司。您可以将整个电子邮件集合视为一条长消息。现在假设一台服务器崩溃了。使用里德-所罗门代码，您需要执行涉及所有编码数据的大量计算，才能从一台丢失的服务器恢复您的电子邮件。 “你必须审视一切，”他说。 泽夫·德维尔，普林斯顿大学计算机科学家。 “这可能是数十亿封电子邮件——可能需要很长时间。”

研究人员使用术语“本地”来描述仅使用编码消息的一小部分来实现的代码。 发现错误 或纠正它们。简单的重复代码具有某种本地特征，但这正是它如此容易被篡改的原因。相比之下，本地可纠正的代码则两全其美——它只需几次查询就可以纠正任何位的错误，而且不会失去使里德-所罗门代码具有如此弹性的互连性。

“这是一个非常严格的概念，”科塔里说。

局部可纠正代码最著名的例子是数学家于 1954 年发明的古老纠错码的版本 大卫·穆勒 和 欧文·里德 （他还帮助开发了里德-所罗门码）。与 Reed-Solomon 码一样，Reed-Muller 码使用将许多项相加的多项式来对长消息进行编码。

里德-所罗门码中使用的多项式涉及单个变量， x，所以添加更多项的唯一方法是使用更高的幂 x。这会导致曲线出现许多波动，只能通过查看多个点来确定。相反，Reed-Muller 码使用多项式，其中每一项可以包含相乘的多个变量。更多变量意味着更多组合它们的方法，这反过来又提供了一种增加多项式项数的方法，而无需将任何单个变量提高到如此高的幂。

Reed-Muller 码非常灵活。您可以通过增加多项式中出现的最高幂、增加变量数量或同时增加两者来编码更长的消息。为了使 Reed-Muller 码可在本地纠正，您只需将每个变量的最大功率限制为一个小的常数值，并通过仅增加变量的数量来处理更长的消息。

特别是对于三查询本地可校正代码，最大功率设置为 2。然后就每个单独的变量而言，编码消息的多项式描绘出一条简单的抛物线。要确定抛物线的确切形状，您只需检查曲线的三个点。更重要的是，对于许多变量来说，有许多这样的抛物线，任何一个都可以用来纠正错误。这就是 Reed-Muller 码如此具有弹性的原因。

不幸的是，Reed-Muller 码有一个严重的缺点：编码消息所需的位数随着变量数量呈指数增长。如果您想要一个高度本地化的代码，只需少量查询即可纠正错误，那么您将需要大量变量来存储长消息，并且 Reed-Muller 代码在实践中很快就会变得毫无用处。

“在这种情况下，指数非常糟糕，”德维尔说。但这是不可避免的吗？

可纠正或可解码？

由于计算机科学家试图找到更有效的本地可纠正代码但未能成功，他们开始怀疑这种代码根本不可能。 2003年，两名研究人员 证明 仅使用两个查询是无法击败 Reed-Muller 代码的。但这只是任何人所能得到的。

“一旦你达到了三个，我们的知识就变得非常粗略，”科塔里说。

下一个突破只会让事情变得更加复杂。在发表于的两篇论文中 2008 和 2009中，计算机科学家 Sergey Yekhanin 和 Klim Efremenko 展示了如何构造比 Reed-Muller 代码更高效的三查询代码，但这些代码并不完全可以进行局部纠正。相反，它们有一个略有不同的属性，称为本地可解码性。

为了理解其中的差异，让我们再次想象一个云存储提供商将用户的数据组合成一条长消息并使用纠错代码对其进行保护。本地可纠正代码和本地可解码代码都可以通过几次查询来纠正原始消息的任何位中的错误。

但每个纠错码还需要原始消息中没有的额外位——这就是为什么对消息进行编码会使其更长。这两种类型的代码在处理这些附加位的方式上有所不同。本地可解码代码不承诺纠正这些位中的错误所需的查询数量。但在本地可纠正的代码中，任何额外位中的错误都可以通过与原始消息中任何位中的错误完全相同的方式进行修复。

“你存储的所有内容，无论是用户的原始数据还是冗余和校验信息——所有这些都可以在本地进行纠正。” 马杜苏丹，哈佛大学计算机科学家。

尽管原则上不同，但本地可纠正性和本地可解码性在 2008 年之前的实践中似乎总是可以互换的——每个已知的本地可解码代码也都是可本地纠正的。叶哈宁和埃夫雷门科的发现提出了这两种情况之间存在根本差异的可能性。或者也许可以修改 Yekhanin 和 Efremenko 的代码，使其可以在本地纠正。这将使这两个条件再次处于平等地位，但这也意味着研究人员错误地认为三查询本地可纠正代码的效率有多高。不管怎样，传统观念都必须改变。

借用逻辑

科塔里和马诺哈尔最终通过采用计算机科学不同领域的一项技术解决了这种紧张局势：即所谓的约束满足问题的研究。试图与一群朋友协调晚餐计划是一种约束满足问题。每个人都有他们会接受的选择和他们会否决的选择。你的工作是要么找到一个让每个人都满意的计划，要么，如果没有这样的计划，尽快弄清楚。

这两种可能的结果之间存在固有的不对称性。一个可接受的解决方案可能并不容易找到，但一旦找到，就很容易说服其他人它会起作用。但即使你知道这个问题确实是“不可满足的”，也可能没有一个例子可以提供证明。

2021 年，Kothari 和 Manohar 与加州大学伯克利分校的 Venkatesan Guruswami 一起做了一项研究 重大突破 在约束满足问题的研究中，使用新的理论技术来识别那些棘手的不可满足的情况。他们怀疑新方法也将成为解决其他问题的强大工具，Guruswami 的研究生 Omar Alrabiah 建议他们研究三查询本地可解码代码。

“可以说，我们手里拿着的是钉子和锤子，”科塔里说。

Yekhanin 和 Efremenko 的令人惊讶的结果表明，三查询本地可解码代码可能比 Reed-Muller 代码更有效。但他们的代码是否是最好的，或者三查询本地可解码代码是否可以变得更加高效？ Kothari、Manohar、Guruswami 和 Alrabiah 认为他们的新技术或许能够证明此类代码效率的限制。他们的计划是建立一个逻辑公式，包含给定大小的所有可能的三查询本地可解码代码的结构，并证明它是不可满足的，从而表明不存在这样的代码。

四位研究人员在 2022 年朝这个方向迈出了第一步，设定了 新限制 关于三查询本地可解码代码的最大效率。结果远远超出了研究人员使用其他技术所能达到的水平，但它并不排除所有比叶哈宁和埃夫雷门科的代码更有效的代码。

科塔里和马诺哈尔怀疑他们可以走得更远。但进展陷入停滞，直到马诺哈记下了一个快速的粗略计算，表明该技术对于本地可纠正的代码可能比本地可解码的代码更有效。

几个月后，在经历了更多的错误开始后，他们担心自己过于乐观，这项技术终于兑现了它的承诺。 Kothari 和 Manohar 证明，正如研究人员所怀疑的那样，任何三查询本地可校正代码都不可能比 Reed-Muller 代码表现得更好。指数缩放是一个基本限制。他们的结果也戏剧性地证明了局部可校正性和局部可解码性虽然表面上相似，但在根本层面上确实存在差异：后者显然比前者更容易实现。

Kothari 和 Manohar 现在希望扩展他们的技术来研究允许进行三个以上查询的代码，因为现在人们对它们知之甚少。纠错理论的进展往往会对其他看似不相关的领域产生影响。特别是，本地可纠正的代码随处可见，因为以下问题 私人数据库搜索 在密码学中的证明 组合数学定理。现在说科塔里和马诺哈尔的技术将如何影响这些不同领域还为时过早，但研究人员感到乐观。

“这里有一个非常漂亮的新想法，”德维尔说。 “我认为有很大的潜力。”