Title: Optimal Reliability over a DMC with Feedback via Deterministic Sequential Coding
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. Time permiting, we consider a 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.