研究者挫败随机性并创建理想编码

求索已久的局域可检测编码最终被一个研究小组通过精心构造一个高维且连通良好的图创建出来，而它会立即暴露自己是否已被破坏。

Mordechai Rorvig 著

左      芬      译

【译注：原文2021年11月24日刊载于QuantaMagazine】

为了得出编码信息的最优方法，研究者们将其表示成一个图，它形如一个向外伸展的连接繁复的册页网络。图中的每一页代表着一条消息中的单个信息比特。

假定你想要传输一条消息。将每个字符转换成比特，再将每个比特转换成信号。接着将它发送出去，通过铜线、光纤或者空气。哪怕你尽其所能地小心，在另一端接收到的信号也不会跟你初始的完全一样了。噪声在破坏上是无所不能的。

1940年代，计算机科学家们首次直面噪声这一无法避免的难题。50年后，他们想到了回避它的一种优雅的方式：将消息这样编码，使得你的接收者在读它之前，一眼就可以看出来是否已经被篡改了。一本书无法通过封面进行评价，但这样的消息却可以。

他们把这一性质称为局域可检测性，因为这样一条性质可以非常快地在仅仅少量位置进行检测就可以断定其正确性。在后续的30年里，研究者们朝着创建这样的检测取得了相当大的进展，但他们的成果始终有所欠缺。许多人认为局域可检测性将永远无法以其理想形式实现。

如今，魏茨曼科学研究院的计算机科学家 Irit Dinur 和耶路撒冷市希伯来大学的四位数学家Shai Evra, Ron Livne, Alex Lubotzky 及 Shahar Mozes 11月8日在预印本网站发布的一篇论文中得到了它。

“这是数学与计算机科学中我所知晓的最卓越的成果之一了，”沃里克大学的 Tom Gur 说道。“它一直是整个领域的圣杯。”

他们的新技术将一条消息转变成某种超级金丝雀，可以比其它任何已知消息更好地检验其健康状况。任何隐藏在它的超级结构某个地方的显著破坏都可以通过少量位置的简单检测暴露出来。

魏茨曼科学研究院的 Irit Dinur 协同构造出集合了多条理想性质，并且它们在码字拉长时保持常值的一种纠错码

“这初看上去并不太可行，”哈佛大学的 Madhu Sudan 说道，“而这一成果突然告诉你这是可以做到的。”

大多数先前用来编码数据的方法都依赖于某种形式的随机性。但是对于局域可检测性，随机性帮助不大。取而代之的，研究者们设计了对于数学家们来说全新的一种高度不随机的图结构，并在此基础上发展了他们的新方法。让信息变得尽可能可靠一方面出于理论上的好奇，另一方面也是实用上的进步。

编码入门

噪声在通信中无所不在。为了对它进行系统分析，研究者们将信息表是成比特0和1的序列。于是我们可以将噪声视为对某些比特的随机翻转效应。

有很多方法来处理这种噪声。考虑这样一段信息，一条简短的消息，01。将它的每个片段——每个比特——重复三次，得到000111。于是，哪怕噪声破坏了比如说第二和第六个比特——将消息编程010110——接受者仍能通过两次多数投票（一次对0，一次对1）来纠正错误。

这种修饰信息的方法被称为编码。此时，与编码随之而来的是一种处理错误的过程，因此也把它叫做纠错码。编码就好比字典，每一种定义了像000111这样的码字的特定集合。

为了运作良好，编码必须具有一些性质。首先，它包含的码字不能太相似了：如果一种编码包含码字0000和0001，只需付出一个比特翻转的代价就可以混淆它们。其次，码字不能太长。比特重复确实可以让消息更耐久，但也使得发送起来耗时更长。

这两条性质被称为码距和码率。好的编码应该（在不同码字之间）有较长的码距，且（在传输真实信息时）有较高的码率。但是你如何才能同时获得这两条性质呢？1948年，Claude Shannon 证明，对于直接随机选取码字的任何编码，这两条性质之间会有一个接近最优的取舍。不过，完全随机选取码字会生成一本不可预知的字典，根本没法查找。换句话说，Shannon 证明好的编码存在，但他得到它们的方法不太好用。

“它是一种存在性结果，”哥伦比亚大学的 Henry Yuen 说道。

在接下来的40年里，计算机科学家们竭力找出非随机方案来排布比特，以逼近随机的理想结果。到了1980年代末期，他们的编码被用到种种领域，从CD到卫星传输。

1990年，研究者们构想出了局域可探测性的概念。但这条性质显得与众不同。如果你随机选出一种编码，像 Shannon 提议的那样，毫无可能它会是局域可检测的。这些就像是随机编码宇宙中的白化蝴蝶——美艳动人，如果它们存在的话。

“事实上哪怕证明它们存在也是无比困难的，”Yuen 说道，“更别说找出一个具体的例子来了。”

图即编码

“对于我们来说，考虑一个图跟考虑一种编码没什么两样。”

                                                                          Dana Moshkovitz, 德克萨斯大学，奥斯汀市

