Z-channel (information theory)

A Z-channel is a communications channel used in coding theory and information theory to model the behaviour of some data storage systems.

Definition

A Z-channel (or a binary asymmetric channel) is a channel with binary input and binary output where the crossover 1 → 0 occurs with nonnegative probability p, whereas the crossover 0 → 1 never occurs. 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

Prob{Y = 0 | X = 0} = 1
Prob{Y = 0 | X = 1} = p
Prob{Y = 1 | X = 0} = 0
Prob{Y = 1 | X = 1} = 1p

Capacity

The 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 α for the occurrence of 0, is calculated as follows.

\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) \},

where \mathsf{H}(\cdot) is the binary entropy function.

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

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}\ne \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 B0, B1, ..., Bn-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

This article is issued from Wikipedia - version of the 11/28/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.