A LINEAR BOUND FOR SLIDING-BLOCK DECODER WINDOW SIZE .2.

An input-constrained channel is the set S of finite sequences of symbo ls 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 a nd the stethering technique of Ashley, Marcus, and Roth. When S has fi nite memory, and p and q are integers where p/g is at most the capacit y of S, the construction guarantees an encoder at rate p : q and havin g a sliding-block decoder (literally at rate q : p) with look-ahead th at is linear in the number of states of the smallest graph G presentin g S. This contrasts with previous constructions. The straight Adler, C oppersmith, and Hassner construction provides an encoder having a slid ing-block decoder at rate q : p, but the best proven upper bound on th e decoder look-ahead is exponential in the number of states of G. A pr evious construction of Ashley provides an encoder having a sliding-blo ck 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 linea r in the number of states of G.