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.

Just as the Hamming weight spectrum of a linear block code sheds light on the performance of a maximum likelihood decoder, the pseudo-weight spectrum provides insight into the performance of a linear programming decoder. Using properties of polyhedral cones, we find the pseudo-weight spectrum of some short codes. We also present two general lower bounds on the minimum pseudo-weight. The first bound is based on the column weight of the parity-check matrix. The second bound is computed by solving an optimization problem. In some cases, this bound is more tractable to compute than previously known bounds and thus can be applied to longer codes

We consider a class of encoders for constrained systems, which we call block-type-decodable encoders. For a constrained system presented by a deterministic graph, we design a block-type-decodable encoder by selecting a subset of states of the graph to be used as encoder states. Such a subset is known as a set of principal states. Our goal is to find an optimal set of principal states, i.e., a set which yields the highest code rate. We study the relationship between optimal sets of principal states at finite block length and at asymptotically large block length. Specifically, we show that for a primitive constraint and a large enough block length, any optimal set of principal states is also asymptotically optimal. Moreover, we give bounds on the block length such that this relationship holds. We also characterize asymptotically optimal block-type-decodable encoders. Finally, we study the complexity of various problems related to block-type-decodable encoders.

In most recording channels, modulation codes are employed to transform user data to sequences that satisfy some desirable constraint. Run-length-limited (RLL(d,k)) and maximum transition run (MTR(j,k)) systems are examples of constraints that improve timing and detection performance. A modulation encoder typically takes the form of a finite-state machine. Alternatively, a look-ahead encoder can be used instead of a finite-state encoder to reduce complexity. Its encoding process involves a delay called look-ahead. If the input labeling of a look-ahead encoder allows block decodability, the encoder is called a bounded-delay-encodable block-decodable (BDB) encoder. These classes of encoders can be viewed as generalizations of the well-known deterministic and block-decodable encoders. Other related classes are finite-anticipation and sliding-block decodable encoders. In this paper, we clarify the relationship among these encoders. We also discuss the characterization of look-ahead and BDB encoders using the concept of path-classes. To minimize encoder complexity, look-ahead is desired to be small. We show that for nonreturn to zero inverted (NRZI) versions of RLL|,(0,k),RLL(1,k), and RLL(d,infin), a BDB encoder does not yield a higher rate than an optimal block-decodable encoder. However, for RLL(d,k) such that dges4 and d+2lesk

In most recording systems, user data is translated to sequences that satisfy some constraint like run-length limited (RLL) and maximum transition run (MTR). An encoder for such a constraint is block decodable encoder. In this paper, the encoder is no longer a finite-state encoder and the encoding process uses the look ahead technique. An look ahead encoder such that the input labeling is consistent is called a bounded-delay-encodable block-decodable encoder. For look-ahead and BDB encoders state-tree as a basis for constructing the encoders. A concept called path-classes to characterize these classes of encoders is used.

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.

A constrained system is presented by a finite-state labeled graph. For such systems, we focus on block-type-decodable encoders, comprising three classes known as block, block-decodable, and deterministic encoders. Franaszek (1968) gives a sufficient condition which guarantees the equality of the optimal rates of block-decodable and deterministic encoders for the same block length. We introduce another sufficient condition, called the straight-line condition, which yields the same result. Run-length limited RLL(d,k) and maximum transition run MTR(j,k) constraints are shown to satisfy both conditions. In general, block-type-decodable encoders are constructed by choosing a subset of states of the graph to be used as encoder states. Such a subset is known as a set of principal states. For each type of encoder and each block length, a natural problem is to find a set of principal states which maximizes the code rate. We show how to compute the asymptotically optimal sets of principal states for deterministic encoders and how they are related to the case of large but finite block lengths. We give optimal sets of principal states for MTR(j,k)-block-type-decodable encoders for all codeword lengths. Finally we compare the code rate of nonreturn to zero inverted (NRZI) encoders to that of corresponding nonreturn to zero (NRZ) and signed NRZI encoders.