Calculating the capacity of a noisy channel

Question

Suppose we have a channel which transmits sequences of length n, of 0s and 1s (i.e. A={0,1} to the nth -> B={0,1} to the nth, such that during transmission, it will randomly (with equal probability) choose one digit from the initial sequence, and multiply it by 0.

e.g. we send in 01110, and it happens to choose the third digit, yielding 01010.

How to calculate the capacity of a channel like this? i.e. what is the max over A of (I(A,B))?

I've struggled with this exercise, I see many potential ways of dealing with it (e.g. simply finding the zero point of the derivative of I(A,B), but that would require quite complicated maths, and I am bound to make mistakes).

Perhaps it could be calculated using some theorems, or approximated using some other channels?

I'd be very grateful for any hints.

Answer 1

Remark 1: In my original answer I had misunderstood the channel effect (many thanks to @leonbloy for pointing that out). I have rewritten the answer, hoping I got it right this time :)

Remark 2: As noted in the comments by @leonbloy, the assumption $H(E|X,Y)=0$ I am making below is not correct. I will leave, however, leave this answer, as it may serve as a starting point for someone else to give it a shot. However, the lower bound stated below still holds, as, clearly, $H(E|X,Y)\geq 0$

Let $X \in \{0,1\}^n$ and $Y \in \{0,1\}^n$ denote the input and output of the channel, respectively, and $E\in \{0,1,\ldots,n-1\}$ denote the position of the input signal that the channel replaces with a zero.

I will use the following standard formula for the mutual information between input and output : $$ I(X;Y) = H(Y) - H(Y|X), $$ in bits per $n$ channel uses.

Consider the computation of $H(Y)$ first. Using the following two expressions for the joint entropy $H(Y,E)$, \begin{align} H(Y,E) &= H(E) + H(Y|E),\\ H(Y,E) &= H(Y) + H(E|Y), \end{align} it follows that $$ H(Y) = H(E) + H(Y|E) - H(E|Y). $$

Similarly, we can show that \begin{align} H(Y|X) &= H(E|X)+H(Y|X,E)-H(E|Y,X)\\ &= H(E)+0-0, \end{align} which follows by noting that $E$ is independent of $X$ and that $Y$ and $E$ are completely determined when $X$, $E$ and $Y$, $X$, are known, respectively. Therefore, we have $$ I(X;Y) = H(Y|E) - H(E|Y). $$ Let's compute the two terms of the left hand side.

Regarding $H(Y|E)$, note that when $E$ is known, the corresponding element of $Y$ is also known (equal to zero) and the uncertainty about $Y$ is with respect to its other $n-1$ elements. Assuming that the input symbols are equiprobable, it follows that $H(Y|E) = n-1$.

The tricky part is the computation of $H(E|Y)$. First note that by observing a realization $Y=y$, we know that $E$ must be restricted to one of the positions of $y$ that are zero. Since any of these positions can be the actual one with equal probability, it follows that $$ H(E|y) = \log_2 k_y, $$

for $1\leq k_y\leq n$, where $k_y \triangleq|\{i:y_i=0\}|$ is the number of elements in $y$ that are zero. Note that if $k_y=1$ (one zero in $y$) then we now that the zero element is where the error is and the conditional entropy becomes zero, as expected.

Now,

\begin{align} H(E|Y) &\triangleq \sum_y \mathbb{P}(Y=y) H(E|y)\\ &= \sum_{i=1}^n \mathbb{P}(k_y=i) \log_2 i \\ &= \sum_{i=1}^n \binom{n-1}{i-1} \left(\frac{1}{2} \right)^{i-1} \left(\frac{1}{2} \right)^{n-1-(i-1)}\log_2 i \\ &= \left(\frac{1}{2} \right)^{n-1}\sum_{i=1}^n \binom{n-1}{i-1} \log_2 i \\ \end{align}

where we used the fact that $k_y=i$ can occur if, apart from the error position, there are $i-1$ out of the rest $n-1$ positions of the input that are zero. It appears that the last expression cannot be further simplified. Of course, one could consider the trivial bound \begin{align} H(E|Y) &\leq H(E)\\ &=\log_2 n, \end{align} resulting in $$ I(X;Y) \geq n-1-\log_2 n. $$

Just for fun, I plot below the numerically evaluated normalized mutual information $I(X;Y)/n$ (in bits per channel use). Note that as $n$ increases, it approaches the bound of the ideal channel ($1$ bit per channel use). The bound becomes tight for large $n$.

Answer 2

My (rather unsuccessful) attempt.

Let's assume (reasonable, probably correct; but it should be better justified) that the optimum input distribution is uniform for each subset of constant Hamming weight.

Let $a_k=P(w(X)=k)$ , where $w()$ is the weight (amount of ones). Then $\sum_{k=0}^n a_k=1$ and the probability of an individual $x$ with $w(x)=k$ is $p(x)=a_k/\binom{n}{k}$.

Let's compute $I(X;Y) = H(Y) - H(Y |X)$ in terms of $a_k$

$$\begin{align} H(Y|X) &= \sum_x p(x) H(Y | X=x)\\ &=\sum_{k=0}^n a_k H(Y | X=x ; w(x)=k)\\ &= - \sum_{k=0}^n a_k \left( (1-k/n)\log(1-k/n) + \frac{k}{n}\log(1/n) \right) \tag{1} \end{align}$$

(all logarithms are in base $2$, as usual).

Now, the respective probabilities of the subsets of equal weight in the output $Y$ (which, again are constant inside each subset) are given by

$$b_k = P(w(Y)=k)=(1-k/n) a_k + \frac{k+1}{n}a_{k+1} \tag{2}$$

where now $k=0\cdots n-1$. Then

$$\begin{align} H(Y) &= -\sum_y p(y) \log(p(y))\\ &=-\sum_{j=0}^{n-1} b_j \log \frac{b_j}{\binom{n}{j}}\tag{3} \end{align}$$

Plugging $(2)$ into $(3)$ one can compute $I(X;Y)$ in terms of $a_k$. To find its maximum, eg via Lagrange multipliers, looks unfeasible (but I might be mistaken). One could at least find the maximum (and hence the capacitity) numerically.

---

A rather rough bound : if $n=2^r-1$ we can use a Hamming code with no errors. Hence $$C \ge n - \log(n+1) \tag{4}$$

For $n=7$ this gives $C \ge 4$. Numerically, it seems to be above $5.06 $

---

If we assume the input $X$ is uniformly distributed (not optimal, but probably not far from optimal, if we recall the moral of the related Z-channel), then we can compute $I(X;Y)=H(X)-H(X|Y) = n - H(X|Y)$ with

$$H(X|Y)=1+\frac{1}{2^{n}}\sum_{j=0}^{n-1} \binom{n-1}{j} \log(n-j) \tag{5}$$

(I'll spare the details, it's straightforward), hence

$$ C \ge n - 1 - \frac{1}{2^{n}}\sum_{j=0}^{n-1} \binom{n-1}{j} \log(n-j) \tag{6}$$

For large $n$ the bound is asymptotically $$ n - \frac{\log(n)}{2} - \frac12 +o(1) \tag{7}$$

---

Some numerical experimentation suggests that the bound $(6)$ is good, and more so for large $n$. This, even though the optimum input distribution is far from uniform. Some values

n    simul     bound(6)    bound ap (7)
4  2.453460   2.3903195    2.5
7  5.068897   5.0396837    5.0963225
8  5.977307   5.9512211    6.0
15 12.54321   12.521618    12.546554
20 17.34202   17.320516    17.339036
32 29.00951   28.988545    29.0