Download

Abstract

The capacity for the discrete memoryless arbitrarily varying channel (AVC) with cost constraints on the jammer is studied using deterministic list codes under both the maximal and average probability of error criteria. For a cost function $l(\cdot)$ on the state set and constraint $\Lambda$ on the jammer it is shown that under maximal error a rate $\max_{P(x)} \min_{W \in \wdep(P,\Lambda)} \mi{X}{Y} - O(L^{-1})$ is achievable with list codes of list size $L$, where $\wdep(P,\Lambda)$ is a subset of the row-convex closure of the AVC. For average error, an integer $\lsym(\Lambda)$, called the \textit{symmetrizability}, is defined. It is shown that any rate below $C_r(\Lambda)$ is achievable under average error using list codes of list size $L > \lsym$, where $C_r(\Lambda)$ is the randomized coding capacity of the AVC. An example is given for a class of discrete additive AVCs.

Notes

The technical report contains an error in the statement and proof for coding under maximal error. Please see the most recent version or the version posted to ArXiV.

Submitted to the IEEE Transactions on Information Theory, Sept. 2007

Links

Reference

A.D. Sarwate and M. Gastpar, Deterministic list codes for state-constrained arbitrarily varying channels, submitted to IEEE Transactions on Information Theory, ArXiV cs.IT/0701146, http://arxiv.org/abs/cs.IT/0701146.

A.D. Sarwate and M. Gastpar, Deterministic list codes for state-constrained arbitrarily varying channels, Technical Memorandum UCB/EECS-2007-6, EECS Department, University of California, Berkeley, January 8, 2007.

BibTeX

@UNPUBLISHED(SarwateG:07listavc,
   AUTHOR = "A.~D.~Sarwate and M. Gastpar",
   TITLE = "Deterministic list codes for state-constrained arbitrarily varying channels",
   NOTE = "ArXiV cs.IT/0701146",
   URL = "http://arxiv.org/abs/cs.IT/0701146",
   MONTH = "September,"
   YEAR = "2007"
)
   

@techreport{SarwateG:07eecs6,
   Author = {A.~D.~Sarwate and M. Gastpar},
   Ttitle = {Deterministic list codes for state-constrained arbitrarily varying channels},
   Institution = {EECS Department, University of California, Berkeley},
   Year = {2007},
   Month = {January 8},
   URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-6.html},
   Number = {UCB/EECS-2007-6}
}