Z-channel (information theory) explained

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:

\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

cap(Z)

of the Z-channel

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:

cap(Z)=H\left(

	1
	1+2^s(p)

\right)-

	s(p)
	1+2^s(p)

	-s(p)
log
	2(1{+}2

)=log_{2\left(1+(1-p)}p^p/(1-p)\right)

where

s(p)=

	H(p)
	1-p

for the binary entropy function

H( ⋅ )

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-

	1
	(1-p)(1+2^H(p)/(1-p))

For small p, the capacity is approximated by

cap(Z) ≈ 1-0.5H(p)

as compared to the capacity

1{-}H(p)

of the binary symmetric channel with crossover probability p.

For any p,

\alpha<0.5

(i.e. more 0s should be transmitted than 1s) because transmitting a 1 introduces noise. As

p → 1

, the limiting value of

\alpha

	1
	e

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

Define the following distance function

d_A(x,y)

on the words

x,y\in\{0,1\}ⁿ

of length n transmitted via a Z-channel

d_A(x,y)\stackrel{\vartriangle}{=}max\left\{|\{i\midx_i=0,y_i=1\}|,|\{i\midx_i=1,y_i=0\}|\right\}.

Define the sphere

V_t(x)

of radius t around a word

x\in\{0,1\}ⁿ

of length n as the set of all the words at distance t or less from

, in other words,

V_t(x)=\{y\in\{0,1\}ⁿ\midd_A(x,y)\leqt\}.

A code

l{C}

of length n is said to be t-asymmetric-error-correcting if for any two codewords

c\nec'\in\{0,1\}ⁿ

, one has

V_t(c)\capV_t(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

2ⁿ⁺¹

	t{\left(
\sum		\binom{\lfloorn/2\rfloor
	j=0

{j}+\binom{\lceiln/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₀=2, B_i=min₀\{B_j+A(n{+}t{+}i{-}j{-}1,2t{+}2,t{+}i)\}

for

i>0

.Then

M(n,t)\leqB_n-2t-1.

References

Book: MacKay, David J.C. . David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. 2003. 0-521-64298-1.
Kløve . T. . Error correcting codes for the asymmetric channel . Technical Report 18–09–07–81 . Department of Informatics, University of Bergen . Norway . 1981.
Book: Verdú, S. . Channel Capacity (73.5) . The electrical engineering handbook . second . IEEE Press and CRC Press . 1997 . 1671–1678.
Tallini. L.G. . Al-Bassam . S. . Bose . B. . On the capacity and codes for the Z-channel . Proceedings of the IEEE International Symposium on Information Theory . Lausanne, Switzerland . 2002 . 422.