要理解检测性为何如此难以获得，我们需要把一条消息不仅仅当成一串比特，还要当成一个数学上的图：由边（线）连接起来的顶点（点）的集体。自从Richard Hamming 在Shannon 工作的两年之后发明第一种巧妙的编码时【译注：这里补充一点细节。事实上，Hamming 码的发明先于 Shannon 1948年的奠基性论文“The Mathematical Theory of Communication”，但出于专利申请的考虑相关论文直到两年后才发表。这一点可以从 Shannon 在该文中对 Hamming 码的引用得到证实。详见，“From Error-Correcting Codes Through Sphere Packings To Simple Groups”，Thomas M. Thompson 著。】，这一等价性对于理解编码就已经很关键了。（在R. Michael Tanner 1981年的论文发表后图论视角变得特别具有影响力。）

Hamming 的工作为1980年代纠错码的普遍应用奠定了基础。他提出了这样一条规则，为每条消息匹配上一套收据，用来记录其比特。具体来说，每条收据是消息中精心选定的一部分比特的总和。当这一求和是偶数时，收据记录0，而当其是奇数时，收据上记录1。换句话说，每条收据可以用单个比特来表示，研究者们称其为奇偶校验比特，或者奇偶比特。

Hamming 指定了一套流程来将这些收据附到一条消息上。而接收者可以自己计算这些求和来尝试重现收据，进而探测错误。这些 Hamming 码运作得极其良好，而它们正是视码为图和视图为码的出发点。

“对于我们来说，考虑一个图跟考虑一种编码没什么两样，”奥斯汀市德克萨斯大学的 Dana Moshkovitz 说道。

为了从编码生成图，先从码字开始。对于每一比特信息，画一个顶点（节点），称为数位节点。接着对于每一个奇偶比特也画一个节点；这些被称为奇偶节点。最后，画线将每个奇偶节点与它要进行求和以得到奇偶值的那些数位节点连起来。这样你就从一种编码生成了一个图。

将编码与图等同起来逐渐在编码创作艺术中变得不可或缺。1996年，Michael Sipser 和Daniel Spielman 使用这一方法，基于一类所谓扩展图（expander graph）创建了一种突破性的编码。虽然仍未提供局域可检测性，但他们的编码在其它方面被证明是最优的，并最终为这里的最新成果奠定了基础。

扩展可能性

扩展图由两条看似矛盾的性质所刻画。首先，它们是稀疏的：每个节点只连到相对较少的其它节点。其次，它们具有所谓扩展性——正如其名——从而意味着没有哪个节点集合会成为瓶颈，使得没多少边通过。【译注：对此一个直观的图像是，每个小的顶点集合都有较大的邻域。】换句话说，每个节点都跟其它节点连接良好——尽管它只有很稀疏的边。

“这样一个实体究竟为何会存在？”Evra 说道，“不难想象，如果图很稀疏，那么它的连接应该不会那么密切才是。”

可事实上扩展图构造起来出人意料地容易。如果你随机地构造一个图，在节点间进行随机连接，扩展图会不可避免地出现。它们就好像纯粹、未加精炼的随机性的源泉，从而成为了Shannon 指出的好编码的天然构建模块。

Sipser 和 Spielman 弄清了如何将一个扩展图转换成一种编码。他们构想出来的码字是由许多短得多的字组装起来的，而这些短字由他们所谓小码来产生，通常选为Hamming码。码字的比特由扩展图的边来表示，而小码的所有收据都在单个节点处表示出来。【译注：一个简单而直观的说明是，我们用小码来装饰每个节点。】

事实上，Sipser和Spielman证明，如果你在每个节点出定义的小码都具有好的性质，那么由于图的连接性如此良好，这些性质会传播到整个编码。这一传播赋予了他们一种创建好编码的方法。

“扩展，扩展，再扩展，”Evra 说道，“这就是成功的秘诀。”

不过，局域可检测性还是不可能。假定你从一种扩展码的一个有效码字出发，将某个节点处的一个收据或者说奇偶比特移除。这会构成一种新的编码，并且它拥有比初始码多得多的有效码字，因为它们需要满足的收据少了一条。对于那些想要冒充初始码的人来说，这些新码字会满足绝大多数节点上的收条——几乎全部节点，除了有条收据被删除的那个。并且，由于两种编码都有较长的码距，看起来对的新码字与初始码字集会相距甚远。局域可检测性根本与扩展码不相容。

为了获得检测性，研究者们只得想办法去对抗之前如此有用的随机性。最终，研究者们前去了随机性无法抵达的地方：更高维度。

随机的对立面

一直以来人们并不清楚这是否一定可以做到。局域可检测性在2007年就已经实现了，不过付出了其它参数例如码率和码距的代价。特别地，这些参数在码字变长时会退化。在一个持续寻求发送和存储超长消息的世界，这些收益的递减将会是一个很大的缺点。（尽管在实际中，哪怕是现存的局域可检测码也已经比大多数工程师的使用需求强大得多了。）

1996年，Michael Sipser（左图）和 Daniel Spielman 基于扩展图构造出一种编码，它拥有多种出色性质，但完全做不到局域可检测。

