Z-channel (information theory)

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.

The Z-channel sees each 0 bit of a message transmitted correctly always and each 1 bit transmitted correctly with probability 1–p, due to noise across the transmission medium.

Definition

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:

${\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=0\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}$

Capacity

The channel capacity ${\mathsf {cap}}(\mathbb {Z} )$ of the Z-channel $\mathbb {Z}$ with the crossover 1 → 0 probability p, when the input random variable X is distributed according to the Bernoulli distribution with probability $\alpha$ for the occurrence of 0, is given by the following equation:

${\mathsf {cap}}(\mathbb {Z} )={\mathsf {H}}\left({\frac {1}{1+2^{{\mathsf {s}}(p)}}}\right)-{\frac {{\mathsf {s}}(p)}{1+2^{{\mathsf {s}}(p)}}}=\log _{2}(1{+}2^{-{\mathsf {s}}(p)})=\log _{2}\left(1+(1-p)p^{p/(1-p)}\right)$

where ${\mathsf {s}}(p)={\frac {{\mathsf {H}}(p)}{1-p}}$ for the binary entropy function ${\mathsf {H}}(\cdot )$.

This capacity is obtained when the input variable X has Bernoulli distribution with probability $\alpha$ of having value 0 and $1-\alpha$ of value 1, where:

$\alpha =1-{\frac {1}{(1-p)(1+2^{{\mathsf {H}}(p)/(1-p)})}},$

For small p, the capacity is approximated by

${\mathsf {cap}}(\mathbb {Z} )\approx 1-0.5{\mathsf {H}}(p)$

as compared to the capacity $1{-}{\mathsf {H}}(p)$ of the binary symmetric channel with crossover probability p.

Calculation

${\mathsf {cap}}(\mathbb {Z} )=\max _{\alpha }\{{\mathsf {H}}(Y)-{\mathsf {H}}(Y\mid X)\}=\max _{\alpha }{\Bigl \{}{\mathsf {H}}(Y)-\sum _{x\in \{0,1\}}{\mathsf {H}}(Y\mid X=x){\mathsf {Prob}}\{X=x\}{\Bigr \}}$ $=\max _{\alpha }\{{\mathsf {H}}((1-\alpha )(1-p))-{\mathsf {H}}(Y\mid X=1){\mathsf {Prob}}\{X=1\}\}$ $=\max _{\alpha }\{{\mathsf {H}}((1-\alpha )(1-p))-(1-\alpha ){\mathsf {H}}(p)\},$ To find the maximum we differentiate ${\frac {d}{d\alpha }}{\mathsf {cap}}(\mathbb {Z} )=-(1-p)\log _{2}\left({\frac {1-(1-\alpha )(1-p)}{(1-\alpha )(1-p)}}\right)+{\mathsf {H}}(p)$ And we see the maximum is attained for $\alpha =1-{\frac {1}{(1-p)(1+2^{{\mathsf {H}}(p)/(1-p)})}},$ yielding the following value of ${\mathsf {cap}}(\mathbb {Z} )$ as a function of p ${\mathsf {cap}}(\mathbb {Z} )={\mathsf {H}}\left({\frac {1}{1+2^{{\mathsf {s}}(p)}}}\right)-{\frac {{\mathsf {s}}(p)}{1+2^{{\mathsf {s}}(p)}}}=\log _{2}(1{+}2^{-{\mathsf {s}}(p)})=\log _{2}\left(1+(1-p)p^{p/(1-p)}\right)\;{\textrm {where}}\;{\mathsf {s}}(p)={\frac {{\mathsf {H}}(p)}{1-p}}.$

For any p, $\alpha <0.5$ (i.e. more 0s should be transmitted than 1s) because transmitting a 1 introduces noise. As $p\rightarrow 1$, the limiting value of $\alpha$ is ${\frac {1}{e}}$.

Bounds on the size of an asymmetric-error-correcting code

Define the following distance function ${\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} )$ on the words $\mathbf {x} ,\mathbf {y} \in \{0,1\}^{n}$ of length n transmitted via a Z-channel

${\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} ){\stackrel {\vartriangle }{=}}\max \left\{{\big |}\{i\mid x_{i}=0,y_{i}=1\}{\big |},{\big |}\{i\mid x_{i}=1,y_{i}=0\}{\big |}\right\}.$

Define the sphere $V_{t}(\mathbf {x} )$ of radius t around a word $\mathbf {x} \in \{0,1\}^{n}$ of length n as the set of all the words at distance t or less from $\mathbf {x}$, in other words,

$V_{t}(\mathbf {x} )=\{\mathbf {y} \in \{0,1\}^{n}\mid {\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} )\leq t\}.$

A code ${\mathcal {C}}$ of length n is said to be t-asymmetric-error-correcting if for any two codewords $\mathbf {c} \neq \mathbf {c} '\in \{0,1\}^{n}$, one has $V_{t}(\mathbf {c} )\cap V_{t}(\mathbf {c} ')=\emptyset$. Denote by $M(n,t)$ the maximum number of codewords in a t-asymmetric-error-correcting code of length n.

The Varshamov bound. For n≥1 and t≥1,

$M(n,t)\leq {\frac {2^{n+1}}{\sum _{j=0}^{t}{\left({\binom {\lfloor n/2\rfloor }{j}}+{\binom {\lceil n/2\rceil }{j}}\right)}}}.$

The constant-weight code bound. For n > 2t ≥ 2, let the sequence B₀, B₁, ..., B_n-2t-1 be defined as

$B_{0}=2,\quad B_{i}=\min _{0\leq j<i}\{B_{j}+A(n{+}t{+}i{-}j{-}1,2t{+}2,t{+}i)\}$ for $i>0$.

Then $M(n,t)\leq B_{n-2t-1}.$

References

• 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.