Deterministic list codes for state-constrained arbitrarily varying channels

Anand D. Sarwate and Michael Gastpar

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-6
January 8, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-6.pdf

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, the achievable rates are upper bounded by the random coding capacity $C_r(\Lambda)$. For maximal error, the rate $R = C_r(\Lambda) - \epsilon$ is achievable using list codes with list size $O(\epsilon^{-1})$. 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$. An example is given for a class of discrete additive AVCs.


BibTeX citation:

@techreport{Sarwate:EECS-2007-6,
    Author = {Sarwate, Anand D. and Gastpar, Michael},
    Title = {Deterministic list codes for state-constrained arbitrarily varying channels},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Jan},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-6.html},
    Number = {UCB/EECS-2007-6},
    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, the achievable rates are upper bounded by the random coding capacity $C_r(\Lambda)$.  For maximal error, the rate $R = C_r(\Lambda) - \epsilon$ is achievable using list codes with list size $O(\epsilon^{-1})$.  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$.  An example is given for a class of discrete additive AVCs.}
}

EndNote citation:

%0 Report
%A Sarwate, Anand D.
%A Gastpar, Michael
%T Deterministic list codes for state-constrained arbitrarily varying channels
%I EECS Department, University of California, Berkeley
%D 2007
%8 January 8
%@ UCB/EECS-2007-6
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-6.html
%F Sarwate:EECS-2007-6