The channel capacity of one and two-dimensional constrained codes

This thesis is in the area of Information Theory. The problem examined is on the channel capacity of Codes for Mass Data Storage/Transmission Systems and involves Combinatorics, Matrix Theory, Graph Spectra, Probability, and Numerical Analysis. Constrained codes are sets of sequences in which certain patterns are forbidden or, alternatively, required, to occur. A two dimensional constrained code is a set of arrays with this property. Such codes, at least in the one-dimensional case, are widely used in magnetic, digital and optical data recordings. Due to this applicability, these codes and their channel capacities, which intuitively can be interpreted as the maximum amount of information which is stored or transmitted per bit, have been extensively studied. Recently, much interest has started focusing on two-dimensional run-length limited codes; these are two-dimensional constrained (0,1)-arrays that satisfy specific one-dimensional run-length limited constraints both horizontally and vertically. Research into these types of codes is currently in its infancy but very active. There is rnuch concerning them that is still not well-understood. In this thesis, we first describe the framework of the topic and then summarize and comment the recent representative works. We then establish theoretical results about the channel capacity of 2-D constrained codes. Finally, we develop new techniques for analyzing and computing capacities