Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2006 | Published
Book Section - Chapter Open

Oblivious channels

Abstract

Let C = {x_1,...,x_N} ⊂ {0, 1}^n be an [n, N] binary error correcting code (not necessarily linear). Let e ∈ {0, 1}^n be an error vector. A codeword X ∈ 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.

Additional Information

© 2006 IEEE. I would like to thank Sidharth Jaggi for several helpful discussions and comments on the oblivious channel model. Research supported in part by NSF grant CCF-0346991.

Attached Files

Published - 04036471.pdf

Files

04036471.pdf
Files (190.0 kB)
Name Size Download all
md5:86a28b28d8e5c2044daabfaf115adb5e
190.0 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 25, 2023