Communication Systems · 96 h · Topic 10 of 11

Information theory

A 3100 Hz telephone channel with 35 dB of signal-to-noise ratio supports at most about 36 kbit/s. The last voice modems reached 33.6: theory set the ceiling before they existed.

Entropy Huffman code Channel capacity Shannon–Hartley Channel coding

01Measuring information

Claude Shannon proposed in 1948 to measure the information of a message by how improbable it is: a message that was expected tells us nothing. The information of a symbol of probability \( p \), and the average over all the symbols of a source, the entropy, are:

\[ I = \log_2 \frac{1}{p} \ \ \mathrm{bits} \] \[ H = \sum_i p_i \log_2 \frac{1}{p_i} \] A fair coin gives 1 bit per toss; a die, 2.585 bits. Entropy is maximum, \( \log_2 M \), when the \( M \) symbols are equiprobable, and is zero if one symbol is certain. Probabilities were covered in probability.

Entropy is not an arbitrary definition: the source coding theorem says it is the minimum number of bits per symbol with which the source can be represented without loss. No code does better, and by coding longer and longer blocks of symbols it is possible to come as close as desired.

02Source coding: Huffman

A variable-length code assigns short words to frequent symbols and long ones to rare symbols, like Morse code. For it to be decodable without separators, no word can be the beginning of another: it is a prefix code. The Huffman algorithm builds the best possible prefix code: it repeatedly merges the two least probable symbols into a new one, until only one remains, and reads the codes by walking the tree.

\[ H \le \bar L < H + 1 \] \( \bar L = \sum p_i \ell_i \) is the mean length of the code. If the probabilities are powers of 1/2, Huffman reaches the entropy exactly. If a single probability is very large, it cannot go below 1 bit per symbol, and it is better to code in pairs or use arithmetic coding.

Lab · the Huffman code

Six symbols with probabilities proportional to the chosen weights. The solid bars are the lengths of the Huffman code; the outlines, the information of each symbol, \( \log_2(1/p) \). Above each bar is the code word.

Weight of A =

Weight of B =

Weight of C =

Weight of D =

Weight of E =

Weight of F =

03Channel capacity

A noisy channel confuses some symbols. The mutual information between input and output measures how much is learned about the input by seeing the output, and its maximum over all input distributions is the capacity of the channel. In the binary symmetric channel, which flips each bit with probability \( p \):

\[ C = 1 - H_b(p) \] \[ H_b(p) = -p\log_2 p - (1-p)\log_2(1-p) \] With p = 0.01, C = 0.919 bits per channel use; with p = 0.11, barely 0.5. With p = 0.5 the output does not depend on the input and the capacity is zero.

The channel coding theorem is Shannon's most surprising result: if the rate is less than the capacity, there exist codes with an error probability as small as desired. There is no need to choose between speed and reliability, only to add redundancy in the right way. Above capacity, on the other hand, no code achieves it.

04The Gaussian channel: the Shannon–Hartley formula

For a channel of bandwidth \( B \) with white Gaussian noise, the capacity is:

\[ C = B \log_2\!\left(1 + \frac{S}{N}\right) \] A 3100 Hz telephone channel with 35 dB of signal-to-noise ratio supports about 36 kbit/s: that is why voice modems stopped at 33.6 kbit/s. Capacity grows in proportion to bandwidth, but only with the logarithm of power.

The formula sets a limit that no modulation or code can exceed, and it makes it possible to measure how good real systems are: turbo and LDPC codes, used in cellular telephony and digital television, operate within 1 dB of it. The comparison of systems against this limit is the subject of system intercomparison.

05In the lab

Activity 1 · Entropy of a text

Count the letter frequencies of a long text in Spanish with a program, calculate its entropy and build the Huffman code. Compare the size with that of a 5-bit-per-letter code.

Activity 2 · Real compression

With a general-purpose compressor, compress text files, audio files and random data, and compare the compression ratios with the estimated entropy.

Activity 3 · Binary channel

Simulate a binary symmetric channel with a three-bit repetition code and majority voting, and compare the error rate with that of the uncoded channel.

06Common mistakes

Confusing a bit of information with a binary digit. A binary digit carries at most one bit of information, and less if it is not equiprobable.
Believing that compression can go below the entropy. Without loss, it is impossible on average.
Reading capacity as a rate achievable with any system. It is a limit: reaching it requires long, complex codes.
Using Shannon's formula with S/N in dB. It takes a ratio: 30 dB is 1000.

07Self-assessment

What entropy does a four-symbol source with probabilities 1/2, 1/4, 1/8 and 1/8 have?

1.75 bits, and the Huffman code 0, 10, 110, 111 achieves it.

What is the capacity of a binary symmetric channel with p = 0.1?

\( 1 - H_b(0.1) = 1 - 0.469 = 0.531 \) bits per use.

What capacity does a 1 MHz channel with 20 dB of signal-to-noise ratio have?

\( 10^6 \log_2 101 \approx 6.66 \) Mbit/s.

Why is Huffman no good for a binary source with p = 0.95?

Because it cannot use less than 1 bit per symbol and the entropy is 0.29 bits: blocks of symbols must be coded.

08Further reading

Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. 2nd ed., Wiley, 2006. The reference for the subject: entropy, source coding and channel capacity.
Claude E. Shannon and Warren Weaver. The Mathematical Theory of Communication. University of Illinois Press, 1949. Shannon's original work, with an introduction by Weaver for non-specialist readers.
David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003. A modern approach, with the codes that approach the Shannon limit.

← Previous topic

Noise in digital modulations

Next topic →

System intercomparison