Arbitrarily varying channel – Wikipedia

An arbitrarily varying channel (AVC) is a communication channel model used in coding theory, and was first introduced by Blackwell, Breiman, and Thomasian. This particular channel has unknown parameters that can change over time and these changes may not have a uniform pattern during the transmission of a codeword.

${displaystyle textstyle n}$

uses of this channel can be described using a stochastic matrix

${displaystyle textstyle W^{n}:X^{n}times }$

${displaystyle textstyle S^{n}rightarrow Y^{n}}$

, where

${displaystyle textstyle X}$

is the input alphabet,

${displaystyle textstyle Y}$

is the output alphabet, and

${displaystyle textstyle W^{n}(y|x,s)}$

is the probability over a given set of states

${displaystyle textstyle S}$

, that the transmitted input

${displaystyle textstyle x=(x_{1},ldots ,x_{n})}$

leads to the received output

${displaystyle textstyle y=(y_{1},ldots ,y_{n})}$

. The state

${displaystyle textstyle s_{i}}$

in set

${displaystyle textstyle S}$

can vary arbitrarily at each time unit

${displaystyle textstyle i}$

. This channel was developed as an alternative to Shannon’s Binary Symmetric Channel (BSC), where the entire nature of the channel is known, to be more realistic to actual network channel situations.

Capacities and associated proofs[edit]

Capacity of deterministic AVCs[edit]

An AVC’s capacity can vary depending on the certain parameters.

${displaystyle textstyle R}$

is an achievable rate for a deterministic AVC code if it is larger than

${displaystyle textstyle 0}$

, and if for every positive

${displaystyle textstyle varepsilon }$

and

${displaystyle textstyle delta }$

, and very large

${displaystyle textstyle n}$

, length-

${displaystyle textstyle n}$

block codes exist that satisfy the following equations:

${displaystyle textstyle {frac {1}{n}}log N>R-delta }$

${displaystyle displaystyle max _{sin S^{n}}{bar {e}}(s)leq varepsilon }$

, where

${displaystyle textstyle N}$

is the highest value in

${displaystyle textstyle Y}$

and where

${displaystyle textstyle {bar {e}}(s)}$

is the average probability of error for a state sequence

${displaystyle textstyle s}$

. The largest rate

${displaystyle textstyle R}$

represents the capacity of the AVC, denoted by

${displaystyle textstyle c}$

.

As you can see, the only useful situations are when the capacity of the AVC is greater than

${displaystyle textstyle 0}$

, because then the channel can transmit a guaranteed amount of data

${displaystyle textstyle leq c}$

without errors. So we start out with a theorem that shows when

${displaystyle textstyle c}$

is positive in an AVC and the theorems discussed afterward will narrow down the range of

${displaystyle textstyle c}$

for different circumstances.

Before stating Theorem 1, a few definitions need to be addressed:

• An AVC is symmetric if
  ${displaystyle displaystyle sum _{sin S}W(y|x,s)U(s|x’)=sum _{sin S}W(y|x’,s)U(s|x)}$

  for every

  ${displaystyle textstyle (x,x’,y,s)}$

  , where

  ${displaystyle textstyle x,x’in X}$

  ,

  ${displaystyle textstyle yin Y}$

  , and

  ${displaystyle textstyle U(s|x)}$

  is a channel function

  ${displaystyle textstyle U:Xrightarrow S}$

  .

• 
  ${displaystyle textstyle X_{r}}$

  ,

  ${displaystyle textstyle S_{r}}$

  , and

  ${displaystyle textstyle Y_{r}}$

  are all random variables in sets

  ${displaystyle textstyle X}$

  ,

  ${displaystyle textstyle S}$

  , and

  ${displaystyle textstyle Y}$

  respectively.

• 
  ${displaystyle textstyle P_{X_{r}}(x)}$

  is equal to the probability that the random variable

  ${displaystyle textstyle X_{r}}$

  is equal to

  ${displaystyle textstyle x}$

  .

• 
  ${displaystyle textstyle P_{S_{r}}(s)}$

  is equal to the probability that the random variable

  ${displaystyle textstyle S_{r}}$

  is equal to

  ${displaystyle textstyle s}$

  .

