# Capacity of binary not symmetrical channel

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:

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

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).

• 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 – four Jun 6 '16 at 20:24
• As the answer points out you need to optimise over $p(x)$ (which uniquely determines $p(y)$ and thus $H(Y)-H(Y|X).$) – kodlu Jun 6 '16 at 22:53
• @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? – four Jun 8 '16 at 19:32
• @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. – Ran G. Jun 8 '16 at 21:11
• @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. – kodlu Jun 8 '16 at 21:55