We propose two modified versions of the classical gradient ascent method to compute the capacity of finite-state channels with Markovian inputs. For the case that the channel mutual information rate is strongly concave in a parameter taking values in a compact convex subset of some Euclidean space, our first algorithm proves to achieve polynomial accuracy in polynomial time and, moreover, for some special families of finite-state channels our algorithm can achieve exponential accuracy in polynomial time under some technical conditions. For the case that the channel mutual information rate may not be strongly concave, our second algorithm proves to be at least locally convergent.

We propose a modified version of the classical gradient descent method to compute the capacity of finite-state channels with Markovian input. Under some concavity assumptions, our algorithm proves to achieve polynomial accuracy in polynomial time for general finite-state channels. Moreover, for some special families of finite-state channels, our algorithm can achieve exponential accuracy in polynomial time.

We first prove that under certain mild assumptions, the entropy rate of a hidden Markov chain, observed when passing a finite-state stationary Markov chain through a discrete-time continuous-output channel, is analytic with respect to the input Markov chain parameters. We then further prove, under strengthened assumptions on the channel, that the entropy rate is jointly analytic as a function of both the input Markov chain parameters and the channel parameters. In particular, the main theorems establish the analyticity of the entropy rate for two representative channels: 1) Cauchy and 2) Gaussian. The analyticity results obtained are expected to be helpful in computation/estimation of entropy rate of hidden Markov chains and capacity of finite-state channels with continuous output alphabet.

For any stationary $\mathbb{Z}^d$ Gibbs measure that satisfies strong spatial mixing, we obtain sequences of upper and lower approximations that converge to its entropy. In the case $d=2$, these approximations are efficient in the sense that they are accurate to within $\epsilon$ and can be computed in time polynomial in $1/\epsilon$.

We consider a memoryless channel with an input Markov process supported on a mixing finite-type constraint. We continue the development of asymptotics for the entropy rate of the output hidden Markov chain and deduce that, at high signal-to-noise ratio, the mutual information rate of such a channel is concave with respect to “almost” all input Markov chains of a given order.

We prove that under mild positivity assumptions, the entropy rate of a continuous-state hidden Markov chain, observed when passing a finite-state Markov chain through a discrete-time continuous-output channel, is analytic as a function of the transition probabilities of the underlying Markov chain. We further prove that the entropy rate of a continuous-state hidden Markov chain, observed when passing a mixing finite-type constrained Markov chain through a discrete-time Gaussian channel, is smooth as a function of the transition probabilities of the underlying Markov chain.

We derive an asymptotic formula for entropy rate of a hidden Markov chain under certain parameterizations. We also discuss applications of the asymptotic formula to the asymptotic behaviors of entropy rate of hidden Markov chains as outputs of certain channels, such as binary symmetric channel, binary erasure channel, and some special Gilbert-Elliot channel.

A method for computing lower bounds on capacities of two-dimensional (2D) constraints having a symmetric presentation in either the horizontal or the vertical direction is presented. The method is a generalization of the method of Calkin and Wilf (SIAMJ. Discrete Math., 1998). Previous best lower bounds on capacities of certain constraints are improved using the method. It is also shown how this method, as well as their method for computing upper bounds on the capacity, can be applied to constraints which are not of finite-type. Additionally, capacities of two families of multidimensional constraints are given exactly.

We consider a finite-state memoryless channel with i.i.d. channel state and the input Markov process supported on a mixing finite-type constraint. We discuss the asymptotic behavior of entropy rate of the output hidden Markov chain and deduce that the mutual information rate of such a channel is concave with respect to the parameters of the input Markov processes at high signal-to-noise ratio. In principle, the concavity result enables good numerical approximation of the maximum mutual information rate and capacity of such a channel.

A method for computing lower bounds on capacities of 2-dimensional constraints having a symmetric presentation in either the horizontal or the vertical direction is presented. The method is a generalization of the method of Calkin and Wilf (SIAM J. Discrete Math., 1998). Previous best lower bounds on capacities of certain constraints are improved using the method. It is also shown how this method, as well as their method for computing upper bounds on the capacity, can be applied to constraints which are not of finite-type. Additionally, capacities of 2 families of multi-dimensional constraints are given exactly.

