Oblivious Communication Channels and Their Capacity

DOI10.1109/TIT.2007.911217zbMATH Open1304.94018arXivcs/0601041OpenAlexW2139194398MaRDI QIDQ3604442FDOQ3604442

Authors: Michael Langberg 

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/cs/0601041

Recommendations

• Elimination of correlation in random codes for arbitrarily varying channels
• On error exponents for arbitrarily varying channels
• Capacity and decoding rules for classes of arbitrarily varying channels
• Optimal rate code constructions for computationally simple channels
• Localized random and arbitrary errors in the light of arbitrarily varying channel theory

zbMATH Keywords

capacitychannel codingArbitrarily varying channelschannel uncertainty

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Channel models (including quantum) in information and communication theory (94A40)

Cited In (3)

• Codes for detection of limited view algebraic tampering
• Detection of algebraic manipulation in the presence of leakage
• Determining Optimal Rates for Communication for Omniscience

This page was built for publication: Oblivious Communication Channels and Their Capacity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604442)