タイトル： Error Probability Bounds for Coded-Index DNA Storage Systems 著者名： Nir Weinberger 雑誌名： IEEE Transactions on Information Theory 号数： Volume: 68, Issue: 11 DOI: 10.1109/TIT.2022.3176917 Abstract： The DNA storage channel is considered, in which a codeword is comprised of M unordered DNA molecules. At reading time, N molecules are sampled with replacement, and then each molecule is sequenced. A coded-index concatenated-coding scheme is considered, in which the m th molecule of the codeword is restricted to a subset of all possible molecules (an inner code), which is unique for each m . The decoder has low-complexity, and is based on first decoding each molecule separately (the inner code), and then decoding the sequence of molecules (an outer code). Only mild assumptions are made on the sequencing channel, in the form of the existence of an inner code and decoder with vanishing error. The error probability of a random code as well as an expurgated code is analyzed and shown to decay exponentially with N . This establishes the importance of increasing the coverage depth N/M in order to obtain low error probability.
タイトル： Correcting Deletions With Multiple Reads 著者名： Johan Chrisnata; Han Mao Kiah; Eitan Yaakobi 雑誌名： IEEE Transactions on Information Theory 号数： Volume: 68, Issue: 11 DOI: 10.1109/TIT.2022.3184868 Abstract： The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads N is fixed. Of significance, for the single-deletion channel, using log_2log_2(n)+O(1) redundant bits, we designed a reconstruction code of length n that reconstructs codewords from two distinct noisy reads (Cai et al. , 2021). In this work, we show that log_2log_2(n)−O(1) redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of the construction. Furthermore, we show that these reconstruction codes can be used in t -deletion channels (with t⩾2) to uniquely reconstruct codewords from n^(t−1)/(t−1)!+O(n^(t−2)) distinct noisy reads. For the two-deletion channel, using higher order VT syndromes and certain runlength constraints, we designed the class of higher order constrained shifted VT code with 2log_2(n)+o(log_2(n)) redundancy bits that can reconstruct any codeword from any N⩾5 of its length- (n−2) subsequences.
タイトル： On the Reverse-Complement String-Duplication System 著者名： Eyar Ben-Tolila; Moshe Schwartz 雑誌名： IEEE Transactions on Information Theory 号数： Volume: 68, Issue: 11 DOI: 10.1109/TIT.2022.3182873 Abstract： Motivated by DNA storage in living organisms, and by known biological mutation processes, we study the reverse-complement string-duplication system. We fully classify the conditions under which the system has full expressiveness, for all alphabets and all fixed duplication lengths. We then focus on binary systems with duplication length 2 and prove that they have full capacity, yet surprisingly, have zero entropy-rate. Finally, by using binary single burst-insertion correcting codes, we construct codes that correct a single reverse- complement duplication of odd length, over any alphabet. The redundancy (in bits) of the constructed code does not depend on the alphabet size.
タイトル： Weight Enumerators and Cardinalities for Number-Theoretic Codes 著者名： Takayuki Nozaki 雑誌名： IEEE Transactions on Information Theory 号数： Volume: 68, Issue: 11 DOI: 10.1109/TIT.2022.3184776 Abstract： The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo r.
