CONSTRUCTION OF ENCODERS WITH SMALL DECODING LOOK-AHEAD FOR INPUT-CONSTRAINED CHANNELS

An input-constrained channel is defined as the set S of finite sequenc es generated by a finite labeled directed graph which defines the chan nel. A construction based on a result of Adler, Goodwyn, and Weiss is presented for finite-state encoders for input-constrained channels. Le t G = (V, E) denote a smallest deterministic presentation of S. For a given input-constrained channel S and for any rate p : q up to the cap acity c(S) of S, the construction provides finite-state encoders of fi xed-rate p : q that can be implemented in hardware with a number of ga tes which is at most polynomially large in \V\ When p/g < c(S), the en coders have order less than or equal to 12\V\, namely, they can be dec oded by looking ahead at up to 12\V\ symbols, thus improving slightly on the order of previously known constructions. A stronger result hold s when p/g less than or equal to c(S) - ((log(2) e)/(2(p)q)) and S is of finite memory, where the encoders can be decoded by a sliding-block decoder with look-ahead less than or equal to 2\V\ + 1.