Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 46 · Information and Channel Coding

Entropy and Channel Capacity

Learn entropy as average information, why Huffman codes approach it, binary symmetric channel capacity, the Shannon-Hartley formula and the -1.59 dB limit.

How much information is in a message? Shannon's answer in 1948 was a number: the average number of yes-or-no questions needed to identify what was sent. Rare events carry more information than common ones, because they are more surprising. This number is the entropy, and it sets two limits at once: the fewest bits a source can be compressed to, and, in its channel form, the most bits a noisy channel can carry reliably.

Both limits are sharp. You can get arbitrarily close to them, and you cannot beat them. Knowing them tells you how far a real system is from perfect.

Left: the binary entropy curve peaking at 1 bit at p = 0.5. Right: Shannon capacity per hertz against SNR in dB, reaching about 6.66 bit/s/Hz at 20 dB.
Entropy measures surprise in bits; capacity says how many of those bits a channel can carry reliably.

What you will learn

  • Compute the entropy of a discrete source.
  • Explain why Huffman coding approaches the entropy.
  • Compute the capacity of a binary symmetric channel.
  • Use the Shannon-Hartley formula C = B·log2(1 + SNR).
  • Derive and interpret the Shannon limit Eb/N0 ≥ −1.59 dB.

Key terms

  • Entropy H(X): −Σ p(x)·log2 p(x) bits per symbol.
  • Huffman code: an optimal prefix code built from symbol probabilities.
  • Capacity C: the largest rate at which reliable communication is possible.
  • Spectral efficiency η: bit rate divided by bandwidth, in bit/s/Hz.
  • Shannon limit: the least Eb/N0 at which reliable communication is possible at all.

Entropy

For a source that emits symbol x with probability p(x), the information in one occurrence is −log2 p(x) bits. The average is the entropy

H = − Σ p(x) · log2 p(x).

A fair coin has H = 1 bit. A coin that lands heads 90 % of the time has H = −0.9·log2(0.9) − 0.1·log2(0.1) ≈ 0.469 bits: you are rarely surprised, so each flip tells you little. For a binary source with probability p the entropy H(p) rises from 0 (certain outcome) to 1 bit at p = 0.5 and falls again. It is plotted at the left of the figure. For M equally likely symbols H = log2(M), the maximum.

Source coding theorem. No lossless code can have an average length below H bits per symbol, and codes exist that come within one bit of it (and arbitrarily close for long blocks).

Huffman coding

A Huffman code assigns short codewords to likely symbols and long ones to unlikely symbols, so that no codeword is the start of another (a prefix code). Build it by repeatedly merging the two least probable symbols. For probabilities 0.4, 0.3, 0.2, 0.1 the codeword lengths are 1, 2, 3, 3, and the average length is 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 1.9 bits. The entropy is 1.846 bits, so the code wastes only 0.05 bits per symbol, against a fixed-length code's 2 bits.

When all probabilities are negative powers of two, such as 1/2, 1/4, 1/8, 1/8, Huffman reaches the entropy exactly (1.75 bits).

Capacity of a binary symmetric channel

A binary symmetric channel (BSC) flips each bit with probability p. Each use of the channel carries at most

C = 1 − H(p) bits.

At p = 0 the capacity is 1; at p = 0.11 it is half a bit per use (because H(0.11) ≈ 0.5); at p = 0.5 it is zero, since the output is pure noise. Shannon's channel coding theorem says that for any rate R < C there are codes with arbitrarily small error probability, and for R > C no code works.

The AWGN channel: Shannon-Hartley

For a channel of bandwidth B with AWGN of density N0, received signal power S, the capacity is

C = B · log2(1 + S / (N0·B)) bits per second.

Read it in two regimes. At high SNR, C ≈ B · log2(SNR), so each extra 3 dB of SNR buys only 1 more bit/s per hertz. At low SNR, C ≈ 1.44·S/N0, which depends on power and not on bandwidth, so adding bandwidth stops helping. An example: a 3 kHz telephone line with an SNR of 30 dB (a factor 1,000) has C = 3000 · log2(1001) ≈ 29.9 kbit/s, which is why dial-up modems topped out near 33.6 kbit/s.

The Shannon limit

Write the rate as Rb = C with Eb = S/Rb. Then the spectral efficiency η = Rb/B satisfies η = log2(1 + η·Eb/N0), or

Eb/N0 ≥ (2^η − 1) / η.

As η → 0 (infinite bandwidth) the bound tends to ln 2 = 0.693, which is −1.59 dB. Below that value reliable communication is impossible however much bandwidth or complexity you use. For a given η the bound gives a gap against real modulation: BPSK at η = 1 needs 9.6 dB for BER 10⁻⁵ while Shannon needs 0 dB, a gap of 9.6 dB that coding can mostly close. Turbo and LDPC codes get within about 1 dB.

Common misconceptions

  • "Entropy measures how random something looks." It measures average surprise under a probability model; the same bits can have different entropy for different models.
  • "Shannon capacity depends on the modulation." It is an upper bound over all schemes. Specific modulations fall below it.
  • "More bandwidth always increases capacity proportionally." Only if the SNR stays the same; with fixed signal power, SNR falls as B grows (it saturates at 1.44·S/N0).
  • "Below capacity there are no errors." The theorem promises error probability as small as you like, with long enough codes, not zero.

Try it

First, compute entropy, build a Huffman code and compare average length with the entropy. The code also prints the BSC capacity at a few flip probabilities.

Python Entropy, Huffman code and BSC capacity

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Second, the Shannon limit. The plot shows the least Eb/N0 that allows reliable communication at each spectral efficiency, with the Eb/N0 that real modulations need for BER 10⁻⁵.

Python The Shannon limit and real modulations

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is the entropy of a source with four equally likely symbols?

    H = log2(4) = 2 bits per symbol.
  2. 2. A binary symmetric channel flips bits with p = 0.5. What is its capacity?

    The output is independent of the input, so C = 1 − H(0.5) = 0.
  3. 3. A channel has B = 1 MHz and SNR = 15 (about 11.8 dB). What is its capacity?

    C = 10⁶ · log2(1 + 15) = 10⁶ · 4 = 4 Mbit/s.
  4. 4. The Shannon limit on Eb/N0 for infinite bandwidth is:

    As η → 0, (2^η − 1)/η → ln 2 = 0.693, which is −1.59 dB.
  5. 5. What does the channel coding theorem promise for a rate R below capacity?

    With long enough codes, the error probability can be driven as low as desired.

Summary

  • Entropy H = −Σ p·log2 p is the minimum average bits per symbol for lossless compression; Huffman codes come close.
  • A BSC has capacity 1 − H(p); an AWGN channel has C = B·log2(1 + SNR).
  • Reliable communication needs Eb/N0 ≥ (2^η − 1)/η, never below −1.59 dB.
  • Real modulations sit several dB above this limit; channel coding closes most of the gap.

Next: Hamming and block codes