I have the following problem: Given a discrete memoryless channel $Y = X + Z \mod5$, where $X$ is selected from one of 5 symbols (0, 1, 2, 3, 4), $Z$ randomly selected from (-1, 0, 1), and $X$ and $Z$ are independent, find the channel capacity. This is equivalent to finding the capacity of an undirected cycle graph.

The solution I have in hand starts with:

$C = \sup_{p_X(x)} I(X;Y) = \sup_{p_X(x)} H(Y) - H(Y|X)$

It then assumes that this is maximized if $Y$ has a uniform distribution, such that $H(Y) = log_2(5)$, and further assumes that $X$ will have a uniform distribution as a consequence. To get $H(Y|X)$, I assume that $H(Y|X) = H(X+Z\mod5|X) = H(Z|X)$, as $X$ does not add entropy if it is known. Since $X$ and $Z$ are independent, I then end up with $C = log_2(5) - H(Z)$.

This seems wrong, as it implies that the channel capacity of an undirected cycle graph can easily be found, but everything I've read says otherwise. Namely, that the capacity of an n-cycle graph cannot be reasonably calculated, and that for a 5-cycle, the actual channel capacity is something like $C = log_2(\sqrt5)$

Is there a flaw in my reasoning here? Am I misunderstanding my problem, and it really isn't equivalent to a cycle graph? Or is this right, and the capacity can be easily calculated if $H(Z)$ is known?


The reason I'm confused is that this wikipedia article seems to perfectly describe this problem, yet lists the general case as an open problem in mathematics. The Wolfram Mathworld article on Shannon capacity does the same. Thus, I can't help but think that I'm making a critical error in my assumptions.

Even more interesting is that my reasoning that $X$ will have a uniform distribution, same as $Y$, must be wrong, as they would then have the same entropy, $log_2(5)$. Since $Y$ has been corrupted by random variable $Z$, this cannot be the case, right?

  • $\begingroup$ Your reasoning and result for the channel capacity is right. I'm not sure about the relation with "the capacity of an undirected cycle graph", perhaps you could add some references $\endgroup$
    – leonbloy
    Oct 6 '14 at 18:10
  • $\begingroup$ Regarding your update last paragraph: nothing wrong with that. If to a uniform input you add uniform noise (with wrapping) you get uniform output, hence same entropy: $H(X)=H(Y)$. Of course, that doesn't imply that $H(X|Y)=0$ (knowing $Y$ know $X$) $\endgroup$
    – leonbloy
    Oct 7 '14 at 19:47

Compare the following two definitions:

(i) Rate $R$ is achievable for a given channel if there exists a sequence of $\left(2^{nR},n \right)$-codes such that the probability of decoding error goes to zero as $n$ goes to infinity. Shannon capacity is the supremum of all achievable rates.

(ii) Rate $R$ is achievable with zero error for a given channel if there exists a $\left( 2^{nR},n\right)$-code with zero probability of decoding error. Zero-error capacity is the supremum of all achievable rates with zero-error.

The capacity of a graph $G$ refers to the zero-error capacity of the channel defined by the graph $G$, whereas your initial problem considers the traditional notion of Shannon capacity, which only asks for asymptotically vanishing error probability; hence, it is not equivalent to finding the capacity of an undirected cycle graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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