Composite DNA is a recent novel method to increase the information capacity of DNA-based data storage above the theoretical limit of 2 bits/symbol. In this method, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have much more than four symbols in the naire approach. While this method enables higher data content per synthesis cycle, potentially reducing the DNA synthesis cost, it also imposes significant challenges for accurate DNA sequencing since the baselevel errors can easily change the mixture of bases and their ratio, resulting in changes to the composite symbols. With this motivation, we propose efficient constrained coding techniques to enforce the biological constraints, including the runlength-limited constraint and the GC-content constraint, into every DNA synthesized oligo, regardless of the mixture of bases in each composite letter and their corresponding ratio. Our contributions include computing the capacity of the constrained channel, constructing efficient encoders/decoders, and providing the best options for the composite letters to obtain capacityapproaching codes. For certain codes' parameters, our methods incur only one redundant symbol.

High costs remain a primary limitation in the practical application of DNA storage, particularly in the synthesis process. This work focuses on a common synthesis method that generates multiple DNA strands in parallel from a fixed supersequence, one nucleotide at a time. The synthesis time is determined by the length of this supersequence. We investigate the maximum sizes and capacities of codes that restrict the maximum synthesis time while adhering to two critical biochemical constraints in a DNA storage channel: the runlength-limited constraint and the GC-content constraint. For specific parameters, we also present an encoding algorithm for codes that restrict the maximum synthesis time and satisfy both constraints.

Recent developments in storage- especially in the area of resistive random access memory (ReRAM)- are attempting to scale the storage density by regarding the information data as two-dimensional (2D), instead of one-dimensional (1D). Correspondingly, new types of 2D constraints are introduced into the input information data to improve the system reliability. While 1D constraints have been extensively investigated in the literature, the study for 2D constraints is much less profound. Particularly, given a constraint ${\mathcal{F}}$ and a design of 1D codes whose codewords satisfy ${\mathcal{F}}$, the problem of constructing efficient 2D codes, such that every row and every column in every codeword satisfy ${\mathcal{F}}$, has been a challenge.This work provides an efficient solution to the challenging coding problem above for the binary bounded-weight constrained codes that restrict the maximum number of 1’s (called weight). Formally, we propose a universal framework to design 2D codes that guarantee the weight of every row and every column of length n to be at most f(n) for any given function f(n). We show that if there exists a design of capacity-approaching 1D codes, then our method also provides capacity-approaching 2D codes for all f = ω(log n).

Resistive random-access memory (ReRAM) is a promising non-volatile memory technology. However, its crossbar array structure leads to a severe problem known as sneak path interference (SPI), which is correlated and data-dependent. From an information-theoretic perspective, memory systems like ReRAM can be considered as special types of communication channels. Inspired by deep learning applications in communication systems, the detection of ReRAM channels with SPI was formulated as a learning problem recently, and a multi-layer perceptron (MLP) network was employed to mitigate SPI. However, it requires a large amount of training data to achieve satisfactory performance. In this paper, we first propose a bidirectional long short-term memory (BiLSTM) based detector for ReRAM to exploit the correlation between memory cells introduced by SPI. Moreover, a few-shot learning algorithm based on meta-transfer learning (MTL) is proposed to further improve the generalization ability of the detector. The bit error rate (BER) bound and generalization bound are also derived to verify the effectiveness of our proposed schemes. Simulation results demonstrate that the BiLSTM-based detector with MTL can dramatically reduce the required training samples by four to five orders of magnitude while improving the BER performance compared to the existing MLP-based detection scheme.

Composite DNA is a novel approach that enables DNA-based data storage to exceed the theoretical limit of 2 bits per symbol. In this approach, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have far more than four symbols compared to the naive approach. Although this method increases data density per synthesis cycle and potentially reduces DNA synthesis costs, it also introduces significant challenges for accurate DNA sequencing since the base-level errors can easily change the mixture of bases and their ratio, leading to changes in the composite symbols.With this motivation, we investigated error-correcting codes for composite DNA in a general setting. Consider a data storage scenario where m reads are provided for each composite DNA sequence, and for each composite symbol, the difference between the observation ratio and the original ratio in its base mixture is at most ϵ. We further assume that at most δm sequences have errors, for some 0 ≤ δ ≤ 1, and each of them suffers from at most t edit errors (i.e., substitutions, insertions, and deletions). Given arbitrary values of m, ϵ, δ and t, our task is to design a codebook such that every codeword can be uniquely reconstructed. In this work, we focus on single edit error, i.e., t = 1, and for several cases, we show that our proposed codes are asymptotically optimal.

