Information has a probability model

Prerequisites: Fractions, logarithms, and binary strings.

Learning objectives

• Calculate entropy for a finite source.
• Construct and check a prefix code.
• Separate lossless compression limits from channel-capacity assumptions.

Uncertainty belongs to a source model

A symbol’s information content under a probability model is −log2(p). Rare symbols carry more surprise than common ones. The entropy H=−Σ p_i log2(p_i) is the expected information per symbol. Entropy is a property of a distribution, not a claim that a particular message is meaningful, true, or useful.

Consider an independent source with symbols A, B, C, D occurring with probabilities 1/2, 1/4, 1/8, 1/8. Their information contents are 1, 2, 3, and 3 bits. The entropy is 0.5×1+0.25×2+0.125×3+0.125×3=1.75 bits per symbol. A fixed-width code uses two bits for each of four symbols. A variable-length code can exploit the unequal frequencies.

Build a code you can decode

Choose A=0, B=10, C=110, D=111. No codeword is a prefix of another, so a decoder can identify each symbol as soon as its codeword ends. The string 010110111 decodes as A, B, C, D. Its nine bits are not representative of the average because that particular message contains one of each symbol. Expected length must weight lengths by the source probabilities, giving 1.75 bits per symbol here.

Now change the true source so all four symbols are equally likely, but retain the code. Expected length becomes (1+2+3+3)/4=2.25 bits per symbol, worse than the two-bit fixed code. Compression depends on the match between the model and data. A code optimized for yesterday’s distribution can perform poorly after a change.

Compression and communication ask different questions

Lossless compression removes predictable redundancy while preserving recoverability. Error-control coding deliberately adds structured redundancy to resist corruption. These objectives can coexist: compress a message, then encode it for a noisy channel. A damaged bit in a variable-length stream may also disturb symbol boundaries, so framing and resynchronization matter.

For an ideal band-limited additive white Gaussian noise channel with bandwidth B and signal-to-noise power ratio S/N, Shannon’s capacity expression is C=B log2(1+S/N). If B=1,000 Hz and S/N=15, this model gives C=4,000 bits per second. It does not promise that any chosen modulation reaches that rate, nor does it give a universal latency bound. Coding arguments approach reliable communication under specified asymptotic conditions. Real interference, nonlinearity, finite block length, and changing channels demand additional modeling.

Before invoking an information limit, identify the alphabet, probabilities, independence assumptions, units, and error criterion. Without these, a number measured in bits can conceal several incompatible questions.

Primary reading

• Basics of Information (MIT OpenCourseWare, Computation Structures).
• Shannon Capacity (Stanford University, EE359).

Practice problem

A source emits X with probability 3/4 and Y with probability 1/4. Compute its entropy and compare it with a one-bit code for each symbol. For a separate ideal Gaussian channel with B=2,000 Hz and S/N=7, calculate capacity. Explain why the entropy result does not mean every individual source symbol can be encoded using a fractional number of bits.

Worked solution

Entropy is −0.75 log2(0.75)−0.25 log2(0.25)≈0.8113 bits per symbol. A single-symbol binary code still needs one bit per symbol. Coding blocks or an arithmetic-coding procedure can make average lengths approach the entropy under an appropriate source model; no isolated stored bit has fractional physical size. The channel calculation gives 2000×log2(8)=6000 bits per second. Source entropy and channel capacity refer to different models. To compare them for a communication task, also specify the source’s symbols per second and acceptable error rate.

Check your understanding

Why does the four-symbol code become worse under a uniform source?

• Its codewords cease to be binary.
• It is no longer prefix-free.
• Long codewords occur more often than the old model predicted.
• Every lossless code must use exactly two bits.

Explanation

The code remains decodable. Its expected length changes because symbol probabilities changed.

What does the 4,000 bits/s capacity calculation assume?

• Arbitrary interference and zero latency.
• The specified band-limited Gaussian-noise channel model.
• A noiseless channel with no power constraint.
• That every practical code achieves the bound.

Explanation

Capacity is conditional on a channel model and reliability criterion, not a measurement-free promise about a device.

Primary reading

• Basics of Information: MIT OpenCourseWare, Computation Structures
• Shannon Capacity: Stanford University, EE359

Open the study and save your work →