著名的c³猜想说的是，可以找到这样一种编码，它拥有最优的码率、码距以及局域可检测性，并且这些性质在消息拉长时全都保持为常值。先前的结果使得一些研究者认为，这样的解必然存在。但进展逐渐迟缓下来，而另外一些结果表明这一猜想或许是错误的。

“许多同行认为，这个梦想有些过于美好，很可能无法成真。”Gur 说道，“情况看起来相当糟糕。”

可到了2017年，一股全新的想法涌现出来了。Dinur 和 Lubotzky 在参加以色列高等研究院的一个年度研究项目时开始合作。他们逐渐认为数学家 Howard Garland 1973的一个结果或许正包含着计算机科学家们寻求的东西。鉴于常规扩展图本质上是一维结构，其中每条边都仅在一个方向上延伸，Garland 创造出了这样一种数学对象，它可以解释为跨越高维度的扩展图，其中图的边被重新定义为正方形或是立方体。

Garland 的高维扩展图拥有对于局域可检测性来说似乎很理想的性质。它们必须从头开始刻意地进行构建，使得它们成为了随机性的天然对立面。并且它们的节点互相连接得如此紧密，以致局域特征变得跟整体行为几乎不可区分。

“在我看来，高维扩展图就是一个奇迹，”Gur 说道，“你只是对对象的某个部分进行了微小的调整，结果一切都改变了。”

Lubotzky 和 Dinur 开始试着基于 Garland 的工作来创建可能解决c³猜想的编码。Evra, Livne 和 Mozes 很快加入了团队，他们中的每个人都精通高维扩展图的某个不同层面。

很快他们就开始在研讨会和报告中展示他们的工作，但并非所有人都确信高维扩展图理论可以铺平前进的道路。而要彻底弄懂它，学习的道路绝非一马平川。

“那时候它看上去就像是太空时代的技术，各种复杂的，怪异的数学工具，在计算机科学里前所未见。”Gur 说道，“看起来有些过度发展了。”

到了2020年，研究者们遇到了阻碍，直到他们意识到无需借助这些相当复杂的新工具就能对付过去。他们从高维扩展图中获得的启发就已足够。

传播错误

在他们的新工作中，作者们设法将扩展图组装成一种新图，进而得出了局域可检测码的最优形式。他们把这种新图称为左-右 Cayley 复形。

正如 Garland 的工作，他们的图的组建模块不再是一维的边，而是二维的正方形。码字中的每个信息比特被指派给一个正方形，而奇偶比特（或者说收据）被指派给边和拐角（也就是节点）。于是每个节点定义了可以连接到它的比特（或者说正方形）的值。

                                    “局域可检测性的关键在于结构。”

Shai Evra, 耶路撒冷市希伯来大学

要对他们的图的形状有所感受，想象一下从内部，站在一条边上，去观察它。他们的图在构造时确保每条边有固定数目的正方形连接到它。于是从你的视角看来，你会感觉到好像在从一本册页的书脊出往外看。然而，在册页页面的其它三条边处，你会看到新的册页的书脊从那里分岔。册页会从每条边处永无止境地分岔出去。

“它没法视觉化。这正是要点所在。”Lubotzky 说道，“正因如此它才如此复杂。”

关键之处在于，这种复杂的图既享有扩展图的性质，例如稀疏性和连通性，同时还具有丰富得多的局域结构。例如，处于高维扩展图的一个顶点处的观测者可以借用这一结构直接推断出整个图是强连通的。

“随机性的对立面是什么？是结构，”Evra 说道，“局域可检测性的关键在于结构。”

要看出这种图如何给出一种局域可检测码，回顾一下扩展图码，如果一个比特（也就是边）出错了，这个错误只能通过校验它直接相邻的节点上的收据来探测。但在左-右 Cayley 复形中，如果比特（正方形）出错，这一错误在多个不同节点处都是可见的，其中一些甚至都没有边将它们相互连接起来。

以这种方式，在一个节点处的检测可以揭示来自遥远节点的错误的信息。通过借用高维度，图的最终连接方式远远超出了我们通常的认知。

在可检测性之外，新编码保有了码率、码距以及其它应有性质，哪怕在码字拉长时，从而证明了c³猜想是对的。它改写了纠错码的现状，同时也标记着将高维扩展图的数学引入到编码所带来的第一次实质性的回报。

“它是看待这些对象的一种全新方式。”Dinur 说道。

在实际和理论上的应用应该很快就会来临。局域可检测编码的不同形式当前已被使用在去中心化金融中，而一个优化的版本将带来更好的去中心化工具。此外，计算机科学中还存在完全不同的理论概念，所谓概率性可校验证明，它与局域可检测编码存在某种相似性。现在既然我们找到了后者的最优形式，前者的破纪录版本很可能也将出现。

从根本上说，新编码标志着概念上的一座里程碑，是至今在超出随机性所设定的边界后迈出的最大步伐。而唯一遗留的问题是，在对信息进行锻造时，其良好程度真的会有上限吗？

原文链接：

https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/