投稿者: Manabu Hagiwara

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

 

タイトル： Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
著者名： Ryan Gabrys, Venkatesan Guruswami, Joao Ribeiro, Ke Wu
アクセス： https://arxiv.org/pdf/2112.09971.pdf

Abstract： We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with
nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations…

---

---

タイトル： Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound
著者名： G Wang, DM Xu, FW Fu
ジャーナル： Advances in Mathematics of Communications, 2021
アクセス： https://www.aimsciences.org/article/doi/10.3934/amc.2021065

Abstract： Codebooks with small maximum cross-correlation amplitudes are used to distinguish the signals from different users in code division multiple access communication systems. In this paper, several classes of codebooks are introduced, whose maximum cross-correlation amplitudes asymptotically achieve the corresponding Welch bound and Levenshtein bound. Specially, a class of optimal codebooks with respect to the Levenshtein bound is obtained. These classes of codebooks are constructed by selecting certain rows deterministically from circulant matrices, Fourier matrices and Hadamard matrices, respectively. The construction methods and parameters of some codebooks provided in this paper are new.

タイトル： List-decodable Codes for Single-deletion Single-substitution with List-size Two
著者名： Wentu Song, Kui Cai, and Tuan Thanh Nguyen
アクセス： https://arxiv.org/abs/2201.02013v1

Abstract： In this paper, we present an explicit construction of list-decodable codes for single-deletion and single-substitution with list size two and redundancy 3 log n+4, where n is the block length of the code. Our construction has lower redundancy than the best known explicit construction by Gabrys et al. (arXiv 2021), whose redundancy is 4 log n + O(1)

---

 

タイトル： A new construction of linear codes with one-dimensional hull
著者名： Lin Sok
ジャーナル： Designs, Codes and Cryptography
アクセス： https://link.springer.com/article/10.1007/s10623-021-00991-4

Abstract： The hull of a linear code C is the intersection of C with its dual C⊥. The hull with low dimensions gets much interest due to its crucial role in determining the complexity of algorithms for computing the automorphism group of a linear code and for checking permutation equivalence of two linear codes. The hull of linear codes has recently found its application to the so-called entanglement-assisted quantum error-correcting codes (EAQECCs). In this paper, we provide a new method to construct linear codes with one-dimensional hull. This construction method improves the code lengths and dimensions of the recent results given by the author. As a consequence, we derive several new classes of optimal linear codes with one-dimensional hull. Some new EAQECCs are presented.

---

タイトル： Design and Performance of Low-Density Parity-Check Codes for
Noisy Channels with Synchronization Errors
著者名： Ryo SHIBATA, Hiroyuki YASHIMA
ジャーナル： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
DOI： https://doi.org/10.1587/transfun.2021EAL2013

Abstract：  In this letter, we study low-density parity-check (LDPC)
codes for noisy channels with insertion and deletion (ID) errors. We
first propose a design method of irregular LDPC codes for such channels,
which can be used to simultaneously obtain degree distributions for
different noise levels. We then show the asymptotic/finite-length
decoding performances of designed codes and compare them with the
symmetric information rates of cascaded ID-noisy channels. Moreover, we
examine the relationship between decoding performance and a code
structure of irregular LDPC codes.

---

タイトル： Coding for Sequence Reconstruction for Single Edits
著者名： Kui Cai, Han Mao Kiah, Tuan Thanh Nguyen, Eitan Yaakobi
ジャーナル： IEEE Transactions on Information Theory
DOI：https://10.1109/TIT.2021.3122798

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. The common setup assumes the
codebook to be the entire space and the problem is to determine the
minimum number of distinct reads that is required to reconstruct the
transmitted codeword. Motivated by modern storage devices, we study a
variant of the problem where the number of noisy reads N is fixed.
Specifically, we design reconstruction codes that reconstruct a codeword
from N distinct noisy reads. We focus on channels that introduce a
single edit error (i.e. a single substitution, insertion, or deletion)
and their variants, and design reconstruction codes for all values of N . In particular, for the case of a single edit, we show that as the
number of noisy reads increases, the number of redundant symbols
required can be gracefully reduced from logqn+O(1) to logqlogqn+O(1) ,
and then to O(1) , where n denotes the length of a codeword. We also
show that these reconstruction codes are asymptotically optimal. Finally,
via computer simulations, we demonstrate that in certain cases,
reconstruction codes can achieve similar performance as classical error-
correcting codes with less redundant symbols.