Optimal Reliability over a DMC with Feedback via Deterministic Sequential Coding

Tara Javidi  

University of California, San Diego

Abstract

This talk considers the problem of variable-length coding over a discrete memoryless channel (DMC) with noiseless feedback.  We first show that the design of variable-length coding with feedback is a special case of active hypothesis testing where a decision maker is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the penalty of wrong declarations. 

In the second part of the talk, motivated by DeGroot's interpretation of information utility as the guiding design principle in active hypothesis testing, we introduce Extrinsic Jensen–Shannon (EJS) divergence as a surrogate measure of information. Relying on EJS as an information utility, a deterministic variable length coding scheme is proposed and is shown to achieve the optimal reliability function (also known as the error exponent). The proposed coding scheme has only one phase, in contrast to all previous coding schemes which required two different phases of operation to achieve the optimal error exponent. More importantly the proposed coding scheme's significantly better performance is investigated and verified in the non-asymptotic regimes. Time permitting; we consider special classes of binary memoryless channels where the above results can be extended further to a simple coding scheme in which the messages are partitioned to the most possible equally probable sets. 

This is joint work with Mohammad Naghshvar, Michele Wigger, and Ofer Shayevitz. 

Biography

Tara Javidi studied electrical engineering at Sharif University of Technology, Tehran, Iran from 1992 to 1996. She received the MS degrees in electrical engineering (systems), and in applied mathematics (stochastics) from the University of Michigan, Ann Arbor, in 1998 and 1999, respectively. She received her Ph.D. in electrical engineering and computer science from the University of Michigan, Ann Arbor, in 2002.

From 2002 to 2004, she was an assistant professor at the Electrical Engineering Department, University of Washington, Seattle. She joined University of California, San Diego, in 2005, where she is currently an associate professor of electrical and computer engineering.

Tara Javidi was a Barbour Scholar during 1999-2000 academic year and received an NSF CAREER Award in 2004. Her research interests are in communication networks, stochastic resource allocation, stochastic control theory, and wireless communications.