学术报告：IEEE Transactions on Information Theory 2025年3月发表的(t,s)-突发错误渐进最优码研究

作者及机构
本研究由Yubo Sun（首都师范大学数学科学学院）、Ziyang Lu与Yiwei Zhang（山东大学网络空间安全学院及密码技术与信息安全教育部重点实验室）、Gennian Ge（首都师范大学数学科学学院/浙江大学）合作完成，发表于2025年3月的*IEEE Transactions on Information Theory*（第71卷第3期）。研究受中国国家重点研发计划（2020YFA0712100、2022YFA1004900等）及国家自然科学基金（12231014）资助。

学术背景
在DNA存储等新兴技术中，突发错误（burst error）——即连续符号的删除或插入——是主要错误类型之一。传统纠错码（如删除码或插入码）未充分利用错误的突发特性，导致冗余度（redundancy）较高。本研究提出了一种广义的(t,s)-突发错误模型（t为连续删除符号数，s为插入符号数），涵盖删除（s=0）、插入（t=0）和替换（t=s）等特例。目标是通过构造q进制（q≥2）的(t,s)-突发纠错码，实现冗余度仅为logn+o(1)的渐进最优解。

研究流程与方法
1. 问题建模与理论边界
- 定义(t,s)-突发错误：删除t个连续符号并在同位置插入s个任意符号。
- 通过球包装（sphere packing）论证，证明最优冗余度下界为logn+o(1)。定理1推导了错误球大小|Bt,s(x)|=q^(s−1)[(q−1)(n−t+1)+1]，定理2据此给出码率上界。

1. 码构造的核心策略

   • 连接性转化（第IV节）：
     
     • 将q进制(t,t)-突发码转化为q^(t−1)进制(2,2)-突发码（定理3），利用阵列表示（array representation）将t维错误降为2维。
       
     • 对t>s的情况，将(t,s)-突发码转化为q^(t−s)进制(t′,t′−1)-突发码，其中t′=⌈t/(t−s)⌉+1（定理4）。
       
   • 具体构造方法：
     
     • (2,2)-突发码（Construction 1）：通过行和约束（sum constraint）与加权校验（wvt constraint）实现解码，冗余度为logn+4logq+2（定理5）。
       
     • (t,t−1)-突发码（第VI节）：
       
     • 二进制码（Construction 2）：结合重量校验（sum mod 2t）、阵列行约束（sum mod 2）和标记序列（marker sequence）的几何约束，确保错误定位（定理7）。
       
     • 非二进制码（定理8）：引入签名函数（signature function）α(x)将q进制序列映射为二进制序列，利用(t+1,t)-突发码解码后，通过符号计数（symbol counting）和分段校验（segment-wise sum）恢复原序列。
       

2. 应用扩展

   • 将(t,s)-突发码应用于稳定删除（stable deletion）纠错的置换码（permutation code），冗余度同样逼近理论下界（表II）。
     

主要结果
1. 理论贡献：
- 证明了对于任意常数t、s和q≥2，存在冗余度为logn+o(1)的(t,s)-突发纠错码（Corollary 1）。
- 通过连接性转化，将复杂参数问题简化为(2,2)和(t,t−1)两类特殊情况（第IV节）。

1. 构造性成果：
   
   • 二进制(t,t−1)-突发码：通过三重约束（重量、阵列行、标记序列）实现p-有界（p-bounded）解码，冗余度logp+o(1)（Corollary 2）。
     
   • 非二进制码：签名函数α(x)将错误定位到单调段（monotone segment）邻域，结合符号计数和分段和校验实现精确恢复（Lemma 6-8）。
     

结论与价值
1. 科学价值：
- 首次为广义(t,s)-突发错误提供统一的理论框架和构造方法，填补了传统突发纠错码与混合错误码（如DNA存储所需）之间的空白。
- 通过降维转化和签名函数等创新方法，解决了非二进制码的高冗余难题。

1. 应用价值：
   
   • 直接服务于DNA存储系统，可高效纠正混合型突发错误。
     
   • 衍生的置换码为高密度存储（如磁记录、闪存）提供新解决方案。
     

研究亮点
1. 理论创新：提出(t,s)-突发错误的球包装边界，并证明其与(s,t)-突发码的等价性（Lemma 1-2）。
2. 技术突破：
- 通过阵列表示实现维度压缩，显著降低解码复杂度。
- 签名函数α(x)的创新应用，将q进制问题转化为二进制问题（Observation 2）。
3. 普适性：覆盖所有q、t、s参数，冗余度均达渐进最优。

其他价值
- 表I对比了现有(t,s)-突发码的冗余度，突显本研究的优越性。
- 第VII节讨论了在稳定删除、局部错误等场景下的扩展应用，进一步拓宽了适用边界。

（注：专业术语如“burst error”首次出现时标注英文，后续使用中文“突发错误”；“redundancy”译为“冗余度”；“signature function”译为“签名函数”并保留α(x)符号。）