Temperature control is of utmost importance in transmission systems. In this paper, a binary channel model is considered in which the transmission of a one causes a temperature increase while communicating a zero causes a temperature drop. By putting constraints on the input sequences, it is guaranteed that the channel temperature will not exceed a certain pre-determined maximum. In the asymptotic regime, the capacity of such a channel is studied. For the non-asymptotic regime, fixed-length codes are presented, with the property that codewords can be freely cascaded without violating the temperature constraint. Optimization of the code size is investigated and codewords are enumerated using generating functions.

The thermal-aware channel has been studied recently to control the temperature of some electronic devices for better performance and longer lifetime. In this work, we consider a thermal-aware channel model where multiple wires are available to the user. The user can use one wire or several wires to write an information word. Particularly, we study the two extreme cases. In the first case, only one wire is permitted for writing the information. The other extreme case is that we are allowed to write information on all the wires in parallel. In the first case, when we send a message through a wire that reaches the highest allowed temperature, we switch to another available wire. We determine the minimum number of wires required to send any arbitrary message. Given the number of wires, our second task is to determine the constrained codewords that can be sent through these wires. We compute the maximum information rate achieved and provide some constructions of codes satisfying these constraints. In the second case when all the wires are available for writing many, interesting questions arise and we briefly describe one of them and its solutions.

DNA synthesis remains the most costly part of the DNA data storage. In this work, we consider a popular synthesis method that generates multiple DNA strands in parallel from a fixed supersequence$S$, one nucleotide at a time. Under this assumption, the synthesis time (or the number of synthesis cycles) is then determined by the length of the common supersequence. In this work, we propose constructions of quaternary codes that simultaneously (i) restrict the maximum synthesis time, (ii) correct a single deletion or insertion error, and (iii) satisfy the runlength limited constraint, a crucial biochemical constraint in a DNA storage channel. For certain parameters, we provide an improved construction of DNA codes with a smaller synthesis time while costing less redundancy as compared to the best-known result in the literature.

Motivated by the information transmission in neurons with various applications in in-vivo nano-machines or emerging medical applications, Ye and Elishco [2023] introduced a communication channel, called the absorption channel, and proposed codes correcting absorption errors. For a non-binary alphabet$\Sigma_{q}$, the authors presented constructions of codes of length$n$correcting a single absorption and the best construction yielded a redundancy of$\log_{q}n+12\log_{q}\log_{q}n+O(1)$symbols. In this work, we make progress on the code design problem above and show that the redundancy can be further reduced significantly as follows: When$q=3$, we construct “nearly optimal” ternary codes of length$n$with at most$\log_{3}n+5.43$redundant symbols. Note that such a redundancy is optimal up to a constant. • For a general alphabet$\Sigma_{q}$, we construct q-ary codes of length$n$correcting a single absorption error with$\log_{q}n+3\log_{q}\log_{q}n+O(1)$redundant symbols, providing an alternative. simpler construction that improves the results given by Ye and Elishco.

We study and propose schemes that map messages onto constant-weight codewords using variable-length prefixes. We provide polynomial-time computable formulas that estimate the average number of redundant bits incurred by our schemes. In addition to the exact formulas, we also perform an asymptotic analysis and demonstrate that our scheme uses 1/2 log2n+O(1) redundant bits to encode messages into length-n words with weight (n/2) + μ for constant μ. We also propose schemes that map messages into balanced codebooks with error-correcting capabilities. For such schemes, we provide methods to enumerate the average number of redundant bits.

