Codes in the Space of Multisets-Coding for Permutation Channels With Impairments
Codes in the Space of Multisets-Coding for Permutation Channels With Impairments
复制标题
DOI：
10.1109/tit.2017.2789292
复制
发表时间：
2018-07-01
影响因子：
2.5
通讯作者：
Tan, Vincent Y. F.
中科院分区：
文献类型：
--
作者：
Kovacevic, Mladen;Tan, Vincent Y. F.
由于传输序列受到随机排列的通信信道以及某些DNA存储系统的激励，我们研究了信息以给定有限字母的多集符号形式存储/传输的设置中的错误控制问题。假设一个通用信道模型，其中传输的多集可能因符号的插入、删除、替换和擦除而受损。描述了该信道的几种纠错码结构，并推导了纠错码大小的界限。在编码冗余的渐近尺度意义上，证明了基于有限阿贝尔群中的西顿集概念的构造对于任何误差半径和字母大小都是最优的。在各种情况下，它也被证明在最大代码基数的更强意义上是最优的。
Motivated by communication channels in which the transmitted sequences are subjected to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors are derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any error radius and alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases.