Arbitrarily varying channel explained

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.

style n uses of this channel can be described using a stochastic matrix style W ^{n:} X ^{n} x style S ^{n} → Y ^{n} , where style X is the input alphabet, style Y is the output alphabet, and style W ^{n} (y | x, s) is the probability over a given set of states style S , that the transmitted input style x = (x _{1,} \ldots, x _{n)} leads to the received output style y = (y _{1,} \ldots, y _{n)} . The state style s _{i} in set style S can vary arbitrarily at each time unit style 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

Capacity of deterministic AVCs

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

style R is an achievable rate for a deterministic AVC code if it is larger than style 0 , and if for every positive style \varepsilon and style \delta , and very large style n , length-style n block codes exist that satisfy the following equations: style (1)/(n) log N > R - \delta and \displaystyle max _{s \in S ^{n}} \bar{e}(s) \leq \varepsilon , where style N is the highest value in style Y and where style \bar{e}(s) is the average probability of error for a state sequence style s . The largest rate style R represents the capacity of the AVC, denoted by style c .

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

style 0 , because then the channel can transmit a guaranteed amount of data style \leq c without errors. So we start out with a theorem that shows when style c is positive in an AVC and the theorems discussed afterward will narrow down the range of style c for different circumstances.

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

• An AVC is symmetric if