We generalize a result in [8] and derive an asymptotic formula for entropy rate of a hidden Markov chain around a "weak Black Hole". We also discuss applications of the asymptotic formula to certain channels.

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.

In this paper, we generalize a result by E. Ordentlich and T. Weissman. (2004) and derive an asymptotic formula for the entropy rate of a hidden Markov chain, observed when a Markov chain passes through a binary symmetric channel. And we prove an asymptotic formula for the capacity of a binary symmetric channel with input process supported on an irreducible finite type constraint.

Consider a hidden Markov chain obtained as the observation process of an ordinary Markov chain corrupted by noise. Recently Zuk et al showed how, in principle, one can explicitly compute the derivatives of the entropy rate of at extreme values of the noise. Namely, they showed that the derivatives of standard upper approximations to the entropy rate actually stabilize at an explicit finite time. We generalize this result to a natural class of hidden Markov chains called "black holes." We also discuss in depth special cases of binary Markov chains observed in binary-symmetric noise, and give an abstract formula for the first derivative in terms of a measure on the simplex due to Blackwell.

We give relaxed sufficient conditions (compared to D. Blackwell (1957)) for analyticity of the entropy rate of a hidden Markov chain. Several special cases of the relaxed conditions are discussed. A general principle to calculate the domain of analyticity is stated. An example is given to estimate the radius of convergence for the entropy rate. Finally, we prove a "stabilizing" property of "black hole" case, which suggests that one can explicitly compute the derivatives and obtain an explicit Taylor series in certain cases, generalizing the results in O. Zuk et al. (2004)

We prove that under mild positivity assumptions the entropy rate of a hidden Markov chain varies analytically as a function of the underlying Markov chain parameters. A general principle to determine the domain of analyticity is stated. An example is given to estimate the radius of convergence for the entropy rate. We then show that the positivity assumptions can be relaxed, and examples are given for the relaxed conditions. We study a special class of hidden Markov chains in more detail: binary hidden Markov chains with an unambiguous symbol, and we give necessary and sufficient conditions for analyticity of the entropy rate for this case. Finally, we show that under the positivity assumptions, the hidden Markov chain itself varies analytically, in a strong sense, as a function of the underlying Markov chain parameters

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

We prove that under mild assumptions a hidden Markov chain varies analytically, in a strong sense, as a function of the underlying Markov chain parameters. In particular, we show that, under these assumptions, the entropy rate of a hidden Markov chain is an analytic function of the parameters. We give examples to show how this can fail in some cases. And we study two natural special classes of hidden Markov chains in more detail: binary hidden Markov chains with an unambiguous symbol and binary Markov chains corrupted by binary symmetric noise

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.

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.

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.

We develop methods for analyzing and constructing combined modulation/error-correcting codes (ECC codes), in particular codes that employ some form of reversed concatenation and whose ECC decoding scheme requires easy access to soft information (e.g., turbo codes, low-density parity-check (LDPC) codes or parity codes). We expand on earlier work of Wijngaarden and Immink (1998, 2001), Immink (1999) and Fan (1999), in which certain bit positions are reserved for ECC parity, in the sense that the bit values in these positions can be changed without violating the constraint. Earlier work has focused more on block codes for specific modulation constraints. While our treatment is completely general, we focus on finite-state codes for maximum transition run (MTR) constraints. We (1) obtain some improved constructions for MTR codes based on short block lengths, (2) specify an asymptotic lower bound for MTR constraints, which is tight in very special cases, for the maximal code rate achievable for an MTR code with a given density of unconstrained positions, and (3) show how to compute the capacity of the set of sequences that satisfy a completely arbitrary constraint with a specified set of bit positions unconstrained.

A new twins constraint for maximum transition run (MTR) codes is introduced to eliminate quasi-catastrophic error propagation in sequence detectors for generalized partial response channels with spectral nulls both at dc and at the Nyquist frequency. Two variants of the twins constraint that depend on whether the generalized partial response detector trellis is unconstrained or j-constrained are studied. Deterministic finite-state transition diagrams that present the twins constraint are specified, and the capacity of the new class of MTR constraints is computed. The connection between (G,I) constraints and MTR(j) constraints is clarified. Code design methodologies that are based on look-ahead coding in combination with violation detection/substitution as well as on state splitting are used to obtain several specific constructions of high-rate MTR codes.

