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.

A Z-channel is a communications channel model used in coding theory and information theory to represent certain data storage systems. In a Z-channel, 0 bits are always transmitted correctly, but 1 bits may be corrupted and received as 0s with some probability.

This asymmetric error pattern, where errors only occur in one direction (1→0 but never 0→1), makes Z-channels particularly relevant for modeling storage technologies with intrinsic recording asymmetries. For example, in some flash memory systems, stored 1s may degrade over time and be read as 0s, but stored 0s remain stable.

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