The problem of correcting deletions and insertions has recently received significantly increased attention due to the DNA-based data storage technology, which suffers from deletions and insertions with extremely high probability. In this work, we study the problem of constructing non-binary burst-deletion/insertion correcting codes. Particularly, for the quaternary alphabet, our designed codes are suited for correcting a burst of deletions/insertions in DNA storage. Non-binary codes correcting a single deletion or insertion were introduced by Tenengolts (1984), and the results were extended to correct a fixed-length burst of deletions or insertions by Schoeny et al. (2017). Recently, Wang et al. (2021) proposed constructions of non-binary codes of length n, correcting a burst of length at most two for q-ary alphabets with redundancy$\log n+O(\log q \log \log n)$bits, for arbitrary even q. The common idea in those constructions is to convert non-binary sequences into binary sequences, and the error decoding algorithms for the q-ary sequences are mainly based on the success of recovering the corresponding binary sequences, respectively. In this work, we look at a natural solution that the error detection and correction algorithms are performed directly over q-ary sequences, and for certain cases, our codes provide a more efficient encoder with lower redundancy than the best-known encoder in the literature. Particularly, (Single-error correction codes) We first present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion, providing an alternative simpler and more efficient encoder of the construction by Tenengolts (1984). Our construction is based on the differential vector, and the codes are referred to as the differential VT codes. In addition, we provide linear-time algorithms that encode user messages into these codes of length n over the q-ary alphabet for$q \geqslant 2$with at most$\lceil \log _{q} n\rceil +1$redundant symbols, while the optimal redundancy required is at least$\log _{q} n+\log _{q} (q-1)$symbols. Our designed encoder reduces the redundancy of the best-known encoder of Tenengolts (1984) by at least 2 redundant symbols or equivalently$2\log _{2} q$bits. (Burst-error correction codes) We use the idea of the binary shifted VT codes to define the q-ary differential shifted VT codes, and propose non-binary codes correcting a burst of up to two deletions (or two insertions) with redundancy$\log n+3\log \log n+ O(\log q)$bits, which improves a recent result of Wang et al. (2021) with redundancy$\log n+O(\log q \log \log n)$bits for all$q\geqslant 8$. We then extend the construction to design non-binary codes correcting a burst of either exactly or at most t deletions (or insertions) for arbitrary$t\geqslant 2$.

In this work, we present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion. Moreover, we provide the first-known linear-time algorithms that encode user messages into these codes of length$n$over the q-ary alphabet for$q$> 2 with at most [logq$n$] + 1 redundant symbols, while the optimal redundancy required is at least logq$n$+ logq(q - 1) symbols. Our designed encoder reduces the redundancy of the best known encoder of Tenengolts (1984) by at least 2 + logq(3) redundant symbols, or equivalently 2 log2q + 3 redundant bits.

High temperatures in electronic devices have a negative effect on their performance. Various techniques have been proposed and studied to address and combat this thermal challenge. To guarantee that the peak temperature of the devices will be bounded by some maximum temperature, the transmitted signal has to satisfy some constraints.With this motivation, we study the constrained channel that only accepts sequences that satisfy prescribed thermal constraints. The main goal in this paper is to compute the capacity of this channel. We provide the exact capacity of the channel with some certain parameters and we also present some bounds on the capacity in various cases.Finally, we consider the model that multiple wires are available to use and find out the smallest number of wires required to satisfy the thermal constraints.

In this work, we investigate a challenging problem, which has been considered to be an important criterion in designing codewords for DNA computing purposes, namely secondary structure avoidance in single-stranded DNA molecules. In short, secondary structure refers to the tendency of a single-stranded DNA sequence to fold back upon itself, thus becoming inactive in the computation process. The main contribution of this work is to provide an explicit construction of DNA codes that completely avoid the formation of secondary structures of arbitrary stem length.Formally, given codeword length n and arbitrary integer m ⩾ 2, we provide efficient methods to construct DNA codes of length n that avoid secondary structure of any stem length more than or equal to m. Particularly, when m = 3, our constructions yield a family of DNA codes of rate 1.3031 bits/nt, while the highest rate found in the prior art was 1.1609 bits/nt. In addition, for m ⩾ 3log n+4, we provide an efficient encoder that incurs only one redundant symbol.

In this work, we propose efficient constrained coding schemes to significantly reduce the sneak path interference (SPI), a fundamental and challenging problem, in crossbar resistive memory arrays. Particularly, we attempt to combat the sneak path effect locally as follows. For arrays of size n × n, we study coding methods that enforce every sliding window of size m×m (where each window refers to a subarray consisting of consecutive rows and consecutive columns), for some m2/2 − δ for δ ⩾ 0, and this constraint is called the locally bounded-weight constraint, or•Sneak-path-free: the written bits in every window do not induce any sneak path to any cell, and this constraint is called the locally sneak-path-free constraint.In this work, we study the maximum information rate that can be achieved (or channel capacity) and design codes for each constraint. Particularly, for the first constraint, for arbitrary m ⩾ 4 and$\delta \leq m\left( {\sqrt m /2 - 1} \right) = \Theta \left( {m\sqrt m } \right)$, we provide an efficient construction of codes with the code rate 1 − 2/$\sqrt m $, while the highest rate found in the prior art is approximately 1 − 1/m, which was only applicable for m = n − o(n) and δ = 0.

