In: Electrical Engineering
Briefly describe the significance of the Shannon limit for information capacity.
Consider the case in which the channel is noisy enough that a
four-bit message requires an eight-bit code. The receiver, like the
sender, would have a codebook that correlates the 16 possible
four-bit messages with 16 eight-bit codes. Since there are 256
possible sequences of eight bits, there are at least 240 that don’t
appear in the codebook. If the receiver receives one of those 240
sequences, she knows that an error has crept into the data. But of
the 16 permitted codes, there’s likely to be only one that best
fits the received sequence — that differs, say, by only a
digit.
Shannon showed that, statistically, if you consider all possible
assignments of random codes to messages, there must be at least one
that approaches the Shannon limit. The longer the code, the closer
you can get: eight-bit codes for four-bit messages wouldn’t
actually get you very close, but two-thousand-bit codes for
thousand-bit messages could.
Of course, the coding scheme Shannon described is totally
impractical: a codebook with a separate, randomly assigned code for
every possible thousand-bit message wouldn’t begin to fit on all
the hard drives of all the computers in the world. But Shannon’s
proof held out the tantalizing possibility that, since
capacity-approaching codes must exist, there might be a more
efficient way to find them.