\displaystyle \sum _{s} W(y|x, s)U(s|x') = \sum _{s} W(y|x', s)U(s|x) for every style (x, x', y,s) , where style x,x'\in X , style y \in Y , and style U(s|x) is a channel function style U: X → S .style X _{r} , style S _{r} , and style Y _{r} are all random variables in sets style X , style S , and style Y respectively.style P _{X _{r}} (x) is equal to the probability that the random variable style X _{r} is equal to style x .style P _{S _{r}} (s) is equal to the probability that the random variable style S _{r} is equal to style s .style P _{X _{r} S _{r} Y _{r}} is the combined probability mass function (pmf) of style P _{X _{r}} (x) , style P _{S _{r}} (s) , and style W(y|x,s) . style P _{X _{r} S _{r} Y _{r}} is defined formally as style P _{X _{r} S _{r} Y _{r}} (x,s,y) = P _{X _{r}} (x)P _{S _{r}} (s)W(y|x,s) .style H(X _{r)} is the entropy of style X _{r} .style H(X _{r|Y} _{r)} is equal to the average probability that style X _{r} will be a certain value based on all the values style Y _{r} could possibly be equal to.style I(X _{r} \land Y _{r)} is the mutual information of style X _{r} and style Y _{r} , and is equal to style H(X _{r)} - H(X _{r|Y} _{r)} .\displaystyle I(P) = min _{Y _{r}} I(X _{r} \land Y _{r)} , where the minimum is over all random variables style Y _{r} such that style X _{r} , style S _{r} , and style Y _{r} are distributed in the form of style P _{X _{r} S _{r} Y _{r}} .

Theorem 1:

style c > 0 if and only if the AVC is not symmetric. If style c > 0 , then \displaystyle c = max _{P} I(P) .

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

style I(P) is positive when the AVC is not symmetric, and then prove that style c = max _{P} I(P) , we will be able to prove Theorem 1. Assume style I(P) were equal to style 0 . From the definition of style I(P) , this would make style X _{r} and style Y _{r} independent random variables, for some style S _{r} , because this would mean that neither random variable's entropy would rely on the other random variable's value. By using equation style P _{X _{r} S _{r} Y _{r}} , (and remembering style P _{X _{r}} = P ,) we can get,\displaystyle P _{Y _{r}} (y) = \sum _{x\in} \sum _{s\in} P(x)P _{S _{r}} (s)W(y|x,s) style \equiv ( since style X _{r} and style Y _{r} are independent random variables, style W(y|x, s) = W'(y|s) for some style W') \displaystyle P _{Y _{r}} (y) = \sum _{x\in} \sum _{s\in} P(x)P _{S _{r}} (s)W'(y|s) style \equiv ( because only style P(x) depends on style x nowstyle ) \displaystyle P _{Y _{r}} (y) = \sum _{s\in} P _{S _{r}} (s)W'(y|s) \left[\sum _{x\in} P(x)\right] style \equiv ( because \displaystyle \sum _{x\in} P(x) = 1 ) \displaystyle P _{Y _{r}} (y) = \sum _{s\in} P _{S _{r}} (s)W'(y|s)

So now we have a probability distribution on

style Y _{r} that is independent of style X _{r} . So now the definition of a symmetric AVC can be rewritten as follows: \displaystyle \sum _{s} W'(y|s)P _{S _{r}} (s) = \sum _{s} W'(y|s)P _{S _{r}} (s) since style U(s|x) and style W(y|x, s) are both functions based on style x , they have been replaced with functions based on style s and style y only. As you can see, both sides are now equal to the style P _{Y _{r}} (y) we calculated earlier, so the AVC is indeed symmetric when style I(P) is equal to style 0 . Therefore, style 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

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

style \Gamma based on the equation \displaystyle g(x) = (1)/(n) \sum ^{n} _{i =1} g(x _{i)} , where style x \in X and style x = (x _{1,...,x} _{n)} .

- A state constraint

style Λ , based on the equation \displaystyle l(s) = (1)/(n) \sum ^{n} _{i =1} l(s _{i)} , where style s \in X and style s = (s _{1,...,s} _{n)} .

-

\displaystyle Λ _{0(P)} = min \sum _{x} P(x)l(s)

-

style I(P, Λ ) is very similar to style I(P) equation mentioned previously, \displaystyle I(P, Λ ) = min _{Y _{r}} I(X _{r} \land Y _{r)} , but now any state style s or style S _{r} in the equation must follow the style l(s) \leq Λ state restriction.

Assume

style g(x) is a given non-negative-valued function on style X and style l(s) is a given non-negative-valued function on style S and that the minimum values for both is style 0 . In the literature I have read on this subject, the exact definitions of both style g(x) and style l(s) (for one variable style x _{i} ,) is never described formally. The usefulness of the input constraint style \Gamma and the state constraint style Λ will be based on these equations.style R is now limited to codewords of format style x _{1,...,x} _{N} that satisfy style g(x _{i)} \leq \Gamma , and now the state style s is limited to all states that satisfy style l(s) \leq Λ . The largest rate is still considered the capacity of the AVC, and is now denoted as style c(\Gamma, Λ ) .

Lemma 1: Any codes where

style Λ is greater than style Λ _{0(P)} cannot be considered "good" codes, because those kinds of codes have a maximum average probability of error greater than or equal to style (N -1)/(2 N) - (1)/(n) (l ^{2} _{max})/(n( Λ - Λ ^{2} _{0 (P))}) , where style l _{max} is the maximum value of style l(s) . This isn't a good maximum average error probability because it is fairly large, style (N -1)/(2 N) is close to style (1)/(2) , and the other part of the equation will be very small since the style ( Λ - Λ _{0(P))} value is squared, and style Λ is set to be larger than style Λ _{0(P)} . Therefore, it would be very unlikely to receive a codeword without error. This is why the style Λ _{0(P)} condition is present in Theorem 2.

Theorem 2: Given a positive

style Λ and arbitrarily small style \alpha > 0 , style \beta > 0 , style \delta > 0 , for any block length style n \geq n _{0} and for any type style P with conditions style Λ _{0(P)} \geq Λ + \alpha and \displaystyle min _{x} P(x) \geq \beta , and where style P _{X _{r}} = P , there exists a code with codewords style x _{1,...,x} _{N} , each of type style P , that satisfy the following equations: style (1)/(n) log N > I(P, Λ ) - \delta , \displaystyle max _{l(s)} \bar{e}(s) \leq \exp( - n\gamma) , and where positive style n _{0} and style \gamma depend only on style \alpha , style \beta , style \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

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 W _{\zeta} (y|x) = \sum _{s} W(y|x, s)P _{S _{r}} (s)
style I(P, \zeta) is very similar to the style I(P) equation mentioned previously, \displaystyle I(P, \zeta) = min _{Y _{r}} I(X _{r} \land Y _{r)} , but now the pmf style P _{S _{r}} (s) is added to the equation, making the minimum of style I(P, \zeta) based a new form of style P _{X _{r} S _{r} Y _{r}} , where style W _{\zeta} (y|x) replaces style W(y|x, s) .

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

\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

• Binary symmetric channel
• Binary erasure channel
• Z-channel (information theory)
• Channel model
• Information theory
• Coding theory

References

• 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," https://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," https://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," https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2627&isnumber=155
• Lapidoth, A. and Narayan, P., "Reliable communication under channel uncertainty," https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=720535&isnumber=15554