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
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2008

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Oblivious communication channels and their capacity'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי