Achieving the Empirical Capacity Using Feedback Part I: Memoryless Additive Models

Details Achieving the Empirical Capacity Using Feedback Part I: Memoryless Additive Models Achieving the Empirical Capacity Using Feedback Part I: Memoryless Additive Models

2008-08-29

arxiv.org/abs/0808.4135v2

Computer Science

Information Theory

Submitted to the IEEE Transactions on Information Theory

Scientific paper

We address the problem of universal communications over an unknown channel with an instantaneous noiseless feedback, and show how rates corresponding to the empirical behavior of the channel can be attained, although no rate can be guaranteed in advance. First, we consider a discrete modulo-additive channel with alphabet $\mathcal{X}$, where the noise sequence $Z^n$ is arbitrary and unknown and may causally depend on the transmitted and received sequences and on the encoder's message, possibly in an adversarial fashion. Although the classical capacity of this channel is zero, we show that rates approaching the empirical capacity $\log|\mathcal{X}|-H_{emp}(Z^n)$ can be universally attained, where $H_{emp}(Z^n)$ is the empirical entropy of $Z^n$. For the more general setting where the channel can map its input to an output in an arbitrary unknown fashion subject only to causality, we model the empirical channel actions as the modulo-addition of a realized noise sequence, and show that the same result applies if common randomness is available. The results are proved constructively, by providing a simple sequential transmission scheme approaching the empirical capacity. In part II of this work we demonstrate how even higher rates can be attained by using more elaborate models for channel actions, and by utilizing possible empirical dependencies in its behavior.

Affiliated with

Also associated with

No associations

Rating

Achieving the Empirical Capacity Using Feedback Part I: Memoryless Additive Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Achieving the Empirical Capacity Using Feedback Part I: Memoryless Additive Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Achieving the Empirical Capacity Using Feedback Part I: Memoryless Additive Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544334