0
$\begingroup$

I have to solve this exercise in information theory:

A binary not symmetrical channel has probability of transition from 0 to 1 $P(output=1|input=0)=p$ and probability of transition from 1 to 0 $P(output=0|input=1)=q$. I have to calculate the channel capacity and the input distribution that leads to this capacity value.

I thought that the channel was the following:

enter image description here

So: $$P(Y|X)=\begin{pmatrix} 1-p & p\\ q & 1-q \end{pmatrix}$$

Then I tried to calculate the capacity:

$$C=\max_{p(x)}I(X;Y)$$

where

$$I(X;Y)=H(Y)-H(Y|X)$$

where

$$H(Y)=-(1-p+q)\log (1-p+q) - (p+1-q) \log (p+1-q) = ?$$

I don't think is correct. How do I calculate $H(Y)$ and $H(Y|X)$?


I tried to solve the exercise in this way.

$$\pi = Pr(X=0), 1 - \pi = Pr(X=1)$$

$$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q))$$

If I call: $$\pi(1-p)+(1-\pi)q = a$$ $$\pi + p(1-\pi)(1-q) = b$$ then $$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q)) = -a \log a - b \log b$$

Now I have to calculate: $$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi H(Y|X=0)+ (1- \pi)H(Y|X=1)$$ where

$$H(Y|X=0) = -P(Y=0|X=0) \log P(Y=0|X=0) - P(Y=1|X=0) \log P(Y=1|X=0) = -(1-p) \log (1-p) - p \log p$$ $$H(Y|X=1) = -P(Y=0|X=1) \log P(Y=0|X=1) - P(Y=1|X=1) \log P(Y=1|X=1) = - q \log q-(1-q) \log (1-q) $$

So: $$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi [-(1-p) \log (1-p) - p \log p]+ (1- \pi)[- q \log q-(1-q) \log (1-q)]$$ and if I call: $$[-(1-p) \log (1-p) - p \log p]=c$$ $$[- q \log q-(1-q) \log (1-q)]=d$$ then $$I(X;Y)=H(Y) - H(Y|X)=-a \log a - b \log b + \pi c + (1-\pi)d$$

it's right? Thanks

$\endgroup$
1
$\begingroup$

You need to compute $H(Y)$ by its definition:

$$ H(Y) \triangleq \Pr(Y=0) \log \frac{1}{\Pr(Y=0)} + \Pr(Y=1)\log\frac{1}{\Pr(Y=1)}$$

To be able to compute this formula, you need to figure out what is $\Pr(Y=1)$ and $\Pr(Y=0)$. These two measures actually depend on the distribution of $X$.

To compute $H(X|Y)$ again, use the definition. $$H(Y|X) \triangleq \Pr(X=0) H(Y| X=0) + \Pr(X=1)H(Y|X=1)$$

where $H(Y | X=0)$ is easy to compute from the original entropy definition $H(Z)$, for a random variable $Z$ that is distributed same as $(Y|X=0)$. This is immediately given by your $P(Y|X)$.

In order to compute the channel's capacity, you will need to find the distribution $p(x)$ that maximizes $H(Y)-H(Y|X)$.


Maybe you should also check a textbook about information and entropy. For instance, try Cover & Thomas, "Elements of Information Theory", Chapter 7 (Channel Capacity).

$\endgroup$
  • $\begingroup$ Thanks for the reply. I'm studying on the Cover and Thomas, but on the book there are no examples of solved exercises. Ok, to find $H(Y)$ and $H(Y|X)$ simply I can apply the formulas $H(Y)=-\sum p(y) \log p(y)$ and $H(Y|X)=\sum_x p(x) H(Y|X=x)$. The problem now is: $p(x)$ and $p(y)$ what they are? $0.5$? How do I find them? Thanks $\endgroup$ – four Jun 6 '16 at 20:24
  • $\begingroup$ As the answer points out you need to optimise over $p(x)$ (which uniquely determines $p(y)$ and thus $H(Y)-H(Y|X).$) $\endgroup$ – kodlu Jun 6 '16 at 22:53
  • $\begingroup$ @kodlu In what sense optimize $p(x)$? I didn't understand, I feel a bit stupid. Ok ,I have to maximize $p(x)$ but first I have to find $I(X; Y)$, am I wrong? Could you help me? $\endgroup$ – four Jun 8 '16 at 19:32
  • $\begingroup$ @four Changing the distribution of $X$ (i.e., the probabilities $p(x=0)$ and $p(x=1)$) changes $I(X;Y)$. Optimizing means - write $I(X;Y)$ as a function of $p(x)$. Now find the values $ p(x=0), p(x=1)$ for which $I(X;Y)$ is maximal. $\endgroup$ – Ran G. Jun 8 '16 at 21:11
  • $\begingroup$ @four let $p(X=0)=r.$ All entropies as well as $I(X;Y)$ can be written as a function of $r.$ The error parameters $p,q$ are constants. $\endgroup$ – kodlu Jun 8 '16 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.