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 encoder 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, Furthermore, each splitting round can be restricted to follow a certain prescribed structure. This result, in turn, provides a necessary and sufficient condition 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 condition is only necessary, but it applies to every deterministic graph presentation of S, Based on these two conditions, lower bounds are derived on the anticipation of finite-state encoders, Those lower bounds improve on previously known bounds and, in particular, they are shown to be tight for the common rates used for the (1, 7)-runlength-limited (RLL) and (2,7)-RLL constraints.