投稿者: Manabu Hagiwara

タイトル：On Prefixed Varshamov-Tenengolts Codes for Segmented Edit Channels
著者名：Xiaopeng Jiao; Haiyang Liu; Jianjun Mu; Hui Han; Yu-Cheng He
雑誌名：IEEE Transactions on Communications
号数：Volume 70, Issue 3
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.

タイトル : A Single-Round File Synchronization Scheme from Insertions and Deletions with Low Redundancy
著者名 : Guochen Ma; Xiaopeng Jiao; Jianjun Mu; Hui Han; Yu-Cheng He
雑誌名 : IEEE Communications Letters
号数 : -
DOI: 10.1109/LCOMM.2022.3193809

Abstract : Consider a file synchronization problem at two remote nodes A and B connected by a noiseless link. The node A has a binary file X, and node B has a binary file Y which is an edited version of X with random insertions and deletions (indels). The goal is to reconstruct X at node B from Y with minimal exchange of information between A and B. In this letter, we design a single-round, thus low latency, file synchronization scheme with low redundancy. In particular, a series of redundancy bits, including markers, check symbols of Reed-Solomon (RS) codes for hashes and Varshamov-Tenengolts (VT) syndromes, are constructed from X at node A and send to node B. According to the received redundancy and Y, we develop a recovery algorithm at node B to reconstruct X. The amount of exchanged information of the proposed scheme is significantly reduced when compared with the existing single-round synchronization scheme 
under random indels.

 

タイトル： 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.

家の庭で鳥が立ち止まっていた。

良く見ると、魚を銜えている。

食べたいのに、魚が大きくて身動きができなくなっているようだ。

魚は尾びれをピクピクと動かしている。

しばしの格闘の末、ついに、魚の向きが変わった。

魚の体が、鳥のくちばしと並行に。

しかし、魚の体が大きくて、くちばしから大きくはみ出している。

 

ついに、まる飲みに成功。

魚の体が大きすぎたのか、鳥の様子がおかしい。

体を立てている。

良く見ると、くちばしから尾びれがチラチラと飛び出しているのが見える。

このまましばらくの間、鳥はじっと止まっていた。

僕は家を出る時間になったため、観察を終わりにした。

 

翌日、おそらく同じ鳥が庭に現れた。ちゃんと消化できたのだろう。