4.1.2 Shannon’s Coding Theorem

Shannon’s second theorem, known as the channel-coding theorem, establishes that it is theoretically possible to transmit information with arbitrarily low error probability over a noisy channel, provided that the code rate does not exceed the channel capacity.

Consider a source generating symbols with entropy E bits per symbol, produced at a rate of 1/T_s symbols per second, transmitted through a discrete memoryless channel with capacity H bits per use of the channel, which is capable of being used once every T_c seconds. Then, if:

\frac{E}{T_{s}} \leq \frac{H}{T_{c}}

(4.11)

there exists a coding scheme whereby the source information can be transmitted across the channel with arbitrarily small probability of error.

For a binary source with entropy E=1, Equation (4.11) becomes:

\frac{1}{T_{s}} \leq \frac{H}{T_{c}} \Rightarrow \frac{T_{c}}{T_{s}} \leq H

(4.12)

The code rate of the channel encoder, r=T_c/T_s, so that:

r \leq H

(4.13)

which means that for a code rate r, which is less than or equal to the channel capacity, H, there exists a code capable of achieving an arbitrarily low probability of error. In other words, if the code rate does not exceed the channel capacity, then a coding scheme exists that can make the probability of error as small as desired.

Two important clarifications must be made:

Existence, not construction. Shannon’s theorem proves that such codes exist, but it does not specify how to construct them. The search for practical codes that approach capacity occupied researchers for decades and led to the development of convolutional codes, Reed–Solomon codes, turbo codes, low-density parity-check (LDPC) codes, and more recently polar codes.
Asymptotic result. The theorem applies in the limit of long block lengths and ideal decoding. In practical systems, finite block length, decoding complexity, latency constraints, and implementation limitations prevent operation exactly at capacity. Nonetheless, modern coding techniques routinely operate within about 1 dB (and sometimes less) of the Shannon limit.

The channel-coding theorem therefore establishes the theoretical legitimacy of error-control coding: redundancy, when properly structured, can overcome the randomness introduced by noise.

From an engineering perspective, the theorem provides a design boundary:

If the transmission rate exceeds capacity, no coding strategy can eliminate errors.
If the transmission rate is below capacity, sufficiently powerful coding can, in principle, reduce error probability to arbitrarily small values.

This result applies universally across communication systems—whether wireless, optical, wired, storage-based, cellular, deep-space, or satellite—and forms the conceptual foundation for all modern error-control techniques.

Shannon’s coding theorem establishes that reliable communication is theoretically possible whenever the transmission rate does not exceed channel capacity. However, the theorem does not describe how such reliability is achieved in practice. To understand how redundancy is introduced and exploited, we now examine the fundamental elements of channel coding.