The Shannon capacity of M-ary constrained codes
Cecilio Jose Lins Pimentel · 2002
We consider a class of constrained codes that prohibits the occurrence of substrings from a finite set F of sequences of finite length over an alphabet Z/sub A/=(0,1,...,A-1). The set F is called the set of distinguished substrings. The capacity of the code S, denoted as C, was defined by Shannon as C=lim/sub n/spl rarr//spl infin//log/sub 2/ c/sub n//n. The standard method of evaluating the capacity is to take log/sub 2//spl lambda/, where /spl lambda/ is the largest real eigenvalue of the adjacent matrix that reflects the constraint. The purpose of this paper is to present a systematic method, based on combinatorial enumeration techniques, to find the number of sequences of length n in S,c/sub n/ satisfying a specified constraint. The capacity is expressed as the base two logarithm of the inverse of the largest real root of the denominator polynomial in the generating series which enumerates the sequences.