Talk abstract:

Capacity of Constrained Systems in One and Two Dimensions

Paul H. Siegel
Signal Transmission and Recording (STAR) Group
Department of Electrical and Computer Engineering
University of California, San Diego
psiegel@ucsd.edu
http://cwc.ucsd.edu/~psiegel/

In this talk, we discuss results and open problems pertaining to the (Shannon) capacity of constrained systems of sequences and two-dimensional arrays.

The capacity represents the growth rate of the number of sequences or arrays in the constrained system, as their size increases toward infinity. The capacity can also be interpreted as the maximum entropy achieved by any probability measure on the constrained system. From the coding perspective, the capacity represents an upper bound on the rate of invertible codes from unconstrained sequences to the constrained system.

We will address a number of questions of mathematical interest and engineering relevance that one can ask about the capacity of constrained systems. These include questions of existence, computability, and uniqueness of maxentropic measures. We will show that the answers in two dimensions can be quite different from those in one dimension.

We will then take a closer look at properties of the capacity for a particular family of constrained systems that have been the subject of extensive investigation, namely, one-dimensional and two-dimensional runlength-limited (d,k) constraints. We will present results, both old and new, pertaining to such issues as: rationality of capacity, capacity identities, bounds on capacity, and asymptotic behavior.

Finally, we will comment upon the design of efficient one-dimensional and two-dimensional (d,k) codes.

[This talk includes results of joint research with Ron Roth, Jack Wolf, and Oyvind Ytrehus]

Material used during the talk

Back to Codes, Systems and Graphical Models