Z-channel (information theory)

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.

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

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:Template:Sfnp

$\begin{array}{cc}\mathrm{Pr}[Y=0|X=0]& =1\\ \mathrm{Pr}[Y=0|X=1]& =p\\ \mathrm{Pr}[Y=1|X=0]& =0\\ \mathrm{Pr}[Y=1|X=1]& =1-p\end{array}$

Capacity

The channel capacity $𝖼𝖺𝗉(\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:

$𝖼𝖺𝗉(\mathbb{Z})=𝖧\left(\frac{1}{1+2^{𝗌(p)}}\right)-\frac{𝗌(p)}{1+2^{𝗌(p)}}={\log }_2(1+2^{-𝗌(p)})={\log }_2(1+(1-p)p^{p/(1-p)})$

where $𝗌(p)=\frac{𝖧(p)}{1-p}$ for the binary entropy function $𝖧(\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^{𝖧(p)/(1-p)})},$

For small p, the capacity is approximated by

$𝖼𝖺𝗉(\mathbb{Z})\approx 1-0.5𝖧(p)$

as compared to the capacity $1-𝖧(p)$ of the binary symmetric channel with crossover probability p.

CalculationTemplate:Sfnp

$𝖼𝖺𝗉(\mathbb{Z})=\underset{\alpha }{\max }\{𝖧(Y)-𝖧(Y\mid X)\}=\underset{\alpha }{\max }\{𝖧(Y)-\sum _{x\in \{0,1\}}𝖧(Y\mid X=x)𝖯𝗋𝗈𝖻\{X=x\}\}$ $=\underset{\alpha }{\max }\{𝖧((1-\alpha )(1-p))-𝖧(Y\mid X=1)𝖯𝗋𝗈𝖻\{X=1\}\}$ $=\underset{\alpha }{\max }\{𝖧((1-\alpha )(1-p))-(1-\alpha )𝖧(p)\},$ To find the maximum we differentiate $\frac{d}{d\alpha }𝖼𝖺𝗉(\mathbb{Z})=-(1-p){\log }_2\left(\frac{1-(1-\alpha )(1-p)}{(1-\alpha )(1-p)}\right)+𝖧(p)$ And we see the maximum is attained for $\alpha =1-\frac{1}{(1-p)(1+2^{𝖧(p)/(1-p)})},$ yielding the following value of $𝖼𝖺𝗉(\mathbb{Z})$ as a function of p $𝖼𝖺𝗉(\mathbb{Z})=𝖧\left(\frac{1}{1+2^{𝗌(p)}}\right)-\frac{𝗌(p)}{1+2^{𝗌(p)}}={\log }_2(1+2^{-𝗌(p)})={\log }_2(1+(1-p)p^{p/(1-p)})\text{where}𝗌(p)=\frac{𝖧(p)}{1-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\to 1$, the limiting value of $\alpha$ is $1-\frac{1}{e}$.Template:Sfnp

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

Define the following distance function ${𝖽}_A(𝐱,𝐲)$ on the words $𝐱,𝐲\in \{0,1{\}}^n$ of length n transmitted via a Z-channel

${𝖽}_A(𝐱,𝐲)\stackrel{△}{=}\max \left\{\right|\{i\mid x_i=0,y_i=1\}|,|\{i\mid x_i=1,y_i=0\}\left|\right\}.$

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

$V_t(𝐱)=\{𝐲\in \{0,1{\}}^n\mid {𝖽}_A(𝐱,𝐲)\le t\}.$

A code $𝒞$ of length n is said to be t-asymmetric-error-correcting if for any two codewords $𝐜\ne {𝐜}^{\prime }\in \{0,1{\}}^n$, one has $V_t(𝐜)\cap V_t({𝐜}^{\prime })=\mathrm{\varnothing }$. 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)\le \frac{2^{n+1}}{\sum _{j=0}^t((\genfrac{}{}{0ex}{}{\lfloor n/2\rfloor }{j})+(\genfrac{}{}{0ex}{}{\lceil n/2\rceil }{j}))}.$

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

$B_0=2,B_i=\underset{0\le j<i}{\min }\{B_j+A(n+t+i-j-1,2t+2,t+i)\}$ for $i>0$.

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

References

• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite conference