The Rate Loss of Single-Letter Characterization: The "Dirty" Multiple Access Channel

Simple item page
dc.creatorPhilosof, Tal
dc.creatorZamir, Ram
dc.date2008-03-07
dc.date2008-03-27
dc.date.accessioned2026-07-07T09:28:37Z
dc.date.available2026-07-07T09:28:37Z
dc.descriptionFor general memoryless systems, the typical information theoretic solution - when exists - has a "single-letter" form. This reflects the fact that optimum performance can be approached by a random code (or a random binning scheme), generated using independent and identically distributed copies of some single-letter distribution. Is that the form of the solution of any (information theoretic) problem? In fact, some counter examples are known. The most famous is the "two help one" problem: Korner and Marton showed that if we want to decode the modulo-two sum of two binary sources from their independent encodings, then linear coding is better than random coding. In this paper we provide another counter example, the "doubly-dirty" multiple access channel (MAC). Like the Korner-Marton problem, this is a multi-terminal scenario where side information is distributed among several terminals; each transmitter knows part of the channel interference but the receiver is not aware of any part of it. We give an explicit solution for the capacity region of a binary version of the doubly-dirty MAC, demonstrate how the capacity region can be approached using a linear coding scheme, and prove that the "best known single-letter region" is strictly contained in it. We also state a conjecture regarding a similar rate loss of single letter characterization in the Gaussian case.
dc.description23 pages, 5 figures
dc.identifierhttps://arxiv.org/abs/0803.1120
dc.identifierhttp://arxiv.org/abs/0803.1120
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/157489
dc.subjectInformation Theory
dc.subjectF.2.2; I.2.7
dc.titleThe Rate Loss of Single-Letter Characterization: The "Dirty" Multiple Access Channel
dc.typetext

Files

Collections

arXiv