Asymptotically Optimal Codes for (t, s)-Burst Error

作     者：Sun, Yubo Lu, Ziyang Zhang, Yiwei Ge, Gennian 

作者机构：Capital Normal Univ Sch Math Sci Beijing 100048 Peoples R China Shandong Univ Key Lab Cryptol Technol & Informat Secur Minist Educ Qingdao 266237 Shandong Peoples R China Shandong Univ Sch Cyber Sci & Technol Qingdao 266237 Shandong Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期：2025年第71卷第3期

页      面：1570-1584页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key Research and Development Program of China [2020YFA0712100] National Natural Science Foundation of China Beijing Scholars Program National Key Research and Development Program of China [2022YFA1004900, 2021YFA1001000] Shandong Provincial Natural Science Foundation [ZR2021YQ46] Taishan Scholars Program 

主　　题：Codes Redundancy Symbols DNA Germanium Additives Sun Lower bound Error correction codes Terminology DNA storage burst error insertion deletion substitution 

摘      要：Recently, codes for correcting a burst of errors have attracted significant attention. One of the most important reasons is that bursts of errors occur in certain emerging techniques, such as DNA storage. In this paper, we investigate a type of error, called a (t,s) -burst, which deletes t consecutive symbols and inserts s arbitrary symbols at the same coordinate. Note that a (t,s) -burst error can be seen as a generalization of a burst of insertions ( t=0 ), a burst of deletions ( s=0 ), and a burst of substitutions ( t=s ). Our main contribution is to give explicit constructions of q-ary (t,s) -burst correcting codes with logn+O(1) bits of redundancy for any given constant non-negative integers t, s, and q = 2 . These codes have optimal redundancy up to an additive constant. Furthermore, we apply our (t,s) -burst correcting codes to combat other various types of errors and improve the corresponding results. In particular, one of our byproducts is a permutation code capable of correcting a burst of t stable deletions with logn+O(1) bits of redundancy, which is optimal up to an additive constant.