(One direction of) Shannon's channel coding theorem says that for a discrete memoryless channel, all rates below capacity $C$ are achievable. Specifically, for every rate $R < C$, there exists a sequence of $(2^{nR}, n)$ codes with maximum probability of error $λ^{(n)} \to 0$.

As I understand, $n$ is counting the number channel uses. Is this correct? If so, then the number $2^{nR}$ of input message is increasing also. What is the physical interpretation of this increase in messages?


2 Answers 2


You are correct.

The physical interpretation of $2^{nR}$ messages is: "messages writeable by nR bits".

Therefore the theorem claims that using long enough messages, we can get arbitrarily close to zero-mistakes in transmission, so long as we transmit in a rate which is less than the channel capacity. Where "transmit in a rate R" is translated as "pass X bits with X/R uses"

e.g. if C = 2, then we can (with arbitrary low error probability, for long enough messages) expect to transmit a bit for every use (R=1); but we would be real fools to try to pass over 3 bits with every use - can't be done (from the other direction of the theory).

  • $\begingroup$ This seems to explain the increase in message length. What about the increase in the number of messages? $\endgroup$ Oct 9, 2011 at 12:47
  • $\begingroup$ I don't understand the question. The message is any of $2^{nR}$ different possibilities, which we can view as a number written in binary with nR bits. The "number of messages" (how many different possibilities there are) and the "length of the message" (how many bits we are using) are the different ways of viewing the same concept. $\endgroup$
    – yaakov
    Oct 9, 2011 at 12:52
  • $\begingroup$ Aren't we using the channel initially on some fixed set of messages? That is, we have a finite collection of informative messages that we'll need to send? If so, then at one time we have possible messages $\{1,\ldots, 2^{nR}\}$. Then we have the messages $\{1, \ldots, 2^{(n+1)R}\}$. Why do we have new massages to send? Where did these new messages come from? $\endgroup$ Oct 9, 2011 at 13:10
  • $\begingroup$ The setting which makes it most simple is this: you have an infinite stream of bits which you have to pass through the channel (think of an international telephone line - after all, Shannon worked for Bell). You can get low error prob., for each rate which is smaller than the channel capacity - but in order to do so you will have to group a stream of bits to be "passed together" (and use error correcting codes). This grouping is the increase of the message length (or the number of messages). $\endgroup$
    – yaakov
    Oct 9, 2011 at 13:24

I am not absolutely sure but I think if you fix the number of messages you want to send, or alternatively, fix the number of bits required to represent your message set to $ k = nR$, then as you increase $n$, $R$ will drop. In a way, you are increasing the redundancy of your message before sending it. So with every use of the channel, you are sending less of the actual message.

However, Shannon's channel coding theorem talks about achievability of a rate. Instead of fixing the number of messages, we first fix the rate $R$. So all it says, is that it is easier to achieve this rate $R$ if we have a lot of messages to send as long as $R \leq C$. So fixing $R$ basically means that we are fixing the amount of redundancy we add to a message. Increasing $n$ in this case, will increase our message set, but we do not really care about that. We are not talking about a specific message set, but rather we are talking about whether a rate can be achieved.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .