Dror Baron -
Universality in channel coding and distributed compression
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.
-
For distributed source coding, when the source statistics are
known, the Slepian-Wolf limit can be approached with redundancy
rate O(1/sqrt(n)).
When source statistics are unknown, a linked encoder
setup sometimes provides O(1/sqrt(n)) redundancy rate.
Unfortunately, the redundancy is sometimes larger.
D. Baron,
M. A. Khojastepour,
and R. G. Baraniuk,
"Redundancy Rates of Slepian-Wolf Coding,"
Proceedings of the 42d Allerton Conference on Communication,
Control, and Computing,
Monticello, IL, September 2004
(pdf).
We have also considered non-asymptotic Slepian-Wolf coding
in different areas of the rate region. The
non-asymptotic rate region is a translated version of the
regular Slepian-Wolf region.
S. Sarvotham,
D. Baron,
and R. G. Baraniuk,
"Non-Asymptotic Performance of Symmetric Slepian-Wolf Coding,"
Proceedings of 39th Annual Conference on Information Sciences and
Systems (CISS2005), Baltimore, MD, March 2005
(pdf).
-
For channel coding with known statistics, we have again shown
that the capacity C can be approached using a gap to
capacity (rates below capacity) that is proportional to
O(1/sqrt(n)).
D. Baron,
M. A. Khojastepour,
and R. G. Baraniuk,
"How Quickly Can We Approach Channel Capacity?,"
Proceedings of the 38th Asilomar Conference on Signals, Systems, and
Computers,
Pacific Grove, CA, November 2004
(pdf).
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.
-
S. Sarvotham,
D. Baron,
and R. G. Baraniuk,
"Variable-Rate Coding with Feedback for Universal Communication Systems,"
Proceedings of the 43d Allerton Conference on Communication,
Control, and Computing,
Monticello, IL, September 2005
(pdf).
-
S. Sarvotham,
D. Baron,
and R. G. Baraniuk,
"Variable-Rate Universal Slepian-Wolf Coding with Feedback,"
Proceedings of the 39th Asilomar Conference on Signals, Systems, and
Computers,
Pacific Grove, CA, November 2005
(pdf).
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.
-
D. Baron,
S. Sarvotham,
and R. G. Baraniuk,
"Coding vs. Packet Retransmission over Noisy Channels,"
Proceedings of 40th Annual Conference on Information Sciences and
Systems (CISS2006), Princeton, NJ, March 2006
(pdf).
Last updated December 2008