信息传输不可避免会受到外部的干扰破坏，我们是否可以编码信息，使得接收者在阅读之前就能一眼识别信息是否被篡改？在一项最新研究中，计算机科学家和数学家通过将扩展图推广到高维形式来表示编码，使之具有稀疏性、关联性，和丰富的局部结构。对图中一个节点进行测试，就可以给出远处节点的错误信息，从而实现局部可测试性。这是一种新的信息编码方式，超越了传统依靠随机性的编码，确立了纠错码的最新技术水平。
研究领域：信息编码，图论，信息论
Mordechai Rorvig | 作者
潘佳栋 | 译者
梁金 | 审校
邓一雪 | 编辑
假设你正试图传输信息。计算机将每个字符转换成比特，将每个比特转换成信号，然后通过铜导线、光纤或空气发送。尽管你尽可能地小心翼翼，但另一边收到的信息将与你发送的信息不一样，噪声总是会造成一些破坏。
在20世纪40年代，计算机科学家首次面对不可避免的噪声问题。五十年后，他们想出了一个优雅的方法来解决问题：是不是可以对一条信息进行编码，使得在收件人阅读之前就能明显看出信息是否被篡改？人们不能通过一本书的封面来判断里面的内容，但这种编码的信息可以。
他们将信息的这一特性称为局部可测试性（local testability），人们可以在其中仅仅几个地方对信息进行超快速测试，以确定信息的正确性。在接下来的30年里，研究人员在创建这种测试方面取得了实质性的进展，但他们的努力总是没有回报。许多人认为，局部可测试性将永远不会以其理想的形式实现。
在11月8日发布的一份预印本论文[1]中，以色列魏兹曼科学研究所的计算机科学家伊雷特·迪努尔（Irit Dinur）[2]和耶路撒冷希伯来大学的四位数学家谢·埃弗拉（Shai Evra）[3]、罗恩·利夫内（Ron Livne）[4]、亚历克斯·卢博茨基（Alex Lubotzky）[5]和沙哈尔·莫兹（Shahar Mozes）[6]找到了实现局部可测试性的方法。
图1：魏茨曼科学研究院的 Irit Dinur 帮助构建了一种具有一系列理想性质的纠错码，即使在码字规模扩大时，纠错码也保持不变。| 来源：Hadar Dveer Benyamini
“这是我所知道的数学和计算机科学领域最了不起的成就之一，它一直是整个领域的圣杯。”华威大学的汤姆·古尔（Tom Gur）说 [7]。
他们的新技术将一条信息转化为一个“超级告密者”（super-canary），它比已知的其他任何信息都能更好地检查信息的完好状态。只需要通过几个点的简单测试，埋藏在其上层结构中任何地方的任何重要错误都会显示出来。
哈佛大学的马杜·苏丹（Madhu Sudan）[8] 说，“这看起来并不合理，但是结果突然告诉你可以做到。”
大多数之前的数据编码方法都依赖于某种形式的随机性。但对于局部可测试性来说，随机性无能为力。相反，研究人员不得不设计出一种数学上全新的高度非随机的图结构，他们的新方法就基于此。这既是一种理论的好奇心，也是尽可能使信息传输更可靠的实践进步。
噪声在通信中无处不在。为了系统地分析它，研究人员首先将信息表示为比特（即1和0）的序列。然后，我们可以将噪声视为翻转某些比特的随机影响。
有许多方法来处理噪声，著名数学家冯·诺伊曼提出一种方法，利用冗余来纠错。考虑一条简短的信息，比如01。如果计算机将每一个比特复制三份，得到 000 111。然后，即使噪声碰巧破坏了三个拷贝中的一个（比如第2和第6位），使信息变为 010 110，接收者仍然可以通过两次多数投票来纠正错误，如将第2位比特翻转回0，第6位翻转回1。
这样一种修改信息的方法被称为纠错码（error-correcting code），在编码有效信息的基础上，码字（codeword）还会附带一个修复错误的程序。编码就像字典，每一个字典都定义了一套特定的码字，如 000 111。
为了运行顺利，纠错码必须有几个特性。首先，纠错码中的字符不应该太相似：如果一个编码包含码字0000和0001，只需要一个比特翻转，就可以混淆这两个字符。第二，码字不应该太长。重复的比特可能会使信息传输更可靠，但也会使信息的发送时间更长。
这两个属性被称为距离（distance）和速率（rate）。一个好的编码应该同时具有较大的距离（不同码字之间）和较高的速率（传输真实信息）。但如何才能同时获得这两个特性呢？1948年，克劳德·香农（Claude Shannon）提出，任何由随机选择形成的码字都会在这两种特性之间有一个近乎最佳的权衡。然而，完全随机地选择码字会产生一个不可预测的字典，它太难整理。换句话说，香农证明，好的编码是存在的，但他制作这些编码的方法并不可行。”这只是一个事实上存在的结果，”哥伦比亚大学的亨利·袁（Henry Yuen）[8]说。
在接下来的40年里，计算机科学家们努力寻找非随机的方法，来实现接近随机选择的比特排列。到20世纪80年代末，他们的编码被用于从光盘到卫星传输的所有领域。
1990年，研究人员提出了局部可测试性的想法。但局部可测试性的性质是不同的。如果像香农建议的那样，随机挑选一个编码，那它就不可能是一个局部可测试的编码。局部可测试的编码是随机编码宇宙中的白化蝴蝶——异常美丽，如果它们存在的话。袁说：“你实际上必须首先努力证明它们的存在，更不用说想出一个明确的例子了。”
为了理解为什么可测试性如此难以获得，我们需要把信息不仅仅看作是一串比特，而是一个数学上的图：一个由边（线）连接的顶点（点）的集合。在香农的证明提出两年后，理查德·汉明（Richard Hamming）创造了第一个聪明的编码——汉明校验码（Hamming codes），使得编码和图的等价关系成为理解编码的核心。（在R.迈克尔·坦纳（R.Michael Tanner）于1981年发表一篇论文[9]之后，图的观点变得十分有影响力。）
汉明的工作为纠错码在20世纪80年代获得普遍应用创造了条件。他提出了一条规则：每条信息都应与一组回执配对，这些回执记录了信息比特。更具体地说，每个回执是这条信息中精心选择的比特子集的总和。当这个总和为偶数时，回执被标记为0，当它为奇数时，回执被标记为1。每个回执由单一比特表示，研究人员称之为奇偶校验或校验位。
汉明设计了一个程序将校验位附加到信息中。然后，接收者可以通过尝试复制校验位、计算比特的总和来检测错误。汉明码的效果非常好，这是将编码视为图、将图视为编码这一思想的出发点。
图2：将编码表示为图。为了检查编码的真实性，我们可以添加一个校验位，跟踪编码的具体形式。每个校验位会检查信息中的一个比特子集。如果该子集总和是偶数，那么校验位就是0；如果是奇数，校验位就是1。这些新的比特可以表示为图中的顶点，这些顶点将它们所检查的比特的顶点连接起来。| 来源：Samuel Velasco/Quanta Magazine
德克萨斯大学奥斯汀分校的达娜·莫斯科维茨（Dana Moshkovitz）[10]说：“对我们来说，思考图和思考编码是同一件事。”
我们可以从编码开始创造图。对于每一个信息比特，画一个顶点（或节点），称为数字节点（digit node）。然后为每个奇偶校验位画一个节点，称为奇偶校验节点（parity node）。最后，从每个奇偶校验结点到相加产生其奇偶校验值的数字结点连线，就从编码创造了图。
将编码和图看作等价物，成为了制作编码的艺术。1996年，迈克尔·西普斯（Michael Sipes）和丹尼尔·斯皮尔曼（Daniel Spielman）用这种方法从扩展图（expander graph）中创造了一种突破性的编码。尽管他们的编码仍然不能实现局部可测试性，但是它在其他方面被证明是最佳的，并最终成为最近这项新成果的基础。
扩展图有两个看似矛盾的特性。首先，它们是稀疏的，每个节点与其他节点的连接都相对较少。其次，它们有一种被称为扩展性的属性——这就是它们名字的由来，这意味着没有一组节点是很少有边经过的瓶颈节点。换句话说，每个节点都与其他节点有很好的连接——尽管它所拥有的连接很稀少。
“为什么这样的图可以存在？”Evra问道，”我们通常认为，如果图是稀疏的，那么它与其他节点就没有那么多连接。”
但出乎意料的是，扩展图实际上很容易构建。如果你以随机的方式构建一个图，随机选择节点连接，就会不可避免地得到一个扩展图。这些图是纯粹的随机性之源，是构建香农所认为的好编码的自然之选。
图3：挖掘随机性。扩展图由节点的随机连接构建而成，这个特点使得它们成为基于随机性获得编码的最好起点。扩展图的两个主要性质：（1）稀疏性：每个节点只有很少的相邻节点；（2）扩展性：节点之间有良好连接，没有瓶颈节点。| 来源：Samuel Velasco/Quanta Magazine
Sipser 和 Spielman 研究出了如何将扩展图变成编码。他们想出的码字由汉明校验码产生的许多更短字符——他们称之为小码（small code）——组成。码字的比特表示为扩展图的边，小码的所有校验位都表示为节点。
实际上，Sipser 和 Spielman 证明，如果在每个节点上定义具有良好属性的小码，那么由于扩展图具有良好的连接性，这些属性会传播到全局编码中。这种传播给了他们一种创建良好编码的方法。”扩展，扩展，再扩展。这就是成功的秘诀。” Evra 说。
然而，局部可测试性是不可能的。假设你有一个来自扩展图编码的有效码字，之后从一个单一节点上去除一个奇偶校验位。这将构成一个新的编码，它比第一个编码有更多的有效码字，因为它们需要满足的校验位会少一个。对于创造原始编码的人来说，这些新的码字将满足大多数节点的校验位——所有节点，除了校验位被抹去的那一个节点。然而，由于这两种编码有很大的距离，看似正确的新码字距离原来的码字集极其遥远。局部可测试性与扩展图编码根本不相容。
为了获得可测试性，研究人员必须弄清楚如何与曾经很有帮助的随机性作斗争。最后，他们选择探索随机性不存在的地方：更高维度。
研究人员并不确定是否能在高维获得可测试性。最终在2007年，局部可测试性得以实现，不过要以速率和距离这些参数为代价。特别是，这些参数会随着码字的增加而降低。在一个不断寻求发送和存储更大信息的世界里，收益递减是一个主要缺陷。（虽然在实践中，即使是现有的局部可测试编码，也已经比大多数工程师需要使用的功能更强大了。）
图4：1996年，Michael Sipes 和 Daniel Spielman 创建了一个基于扩展图的编码，它具有很好的组合特性，但完全未能达到局部可测试。| 来源：Bryce Vickmark; John D. and Catherine T. MacArthur Foundation
研究人员提出猜想，可以找到具有最佳速率、距离和局部可测试性的编码——即使信息量增大，这些参数都保持不变——这被称为 c3 猜想。先前的结果使一些研究人员认为，这个猜想必然会被证明。但实际上，进展十分缓慢，并且其他结果表明该猜想可能是错误的。“这个研究领域中的许多人都认为，这个猜想是一个看似美好，但事实上遥不可及的梦，”Gur说，“事情看起来相当严峻。”
但在2017年，新的想法出现了。Dinur 和 Lubotzky 在参加以色列高等研究所为期一年的研究项目时开始合作。他们开始相信，数学家霍华德·加兰（Howard Garland）在1973年的一项成果可能正是计算机科学家所寻求的。普通的扩展图本质上是一维结构，每条边只向一个方向延伸，而 Garland 创造了一个数学对象，可以被解释为一个张开更高维度的扩展图，图的边被重新定义为正方形或立方体。
Garland 的高维扩展图似乎是实现局部可测试性的理想选择。它们必须被有意地从头开始构建，因而是随机性的对立面。而且它们的节点如此紧密的相互连接，以至于局部特征与全局特征几乎没有区别。“高维扩展图是一个奇迹。只要对图的一部分做微小调整，一切都会改变。”Gur 说。
Lubotzky 和 Dinur 开始尝试在 Garland 工作的基础上创建一个可能解决 c3 猜想的编码。Evra, Livne 和 Mozes 很快加入了这个团队，他们每个人都是高维扩展图不同方面的专家。很快，他们就在研讨会和讲座上介绍了自己的工作，但并不是每个人都相信高维扩展图能够解决问题。要完全理解高维扩展图需要攀越一条陡峭的学习曲线。“当时它看起来像是遥远未来的技术，是计算机科学中从未见过的复杂而奇特的数学工具。这似乎有些小题大做。”Gur 说。
2020年，研究人员陷入了困境，直到他们意识到，不依靠复杂的新工具也能解决问题。从高维扩展理论中获得的灵感已经足够。
在他们的新工作中，作者们提出将扩展图组装起来创建一个新的图，这会产生具有最佳形式的局部可测试编码。他们称之为左右Cayley复形（left-right Cayley complex）。
与 Garland 的工作一样，这种图的构件不再是一维的边，而是二维的正方形。编码中的每个信息比特被分配到一个正方形，而奇偶校验位被分配到边和角（即节点）。因此，每个节点都定义了连接到它的比特（或正方形）的值。
为了了解这个图到底是什么样，我们可以想象站在其中一条边上，从图的内部进行观察。在构建图时，每条边上都连接有固定数量的正方形。因此，从你的位置看来，会感觉像是从小册子的书脊向外看；但是，从书页的其他三边，也会看到从中分出新小册子的书脊。小册子会从每个边缘分出，直至无穷。
图5. 为了创造一种最佳的信息编码方法，研究人员用图来表示编码，这个图的形式是由小册子组成的相互连接的网络，它向外扩展，直至无穷。图中的一个正方形代表信息的一个比特。| 来源：Olena Shmahalo for Quanta Magazine
“不可能看到这样的图像，这就是问题的关键，也是为什么问题如此复杂。”Lubotzky 说。
至关重要的是，这种复杂的图也具有扩张图的属性，如稀疏性和关联性，但具有更丰富的局部结构。例如，坐在高维扩展图一个顶点的观察者可以利用局部结构直接推断出整个图是强连接的。
“随机性的对立面是什么？是结构。局部可测试性的关键是结构。”Evra 说。
为了了解这种新的高维扩展图如何导致局部可测试的编码，首先考虑一个扩展图的编码，如果一个比特（一条边）有错误，只能通过检测其紧邻节点的校验位来发现这个错误。但在左右Cayley复形中，如果一个比特（一个正方形）有错误，那么这个错误可以从多个不同的节点看到，甚至包括一些没有互相连接的节点。这样一来，对一个节点的测试可以给出远处节点的错误信息。通过利用更高的维度，图以超出我们认知的方式连接。
除了可测试性之外，新编码还保持了速率、距离和其他所需的特性，甚至在码字扩展时也是如此，证明了 c3 猜想的正确性。它确立了纠错码的最新技术水平，也是将高维扩展图应用于编码的第一个实质性回报。“这是观察这些编码的全新方式。”Dinur 说。
算法实践和理论上的应用应该很快就会出现。不同形式的局部可检测编码现在正被用于去中心化的金融，而一个最佳版本将帮助实现更好的去中心化工具。此外，计算机科学中有完全不同的理论构造，称为概率可检测证明（probabilistically checkable proofs），它与局部可检测编码有相似之处。现在我们已经找到了后者的最佳形式，前者的新版本似乎也可能出现。
最终，新编码标志着一个概念上的里程碑，这是超越由随机性设置的编码界限的最大一步。剩下的唯一问题是，信息的伪造程度是否存在真正的限制。
[1]https://arxiv.org/abs/2111.04808
[2]https://www.wisdom.weizmann.ac.il/~dinuri/
[3]https://mathematics.huji.ac.il/people/shai-evra?ref_tid=4311
[4]https://mathematics.huji.ac.il/people/ron-livne
[5]http://www.ma.huji.ac.il/~alexlub/
[6]https://mathematics.huji.ac.il/people/shahar-mozes
[7]https://www.dcs.warwick.ac.uk/~tomgur/
[8]http://www.henryyuen.net/
[9]https://ieeexplore.ieee.org/abstract/document/1056404
[10]https://www.cs.utexas.edu/~danama/
https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/
集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「集智斑图」推送论文信息。扫描下方二维码即可一键订阅：
点击“阅读原文”，追踪复杂科学顶刊论文
