Fun with porosity and aliens in channel coding

Abstract:

Beginning with Lempel and Ziv's seminal work in 1977/78, there has been tremendous interest in universal schemes in information theory --- that is, schemes that simultaneously achieve close-to-optimal performance for a wide variety of system models. Two extreme forms of universality in the channel coding setting are examined. First, results analogous to those of Lempel and Ziv's are established for modulo-additive noise sequences; just as Lempel and Ziv consider source coding universality with respect to arbitrary individual source sequences, one may request channel coding universality with respect to arbitrary individual ``noise'' sequences. Second, one may consider channel coding universality not only with respect to the channel model, but also with respect to the codebook employed (e.g. "communicating with aliens"). It is shown that if a random block code is used to communicate under the capacity of a discrete memoryless channel, one may decode the "pattern" of the source message, in the sense introduced by Orlitsky et al., without knowledge of the codewords, block-length, rate, or channel model.

Presentation Slides

Biography:Vinith Misra is currently pursuing a PhD in Stanford University's Department of Electrical Engineering, under the joint support of the National Defense Science and Engineering Graduate Fellowship and  the Stanford Graduate Fellowship.  As an undergraduate, he obtained S.B. and M.Eng. degrees in electrical engineering from MIT, where he was awarded the David Adler memorial prize for best EE M.Eng thesis. His research interests include information theory, signal processing, and circuit design, with a particular bias towards extracting theoretical problems from practical systems.