Abstract:

Certain channels, used in communication and storage
applications, require that we constrain the input bit stream to
obey certain restrictions. Translating an arbitrary bit stream
to a constrained one incurs a rate penalty. The study of such
encoders and the maximum achievable capacity of constrained
systems, may be traced back to the work of Shannon, which today
is considered the founder of information theory.

Probably the most famous constrained system, and the subject of
this talk, is the RLL (run-length limited) system. Its use today
is widespread, in hard-disk drives, CD-ROMs, DVDs, and
fiber-optic communications, just to name a few. We will show new
results in bounding the capacity of two-dimensional RLL systems,
which still lack a closed form solution even after years of
intense research. Our work makes use of the probabilistic method
to obtain asymptotically-tight lower and upper bounds. We will
also revisit the well-known one-dimensional RLL system and show
a simple extension to it which better suits the original problem
that motivated the RLL solution. This new extension, which is
just an instance of a more general framework we call the
precision/resolution system, provides an increase of capacity
over RLL. Thus, for example, we may increase the capacity of a
DVD by more than 40%.

The presentation is for a general audience. No prior knowledge
is needed.

The talk is based on some recent works with Alexander Vardy
(UCSD) and Jehoshua Bruck (Caltech).