Finite-state codes and input-constrained channels.

This work deals with finite-state code construction for input-constrained noiseless channels. An unconstrained channel accepts as an input any sequence of channel symbols. An input-constrained channel does not. The channels are noiseless in the sense that their output equals their input. A hard-constrained channel accepts only certain sequences, and rejects all others. A costly channel is a more general model, in which sequences are assigned costs, and the channel constraint is in the form of a limitation on average cost. The hard-constrained channel becomes a special case of the costly channel where sequences have cost zero or infinity. Many constrained channels can be described by finite directed graphs. Of special interest are models for magnetic and optical recording disks. The goal of coding for such channels is to design a code that maps information into sequences acceptable to the channel at the maximum possible rate (in bits per channel symbol), which is referred to as channel capacity. Shannon found the capacity of hard-constrained channels, and proposed achieving it with block codes. Adler et al. developed a powerful method for constructing finite-state codes that achieve capacity. Finite-state codes have much lower complexity than block codes. Hard-constrained channels coincide with the mathematical notion of a subshift. We present a self-contained tutorial on subshifts, their properities, and finite-state codes. The focus is on sofic and finite type subshifts, their graph representations, and sliding-block decoders. Included is Adler et al.'s state splitting algorithm for finite-state code construction. While the results presented are known, the treatment is largely new. Karabed et al. found the capacity-cost function of a costly channel (which is the maximum rate as a function of the cost constraint value) and proposed achieving it with block codes. We give a more general characterization of the costly channel that parallels our treatment of subshifts, e.g. sofic and finite type costs and their graph representation. We also present a method similar to Adler's for constructing finite-state codes for the costly channel. They are shown to achieve a function slightly less than the capacity-cost function.PhDElectrical engineeringUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/162331/1/9001658.pd