Shannon capacity of some channels

58 Views Asked by At

Let $G$ be a finite group. Suppose that $\mu$ is a mesure of probability on $G$. Consider the convolution operator $C: \ell^1(G) \to \ell^1(G)$, $f \mapsto \mu * f$.

What is the capacity of the channel $C$ ?

The capacity of a channel is defined here.

1

There are 1 best solutions below

3
On BEST ANSWER

Here is a derivation of the capacity (where $h_2(\mu) = -\sum_{x\in G} \mu(x) \log_2(\mu(x))$ is the entropy of the distribution $\mu$) \begin{align*} &\max_{p_X} I(X;C(X))\\ =& \max_{p_X} H(C(X)) - H(C(X)|X)\\ =& \max_{p_X} H(C(X)) - h_2(\mu)\\ =& \log_2 |G| - h_2(\mu) \end{align*} The third line is because when we know $X$, the distribution of $C(X)$ is $\mu$ with some permutation, the last line is because since $G$ is a group, when $p_X$ is uniform, $\mu\ast p_X$ is also a uniform distribution which has maximal entropy.


As a sannity check I always like to check the extreme cases. If $\mu$ is the uniform distribution, then all information is lost, then we get $h_2(\mu)=\log_2|G|$ and the capacity is $0$. When $\mu$ gives probability $1$ to an element, then the channel is deterministic and $h_2(\mu)=0$, which gives a capacity of $\log_2|G|$.