论文标题
纵横交错的插入和删除校正代码
Criss-Cross Insertion and Deletion Correcting Codes
论文作者
论文摘要
本文研究了构建代码纠正阵列中缺失的问题。在此模型下，假定一个$ n \ times n $数组可以遇到行的删除行。这些删除错误称为$（t_r，t_c）$ - criss-cross删除如果$ t_r $ lows和$ t_c $列删除，而纠正这些删除模式的代码称为$（T_R，T_R，T_C）$ - Criss-Cross-Cross删除校正校正码。纵横交错的定义相似。 首先显示，当$ t_r = t_c $纠正纵横交错的删除和纵横交错的问题时，插入是等效的。本文的重点在于$（1,1）$ - Criss-Cross删除的情况。在$（1,1）$ - CRISS-CROSS缺失校正代码的基数（1,1）$（1,1）的非反应上限上显示，该代码确保了冗余至少$ 2N-3+2 \ log n $ bits。提出了带有存在编码和明确解码算法的代码构建。构造的冗余最多是$ 2N +4 \ log n +7 +2 \ log e $。提出了带有显式编码器和解码器的结构。显式编码器为构造添加了额外的$ 5 \ log n + 5 $冗余。
This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n\times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $(t_r,t_c)$-criss-cross deletions if $t_r$ rows and $t_c$ columns are deleted, while a code correcting these deletion patterns is called a $(t_r,t_c)$-criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_r=t_c$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of $(1,1)$-criss-cross deletions. A non-asymptotic upper bound on the cardinality of $(1,1)$-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction.
