On the Capacity of Constrained Systems

Konferenz: SCC'10 - 8th International ITG Conference on Source and Channel Coding
18.01.2010 - 21.01.2010 in Siegen, Germany

Tagungsband: SCC'10

Seiten: 6Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

Bächerer, G.; Mathar, R. (Institute for Theoretical Information Technology, RWTH Aachen University, 52056 Aachen, Germany)
Rocha, V. C. da jun.; Pimentel, C. (Communications Research Group - CODEC, Department of Electronics and Systems, P.O. Box 7800, Federal University of Pernambuco, 50711-970 Recife PE, Brazil)

In the first chapter of Shannon’s A Mathematical Theory of Communication, it is shown that the maximum entropy rate of an input process of a constrained system is limited by the combinatorial capacity of the system. Shannon considers systems where the constraints define regular languages and uses results from matrix theory in his derivations. In this work, the regularity constraint is dropped. Using generating functions, it is shown that the maximum entropy rate of an input process is upper-bounded by the combinatorial capacity in general. The presented results also allow for a new approach to systems with regular constraints. As an example, the results are applied to binary sequences that fulfill the (j, k) run-length constraint and by using the proposed framework, a simple formula for the combinatorial capacity is given and a maxentropic input process is defined.