Z-channel (information theory)
![]() | This article provides insufficient context for those unfamiliar with the subject.(June 2024) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Z-channel.svg/440px-Z-channel.svg.png)
In coding theory and information theory, a Z-channel or binary asymmetric channel is a communications channel used to model the behaviour of some data storage systems.
Definition
[edit]A Z-channel is a channel with binary input and binary output, where each 0 bit is transmitted correctly, but each 1 bit has probability p of being transmitted incorrectly as a 0, and probability 1–p of being transmitted correctly as a 1. In other words, if X and Y are the random variables describing the probability distributions of the input and the output of the channel, respectively, then the crossovers of the channel are characterized by the conditional probabilities:[1]
Capacity
[edit]The channel capacity of the Z-channel with the crossover 1 → 0 probability p, when the input random variable X is distributed according to the Bernoulli distribution with probability for the occurrence of 0, is given by the following equation:
where for the binary entropy function .
This capacity is obtained when the input variable X has Bernoulli distribution with probability of having value 0 and of value 1, where:
For small p, the capacity is approximated by
as compared to the capacity of the binary symmetric channel with crossover probability p.
Calculation[2] To find the maximum we differentiate
And we see the maximum is attained for
yielding the following value of as a function of p
For any p, (i.e. more 0s should be transmitted than 1s) because transmitting a 1 introduces noise. As , the limiting value of is .[2]
Bounds on the size of an asymmetric-error-correcting code
[edit]Define the following distance function on the words of length n transmitted via a Z-channel
Define the sphere of radius t around a word of length n as the set of all the words at distance t or less from , in other words,
A code of length n is said to be t-asymmetric-error-correcting if for any two codewords , one has . Denote by the maximum number of codewords in a t-asymmetric-error-correcting code of length n.
The Varshamov bound. For n≥1 and t≥1,
The constant-weight[clarification needed] code bound. For n > 2t ≥ 2, let the sequence B0, B1, ..., Bn-2t-1 be defined as
- for .
Then
Notes
[edit]- ^ MacKay (2003), p. 148.
- ^ a b MacKay (2003), p. 159.
References
[edit]- MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1.
- Kløve, T. (1981). "Error correcting codes for the asymmetric channel". Technical Report 18–09–07–81. Norway: Department of Informatics, University of Bergen.
- Verdú, S. (1997). "Channel Capacity (73.5)". The electrical engineering handbook (second ed.). IEEE Press and CRC Press. pp. 1671–1678.
- Tallini, L.G.; Al-Bassam, S.; Bose, B. (2002). On the capacity and codes for the Z-channel. Proceedings of the IEEE International Symposium on Information Theory. Lausanne, Switzerland. p. 422.