Oblivious communication channels and their capacity

Michael Langberg

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


Let C = {x1 ⋯ xN ⊂ {0; 1}n 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 Ae 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}n. 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 Ae 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.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)424-429
عدد الصفحات6
دوريةIEEE Transactions on Information Theory
مستوى الصوت54
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يناير 2008


أدرس بدقة موضوعات البحث “Oblivious communication channels and their capacity'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا