Improved Gilbert-Varshamov Bound for Constrained Systems

Abstract

Nonconstructive existence results are obtained for block error-correcting codes whose codewords lie in a given constrained system. Each such system is defined as a set of words obtained by reading the labels of a finite directed labeled graph. For a prescribed constrained system and relative minimum distance δ, the new lower bounds on the rate of such codes improve on those derived recently by Kolesnik and Krachkovsky. The better bounds are achieved by considering a special subclass of sequences in the constrained system, namely, those having certain empirical statistics determined by δ. © 1992 IEEE