Search

Error-correcting codes over sets, with applications to DNA storage, are studied. The DNA-storage channel receives a set of sequences, and produces a corrupted version of the set, including sequence loss, symbol substitution, symbol insertion/deletion, and limited-magnitude errors in symbols. Various parameter regimes are studied. New bounds on code parameters are provided, which improve upon known bounds. New codes are constructed, at times matching the bounds up to lower-order terms or small constant factors. [ABSTRACT FROM AUTHOR]

We construct integer error-correcting codes and covering codes for the limited-magnitude error channel with more than one error. The codes are lattices that pack or cover the space with the appropriate error ball. Some of the constructions attain an asymptotic packing/covering density that is constant. The results are obtained via various methods, including the use of codes in the Hamming metric, modular Bt-sequences, 2-fold Sidon sets, and sets avoiding arithmetic progression. [ABSTRACT FROM AUTHOR]

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length $n$ , minimum distance $d$ with $(d+1) \log _{4}\,\,n +O(1)$ redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth’s balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes and codes for DNA computing. [ABSTRACT FROM AUTHOR]

Perfect $$t$$ -deletion-correcting codes of length $$n$$ over the alphabet of size $$q$$ , denoted by perfect $$(n,t)_q\text {-DCCs}$$ , can have different number of codewords, because the balls of radius $$t$$ with respect to Levenshteĭn distance may be of different sizes. Thus determining all possible sizes of a perfect $$t$$ -deletion-correcting code makes sense. When $$t=n-2$$ , $$t$$ -deletion-correcting codes are closely related to directed packings, constructions of which are based on the tools of design theory. Recently, Chee, Ge and Ling determined completely the spectrum of possible sizes for perfect $$q$$ -ary 1-deletion-correcting codes of length three for all $$q$$ , and perfect $$q$$ -ary 2-deletion-correcting codes of length four for all but $$19$$ values of $$q$$ . In this paper, we continue to investigate the spectrum problem for perfect $$(4,2)_q\text {-DCCs}$$ . By constructing a considerable number of incomplete directed packings, we give an almost complete solution to the spectrum problem of sizes for perfect $$(4,2)_q\text {-DCCs}$$ , leaving the existence of $$(4,2)_{19}\text {-DCC}$$ of size $$62$$ and $$(4,2)_{34}\text {-DCC}$$ of size $$196$$ in doubt. [ABSTRACT FROM AUTHOR]

We study whether an asymmetric limited-magnitude ball may tile Z n. This ball generalizes previously studied shapes: crosses, semi-crosses, and quasi-crosses. Such tilings act as perfect error-correcting codes in a channel which changes a transmitted integer vector in a bounded number of entries by limited-magnitude errors. A construction of lattice tilings based on perfect codes in the Hamming metric is given. Several non-existence results are proved, both for general tilings, and lattice tilings. A complete classification of lattice tilings for two certain cases is proved. [ABSTRACT FROM AUTHOR]