In this work, we study two types of constraints on two-dimensional binary arrays. Given$p\in [{0,1}],\epsilon \in [{0,1/2}]$, we study 1) the$p$-bounded constraint: a binary vector of size$n$is said to be$p$-bounded if its weight is at most$pn$, and 2) the$\epsilon $-balanced constraint: a binary vector of size$n$is said to be$\epsilon $-balanced if its weight is within$\big [(1/2-\epsilon)n, (1/2+\epsilon)n\big]$. Such constraints are crucial in several data storage systems, those regard the information data as two-dimensional (2D) instead of one-dimensional (1D), such as the crossbar resistive memory arrays and the holographic data storage. In this work, efficient encoding/decoding algorithms are presented for binary arrays so that the weight constraint (either$p$-bounded constraint or$\epsilon $-balanced constraint) is enforced over every row and every column, regarded as 2D row-column (RC) constrained codes; or over every window (where each window refers to as a subarray consisting of consecutive rows and consecutive columns), regarded as 2D sliding-window (SW) constrained codes. While low-complexity designs have been proposed in the literature, mostly focusing on 2D RC constrained codes where$p=1/2$and$\epsilon =0$, this work provides efficient coding methods that work for both 2D RC constrained codes and 2D SW constrained codes, and more importantly, the methods are applicable for arbitrary values of$p$and$\epsilon $. Furthermore, for certain values of$p$and$\epsilon $, we show that, for sufficiently large array size, there exists linear-time encoding/decoding algorithm that incurs at most one redundant bit.

In this work, given n,ϵ > 0, two efficient encoding (decoding) methods are presented for mapping arbitrary data to (from) n×n binary arrays in which the weight of every row and every column is within [(1/2–ϵ)n, (1/2+ϵ)n], which is referred to as the ϵ-balanced constraint. The first method combines the divide and conquer algorithm and a modification of the Knuth’s balancing technique, resulting a redundancy of Θ(n) bits. On the other hand, for sufficiently large n, the second method uses the sequence replacement technique, which costs only 1 redundant bit. The latter method reduces significantly the redundancy of the best known encoder for two-dimensional p-bounded weight constrained codes from (n + 3) bits to a single bit.

Advances in synthesis and sequencing technologies have made DNA macromolecules an attractive medium for digital information storage. Compared with the ex vivo method that stores data in a non-biological environment, there have been considerations and attempts to store data in living organisms, also known as the in vivo method or live DNA due to several magnificent advantages. Data stored in this medium is prone to errors arising from various mutations such as point mutations (when there is a change in a single nucleotide in DNA, i.e. deletion, insertion, or substitution) or chromosomal alterations (that change the structure of a segment of DNA, i.e. tandem duplication, inversion).In this paper, we provide error-correcting codes for errors caused by inversions, that reverse the order of a segment of DNA. In particular, we construct families of codes for correcting single inversion of a fixed length or variable length up to a given constant k with at most log n+Θ(1) redundant bits, where the redundancy matches the optimal value up to only a constant additive term. Moreover, our codes remain order-optimal, i.e. the redundancy is at most log n + o(log n), when k = o(log n). The redundancy can be further reduced when k ≪ 3.

In this paper, we present an explicit construction of list-decodable codes for single-deletion and single-substitution with list size two and redundancy 3log 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 4log n + O(1).

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 designreconstruction codesthat 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$\log _{q} n+O(1)$to$\log _{q} \log _{q} n+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.

We study segmented edit channels where the channel input is divided into disjoint segments, and each segment suffers at most one error, either a deletion or an insertion. The model was first introduced by Liu and Mitzenmacher [2010] over the binary alphabet, and was extended for the q-ary alphabet by Abroshan et al. [2018]. In this work, we first propose an efficient construction for segments with less redundancy than previous works, hence significantly improving the redundancy over the entire sequence, for any q-ary alphabet where$q$≥ 3. Additionally, motivated by the applications of constrained codes in DNA-based data storage systems and energy harvesting communication channels, to reduce the probability of having errors, we also impose certain weight constraints in every segment instead of over the whole sequence. In particular, for DNA storage systems, besides error correction capability, our coding method guarantees that all segments in every codeword are almost GC-balanced.

