Oblivious communication channels and their capacity

Let C = {x₁ ⋯ x_N ⊂ {0; 1}ⁿ be an [n;N] binary error correcting code (not necessarily linear). Let e ∈ {1} be an error vector. A codeword x ∈ C is said to be disturbed by the error e if the closest code-word 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 in random codes C (i.e., codes in which each codeword x is chosen uniformly and independently at random from {0, 1}ⁿ. Using recent results of Vu [Random Structures and Algorithms, vol. 20, no. 3, pp. 262-316, 2002] 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 code-word x. A family of channels W is said to be oblivious if every memberW of the family is oblivious. In thiswork, we define oblivious and partially oblivious families of (not necessarily memoryless) channels and analyze their capacity. When considering the capacity of a family of channelsW, one must address the design of error correcting codes which allow communication under the uncertainty of which channel W ∈ W is actually used. The oblivious channels we define have connections to Arbitrarily Varying Channels with state constraints.