Lower bounds on the anticipation of encoders for input-constrained channels

An input-constrained channel S is defined as the set of words generated by a finite labeled directed graph. It is shown that every finite-state encode r with finite anticipation (i,e,, with finite decoding delay) for S can be obtained through state-splitting rounds applied to some deterministic graph presentation of S, followed by a reduction of equivalent states, Furthermo re, each splitting round can be restricted to follow a certain prescribed s tructure. This result, in turn, provides a necessary and sufficient conditi on on the existence of finite-state encoders for S with a given rate p : q and a given anticipation a. A second condition is derived on the existence of such encoders; this condi tion is only necessary, but it applies to every deterministic graph present ation of S, Based on these two conditions, lower bounds are derived on the anticipation of finite-state encoders, Those lower bounds improve on previo usly known bounds and, in particular, they are shown to be tight for the co mmon rates used for the (1, 7)-runlength-limited (RLL) and (2,7)-RLL constr aints.