What is the $n$ in the channel coding theorem counting?

(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?

-

1 Answer

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

-
This seems to explain the increase in message length. What about the increase in the number of messages? – Quinn Culver Oct 9 '11 at 12:47
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. – yaakov Oct 9 '11 at 12:52
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? – Quinn Culver Oct 9 '11 at 13:10
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). – yaakov Oct 9 '11 at 13:24