Sliding-block coding for input-restricted channels

Abstract

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)<or=(h/log n) is satisfied, where h is the entropy of the system S. If strict inequality holds or if equality holds and S satisfies a natural condition called 'almost of finite type' (which includes the systems used in practice), a stronger result is obtained, namely, the decoders can be made 'state-independent' sliding-block. This generalizes previous results. An example is also given to show that the stronger result does not hold for general sofic systems.<<ETX>>