On the Capacity of Constrained Systems

Conference: SCC'10 - 8th International ITG Conference on Source and Channel Coding
01/18/2010 - 01/21/2010 at Siegen, Germany

Proceedings: SCC'10

Pages: 6Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

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.