Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm studying information theory right now and I'm reading about channel capacities.

I know that there are known expressions for computing the capacities for some well known simple channels such as BSC, the Z channel.

Could you show me or point me to the source showing how to derive the channel capacity for a binary asymmetric channel? Say that $X$ is input $Y$ is output. $\Pr(x = 0 | y = 1) = p_1$, $\Pr(x = 1 | y = 0) = p_2$.

Further, I'm wondering is there any known result for computing the capacity of an arbitrary non-symmetric channel? By arbitrary non-symmetric channel, I mean, X and Y are from the alphabet set {${0, 1, \cdots, q-1}$}, and $\Pr(x = i \mid y = j) = p_{i, j}$ for $i, j \in$ {$0, 1, ..., q-1$}.

share|improve this question
1  
Shannon's original article treats arbitrary channel, as far ad I Understand –  Alexander Chervov May 9 '12 at 19:04
    
The answers below perfectly clear my confusions! –  Kelvin Lee May 10 '12 at 18:09

3 Answers 3

up vote 3 down vote accepted

A quick google search for "capacity of binary asymmetric channel" gives a few papers stating a closed form solution (for example this paper of Stefan Moser). I've never personally seen a derivation of this, so following on from Dinesh's very nice answer we can attempt to find the capacity exactly using calculus.

The binary entropy function is $$h(x)=-x\log_2(x)-(1-x)\log_2(1-x)$$ which we can check has derivative $$h'(x)=\log_2\left(\frac{1}{x}-1\right).$$

So if we use $x$ for $\alpha$, our task is to find the $x$ that maximizes $$I(x)=h(x(1-p_1)+(1-x)p_2)-xh(p_1)-(1-x)h(p_2).$$ We rewrite this function as $$I(x)=h(x(1-p_1-p_2)+p_2)-x(h(p_1)-h(p_2))-h(p_2)$$ and take the derivative to get $$I'(x)=(1-p_1-p_2)\log_2\left(\frac{1}{x(1-p_1-p_2)+p_2}-1\right)-(h(p_1)-h(p_2)).$$ Solving $I'(x)=0$ gives $$\frac{1}{x(1-p_1-p_2)+p_2}-1=2^{\frac{h(p_1)-h(p_2)}{1-p_1-p_2}}$$ and thus $$x=\frac{1}{1-p_1-p_2}\left(\frac{1}{2^{\frac{h(p_1)-h(p_2)}{1-p_1-p_2}}+1}-p_2\right).$$ Write $$z=2^{\frac{h(p_1)-h(p_2)}{1-p_1-p_2}}$$ and then we can simplify this to $$x=\frac{1-p_2(1+z)}{(1-p_1-p_2)(1+z)}.$$ So the capacity of the binary asymmetric channel is $$C=h\left(\frac{1-p_2(1+z)}{1+z}+p_2\right)-\frac{1-p_2(1+z)}{(1-p_1-p_2)(1+z)}(h(p_1)-h(p_2))-h(p_2)$$ which using the definition of $z$ we can write as $$C=h\left(\frac{1}{1+z}\right)-\frac{\log_2(z)}{1+z}+p_2\log_2(z)-h(p_2).$$ Now from the definition of $h$ and some log laws we have $$h\left(\frac{1}{1+z}\right)=\log_2(1+z)-\frac{z\log_2(z)}{z+1}$$ and so $$C=\log_2(1+z)-\log_2(z)+p_2\log_2(z)-h(p_2)$$ which we can rewrite as $$C=\log_2(1+z)-\frac{1-p_2}{1-p_1-p_2}(h(p_1)-h(p_2))-h(p_2)$$ and final simplifications give $$C=\log_2(1+z)-\frac{1-p_2}{1-p_1-p_2}h(p_1)+\frac{p_1}{1-p_1-p_2}h(p_2).$$

share|improve this answer

Given a memoryless ergodic channel $P(Y|X)$, the Shannon capacity of that channel $C$ is given by $C = \max_{p(x)} I(X;Y)$ where $I(\cdot,\cdot)$ is the mutual information and the maximization is over all input distributions (possibly subject to some constraints such as transmit power). This statement does not assume anything about the symmetric nature of the channel.

In the example that you mentioned (I am assuming that $P(Y=1 | X = 0) = p_1$ and $P(Y=0 | X = 1) = p_2$ which is the reverse of your notation), the capacity can be calculated as follows. Let us assume that $P(X = 0) = \alpha$ and $P(X = 1) = \beta = 1 - \alpha$. Also, let $q_i = 1-p_i$ for $i = 1,2$. The output distribution becomes $P(Y = 0) = \alpha q_1 + \beta p_2$. The conditional entropy of $Y$ given $X$ is

$H(Y|X) = \alpha h(p_1) + \beta h(p_2)$

where $h(\cdot)$ is the binary entropy function. The mutual information is given by

$I(X;Y) = H(Y) - H(Y|X)$ = $h(\alpha q_1 + \beta p_2) - \alpha h(p_1) - \beta h(p_2)$

Optimizing this over $\alpha$ will give us the capacity of this channel. This is messy and probably doesn't have a nice closed form expression which is one of the reasons why such examples don't show up in textbooks.

It is another question to ask how this capacity can be achieved, i.e., what kind of coding over the input alphabets can get us to this capacity? It is in this context that the channel symmetry becomes important - linear codes (which are a very important family of practically relevant codes) can be shown to approach channel capacity only for symmetric channels. Here, the notion of symmetry must be carefully defined but for the simple case of binary channel inputs, it will agree with the obvious definition ($p_1 = p_2$ in your notation).

share|improve this answer

I adapt the following from Theorem 3.3.3 of Ash's information theory book: if the channel matrix $P$ of a discrete memoryless channel is nonsingular and

$d_k := \sum_j (P^{-1})_{jk} \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right ) > 0$

for all $k$, then the channel capacity is

$C = \log \sum_j \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right )$

and $d$ is proportional to a capacity-achieving distribution.


In general, the capacity of a DMC must be computed numerically using the Blahut-Arimoto algorithm (PDF of Blahut's original paper here). Here is a MATLAB M-file I wrote for this:

function y = blahutarimoto(P,e);

% channel capacity of a DMC with transition matrix P (not necessarily
% square); e is an error parameter
% except for P vs Q, we use Blahut's notation in Fig.1 of his paper

n = size(P,1);  % number of input symbols

% initializations 
p = ones(1,n)/n;  % input distribution
IU = 1; % upper bound for the capacity
IL = 0; % lower bound for the capacity
e = min(.5,e);

while IU - IL > e
    c = exp(sum(P.*log(P./repmat(p*P,[n 1])),2));
    IL = log(p*c);
    IU = log(max(c));
    p = p.*c'/(p*c);
end

C = IL;

y = [p,C];
share|improve this answer
    
Your answer solves my last question so well! Also I appreciate the matlab code too, will definitely try to run it! –  Kelvin Lee May 10 '12 at 18:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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