Bounds on the number of states in encoder graphs for input-constrained channels

Publisher Website
Google Scholar
Abstract
The authors obtain general lower bounds on the number of states in any encoder for a given constrained system and rate. Lower bounds on the number of states are exhibited in a fixed-rate finite-state encoder that maps unconstrained n-ary sequences into a given set of constrained sequences, defined by a finite labeled graph G. In particular, one simple lower bound is given by min/sub x/max/sub v/x/sub v/ where x=(x/sub v/) ranges over certain (nonnegative integer) approximate eigenvectors of the adjacency matrix for G. In some sense, the bounds are close to what can be realized by the state splitting algorithm and in some cases, they are shown to be tight. In particular, these bounds are used to show that the smallest (in number of states) known encoders for the

This publication has 15 references indexed in Scilit: