上海创智学院李帅老师团队，借助自研智能体系统与前沿AI模型，围绕二元线性码最优最小距离问题开展数学证明与计算验证，取得系列进展：确定了四组长期未定的二元线性码最优最小距离，同时将另一组的最小距离上界进行压缩。此次突破涉及的五组参数的研究最早可追溯到1985年Tom Verhoeff 的技术报告《二元线性码最小距离界限表》（UPDATING A TABLE OF BOUNDS ON THE MINIMUM DISTANCE OF BINARY LINEAR CODES）[1]，其中四组上界自1985年后便再无突破 [1-3]。
一、一个基础而困难的堆球问题
从手机接收信号，到计算机保存数据、深空探测器传回图像，信息都可能因噪声或设备扰动而出现比特错误。纠错编码是支撑可靠信息传输与保存的数学基石，其中，二元线性码是最基础、应用最广泛的一类，Wi-Fi和5G使用的LDPC码，以及5G使用的Polar码，都是典型代表 [4–5]。1948年，香农在奠定现代信息论的论文中揭示了带噪信道可靠通信的理论极限，开启了寻找高效纠错码的长期探索 [6]。1950年，理查德·汉明在奠基论文《检错与纠错码》中，将码字之间的最小距离与检错、纠错能力明确联系起来，为研究编码的性能边界提供了基本尺度 [7]。这些基础理论逐步走向产业应用，推动了通信与存储技术的发展。华为轮值董事长徐直军曾将编码技术称为“通信领域里最璀璨的一颗明珠” [8]。
从理论探索到实际应用，一个基础问题始终牵引着研究：在码长和承载的信息量固定时，究竟能抵御多少错误？最小距离问题正是刻画这种能力的核心问题之一。确定一个最优值，意味着同时回答“最好能做到什么”与“哪些性能不可能实现”，为给定条件下的二元线性码划定严格的性能边界。香农奖得主N. J. A. Sloane也将这类最优码问题列为编码理论最基本的问题之一 [9-10]。
从数学上看，它可以理解为汉明空间里的“堆球”问题：把二进制串看成点，两个串有多少位不同，距离就是多少。编码要选出一组彼此足够远的点作为合法码字；每个码字周围半径为t的汉明球，包含与它相差不超过t位的字符串。只要这些球互不相交，就能纠正至多t位错误，找回原来的消息 [11]。
图1 汉明空间中的“堆球”示意。以 (7,3,4) 码为例，球心代表合法码字，球内包含与其相差至多一位的二进制串。各球互不相交，使信息在发生一位比特错误后仍能被正确恢复 [11]。
一个二元 (n,k,d) 线性码，用n位承载k位信息，让不同码字至少相差d位。问题的核心是：固定n和k，最大的d是多少？定义只需几句话，答案却可能数十年无法确定。
二、自动化科研助力问题突破
自香农奠基现代信息论之后的近八十年间，MacWilliams、Sloane等学者为该问题发展了丰富的代数工具，Verhoeff、Brouwer、Grassl等研究者持续整理和更新具体参数的距离界 [1-3]，但仍有许多开放区间困扰着前赴后继的科学家。
图2 二元线性码的未定区间与五项进展。横轴为码长n，纵轴为维数k，蓝灰色格子表示最优最小距离仍未确定。棕色框及右侧放大图为五项结论：四项最优值确定，一项区间收窄。码表中仍有众多开放区间等待突破 [3]。
面对众多尚未闭合的区间，团队借助自动化科研系统，将文献调研、路线设计、证明推进与独立验证贯通起来。系统围绕目标参数探索可行路线，根据推导与计算证据持续修订方案，并将已核结论、失败路线和验证记录沉淀到研究知识库，为后续研究提供依据。在此次研究中，一个核心计算证明及三个直接推论带来了四项上界改进，再结合一项基于已有文献的归约，最终形成五项结论：确定四个最优最小距离，并收窄一个尚未闭合的区间。
图3 自动化科研流程与五项编码结论。通过结构归约、穷尽排除和独立复核，核心证明导出三个直接推论；另结合已有文献完成一条独立归约。五项结论与已有构造相结合，确定四个最优最小距离，并收窄一个尚未闭合的区间。
此次证明推进的四项上界，在1985年的码表中就已明确列出，距今已有四十余年，将 (43,10)、(44,10)、(44,11) 和 (45,11) 的最小距离上界分别列为17、18、17和18。此次研究将它们分别降低至16、17、16和17，使前三组参数的上下界重合，确定其最优值，并将第四组参数的未知范围收窄至16–17。
团队首先聚焦于其中的 (43,10)，因为该问题的推进，还能推动其他参数的结论一并确定。该问题难点在于，证明“不存在”必须覆盖所有可能，仅把生成矩阵写成标准形式，就有330个待定二进制项，约有1099种原始组合。
（一）先找结构，再穷尽验证
团队首先假设存在最小距离至少为17的 (43,10) 码，为它添加一个奇偶校验位，得到最小距离至少为18的偶 (44,10) 码。利用MacWilliams恒等式与一个四次多项式，团队证明它必然具有涉及四个坐标的特殊校验关系。沿这些坐标缩短，就得到一个满支撑的 (40,7,18) 母码。
已有分类结果表明，相关母码在坐标置换意义下只有172类 [12-13]。任何目标码都必须由其中一类扩张而来，庞大的搜索由此有了明确的覆盖范围。
接下来，团队找到一个能提前排除扩张的必要条件：对每个母码，列出所有满足距离要求的候选陪集；目标码若存在，至少需要两个不同候选各自合格，且相加后仍然合格。然而，全部172类母码的候选集合都具有“无和”（sum-free）性质：任意两个不同候选相加，都会违反距离要求。扩张因此不可能完成。
至此，团队已筛选排除约99.99994%的偶陪集候选，将后续兼容性检查的范围缩小至429,024个候选陪集。按照团队的计算记录，两套独立枚举程序得到相同的完整候选集合。独立验证程序进一步重放了各母码内合计约6.19亿对不同候选的排除见证，没有一对兼容。每一对都有可直接复核的低重量码字作为拒绝依据，最终排除了所有可能的扩张路径，证明 (43,10,≥17) 码不存在。
（二）一个核心证明，带来一组连锁结论
由这一核心定理，通过删去坐标和缩短码等标准操作，可以直接推出 (44,10,≥18)、(44,11,≥17) 和(45,11,≥18) 码也不存在。结合已有构造，前三组参数的最优最小距离由此确定d2(43,10)=16、d2(44,10)=17、d2(44,11)=16；第四组参数则收窄为16≤d2(45,11)≤17。
沿着利用不同参数之间的关系推导结论的思路，团队进一步梳理已有研究，将目光投向 (42,16)。2020年，Stefka Bouyuklieva与Iliya Bouyukliev在论文《通过扩张残余码分类线性码》（CLASSIFICATION OF LINEAR CODES BY EXTENDING THEIR RESIDUALS）[14] 中证明，二元线性 (41,14,14) 码不存在。团队以这一已发表结果为起点，建立了一条通向 (42,16) 的完整归约链：若 (42,16,≥13) 存在，经奇偶扩展、两次缩短并按需取子码，再将最小距离归一化到14，即可得到被文献排除的 (41,14,14) 码，产生矛盾。因此，结合已有构造，d2(42,16)=12。
三、成果意义与后续方向
这项工作形成了五项相互衔接的结论：一个核心计算证明导出三个直接推论，再结合一个文献推论，确定四个最优值，并收窄一个尚未闭合的区间。其中 (43,10)、(44,10) 和 (44,11) 的最优最小距离分别确定为16、17和16；结合2020年已发表的不存在性结论，进一步确定 (42,16) 的最优最小距离为12。这四组参数下，已有构造均达到理论最优；(45,11) 的未知区间则由16–18收窄至16–17。明确这些边界，让研究者能够将精力转向仍有突破空间的目标。
五项结论之外，二元线性码的距离表中仍有众多尚未闭合的区间，等待新的构造与证明。目前，团队正在扩大自动化研究的覆盖范围，并行开展构造搜索与不存在性研究。系统将持续积累可复用的归约、失败路线和验证证据，推动更多参数的上下界逐步接近。
◆ 参考资料：
[1] Verhoeff, T. Updating a Table of Bounds on the Minimum Distance of Binary Linear Codes. EUT Report 85-WSK-01. Eindhoven: Technische Hogeschool Eindhoven, January 1985.
[2] Brouwer, A. E.; Verhoeff, T. An Updated Table of Minimum-Distance Bounds for Binary Linear Codes. IEEE Transactions on Information Theory, 1993, 39(2): 662–677. Table I, Column 1. DOI：10.1109/18.212301.
[3] Grassl, M. Bounds on the Minimum Distance of Linear Codes and Quantum Codes. CodeTables.
[4] IEEE. IEEE Std 802.11n-2009: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications—Amendment 5: Enhancements for Higher Throughput. 2009. DOI：10.1109/IEEESTD.2009.5307322.
[5] 3GPP / ETSI. 5G; NR; Multiplexing and Channel Coding. 3GPP TS 38.212, Version 15.2.0, Release 15; ETSI TS 138 212 V15.2.0, July 2018. §5.3.1: Polar coding; §5.3.2: Low density parity check coding.
[6] Shannon, C. E. A Mathematical Theory of Communication. The Bell System Technical Journal, 1948, 27(3): 379–423; 27(4): 623–656. DOI：10.1002/j.1538-7305.1948.tb01338.x；10.1002/j.1538-7305.1948.tb00917.x.
[7] Hamming, R. W. Error Detecting and Error Correcting Codes. The Bell System Technical Journal, 1950, 29(2): 147–160. DOI：10.1002/j.1538-7305.1950.tb00463.x.
[8] 徐直军. 致敬探索者. 《华为人》，2018年9月，第338期，第3页。
[9] Sloane, N. J. A. Unsolved Problems in Graph Theory Arising from the Study of Codes. Graph Theory Notes of New York, 1989, 18: 11–20.
[10] IEEE Information Theory Society. Claude E. Shannon Award. N. J. A. Sloane.
[11] MacWilliams, F. J.; Sloane, N. J. A. The Theory of Error-Correcting Codes. North-Holland Mathematical Library, Vol. 16. Amsterdam: North-Holland, 1977.
[12] Bouyukliev, I.; Jaffe, D. B. Optimal Binary Linear Codes of Dimension at Most Seven. Discrete Mathematics, 2001, 226(1–3): 51–70. DOI：10.1016/S0012-365X(00)00125-4.
[13] Bouyuklieva, S.; Dzhumalieva-Stoeva, M. Optimal Linear Codes and Their Hulls. Mathematics, 2025, 13(15): 2491. §2, §5, Table A5. DOI：10.3390/math13152491.
[14] Bouyuklieva, S.; Bouyukliev, I. Classification of Linear Codes by Extending Their Residuals. In: Mathematical Software—ICMS 2020. Lecture Notes in Computer Science, Vol. 12097. Springer, 2020: 173–180. Proposition 2. DOI：10.1007/978-3-030-52200-1_17.
