A statistical simulation method is introduced to estimate the sector error rate (SER) of proposed triply concatenated coding systems for magnetic hard disk drives. The outer code is a standard interleaved Reed-Solomon code. The 'middle' codes are run length limiting codes used to demonstrate the effect of error propagation. The inner code(s) are block codes with 1 or 3 parity check bits. First, a baud rate simulation is used to estimate sufficient statistics to extrapolate ECC performance. Second, a Monte Carlo error event simulator generates error instances which are simply checked for correctability. In all code combinations the apparent SNR gains when considering error (or bit) event rates are considerably lessened or completely lost when considering SER.

In todays high-speed disk drive read channel ICs maximum likelihood detection using the Viterbi algorithm is a key component in reconstructing digital data sequences. The presented Viterbi decoder was realized in a 0.25 /spl mu/m CMOS technology. Using the proposed comparison approach, it achieves a throughput rate of 550 Mb/s.

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.

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.

For pt.I see ibid., vol.34, p. 389-99, 1988. An input-constrained channel is the set S of finite sequences of symbols generated by the walks on a labeled finite directed graph G (which is said to present S). We introduce a new construction of finite-state encoders for input-constrained channels. The construction is a hybrid of the state-splitting technique of Adler, Coppersmith, and Hassner (1983) and the stethering technique of Ashley, Marcus, and Roth (see ibid., vol.41, p.55-76, 1995). When S has finite memory, and p and g are integers where p/g is at most the capacity of S, the construction guarantees an encoder at rate p:g and having a sliding-block decoder (literally at rate q:p) with look-ahead that is linear in the number of states of the smallest graph G presenting S. This contrasts with previous constructions. The straight Adler, Coppersmith, and Hassner construction provides an encoder having a sliding-block decoder at rate q:p, but the best proven upper bound on the decoder look-ahead is exponential in the number of states of G. A previous construction of Ashley provides an encoder having a sliding-block decoder whose look-ahead has been proven to be linear in the number of states of G, but the decoding is at rate tq:tp, where t is linear in the number of states of G.

A constrained system, or sofic system, S is the set of symbol strings generated by the finite-length paths through a finite labeled, directed graph. Karabed and Marcus (1988), extending the work of Adler, Coppersmith, and Hassner (1983), used the technique of state-splitting to prove the existence of a noncatastrophic, rate p:q finite-state encoder from binary data into S for any input word length p and codeword length q satisfying p/q/spl les/cap(S), the Shannon (1948) capacity. For constrained systems that are almost-finite-type, they further proved the existence of encoders enjoying a stronger form of decodability-namely, sliding-block decodability. In particular, their result implies the existence of a 100% efficient (rate 1/2), sliding-block code for the charge-constrained, runlength-limited constraint with parameters (d, k; c)=(1,3; 3), an almost-finite-type system with capacity precisely 1/2. We describe two quite different constructions of such codes. The constructions highlight connections between the problem of determining sliding-block decodability of a finite-state encoder and certain problems of colorability for graphs and sets. Using these connections, we show that the problem of determining the existence of a block-decodable input tag assignment for a given rate p:q, finite-state encoder is NP-complete, for p>1. We also prove NP-completeness results for several related problems in combinatorics and coding.

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>

The problem of scalar and vector quantization in conjunction with a noisy binary symmetric channel is considered. The issue is the assignment of the shortest possible distinct binary sequences to quantization levels or vectors so as to minimize the mean-squared error caused by channel errors. By formulating the assignment as a matrix (or vector in the scalar case) and showing that the mean-squared error due to channel errors is determined by the projections of its columns onto the eigenspaces of the multidimensional channel transition matrix, a class of source/quantizer pairs is identified for which the optimal index assignment has a simple and natural form. Among other things, this provides a simpler and more accessible proof of the result of Crimmins et al. (1969) that the natural binary code is an optimal index assignment for the uniform scalar quantizer and uniform source. It also provides a potentially useful approach to further developments in source-channel coding.

The method of poles is a method for constructing a rate 1:1 finite state code from K-ary data into a constrained channel S, where S is recognized by a given local automaton and S has capacity at least log(k). We characterize those automata to which the method of poles applies in the case where h(S)=log(k). The code produced by the method of poles has a sliding-block decoder. We also give an upper bound on the window length of the decoder that applies when h(S)/spl ges/log(k).>

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 construction of finite-state codes between constrained systems called sofic systems introduced by R. Karabed and B. Marcus (1988) is continued. It is shown that if Sigma is a shift of finite type and S is a sofic system with k/n=h(S)/h( Sigma ), where h denotes entropy, there is a noncatastrophic finite-state invertible code from Sigma to S at rate k:n if Sigma and S satisfy a certain algebraic condition involving dimension groups, and Sigma and S satisfy a certain condition on their periodic points. Moreover, if S is an almost finite type sofic system, then the decoder can be sliding block.>

Two remarks in the above-titled paper by J. Ashley and P.H. Siegel (see ibid. vol.33, no.4, p.601-5, July 1987) pertaining to the rationality of the base b capacity of (d, k) runlength-limited (RLL) constraints and (d, k; c) charge-constrained RLL constraints, where b>2, are corrected.>

The author gives an upper bound on the necessary length of a sliding-block decoder window for finite-state codes from arbitrary n-ary data into any constrained system Sigma with capacity at least log(n) presented by a graph G with memory m and anticipation a. Specifically, it is shown that the ACH code construction algorithm can be used to construct a code with a sliding-block decoder at rate t:t and with window length m+a+2t, where t is upper-bounded by a linear function of the number of states of G. It is demonstrated that this is the best one can do in the sense that any general upper bound on the decoder window length for finite-state codes into systems Sigma with finite memory must grow at least linearly with the number of states of the graph G presenting Sigma .>

Let eta denote the length of the shortest error event achieving the minimum detection distance of maximum-likelihood signal detection for an impulse response having memory v. A family of impulse responses where eta is of order v/sup 2/ is exhibited. This, in turn, shows that some difficulty can arise in computing the minimum detection distance.>

It is proven that 100-percent efficient fixed-rate codes for run-length-limited (RLL)(d,k)and RLL charge-constrained(d, k; c)channels are possible in only two eases, namely(d,k; c)=(0,1;1)and(1,3;3). Specifically, the binary Shannon capacity of RLL(d, k)constrained systems is shown to be irrational for all values of(d, k),0 \leq d < k. For RLL charge-constrained systems with parameters(d, k;c), the binary capacity is irrational for all values of(d, k; c),0 \leq d < k,2c \geq k + 1, except(0,1; 1)and(1,3;3), which both have binary capacity1/2.