Information rates of two-dimensional recording channels

Page-oriented storage technologies have been studied because of their potential to achieve storage densities beyond the reach of current track-oriented storage technologies. Such technologies store arrays of data on a two-dimensional surface. Thus the recording channel can be modeled as a two-dimensional finite-state intersymbol interference (ISI) channel. Two-dimensional constrained codes and two-dimensional error-correcting codes are required to achieve reliable data recording and retrieval for such channels. In this dissertation, we investigate information rates for two-dimensional discrete noiseless channels with constrained inputs and for two-dimensional noisy ISI channels. These information rates provide information-theoretic limits on the storage density achievable by the page-oriented technologies represented by these channel models.; In the setting of two-dimensional noiseless channels with constrained inputs, we derive tight lower bounds on (d, infinity) runlength-limited (RLL) constraints by studying the average coding ratio of two-dimensional bit-stuffing encoders. The bounds are applicable to both symmetric and asymmetric (d, infinity)-constraints.; For the noisy two-dimensional ISI channel, we investigate information rates from two perspectives. Since the mutual information rate differs from the output entropy rate by a constant, one approach is to focus on the evaluation of the entropy rate of the channel output array which is a stationary two-dimensional hidden Markov field. Upper and lower bounds on the symmetric information rate (SIR) are developed using this approach. The other approach is to modify existing bounds on the information rates of one-dimensional ISI channels such that they can be applied to two-dimensional ISI channels. A set of bounds on the SIR and on the capacity are derived in this manner.; Finally, we prove that an optimized Markov source whose state is its previous r symbols can asymptotically achieve the capacity of finite-state ISI channels. Optimal Markov sources have been used to obtain a lower bound on channel capacity and the optimized input distributions have been used in the design of capacity-approaching codes. Our result provides a solid theoretical justification of this approach. The asymptotic optimality is shown to extend to the binary symmetric channel with constrained input, two-dimensional ISI channels, and general indecomposable finite-state channels.