Oblivious channels

Details Oblivious channels Oblivious channels

2006-01-10

arxiv.org/abs/cs/0601041v1

Computer Science

Information Theory

Submitted to the IEEE International Symposium on Information Theory (ISIT) 2006

Scientific paper

Let C = {x_1,...,x_N} \subset {0,1}^n be an [n,N] binary error correcting code (not necessarily linear). Let e \in {0,1}^n be an error vector. A codeword x in C is said to be "disturbed" by the error e if the closest codeword to x + e is no longer x. Let A_e be the subset of codewords in C that are disturbed by e. In this work we study the size of A_e in random codes C (i.e. codes in which each codeword x_i is chosen uniformly and independently at random from {0,1}^n). Using recent results of Vu [Random Structures and Algorithms 20(3)] on the concentration of non-Lipschitz functions, we show that |A_e| is strongly concentrated for a wide range of values of N and ||e||. We apply this result in the study of communication channels we refer to as "oblivious". Roughly speaking, a channel W(y|x) is said to be oblivious if the error distribution imposed by the channel is independent of the transmitted codeword x. For example, the well studied Binary Symmetric Channel is an oblivious channel. In this work, we define oblivious and partially oblivious channels and present lower bounds on their capacity. The oblivious channels we define have connections to Arbitrarily Varying Channels with state constraints.

Affiliated with

Also associated with

No associations

Rating

Oblivious channels 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 Oblivious channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Oblivious channels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-214243