A rate p : q block encoder is a dataword-to-codeword assignment from 2/sup p/ p-bit datawords to 2/sup p/ q-bit codewords, and the corresponding block decoder is the inverse of the encoder. When designing block encoders/decoders for constrained systems, often, more than 2/sup p/ codewords are available. In this paper, as our main contribution, we propose efficient heuristic computer algorithms to eliminate the excess codewords and to construct low hardware complexity block encoders/decoders. For (0,4/4) and (0,3/6) PRML constraints, block encoders/decoders generated using the proposed algorithms are comparable in complexity to human-generated encoders/decoders, but are significantly simpler than lexicographical encoders/decoders.

Time-varying encoders for constrained systems are introduced. The approach generalizes the state-splitting (ACH) algorithm in a way that yields encoders consisting of multiple phases, with encoding proceeding cyclically from one phase to the next. The framework is useful for design of high-rate codes with reduced decoder error propagation and reduced complexity.

A method is presented for designing lossless sliding-block compression schemes that map constrained sequences onto unconstrained ones. The new compression scheme is incorporated into a coding technique for noisy constrained channels, which has applications to magnetic and optical storage. As suggested previously by Immink (see ibid., vol.43, p.1389-99, 1997), the use of a lossless compression code can improve the performance of a modified concatenation scheme where the positions of the error-correcting code and constrained code are reversed (primarily in order to eliminate error propagation due to the constrained code). Examples are presented that demonstrate the advantage of using sliding-block compression over block compression in a noisy constrained setting.

We describe a framework for designing encoders that transform arbitrary data sequences into two-dimensional arrays satisfying certain constraints, in particular, constraints that guarantee arrays with limited high spatial frequency content. We also exhibit specific codes that produce such arrays. Such codes are useful for holographic recording systems.

We describe a generalization of the state-splitting algorithm (also known as the Adler-Coppersmith-Hassner (1983) algorithm) for constructing encoders which encode arbitrary data into constrained systems of sequences. In the generalized algorithm, we replace approximate eigenvectors with approximate eigenmatrices to yield a framework for designing encoders with smaller sliding-block windows and therefore lower error propagation.

Finite-state encoders that encode n-ary data into a constrained system S are considered. The anticipation, or decoding delay, of such an (S,n)-encoder is the number of symbols that a state-dependent decoder needs to look ahead in order to recover the current input symbol. Upper bounds are obtained on the smallest attainable number of states of any (S, n)-encoder with anticipation t. Those bounds can be explicitly computed from t and S, which implies that the problem of checking whether there is an (S, n)-encoder with anticipation t is decidable. It is also shown that if there is an (S,n)-encoder with anticipation t, then a version of the state-splitting algorithm can be applied to produce an (S, n) encoder with anticipation at most 2t-1. We also observe that the problem of checking whether there is an (S, n)-encoder having a sliding-block decoder with a given memory and anticipation is decidable.

The existence and uniqueness of a canonical minimal encoder for any given sliding block decoder are proven. The structure of this encoder is given in terms of an explicit sequence of state splittings. The universality of the state splitting algorithm for code construction is clarified.

An input-constrained channel is defined as the set S of finite sequences generated by a finite labeled directed graph which defines the channel. A construction based on a result of Adler, Goodwyn, and Weiss (1977) is presented for finite-state encoders for input-constrained channels. Let G=(V, E) denote a smallest deterministic presentation of S. For a given input-constrained channel S and for any rate p: q up to the capacity c(S) of S, the construction provides finite-state encoders of fixed-rate p: q that can be implemented in hardware with a number of gates which is at most polynomially large in |V|. When p/q>

We re-cast a theorem of Willems (1989) in terms of symbolic dynamics. We then present a new result which characterizes when an irreducible sofic shift (i.e., constrained system) has a unique minimal irreducible presentation.>

Several constructions are presented for extending a bounded-to-one sliding-block code to a bounded-to-one surjection onto its range, while preserving nice properties of the original code.

