Efficient Variable Length Channel Coding for Unknown Discrete MemorylessChannels

In this talk we present a coding strategy for the reliable communication
of a message selected from a codebook of fixed size, in a variable number
of channel uses, over an unknown discrete memoryless channel. At each time
the decoder tests the received sequence and decides if it can decode. If
it can, it sends an acknowledgment to the transmitter, which then stops
transmitting. By choosing the size of the codebook large enough, with high
probability the rate that is realized by the strategy can be made to
approach arbitrarily closely the mutual information between the
user-chosen input distribution and the induced channel output
distribution. Without additional knowledge, the input distribution cannot
be guaranteed to be set equal to the capacity-achieving input
distribution.

The strategy presented can be considered as a generalization to arbitrary
unknown discrete memoryless channels of earlier variable length coding
schemes, such as digital fountain codes for erasure channels, and a coding
strategy for binary symmetric channels presented by Tchamkerten and
Telatar. This work is also closely related to the common broadcasting
framework developed independently by N. Shulman in his recent
dissertation.

Given time, we will comment on work on building practical encoders and
decoders.

Joint work with Frank Kschischang and Brendan Frey.
Stark Draper holds the Information Processing Laboratory
Post-Doctoral Fellowship at the University of Toronto. He did his graduate work at MIT and undergraduate work at Stanford. He has held industrial positions at a variety of places, including Arraycomm and Draper Laboratory. Among several awards, he has received the MIT Carlton E.
Tucker Teaching Award, an Intel Graduate Fellowship, and a Fulbright Fellowship. His research interests and activities span several aspects of signal processing, communications, estimation, information theory, queuing, and networking.