タイトル：On Prefixed Varshamov-Tenengolts Codes for Segmented Edit
Channels
著者名 : Xiaopeng Jiao; Haiyang Liu; Jianjun Mu; Hui Han; Yu-Cheng He
雑誌名： IEEE Trans. on Comm.
DOI: 10.1109/TCOMM.2022.3146285
Abstract : The prefixed Varshamov-Tenengolts (VT) codes, which are
subsets of VT codes with predetermined prefixes, can be used for error
correction over segmented edit channels. In this paper, we investigate
the construction and analysis of this class of codes. First, we derive
upper bounds on the size of zero-error codes for segmented edit channels
with segment-by-segment decoding. Second, we establish a one-to-one
correspondence between prefixed VT codes and Levenshtein codes. Based on
this relation, we can obtain explicit formulas on the size of prefixed
VT codes via the existing results on the size of Levenshtein codes.
Third, we construct a new zero-error prefixed VT code and show that the
size of the constructed code is strictly larger than that of the
existing prefixed VT code for the segmented deletion channel. Finally,
an efficient systematic encoding method of prefixed VT codes is proposed
for the segmented edit channels.
タイトル : Error-Correcting Codes for Short Tandem Duplication and Edit
Errors
著者名 : Yuanyuan Tang; Farzad Farnoud
雑誌名 : IEEE Transactions on Information Theory
号数 : Volume: 68,
Issue: 2
DOI: 10.1109/TIT.2021.3125724
Abstract : Due to its high data density and longevity, DNA is considered
a promising medium for satisfying ever-increasing data storage needs.
However, the diversity of errors that occur in DNA sequences makes
efficient error-correction a challenging task. This paper aims to
address simultaneously correcting two types of errors, namely, short
tandem duplication and edit errors, where an edit error may be a
substitution, deletion, or insertion. We focus on tandem repeats of
length at most 3 and design codes for correcting an arbitrary number of
duplication errors and one edit error. Because an edited symbol can be
duplicated many times (as part of substrings of various lengths), a
single edit can affect an unbounded substring of the retrieved word.
However, we show that with appropriate preprocessing, the effect may be
limited to a substring of finite length, thus making efficient error-
correction possible. We construct a code for correcting the
aforementioned errors and provide lower bounds for its rate. Compared to
optimal codes correcting only duplication errors, numerical results show
that the asymptotic cost of protecting against an additional edit is
only 0.003 bits/symbol when the alphabet has size 4, an important case
corresponding to data storage in DNA.
タイトル : Improved Singleton Bound on Insertion-Deletion Codes and
Optimal Constructions
著者名 : Bocong Chen; Guanghui Zhang
雑誌名 : IEEE Transactions on Information Theory
号数 : -
DOI: 10.1109/TIT.2022.3148185
Abstract : Insertion-deletion codes (insdel codes for short) play an important role in synchronization error correction. The higher the minimum insdel distance, the more insdel errors the code can correct. Haeupler and Shahrasbi established the Singleton bound for insdel codes: the minimum insdel distance of any [n, k] linear code over Fq satisfies d ≤ 2n - 2k + 2. There have been some constructions of insdel codes through Reed-Solomon codes with high capabilities, but none has come close to this bound. Recently, Do Duc et al. showed that the minimum insdel distance of any [n, k] Reed-Solomon code is no more than 2n - 2k if q is large enough compared to the code length n; optimal codes that meet the new bound were also constructed explicitly. The contribution of this paper is twofold. We first show that the minimum insdel distance of any [n, k] linear code over Fq satisfies d ≤ 2n-2k if n > k > 1. This result improves and generalizes the previously known results in the literature.We then give a sufficient condition under which the minimum insdel distance of a two-dimensional Reed-Solomon code of length n over Fq is exactly equal to 2n-4. As a consequence, we show that the sufficient condition is not hard to achieve; we explicitly construct an infinite family of optimal two-dimensional Reed-Somolom codes meeting the bound.
タイトル : Improved Constructions of Coding Schemes for the Binary
Deletion Channel and the Poisson Repeat Channel
著者名 : Roni Con; Amir Shpilka
雑誌名 : IEEE Transactions on Information Theory
号数 : -
DOI: 10.1109/TIT.2022.3148190
Abstract : This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel with parameter p (BDCp) every bit is deleted independently with probability p. A lower bound of (1-p)/9 is known on the capacity of the BDCp [1], yet no explicit construction is known to achieve this rate. We give an explicit family of codes of rate (1 - p)/16, for every p. This improves upon the work of Guruswami and Li [2] that gave a construction of rate (1-p)/120. The codes in our family have polynomial time encoding and decoding algorithms. Another channel considered in this work is the Poisson repeat channel with parameter λ (PRCλ) in which every bit is replaced with a discrete Poisson number of copies of that bit, where the number of copies has mean λ. We show that our construction works for this channel as well. As far as we know, this is the first explicit construction of an error correcting code for PRCλ.
