The maximum insertion rate of a one-dimensional constrained system over a finite alphabet is defined to be the maximum density of positions that can be freely, and independently, filled in with arbitrary symbols of the alphabet and still satisfy the constraint. In this paper, this concept is extended to higher dimensional constraints, that is, to constraints on D-dimensional arrays defined by imposing a 1-dimensional constraint in each dimension. We give a simple upper bound on the D-dimensional maximum insertion rate in terms of the individual 1-dimensional maximum insertion rate. For D-dimensional constraints defined by imposing the same 1-dimensional constraint in each dimension, we show that the D-dimensional maximum insertion rate is the same as the 1-dimensional maximum insertion rate. In this case (called the isotropic or, sometimes, symmetric case), we show that the maximum insertion rate is a lower bound on the limiting D-dimensional capacity as D tends to infinity. Finally, we show that in the case of a finite memory constraint, when the maximum insertion rate is zero, the D-dimensional capacity decays exponentially fast to zero.

We introduce a new method for analyzing and constructing combined modulation and error-correcting codes (ECCs), in particular codes that utilize some form of reverse concatenation and whose ECC decoding scheme requires easy access to soft information. We expand the work of Immink and Wijngaarden and also of Campello, Marcus, New, and Wilson, in which certain bit positions in the modulation code are deliberately left unconstrained for the ECC parity bits, in the sense that such positions can take on either bit value without violating the constraint. Our method of analysis involves creating a single graph that incorporates information on these unconstrained positions directly into the constraint graph without any assumptions of periodicity or sets of unconstrained positions, and is thus completely general. We establish several properties of the tradeoff function that relates the density of unconstrained positions to the maximum code rate. In particular, the tradeoff function is shown to be concave and continuous. Algorithms for computing lower and upper bounds for this function are presented. We also show how to compute the maximum possible density of unconstrained positions and give explicit values for the runlength-limited (RLL(d,k)) and maximum-transition-run (MTR(j,k)) constraints.

Maximum transition run (MTR) constrained systems are used to improve detection performance in storage channels. Recently, there has been a growing interest in time-varying MTR (TMTR) systems, after such codes were observed to eliminate certain error events and thus provide high coding gain for EnPR4 channels for n=2,3. In this work, TMTR constraints parameterized by a vector, whose coordinates specify periodically the maximum runlengths of 1's ending at the positions, are investigated. A canonical way to classify such constraints and simplify their minimal graph presentations is introduced. It is shown that there is a particularly simple presentation for a special class of TMTR constraints and explicit descriptions of their characteristic equations are derived. New upper bounds on the capacity of TMTR constraints are established, and an explicit linear ordering by capacity of all tight TMTR constraints up to period 4 is given. For MTR constrained systems with unconstrained positions, it is shown that the set of sequences restricted to the constrained positions yields a natural TMTR constraint. Using TMTR constraints, a new upper bound on the tradeoff function for MTR systems that relates the density of unconstrained positions to the maximum code rates is determined

A graph-theoretic method for analyzing a scheme of combining modulation and error-correcting codes (ECC), in which certain bit positions in the modulation code are left unconstrained for insertion of ECC parity bits is presented in this paper. We establish several properties of the tradeoff function that relates the density of unconstrained positions to the maximum code rate, including concavity and continuity.

In digital storage systems where the input to the noisy channel is required to satisfy a modulation constraint, the constrained code and error-control code (ECC) are typically designed and decoded independently. The achievable rate for this situation is evaluated as the rate of average intersection of the constraint and the ECC. The gap from the capacity of the noisy constrained channel is called the constraint gain, which represents the potential improvement in combining the design and decoding of the constrained code and the ECC. The constraint gain is computed for various constraints over the binary-input additive white Gaussian noise (AWGN) channel (BIAWGNC) as well as over intersymbol interference (ISI) channels. Finally, it is shown that an infinite cascade of reverse concatenation with independent decoding of constraint and ECC has a capacity equal to the rate of average intersection.