Dror Baron - Universality in channel coding and distributed compression

Feedback for universal communication

Information theory has characterized the limiting performance of a variety of communication systems in the asymptotic regime. Unfortunately, when a finite amount of data must be communicated, it is not clear what resources are needed. In a wireless world, channel impairments are always possible, and instead of reliable communication, a more realistic goal might be to communicate a packet of k bits using minimal resources, subject to a reasonably small probability of error. Therefore, we view the block length n and probability epsilon of block error as a constraint. Our goal is to understand how quickly communication systems can approach the performance limits of information theory. Universality: When the source and channel statistics are unknown, we use a block-sequential scheme that relies on a trickle of feedback from the decoder to the encoder. This feedback helps the encoder to estimate the statistics and use variable rate coding. We have provided details of a feedback scheme whose penalty (redundancy or gap to capacity) is O(1/sqrt(n)). Combining the observation that LDPC codes also approach the limiting performance at this rate, our universal feedback scheme is near-optimal. The plot thickens when channels with transitions between iid segments are considered. In this case, the penalty for universality increases to O(n^2/3) bits. The problem is that when the transition works against us and the channel becomes more noisy, we may lose an entire packet. To reduce this problem, packet lengths are increased very slowly, in contrast to the previous feedback scheme where block lengths increase rapidly.
Last updated December 2008