en>Omnipaedista: standardized punctuation

2014-07-29T14:43:35Z

standardized punctuation

en>Kvng: reorder paragraphs. link improvements. bait maximum time interval error.

2012-05-24T17:38:53Z

reorder paragraphs. link improvements. bait maximum time interval error.

New page

{{Refimprove|date=January 2012}}
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 [[Communication channel|channel]] has unknown parameters that can change over time and these changes may not have a uniform pattern during the transmission of a [[codeword]]. <math>\textstyle n</math> uses of this [[Channel model|channel]] can be described using a [[stochastic matrix]] <math>\textstyle W^n: X^n \times</math> <math>\textstyle S^n \rightarrow Y^n</math>, where <math>\textstyle X</math> is the input alphabet, <math>\textstyle Y</math> is the output alphabet, and <math>\textstyle W^n (y | x, s)</math> is the probability over a given set of states <math>\textstyle S</math>, that the transmitted input <math>\textstyle x = (x_1, \ldots, x_n)</math> leads to the received output <math>\textstyle y = (y_1, \ldots, y_n)</math>. The state <math>\textstyle s_i</math> in set <math>\textstyle S</math> can vary arbitrarily at each time unit <math>\textstyle i</math>. This [[Channel model|channel]] was developed as an alternative to [[Claude Shannon|Shannon's]] [[Binary symmetric channel|Binary Symmetric Channel]] (BSC), where the entire nature of the [[Channel model|channel]] is known, to be more realistic to actual [[Communication channel|network channel]] situations.

==Capacities and associated proofs==

===Capacity of deterministic AVCs===
An AVC's [[Channel capacity|capacity]] can vary depending on the certain parameters.

<math>\textstyle R</math> is an achievable [[Information theory#Rate|rate]] for a deterministic AVC [[Channel coding|code]] if it is larger than <math>\textstyle 0</math>, and if for every positive <math>\textstyle \varepsilon</math> and <math>\textstyle \delta</math>, and very large <math>\textstyle n</math>, length-<math>\textstyle n</math> [[block code]]s exist that satisfy the following equations: <math>\textstyle \frac{1}{n}\log N > R - \delta</math> and <math>\displaystyle \max_{s \in S^n} \bar{e}(s) \leq \varepsilon</math>, where <math>\textstyle N</math> is the highest value in <math>\textstyle Y</math> and where <math>\textstyle \bar{e}(s)</math> is the average probability of error for a state sequence <math>\textstyle s</math>. The largest [[Information theory#Rate|rate]] <math>\textstyle R</math> represents the [[Channel capacity|capacity]] of the AVC, denoted by <math>\textstyle c</math>.

As you can see, the only useful situations are when the [[Channel capacity|capacity]] of the AVC is greater than <math>\textstyle 0</math>, because then the [[Channel model|channel]] can transmit a guaranteed amount of data <math>\textstyle \leq c</math> without errors. So we start out with a [[theorem]] that shows when <math>\textstyle c</math> is positive in a AVC and the [[theorem]]s discussed afterward will narrow down the [[Range (mathematics)|range]] of <math>\textstyle c</math> for different circumstances.

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

* An AVC is ''symmetric'' if <math>\displaystyle \sum_{s \in S}W(y|x, s)U(s|x') = \sum_{s \in S}W(y|x', s)U(s|x)</math> for every <math>\textstyle (x, x', y,s)</math>, where <math>\textstyle x,x'\in X</math>, <math>\textstyle y \in Y</math>, and <math>\textstyle U(s|x)</math> is a channel function <math>\textstyle U: X \rightarrow S</math>.
* <math>\textstyle X_r</math>, <math>\textstyle S_r</math>, and <math>\textstyle Y_r</math> are all [[random variable]]s in sets <math>\textstyle X</math>, <math>\textstyle S</math>, and <math>\textstyle Y</math> respectively.
* <math>\textstyle P_{X_r}(x)</math> is equal to the probability that the [[random variable]] <math>\textstyle X_r</math> is equal to <math>\textstyle x</math>.
* <math>\textstyle P_{S_r}(s)</math> is equal to the probability that the [[random variable]] <math>\textstyle S_r</math> is equal to <math>\textstyle s</math>.
* <math>\textstyle P_{X_{r}S_{r}Y_{r}}</math> is the combined [[probability mass function]] (pmf) of <math>\textstyle P_{X_r}(x)</math>, <math>\textstyle P_{S_r}(s)</math>, and <math>\textstyle W(y|x,s)</math>. <math>\textstyle P_{X_{r}S_{r}Y_{r}}</math> is defined formally as <math>\textstyle P_{X_{r}S_{r}Y_{r}}(x,s,y) = P_{X_r}(x)P_{S_r}(s)W(y|x,s)</math>.
* <math>\textstyle H(X_r)</math> is the [[Information entropy|entropy]] of <math>\textstyle X_r</math>.
* <math>\textstyle H(X_r|Y_r)</math> is equal to the average probability that <math>\textstyle X_r</math> will be a certain value based on all the values <math>\textstyle Y_r</math> could possibly be equal to.
* <math>\textstyle I(X_r \land Y_r)</math> is the [[Conditional entropy|mutual information]] of <math>\textstyle X_r</math> and <math>\textstyle Y_r</math>, and is equal to <math>\textstyle H(X_r) - H(X_r|Y_r)</math>.
* <math>\displaystyle I(P) = \min_{Y_r} I(X_r \land Y_r)</math>, where the minimum is over all random variables <math>\textstyle Y_r</math> such that <math>\textstyle X_r</math>, <math>\textstyle S_r</math>, and <math>\textstyle Y_r</math> are distributed in the form of <math>\textstyle P_{X_{r}S_{r}Y_{r}}</math>.

'''Theorem 1:''' <math>\textstyle c > 0</math> if and only if the AVC is not symmetric. If <math>\textstyle c > 0</math>, then <math>\displaystyle c = \max_P I(P)</math>.

''Proof of 1st part for symmetry:'' If we can prove that <math>\textstyle I(P)</math> is positive when the AVC is not symmetric, and then prove that <math>\textstyle c = \max_P I(P)</math>, we will be able to prove Theorem 1. Assume <math>\textstyle I(P)</math> were equal to <math>\textstyle 0</math>. From the definition of <math>\textstyle I(P)</math>, this would make <math>\textstyle X_r</math> and <math>\textstyle Y_r</math> [[Independence (probability theory)|independent]] [[random variable]]s, for some <math>\textstyle S_r</math>, because this would mean that neither [[random variable]]'s [[Information entropy|entropy]] would rely on the other [[random variable]]'s value. By using equation <math>\textstyle P_{X_{r}S_{r}Y_{r}}</math>, (and remembering <math>\textstyle P_{X_r} = P</math>,) we can get,

:<math>\displaystyle P_{Y_r}(y) = \sum_{x\in X} \sum_{s\in S} P(x)P_{S_r}(s)W(y|x,s)</math>
:<math>\textstyle \equiv (</math>since <math>\textstyle X_r</math> and <math>\textstyle Y_r</math> are [[Independence (probability theory)|independent]] [[random variable]]s, <math>\textstyle W(y|x, s) = W'(y|s)</math> for some <math>\textstyle W')</math>
:<math>\displaystyle P_{Y_r}(y) = \sum_{x\in X} \sum_{s\in S} P(x)P_{S_r}(s)W'(y|s)</math>
:<math>\textstyle \equiv (</math>because only <math>\textstyle P(x)</math> depends on <math>\textstyle x</math> now<math>\textstyle )</math>
:<math>\displaystyle P_{Y_r}(y) = \sum_{s\in S} P_{S_r}(s)W'(y|s) \left[\sum_{x\in X} P(x)\right]</math>
:<math>\textstyle \equiv (</math>because <math>\displaystyle \sum_{x\in X} P(x) = 1)</math>
:<math>\displaystyle P_{Y_r}(y) = \sum_{s\in S} P_{S_r}(s)W'(y|s)</math>

So now we have a [[probability distribution]] on <math>\textstyle Y_r</math> that is [[Independence (probability theory)|independent]] of <math>\textstyle X_r</math>. So now the definition of a symmetric AVC can be rewritten as follows: <math>\displaystyle \sum_{s \in S}W'(y|s)P_{S_r}(s) = \sum_{s \in S}W'(y|s)P_{S_r}(s)</math> since <math>\textstyle U(s|x)</math> and <math>\textstyle W(y|x, s)</math> are both functions based on <math>\textstyle x</math>, they have been replaced with functions based on <math>\textstyle s</math> and <math>\textstyle y</math> only. As you can see, both sides are now equal to the <math>\textstyle P_{Y_r}(y)</math> we calculated earlier, so the AVC is indeed symmetric when <math>\textstyle I(P)</math> is equal to <math>\textstyle 0</math>. Therefore <math>\textstyle I(P)</math> 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 [[Channel capacity|capacity]] for AVCs with input and/or state constraints. These constraints help to decrease the very large [[Range (mathematics)|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 [[Lemma (mathematics)|lemmas]]:

For such AVCs, there exists:<br>
:- An input constraint <math>\textstyle \Gamma</math> based on the equation <math>\displaystyle g(x) = \frac{1}{n}\sum_{i=1}^n g(x_i)</math>, where <math>\textstyle x \in X</math> and <math>\textstyle x = (x_1,\dots,x_n)</math>.
:- A state constraint <math>\textstyle \Lambda</math>, based on the equation <math>\displaystyle l(s) = \frac{1}{n}\sum_{i=1}^n l(s_i)</math>, where <math>\textstyle s \in X</math> and <math>\textstyle s = (s_1,\dots,s_n)</math>.
:- <math>\displaystyle \Lambda_0(P) = \min \sum_{x \in X, s \in S}P(x)l(s)</math>
:- <math>\textstyle I(P, \Lambda)</math> is very similar to <math>\textstyle I(P)</math> equation mentioned previously, <math>\displaystyle I(P, \Lambda) = \min_{Y_r} I(X_r \land Y_r)</math>, but now any state <math>\textstyle s</math> or <math>\textstyle S_r</math> in the equation must follow the <math>\textstyle l(s) \leq \Lambda</math> state restriction.

Assume <math>\textstyle g(x)</math> is a given non-negative-valued function on <math>\textstyle X</math> and <math>\textstyle l(s)</math> is a given non-negative-valued function on <math>\textstyle S</math> and that the minimum values for both is <math>\textstyle 0</math>. In the literature I have read on this subject, the exact definitions of both <math>\textstyle g(x)</math> and <math>\textstyle l(s)</math> (for one variable <math>\textstyle x_i</math>,) is never described formally. The usefulness of the input constraint <math>\textstyle \Gamma</math> and the state constraint <math>\textstyle \Lambda</math> will be based on these equations.

For AVCs with input and/or state constraints, the [[Information_theory#Rate|rate]] <math>\textstyle R</math> is now limited to [[codeword]]s of format <math>\textstyle x_1,\dots,x_N</math> that satisfy <math>\textstyle g(x_i) \leq \Gamma</math>, and now the state <math>\textstyle s</math> is limited to all states that satisfy <math>\textstyle l(s) \leq \Lambda</math>. The largest [[Information_theory#Rate|rate]] is still considered the [[Channel capacity|capacity]] of the AVC, and is now denoted as <math>\textstyle c(\Gamma, \Lambda)</math>.

''Lemma 1:'' Any [[Channel coding|codes]] where <math>\textstyle \Lambda</math> is greater than <math>\textstyle \Lambda_0(P)</math> cannot be considered "good" [[Channel coding|codes]], because those kinds of [[Channel coding|codes]] have a maximum average probability of error greater than or equal to <math>\textstyle \frac{N-1}{2N} - \frac{1}{n}\frac{l_{max}^2}{n(\Lambda - \Lambda_0(P))^2}</math>, where <math>\textstyle l_{max}</math> is the maximum value of <math>\textstyle l(s)</math>. This isn't a good maximum average error probability because it is fairly large, <math>\textstyle \frac{N-1}{2N}</math> is close to <math>\textstyle \frac{1}{2}</math>, and the other part of the equation will be very small since the <math>\textstyle (\Lambda - \Lambda_0(P))</math> value is squared, and <math>\textstyle \Lambda</math> is set to be larger than <math>\textstyle \Lambda_0(P)</math>. Therefore it would be very unlikely to receive a [[codeword]] without error. This is why the <math>\textstyle \Lambda_0(P)</math> condition is present in Theorem 2.

'''Theorem 2:''' Given a positive <math>\textstyle \Lambda</math> and arbitrarily small <math>\textstyle \alpha > 0</math>, <math>\textstyle \beta > 0</math>, <math>\textstyle \delta > 0</math>, for any block length <math>\textstyle n \geq n_0</math> and for any type <math>\textstyle P</math> with conditions <math>\textstyle \Lambda_0(P) \geq \Lambda + \alpha</math> and <math>\displaystyle \min_{x \in X}P(x) \geq \beta</math>, and where <math>\textstyle P_{X_r} = P</math>, there exists a [[Channel coding|code]] with [[codeword]]s <math>\textstyle x_1,\dots,x_N</math>, each of type <math>\textstyle P</math>, that satisfy the following equations: <math>\textstyle \frac{1}{n}\log N > I(P,\Lambda) - \delta</math>, <math>\displaystyle \max_{l(s) \leq \Lambda} \bar{e}(s) \leq \exp(-n\gamma)</math>, and where positive <math>\textstyle n_0</math> and <math>\textstyle \gamma</math> depend only on <math>\textstyle \alpha</math>, <math>\textstyle \beta</math>, <math>\textstyle \delta</math>, 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 [[Information entropy|randomized]] [[Channel coding|code]]. For such AVCs the [[Channel coding|code]] is a [[random variable]] with values from a family of length-n [[block code]]s, and these [[Channel coding|code]]s are not allowed to depend/rely on the actual value of the [[codeword]]. These [[Channel coding|codes]] have the same maximum and average error probability value for any [[Channel model|channel]] because of its random nature. These types of [[Channel coding|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:

<math>\displaystyle W_{\zeta}(y|x) = \sum_{s \in S} W(y|x, s)P_{S_r}(s)</math><br>
<math>\textstyle I(P, \zeta)</math> is very similar to the <math>\textstyle I(P)</math> equation mentioned previously, <math>\displaystyle I(P, \zeta) = \min_{Y_r} I(X_r \land Y_r)</math>, but now the [[/Probability mass function|pmf]] <math>\textstyle P_{S_r}(s)</math> is added to the equation, making the minimum of <math>\textstyle I(P, \zeta)</math> based a new form of <math>\textstyle P_{X_{r}S_{r}Y_{r}}</math>, where <math>\textstyle W_{\zeta}(y|x)</math> replaces <math>\textstyle W(y|x, s)</math>.

'''Theorem 3:''' The [[Channel capacity|capacity]] for [[Information entropy|randomized]] [[Channel coding|codes]] of the AVC is <math>\displaystyle c = max_P I(P, \zeta)</math>.

''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," http://ieeexplore.ieee.org.gate.lib.buffalo.edu/stamp/stamp.jsp?tp=&arnumber=4069128
* Blackwell, David, Breiman, Leo, and Thomasian, A. J., "The Capacities of Certain Channel Classes Under Random Coding," http://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

[[Category:Coding theory]]

Time deviation - Revision history

en>Omnipaedista: standardized punctuation

en>Kvng: reorder paragraphs. link improvements. bait maximum time interval error.