Blackwell channel

The Blackwell channel is a deterministic broadcast channel model used in coding theory and information theory. It was first proposed by mathematician David Blackwell.[1] 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.

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.

Capacity of the Blackwell channel

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

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

2. R₁ = H(a), R₂ = 1 − a, for 13 ≤ a ≤ 12

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

4. R₁ = 1 − a, R₂ = H(a), for 13 ≤ a ≤ 12

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

A solution was also found by Pinkser et al. (1995).[4]

References

L Breiman; D Blackwell; A J Thomasian (1958). "Proof of shannon's transmission theorem for finite-state indecomposable channels". The Annals of Mathematical Statistics. United States: Institute of Mathematical Statistics. 29 (4): 1209–2220. doi:10.1214/aoms/1177706452.
S I Gel'fand (1977). "Capacity of one broadcast channel". Problemy Peredachi Informatsii. Moscow, Russia: Russian Academy of Sciences, Branch of Informatics, Computer Equipment and Automatization. 13 (3): 106–108.
E van der Meulen (1977). "A survey of multi-way channels in information theory: 1961-1976". IEEE Transactions on Information Theory. New York City, New York, United States: Institute of Electrical and Electronics Engineers. 23 (1): 1–37. doi:10.1109/tit.1977.1055652.
M Pinsker; S. Prelov; S. Verdú (November 1995). "Sensitivity of Channel Capacity". IEEE Transactions on Information Theory. New York City, New York, United States: Institute of Electrical and Electronics Engineers. 41 (6): 1877–1888. doi:10.1109/18.476313. S2CID 9687919.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[breiman-blackwell-thomasian-1958-1] L Breiman; D Blackwell; A J Thomasian (1958). "Proof of shannon's transmission theorem for finite-state indecomposable channels". The Annals of Mathematical Statistics. United States: Institute of Mathematical Statistics. 29 (4): 1209–2220. doi:10.1214/aoms/1177706452.

[gelfand-1977-2] S I Gel'fand (1977). "Capacity of one broadcast channel". Problemy Peredachi Informatsii. Moscow, Russia: Russian Academy of Sciences, Branch of Informatics, Computer Equipment and Automatization. 13 (3): 106–108.

[van-der-meulen-1977-3] E van der Meulen (1977). "A survey of multi-way channels in information theory: 1961-1976". IEEE Transactions on Information Theory. New York City, New York, United States: Institute of Electrical and Electronics Engineers. 23 (1): 1–37. doi:10.1109/tit.1977.1055652.

[pinsker-prelov-verdu-1995-4] M Pinsker; S. Prelov; S. Verdú (November 1995). "Sensitivity of Channel Capacity". IEEE Transactions on Information Theory. New York City, New York, United States: Institute of Electrical and Electronics Engineers. 41 (6): 1877–1888. doi:10.1109/18.476313. S2CID 9687919.