A linear bound for sliding-block decoder window size, II

Abstract

An input-constrained channel is the set 5 of finite sequences of symbols generated by the walks on a labeled finite directed graph G (which is said to present 5). 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 and the stethering technique of Ashley, Marcus, and Roth. When 5 has finite memory, and p and q are integers where pjq is at most the capacity of 5, the construction guarantees an encoder at rate p : q 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 5. 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. ©1996 IEEE.