In this work, given$n, p > 0$, efficient encoding/decoding algorithms are presented for mapping arbitrary data to and from$n\times n$binary arrays in which the weight of every row and every column is at most$pn$. Such constraint, referred as$p$-bounded-weight-constraint, is crucial for reducing the parasitic currents in the crossbar resistive memory arrays, and has also been proposed for certain applications of the holographic data storage. While low-complexity designs have been proposed in the literature for only the case$p=1/2$, this work provides efficient coding methods that work for arbitrary values of$p$. The coding rate of our proposed encoder approaches the channel capacity for all$p$.

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉+ O(loglog n) redundancy bits, while the other corrects a single indel with ⌈log n⌉+2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit.

The subblock energy-constrained codes (SECCs) and sliding window-constrained codes (SWCCs) have recently attracted attention due to various applications in communication systems such as simultaneous energy and information transfer. In a SECC, each codeword is divided into smaller non-overlapping windows, called subblocks, and every subblock is constrained to carry sufficient energy. In a SWCC, however, the energy constraint is enforced over every window. In this work, we focus on the binary channel, where sufficient energy is achieved theoretically by using relatively high weight codes, and study the bounded SECCs and bounded SWCCs, where the weight in every window is bounded between a minimum and maximum number. Particularly, we focus on the cases of parameters that there is no rate loss, i.e. the channel capacity is one, and propose two methods to construct capacity-approaching codes with low redundancy and linear-time complexity, based on Knuth’s balancing technique and sequence replacement technique. These methods can be further extended to construct SECCs and SWCCs. For certain codes parameters, our methods incur only one redundant bit. We also impose the minimum distance constraint for error correction capability of the designed codes, which helps to reduce the error propagation during decoding as well.

We propose coding techniques that simultaneously limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for givenl, ∈ > 0, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C and G, that satisfy all of the following properties: 1) runlength constraint: the maximum homopolymer run in each codeword is at mostl; 2) GC-content constraint: the GC-content of each codeword is within [0.5-∈,0.5+∈]; 3) error-correction: each codeword is capable of correcting a single deletion, or single insertion, or single substitution error. While various combinations of these properties have been considered in the literature, this work provides generalizations of codes constructions that satisfy all the properties with arbitrary parameters ofland ∈. Furthermore, for practical values ofland ∈, we show that our encoders achieve higher rates than existing results in the literature and approach capacity. Our methods have low encoding/decoding complexity and limited error propagation.

A nucleotide substitution is said to occur when a base in {A, T} is substituted for a base in {C, G}, or vice versa. Recent experiment (Heckel et al. 2019) showed that a nucleotide substitution occurs with a significantly higher probability than other substitution errors. A nucleotide edit refers to a single insertion, deletion or nucleotide substitution. In this paper, we investigate codes that corrects a single nucleotide edit and provide linear-time algorithms that encode binary messages into these codes of length n. Specifically, we provide an order-optimal encoder which corrects a single nucleotide edit with log n + log log n + O(1) redundant bits. We also demonstrate that the codewords obey certain runlength constraints and that the code can be modified to accommodate certain GC-content constraints..

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 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 bits required can be gracefully reduced from logn + O(1) to loglogn + O(1), and then to O(1), where n denotes the length of a codeword. We also show that the redundancy of certain reconstruction codes is within one bit of optimality.

The subblock energy-constrained codes (SECCs) have recently attracted attention due to various applications in communication systems such as simultaneous energy and information transfer. In a SECC, each codeword is divided into smaller subblocks, and every subblock is constrained to carry sufficient energy. In this work, we study SECCs under more general constraints, namely bounded SECCs and sliding-window constrained codes (SWCCs), and propose two methods to construct such codes with low redundancy and linear-time complexity, based on Knuth's balancing technique and sequence replacement technique. For certain codes parameters, our methods incur only one redundant bit.