• 
  ${displaystyle textstyle P_{X_{r}S_{r}Y_{r}}}$

  is the combined probability mass function (pmf) of

  ${displaystyle textstyle P_{X_{r}}(x)}$

  ,

  ${displaystyle textstyle P_{S_{r}}(s)}$

  , and

  ${displaystyle textstyle W(y|x,s)}$

  .

  ${displaystyle textstyle P_{X_{r}S_{r}Y_{r}}}$

  is defined formally as

  ${displaystyle textstyle P_{X_{r}S_{r}Y_{r}}(x,s,y)=P_{X_{r}}(x)P_{S_{r}}(s)W(y|x,s)}$

  .

• 
  ${displaystyle textstyle H(X_{r})}$

  is the entropy of

  ${displaystyle textstyle X_{r}}$

  .

• 
  ${displaystyle textstyle H(X_{r}|Y_{r})}$

  is equal to the average probability that

  ${displaystyle textstyle X_{r}}$

  will be a certain value based on all the values

  ${displaystyle textstyle Y_{r}}$

  could possibly be equal to.

• 
  ${displaystyle textstyle I(X_{r}land Y_{r})}$

  is the mutual information of

  ${displaystyle textstyle X_{r}}$

  and

  ${displaystyle textstyle Y_{r}}$

  , and is equal to

  ${displaystyle textstyle H(X_{r})-H(X_{r}|Y_{r})}$

  .

• 
  ${displaystyle displaystyle I(P)=min _{Y_{r}}I(X_{r}land Y_{r})}$

  , where the minimum is over all random variables

  ${displaystyle textstyle Y_{r}}$

  such that

  ${displaystyle textstyle X_{r}}$

  ,

  ${displaystyle textstyle S_{r}}$

  , and

  ${displaystyle textstyle Y_{r}}$

  are distributed in the form of

  ${displaystyle textstyle P_{X_{r}S_{r}Y_{r}}}$

  .

Theorem 1:

${displaystyle textstyle c>0}$

${displaystyle textstyle c>0}$

${displaystyle displaystyle c=max _{P}I(P)}$

.

Proof of 1st part for symmetry: If we can prove that

${displaystyle textstyle I(P)}$

is positive when the AVC is not symmetric, and then prove that

${displaystyle textstyle c=max _{P}I(P)}$

, we will be able to prove Theorem 1. Assume

${displaystyle textstyle I(P)}$

were equal to

${displaystyle textstyle 0}$

. From the definition of

${displaystyle textstyle I(P)}$

, this would make

${displaystyle textstyle X_{r}}$

and

${displaystyle textstyle Y_{r}}$

independent random variables, for some

${displaystyle textstyle S_{r}}$

, because this would mean that neither random variable’s entropy would rely on the other random variable’s value. By using equation

${displaystyle textstyle P_{X_{r}S_{r}Y_{r}}}$

, (and remembering

${displaystyle textstyle P_{X_{r}}=P}$

,) we can get,

${displaystyle displaystyle P_{Y_{r}}(y)=sum _{xin X}sum _{sin S}P(x)P_{S_{r}}(s)W(y|x,s)}$

