ON THE DECODING DELAY OF ENCODERS FOR INPUT-CONSTRAINED CHANNELS

Finite-state encoders that encode n-ary data into a constrained system S are considered, The anticipation, or decoding delay, of such an (S, n)-encoder is the number of symbols that a state-dependent decoder ne eds to look ahead in order to recover the current input symbol, Upper bounds are obtained on the smallest attainable number of states of any (S, n)-encoder with anticipation t. Those bounds can be explicitly co mputed from t and S, which implies that the problem of checking whethe r there is an (S, n)-encoder with anticipation t is decidable, It is a lso shown that if there is an (S, n)-encoder with anticipation t, then a version of the state-splitting algorithm can be applied to produce an (S, n) encoder with anticipation at most 2t-1, We also observe that the problem of checking whether there is an (S, n)-encoder having a s liding-block decoder with a given memory and anticipation is decidable .