Z-channel (information theory)

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{align} \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{align} == 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. : For any p > 0, \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 1-\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}\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 for i > 0. Then M(n,t) \leq B_{n-2t-1}. == Notes ==