S5-1.4 Information Theory & Source Coding

Work through these

• Uncertainty, information and entropy

  Shannon's starting move: information is surprise, and a certain event carries none. Entropy measures the average surprise in bits, and every result in this topic is built on it.

• The source coding theorem

  The theorem that says how far a source can be compressed and no further. It gives you a number to compare a real code against, which is what makes the next two items meaningful rather than arbitrary recipes.

• Shannon-Fano algorithm

  The first practical code, and a good one to work by hand. Its gap from the entropy bound is exactly what the next item closes.

• Huffman coding

  Optimal for symbol by symbol coding, and worth building a tree for by hand until the construction is automatic. This is the one algorithm from this topic you are most likely to meet again in a compression setting.

• Discrete memoryless channels; types of channels; cascaded channels

  The receiving end of the theory: a model of what the channel does to your symbols. The cascaded case matters because real links are several stages, not one.

• Mutual information

  How much what you received tells you about what was sent. It is the quantity channel capacity is defined from, so it is worth being solid here before the next item.

• Channel capacity; information rate and information capacity

  The second of Shannon's two great results, and the one people misquote. Keep it apart from source coding: that says how far you can compress, this says how fast you can transmit and still be reliable.

• Introduction to error control coding

  The bridge from theory to practice: capacity says a reliable rate exists, and coding is how you get near it. Treated as an introduction here and taken further in later subjects.