The Adaptive Zero-Error Capacity for Memory-less Channels with Noisy FeedbackDate: 2017-03-24 Add to Google Calendar
Location: Holmes 388
Speaker: Meysam Asadi, PhD Postdoctorate at the University of Illinois, Chicago
Shannon determined that the zero-capacity, of a point-to-point channel is positive if and only if there exists two inputs that are "non-confusable." Equivalently, it is non-zero if and only if, the independence number of its confusability graph is strictly greater than 1.
Shannon's condition for positive zero-error capacity is restrictive; that for positive zero-error capacity in the presence of perfect output feedback is less so. In the presence of noiseless feedback, Massey showed that it is possible to communicate at a non-zero rate with zero-error over a DMC with noiseless feedback if, and only if, there exists at least one channel output that is reachable fram some but not all the channel inputs. Such a channel output is called a "disprover." Not only does the existence of a disprover allow for positive rates, but Massey showed that with perfect feedback, the adaptive zero-error capacity of channels attains the small-error Shannon capacity C. Note that the adaptive zero-error capacity allows for the adaptive and variable-length code words rather than block codes. Here, we study the zero-error capacity of a DMC when the channel feedback is noisy rather than perfect.
We provide a lower bound on the adaptive zero-error capacity with noisy feedback and show that under certain conditions this lower bound attains the Shannon capacity.