Computing channel capacities for non-symmetric channels

Question

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$}.

Answer 1

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

Answer 2

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

Answer 3

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 square and 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];