Blackwell channel

From Wikipedia, the free encyclopedia

The Blackwell channel is a deterministic broadcast channel model used in coding theory and information theory. It was first proposed by mathematician David Blackwell. In this model, a transmitter transmits one of three symbols to two receivers. For two of the symbols, both receivers receive exactly what was sent; the third symbol, however, is received differently at each of the receivers. This is one of the simplest examples of a non-trivial capacity result for a non-stochastic channel.

[edit] Definition

The Blackwell channel is composed of one input (transmitter) and two outputs (receivers). The channel input is ternary (three symbols) and is selected from {0, 1, 2}. This symbol is broadcast to the receivers; that is, the transmitter sends one symbol simultaneously to both receivers. Each of the channel outputs is binary (two symbols), labeled {0, 1}.

Whenever a 0 is sent, both outputs receive a 0. Whenever a 1 is sent, both outputs receive a 1. When a 2 is sent, however, the first output is 0 and the second output is 1. Therefore, the symbol 2 is confused by each of the receivers in a different way.

The operation of the channel is memoryless and completely deterministic.

[edit] Capacity of the Blackwell channel

The capacity of the channel was found by S. I. Gel'fand. It is defined by the region:

1. R₁ = 1, 0 ≤ R₂ ≤ ½

2. R₁ = H(a), R₂ = 1 − a, for ⅓ ≤ a ≤ ½

3. R₁ + R₂ = log₂ 3, log₂ 3 - ⅔ ≤ R₁  ≤ ⅔

4. R₁ = 1 − a, R₂ = H(a), for ⅓ ≤ a ≤ ½

5. 0 ≤ R₁ ≤ ½, R₂ = 1

[edit] References

• S. I. Gel'fand. "Capacity of one broadcast channel." Problemy Peredachi Informatsii (Problems in Information Transmission), Vol. 13(3), pp. 106-108, 1977.
• E. van der Meulen, "A survey of multi-way channels in information theory: 1961-1976." IEEE Trans. on Information Theory, Vol.23, Iss.1, Jan 1977, pp 1-37. (IEEExplore pdf)