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
展开▼
机译：作者针对给定的受约束系统和速率获得了任何编码器中状态数量的一般下限。在固定速率有限状态编码器中显示状态数的下限，该编码器将无约束的n元序列映射到由有限标记图G定义的一组给定的约束序列。特别是，给出了一个简单的下限按min / sub x / max / sub v / x / sub v /计算，其中x =（x / sub v /）的范围在G的邻接矩阵的某些（非整数）近似特征向量上。在某种意义上，边界是接近的状态分离算法可以实现的目标，并且在某些情况下，它们被证明是严格的。尤其是，这些界限用于显示针对该状态的最小（状态数）已知的编码器
展开▼