The authors provide a self-contained exposition of modulation code design methods based upon the state splitting algorithm. They review the necessary background on finite state transition diagrams, constrained systems, and Shannon (1948) capacity. The state splitting algorithm for constructing finite state encoders is presented and summarized in a step-by-step fashion. These encoders automatically have state-dependent decoders. It is shown that for the class of finite-type constrained systems, the encoders constructed can be made to have sliding-block decoders. The authors consider practical techniques for reducing the number of encoder states as well as the size of the sliding-block decoder window. They discuss the class of almost-finite-type systems and state the general results which yield noncatastrophic encoders. The techniques are applied to the design of several codes of interest in digital data recording.>

An irreducible Markov chain with stationary transition probabilities on a finite directed graph is considered. The probability of large deviations of the random variable denoting the empirical type of the first n transitions is investigated.>

Nonconstructive existence results are obtained for block error-correcting codes whose codewords lie in a given constrained system. Each such system is defined as a set of words obtained by reading the labels of a finite directed labeled graph. For a prescribed constrained system and relative minimum distance delta , the new lower bounds on the rate of such codes improve on those derived recently by V.D. Kolesnik and V.Y. Krachkovsky (1991). The better bounds are achieved by considering a special subclass of sequences in the constrained system, namely, those having certain empirical statistics determined by delta .>

A new class of constrained systems average runlength constraints (ARCs), is defined by requiring that the sum of n consecutive run lengths be bounded above by a linear function of n. In particular, the running average runlength of every sequence in the system is bounded above by a constant. A general result is given on the capacity of ARC systems. The state splitting algorithm is then improved for variable-length graphs. This is then applied to obtain high, fixed-rate codes from the free binary source to ARC systems. As an example, a rate 1/2, (d,k)=

The authors obtain general lower bounds on the number of states in any encoder for a given constrained system and rate. Lower bounds on the number of states are exhibited in a fixed-rate finite-state encoder that maps unconstrained n-ary sequences into a given set of constrained sequences, defined by a finite labeled graph G. In particular, one simple lower bound is given by min/sub x/max/sub v/x/sub v/ where x=(x/sub v/) ranges over certain (nonnegative integer) approximate eigenvectors of the adjacency matrix for G. In some sense, the bounds are close to what can be realized by the state splitting algorithm and in some cases, they are shown to be tight. In particular, these bounds are used to show that the smallest (in number of states) known encoders for the

Work on coding arbitrary sequences into a constrained system of sequences (called a sofic system) is presented. Such systems model the input constraints for input-restricted channels (e.g., run-length limits and spectral constraints for the magnetic recording channel). In this context it is important that the code be noncatastrophic to ensure that the decoder has limited error propagation. A constructive proof is given of the existence of finite-state invertible noncatastrophic codes from arbitrary n-ary sequences to a sofic system S at constant rate p:q provided only that Shannon's condition (p/q)>

In digital data transmission (respectively, storage systems), line codes (respectively, recording codes) are used to tailor the spectrum of the encoded sequences to satisfy constraints imposed by the channel transfer characteristics or other system requirements. For instance, pilot tone insertion requires codes with zero mean and zero spectral density at tone frequencies. Embedded tracking/focus servo signals produce similar needs. Codes are studied with spectral nulls at frequenciesf=kf_{s}/n, wheref, is the symbol frequency andk, nare relatively prime integers withk \leq n;in other words, nulls at rational submultiples of the symbol frequency. A necessary and sufficient condition is given for a null atfin the form of a finite discrete Fourier transform (DFT) running sum condition. A corollary of the result is the algebraic characterization of spectral nulls which can be simultaneously realized. Specializing to binary sequences, we describe canonical Mealy-type state diagrams (directed graphs with edges labeled by binary symbols) for each set of realizable spectral nulls. Using the canonical diagrams, we obtain a frequency domain characterization of the spectral null systems obtained by the technique of time domain interleaving.

The state splitting algorithm of Adler, Coppersmith, and Hassner for graphs with edges of fixed length is extended to graphs with edges of variable lengths. This has the potential to improve modulation code construction techniques. Although the ideas of state splitting come from dynamical systems, completely graph-theoretic terms are used.

Techniques of symbolic dynamics are applied to prove the existence of codes suitable for certain input-restricted channels. This generalizes the earlier work of Adler, Coppersmith, and Hassner on the same problem.