摘要
arXiv:2504.00613v1 Announce Type: 新
摘要:寻找最大规模的删除校正码超过70年一直是开放问题,即使对于单个删除也是如此。在本文中,我们提出了一种新的方法来构造删除校正码。一个码是由满足某些约束条件的序列集合构成的,我们通过根据优先级函数贪心地添加优先级最高的序列来构建它。为了找到好的优先级函数,我们利用了Romera等人于2024年提出的由大型语言模型(LLM)指导的进化搜索FunSearch。FunSearch会迭代生成、评估和精化优先级函数,以构建大规模的删除校正码。对于单个删除,我们的进化搜索找到了构造出已知最大规模的函数,达到最大(猜想最优的)范沙莫夫-特内戈尔茨码大小,即使最大值未知,也独立地以等效形式重新发现它们。对于两个删除,我们找到了构造出新最佳规模的函数,对于码长 \( n = 12, 13 \) 和 \( 16 \),建立了改进的下界。这些结果展示了LLM指导的搜索方法在信息论和码设计中的潜力,并且是首次将此类方法应用于构建纠错码的应用。