Numerous code constructions which limit the maximum homopolymer run length and constrain GC-content have been proposed in literature for DNA data storage. These codes help to reduce insertion, deletion and substitution errors in DNA strands, since strands with large homopolymer runs and a large unbalance in GC-content, i.e., GC-content is too high or too low, are more prone to the previously mentioned errors during synthesis and sequencing. While the capacity of non-binary runlength-limited codes is known, the capacity of non-binary balanced runlength-limited codes is unknown. Here, we generalize the capacity result of binary balanced runlength-limited codes to the non-binary alphabet and demonstrate that the capacity of non-binary balanced (equal number of occurrences of each non-binary symbol) runlength-limited codes is equal to the capacity of the corresponding runlength-limited codes without the balancing constraint. An immediate consequence of the above result when applied to the quaternary alphabet of DNA data storage is that the capacity of runlength-limited and GC-content constrained codes for any arbitrary range of permitted GC-content unbalance which includes the balanced case is equal to the capacity of the corresponding runlength-limited codes without the GC-content constraint, i.e., the imposition of any GC-content constraint to runlength-limited codes does not induce a capacity penalty.

It is known that, for large user word lengths, the auxiliary data can be used to recover most of the redundancy losses of Knuth's simple balancing method compared with the optimal redundancy of balanced codes for the binary case. Here, this important result is extended in a number of ways. First, an upper bound for the amount of auxiliary data is derived that is valid for all codeword lengths. This result is primarily of theoretical interest, as it defines the probability distribution of the number of balancing indices that results in optimal redundancy. This result is equally valid for particular non-binary generalizations of Knuth's balancing method. Second, an asymptotically exact expression for the amount of auxiliary data for the ternary case of a variable length realization of the modified balanced code construction is derived, that, in all respects, is the analogue of the result obtained for the binary case. The derivation is based on a generalization of the binary random walk to the ternary case and a simple modification of an existing generalization of Knuth's method for the non-binary balanced codes. Finally, a conjecture is proposed regarding the probability distribution of the number of balancing indices for any alphabet size.

A novel Knuth-like balancing method for runlength-limited words is presented, which forms the basis of new variable- and fixed-length balanced runlength-limited codes that improve on the code rate as compared to balanced runlength-limited codes based on Knuth's original balancing procedure developed by Immink et al. While Knuth's original balancing procedure, as incorporated by Immink et al., requires the inversion of each bit one at a time, our balancing procedure only inverts the runs as a whole one at a time. The advantage of this approach is that the number of possible inversion points, which needs to be encoded by a redundancy-contributing prefix/suffix, is reduced, thereby allowing a better code rate to be achieved. Furthermore, this balancing method also allows for runlength violating markers which improve, in a number of respects, on the optimal such markers based on Knuth's original balancing method.

A simple and general method is presented for enumerating the number of balanced (zero-disparity) runlength-limited words based on bivariate generating functions and the symbolic methods of analytic combinatorics. This procedure scales well with increasing word length, allowing for exact enumerations for very large word lengths. As a result, it serves as a precise benchmark against which to evaluate the performance, in terms of code rate, of balanced runlength-limited coding schemes.

Insertion/deletion detecting codes were introduced by Konstantinidis In this paper we define insertion/deletion detecting codes in a slightly different manner, and based on this definition, we introduce multiple deletion and multiple insertion detecting codes. It is shown that these codes, which are systematic, are optimal in the sense that there exists no other systematic multiple deletion (insertion) detecting codes with a better rate. One of the limitations of number-theoretic code constructions intended to correct insertion/deletion errors, e.g., the Levenshtein code, is that they require received codeword boundaries to be known in order to successfully decode. In literature, a number of schemes have been proposed to deal with this problem. We show how insertion/deletion detecting codes as presented in this paper can be used to improve and/or extend some of these schemes.

A proof that the Helberg code is capable of correcting multiple deletion/insertion errors is presented. This code is a generalization of the number-theoretic Levenshtein code which is capable of correcting a single deletion/insertion. However, apart from exhaustive testing of short codes, no proof was hitherto given to verify that the Helberg code is indeed capable of correcting multiple deletions and insertions.

A code construction is proposed to add a multiple insertion/deletion error correcting capability to a run-length limited sequence. The codewords of this code are themselves run-length limited. The insertion/deletion correcting capability is achieved by requiring several weighted sums of run-lengths in the codewords to satisfy certain congruences modulo primes. The construction is similar to the number-theoretic code proposed by Dolecek and Anantharam, which can correct multiple repetition errors or, equivalently, multiple insertions of zeros. It is shown that if the codewords in this code are run-length limited, then the code is capable of correcting both insertions and deletions of zeros and ones. An algorithm is proposed for decoding over a multiple insertion/deletion channel. Following the work of Dolecek and Anantharam, a systematic encoding method is also proposed for the codes. Furthermore, it is shown that the proposed construction has a higher rate asymptotically than the Helberg code, which is unconstrained in terms of run-lengths, even though our construction has the additional run-length constraints. The need for run-length limited codes that can correct insertion/deletion errors is motivated by bit-patterned media for magnetic recording.

We propose the construction of a non-binary multiple insertion/deletion correcting code based on a binary multiple insertion/deletion correcting code. In essence, it is a generalisation of Tenengol'ts' non-binary single insertion/deletion correcting code. We evaluate the cardinality of the proposed construction based on the asymptotic upper bound on the cardinality of a maximal binary multiple insertion/deletion correcting code derived by Levenshtein.

Moment balancing templates have been proposed for channels with a small probability of an insertion/deletion (several orders smaller than additive errors) that add a minimal amount of redundancy. These templates are essentially a systematic way of encoding number-theoretic codes (primarily Levenshtein's s = 1 insertion/deletion code). Moment balancing templates proposed up to this point have been of fixed length. In this paper, it is shown that by using variable length templates, it is possible to obtain better performance than the optimal fixed length moment balancing template. Here, performance is defined as the amount of redundancy, which includes the moment balancing bits and the marker, that needs to be added.

Moment balancing templates have been proposed for channels with a small probability of an insertion/deletion (several orders smaller than additive errors) that add a minimal amount of redundancy. These templates are essentially a systematic way of encoding number-theoretic codes (primarily Levenshteinpsilas s = 1 insertion/deletion code). Moment balancing templates proposed up to this point have been fixed length. In this paper, it is shown, that by using variable length templates, it is possible to obtain better performance than the optimal fixed length moment balancing template. Here, performance is defined as the amount of redundancy that needs to be added.

A partitioned moment balancing template (systematic encoding of some number theoretic codes) is presented that can correct a single insertion/deletion. Instead of dispersing the moment balancing bits across the template, they are grouped together. Moment balancing templates are used to add insertion/deletion correcting capability to an additive-error-correcting code. The effect of using a particular additive-error-correcting code on the minimum number of moment balancing bits is investigated.