${displaystyle textstyle equiv (}$

since

${displaystyle textstyle X_{r}}$

and

${displaystyle textstyle Y_{r}}$

are independent random variables,

${displaystyle textstyle W(y|x,s)=W'(y|s)}$

for some

${displaystyle textstyle W’)}$

${displaystyle displaystyle P_{Y_{r}}(y)=sum _{xin X}sum _{sin S}P(x)P_{S_{r}}(s)W'(y|s)}$

${displaystyle textstyle equiv (}$

because only

${displaystyle textstyle P(x)}$

depends on

${displaystyle textstyle x}$

now

${displaystyle textstyle )}$

${displaystyle displaystyle P_{Y_{r}}(y)=sum _{sin S}P_{S_{r}}(s)W'(y|s)left[sum _{xin X}P(x)right]}$

${displaystyle textstyle equiv (}$

because

${displaystyle displaystyle sum _{xin X}P(x)=1)}$

${displaystyle displaystyle P_{Y_{r}}(y)=sum _{sin S}P_{S_{r}}(s)W'(y|s)}$

So now we have a probability distribution on

${displaystyle textstyle Y_{r}}$

that is independent of

${displaystyle textstyle X_{r}}$

. So now the definition of a symmetric AVC can be rewritten as follows:

${displaystyle displaystyle sum _{sin S}W'(y|s)P_{S_{r}}(s)=sum _{sin S}W'(y|s)P_{S_{r}}(s)}$

since

${displaystyle textstyle U(s|x)}$

and

${displaystyle textstyle W(y|x,s)}$

are both functions based on

${displaystyle textstyle x}$

, they have been replaced with functions based on

${displaystyle textstyle s}$

and

${displaystyle textstyle y}$

only. As you can see, both sides are now equal to the

${displaystyle textstyle P_{Y_{r}}(y)}$

we calculated earlier, so the AVC is indeed symmetric when

${displaystyle textstyle I(P)}$

is equal to

${displaystyle textstyle 0}$

. Therefore,

${displaystyle textstyle I(P)}$

can only be positive if the AVC is not symmetric.

Proof of second part for capacity: See the paper “The capacity of the arbitrarily varying channel revisited: positivity, constraints,” referenced below for full proof.

Capacity of AVCs with input and state constraints[edit]

The next theorem will deal with the capacity for AVCs with input and/or state constraints. These constraints help to decrease the very large range of possibilities for transmission and error on an AVC, making it a bit easier to see how the AVC behaves.

Before we go on to Theorem 2, we need to define a few definitions and lemmas:

For such AVCs, there exists:

– An input constraint

${displaystyle textstyle Gamma }$

based on the equation

${displaystyle displaystyle g(x)={frac {1}{n}}sum _{i=1}^{n}g(x_{i})}$

, where

${displaystyle textstyle xin X}$

and

${displaystyle textstyle x=(x_{1},dots ,x_{n})}$

.

– A state constraint

${displaystyle textstyle Lambda }$

, based on the equation

${displaystyle displaystyle l(s)={frac {1}{n}}sum _{i=1}^{n}l(s_{i})}$

, where

${displaystyle textstyle sin X}$

and

${displaystyle textstyle s=(s_{1},dots ,s_{n})}$

.

–

${displaystyle displaystyle Lambda _{0}(P)=min sum _{xin X,sin S}P(x)l(s)}$

–

${displaystyle textstyle I(P,Lambda )}$

is very similar to

${displaystyle textstyle I(P)}$

equation mentioned previously,

${displaystyle displaystyle I(P,Lambda )=min _{Y_{r}}I(X_{r}land Y_{r})}$

, but now any state

${displaystyle textstyle s}$

or

${displaystyle textstyle S_{r}}$

in the equation must follow the

${displaystyle textstyle l(s)leq Lambda }$

state restriction.

Assume

${displaystyle textstyle g(x)}$

is a given non-negative-valued function on

${displaystyle textstyle X}$

and

${displaystyle textstyle l(s)}$

is a given non-negative-valued function on

${displaystyle textstyle S}$

and that the minimum values for both is

${displaystyle textstyle 0}$

. In the literature I have read on this subject, the exact definitions of both

${displaystyle textstyle g(x)}$

and

${displaystyle textstyle l(s)}$

(for one variable

${displaystyle textstyle x_{i}}$

,) is never described formally. The usefulness of the input constraint

${displaystyle textstyle Gamma }$

and the state constraint

${displaystyle textstyle Lambda }$

will be based on these equations.

For AVCs with input and/or state constraints, the rate

${displaystyle textstyle R}$

is now limited to codewords of format

${displaystyle textstyle x_{1},dots ,x_{N}}$

that satisfy

${displaystyle textstyle g(x_{i})leq Gamma }$

, and now the state

${displaystyle textstyle s}$

is limited to all states that satisfy

${displaystyle textstyle l(s)leq Lambda }$

. The largest rate is still considered the capacity of the AVC, and is now denoted as

${displaystyle textstyle c(Gamma ,Lambda )}$

.

Lemma 1: Any codes where

${displaystyle textstyle Lambda }$

is greater than

${displaystyle textstyle Lambda _{0}(P)}$

cannot be considered “good” codes, because those kinds of codes have a maximum average probability of error greater than or equal to

${displaystyle textstyle {frac {N-1}{2N}}-{frac {1}{n}}{frac {l_{max}^{2}}{n(Lambda -Lambda _{0}(P))^{2}}}}$

, where

${displaystyle textstyle l_{max}}$

is the maximum value of

${displaystyle textstyle l(s)}$

. This isn’t a good maximum average error probability because it is fairly large,

${displaystyle textstyle {frac {N-1}{2N}}}$

is close to

${displaystyle textstyle {frac {1}{2}}}$

, and the other part of the equation will be very small since the

${displaystyle textstyle (Lambda -Lambda _{0}(P))}$

value is squared, and

${displaystyle textstyle Lambda }$

is set to be larger than

${displaystyle textstyle Lambda _{0}(P)}$

. Therefore, it would be very unlikely to receive a codeword without error. This is why the

${displaystyle textstyle Lambda _{0}(P)}$

condition is present in Theorem 2.

Theorem 2: Given a positive

${displaystyle textstyle Lambda }$

and arbitrarily small

${displaystyle textstyle alpha >0}$

${displaystyle textstyle beta >0}$

${displaystyle textstyle delta >0}$

${displaystyle textstyle ngeq n_{0}}$

and for any type

${displaystyle textstyle P}$

with conditions

${displaystyle textstyle Lambda _{0}(P)geq Lambda +alpha }$

and

${displaystyle displaystyle min _{xin X}P(x)geq beta }$

, and where

${displaystyle textstyle P_{X_{r}}=P}$

, there exists a code with codewords

${displaystyle textstyle x_{1},dots ,x_{N}}$

, each of type

${displaystyle textstyle P}$

, that satisfy the following equations:

${displaystyle textstyle {frac {1}{n}}log N>I(P,Lambda )-delta }$

${displaystyle displaystyle max _{l(s)leq Lambda }{bar {e}}(s)leq exp(-ngamma )}$

, and where positive

${displaystyle textstyle n_{0}}$

and

${displaystyle textstyle gamma }$

depend only on

${displaystyle textstyle alpha }$

,

${displaystyle textstyle beta }$

,

${displaystyle textstyle delta }$

, and the given AVC.

Proof of Theorem 2: See the paper “The capacity of the arbitrarily varying channel revisited: positivity, constraints,” referenced below for full proof.

Capacity of randomized AVCs[edit]

The next theorem will be for AVCs with randomized code. For such AVCs the code is a random variable with values from a family of length-n block codes, and these codes are not allowed to depend/rely on the actual value of the codeword. These codes have the same maximum and average error probability value for any channel because of its random nature. These types of codes also help to make certain properties of the AVC more clear.

Before we go on to Theorem 3, we need to define a couple important terms first:

${displaystyle displaystyle W_{zeta }(y|x)=sum _{sin S}W(y|x,s)P_{S_{r}}(s)}$

${displaystyle textstyle I(P,zeta )}$

is very similar to the

${displaystyle textstyle I(P)}$

equation mentioned previously,

${displaystyle displaystyle I(P,zeta )=min _{Y_{r}}I(X_{r}land Y_{r})}$

, but now the pmf

${displaystyle textstyle P_{S_{r}}(s)}$

is added to the equation, making the minimum of

${displaystyle textstyle I(P,zeta )}$

based a new form of

${displaystyle textstyle P_{X_{r}S_{r}Y_{r}}}$

, where

${displaystyle textstyle W_{zeta }(y|x)}$

replaces

${displaystyle textstyle W(y|x,s)}$

.

Theorem 3: The capacity for randomized codes of the AVC is

${displaystyle displaystyle c=max_{P}I(P,zeta )}$

.

Proof of Theorem 3: See paper “The Capacities of Certain Channel Classes Under Random Coding” referenced below for full proof.

See also[edit]

References[edit]

• Ahlswede, Rudolf and Blinovsky, Vladimir, “Classical Capacity of Classical-Quantum Arbitrarily Varying Channels,” https://ieeexplore.ieee.org/document/4069128
• Blackwell, David, Breiman, Leo, and Thomasian, A. J., “The Capacities of Certain Channel Classes Under Random Coding,” https://www.jstor.org/stable/2237566
• Csiszar, I. and Narayan, P., “Arbitrarily varying channels with constrained inputs and states,” http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2598&isnumber=154
• Csiszar, I. and Narayan, P., “Capacity and Decoding Rules for Classes of Arbitrarily Varying Channels,” http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=32153&isnumber=139
• Csiszar, I. and Narayan, P., “The capacity of the arbitrarily varying channel revisited: positivity, constraints,” http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2627&isnumber=155
• Lapidoth, A. and Narayan, P., “Reliable communication under channel uncertainty,” http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=720535&isnumber=15554