Oblivious channels
Michael L. Langberg · 2006
Let C = {X1,...,XN} ⊂ {0, 1}nbe an [n, N] binary error correcting code (not necessarily linear). Let e isin {0, 1}nbe an error vector. A codeword X isin C is said to be disturbed by the error e if the closest codeword to X oplus e is no longer X. Let Aebe the subset of codewords in C that are disturbed by e. In this work we study the size of Aein random codes C (i.e. codes in which each codeword Xiis 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 |Ae| is strongly concentrated for a wide range of values of N and parepar. 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