Construction of Encoders with Small Decoding Look-Ahead for Input-Constrained Channels

Abstract

An input-constrained channel is defined as the set S of finite sequences generated by a finite labeled directed graph which defines the channel. A construction based on a result of Adler, Goodwyn, and Weiss is presented for finite-state encoders for input-constrained channels. Let 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 capacity c(S) of S, the construction provides finite-state encoders of fixed-rate p : q that can be implemented in hardware with a number of gates which is at most polynomially large in |V|. When p/q < c(S), the encoders have order ≤ 12|V|, namely, they can be decoded by looking ahead at up to 12|V| symbols, thus improving slightly on the order of previously known constructions. A stronger result holds when p/q ≤ c(S) − ((log2 e)/(2p q)) and S is of finite memory, where the encoders can be decoded by a sliding-block decoder with look-ahead ≤ 2|V| + 1. © 1995 IEEE.