Stark Draper

Prof. Stark C. Draper

Department of Electrical & Computer Engineering

University of Toronto

Monday, April 19, 2004
4:30 - 6:00 PM
1311 EECS

Efficient Variable Length Channel Coding for Unknown Discrete Memoryless Channels

Abstract -

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.

Biosketch -

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.

return to Current CSPL Seminars