In this paper, we first propose coding techniques for DNA-based data storage which account the maximum homopolymer runlength and the GC-content. In particular, for arbitrary ℓ,ε>0, we propose simple and efficient (ℓ,ε)-constrained encoders that transform binary sequences into DNA base sequences (codewords), that satisfy the following properties: · Runlength constraint: the maximum homopolymer run in each codeword is at most ℓ, · GC-content constraint: the GC-content of each codeword is within [0.5-ε, 0.5+ε]. For practical values of ℓ and ε, our codes achieve higher rates than the existing results in the literature. We further design efficient (ℓ, ε)-constrained codes with error-correction capability. Specifically, the designed codes satisfy the runlength constraint, the GC-content constraint, and can correct a single edit (i.e. a single deletion, insertion, or substitution) and its variants. To the best of our knowledge, no such codes are constructed prior to this work.

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. Such code constructions are almost optimal to combat tandem duplications of length at most k where k ≤ 3. However, the problem of designing efficient encoder/decoder for such codes has not been investigated. In addition, the method cannot be extended to deal with the case of arbitrary k, where k ≥ 4. In this work, we study efficient encoding/decoding methods for irreducible words over general q-ary alphabet. Our methods provide the first known efficient encoder/decoder for q-ary codes correcting tandem duplications of length at most k, where k ≤ 3. In particular, we describe an (1, m)-finite state encoder and show that when m = Θ(1/ε) and ϊ = Θ(1/ε), the encoder achieves rate that is ε away from the optimal rate. We also provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder. Over the DNA alphabet (or quaternary alphabet), we also impose weight constraint on the codewords. In particular, a quaternary word is GC-balanced if exactly half of the symbols of are either C or G. Via a modification of Knuth's balancing technique, we provide an efficient method that translates quaternary messages into GC-balanced codewords and the resulting codebook is able to correct tandem duplications of length at most k, where k ≤ 3. In addition, we provide the first known construction of codes to combat tandem duplications of length at most k, where k ≥ 4. Such codes can correct duplication errors in linear-time and they are almost optimal in terms of rate.

Permutation codes and multipermutation codes are widely studied due to various applications in information theory. Designing codes correcting deletion errors has been the main subject of works in the literature and to the best of our knowledge, there exist only optimal codes capable of correcting a single deletion in a permutation. In this paper, we construct several classes of permutation and multipermutation codes that are capable of correcting a burst deletion of length s ≥ 2, for both stable and unstable models. Efficient error decoders are provided to show the correctness of our constructions.

An indel refers to a single insertion or deletion, while an edit refers to either a single insertion, deletion or substitution. We investigate codes that combat either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with 2⌈log n⌉ + 2 redundant bits, while the other corrects a single indel with ⌈log n⌉ + 2 redundant bits. The latter encoder reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, exactly half of the symbols of a GC-balanced word are either C or G. Via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single edit. The redundancy of our encoder is 3⌈log n⌉ + 2 bits and this is the first known construction of a GC-balanced code that corrects a single edit.

Tandem duplication in DNA is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2016) proposed the study of codes that correct tandem duplications to improve the reliability of data storage. We investigate algorithms associated with the study of these codes. Two words are said to be ⩽-confusable if there exists a sequence of tandem duplications for each word, where each duplication is of length at most k , such that the resulting two words after duplications are equal. For k =3, we demonstrate that the problem of deciding whether two words is ⩽3-confusable is linear-time solvable through a characterisation that can be checked efficiently. Combining with previous results, the decision problem is linear-time solvable for k ⩽ 3. We conjecture that this problem is undecidable for k > 3. Using insights gained from the algorithm, we study the size of tandem-duplication codes. We improve the previous known upper bound and then construct codes with larger sizes as compared to the previous constructions. We determine the sizes of optimal tandem-duplication codes for lengths up to 20, develop recursive methods to construct tandem-duplication codes for all word lengths, and compute explicit lower bounds for the size of optimal tandem-duplication codes for lengths from 21 to 30.

We investigate constant-composition constrained codes for the mitigation of intercell interference for multilevel cell flash memories with a dynamic threshold scheme. The first explicit formula for the maximum size of a q-ary F-avoiding code with a given composition and certain families of substrings F is presented. In addition, we provide methods to determine the asymptotic rate for F-avoiding codes with any composition ratio and to find the optimal composition ratio that maximizes the asymptotic rate. We also give the first efficient encoder/decoder for these q-ary constant-composition codes achieving the channel capacity, for all q values.

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. We study efficient encoding/decoding methods for irreducible words. First, we describe an (ℓ, m) -finite state encoder and show that when m=Θ(1/ε) and ℓ = Θ(1/ε), the encoder has rate that is ε away from the optimal. Next, we provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder.

We construct permutation codes capable of correcting bursts of stable deletions. For correcting a single burst of exactly s stable deletions, our code has size sn!/((2s)!n)2, while the upper bound n!/s!(n - s + 1). We also construct permutation codes for the cases of single burst of up to s stable deletions, and up to b bursts of at most s stable deletions each.

We construct codes for the Chebyshev permutation channels whose study was initiated by Langberg et al. (2015). We establish several recursive code constructions and present efficient decoding algorithms for our codes. In particular, our constructions yield a family of binary codes of rate 0.643 when r = 1. The upper bound on the rate in this case is 2/3 and the previous highest rate is 0.609.