STRATA
Skip to study
XLVII

X.05 / SHARED INSTRUMENTS

Information theory, coding, and compression

How does the attainable message length depend on the cost assigned to reconstruction errors?

A source-led introduction2 source references2 related experiments

Start with the question.

Information theory, coding, and compression connect source structure to representations that can be stored or transmitted. Shannon's communication work provides the formal foundation, while his sampling paper addresses the representation of band-limited signals. A practical comparison must include the encoding convention, model overhead, reconstruction requirement, and channel conditions. Compression and sampling solve related representation problems with different assumptions.

Make a codebook part of the size calculation.

Suppose a short document uses four words repeatedly. Replacing each word with a short symbol can shrink the body, but the decoder also needs the symbol-to-word dictionary. Count both components and compare the total with the original. Repeat with a much longer document to see how shared overhead changes the result.

What would you inspect?

  • Source model, codebook size, average code length, and reconstruction fidelity.
  • Sampling rate and the frequency range assumed when representing a signal.

Take the next step.

Compare two encodings of one fixed dataset, including all metadata required to decode it, and state whether the reconstruction is exact or approximate.

Put part of the question to work.

These models isolate a mechanism you can vary. Their assumptions define the part of this topic they can illuminate.

Try entropy and compression.

Change one parameter, compare the numerical output, and export the result. The experiment loads when you open it.

Open its full page

Try sampling and aliasing.

Change one parameter, compare the numerical output, and export the result. The experiment loads when you open it.

Open its full page

Watch the quantities change.

12 seconds · Original model visualization · Silent

Entropy and compression

Compare symbol frequencies with the ordering that a code can exploit.

Read the explanation and method

The first sweep changes the probability of A while drawing each symbol independently. The other three symbols share the remaining probability.

As one symbol dominates, the observed symbol entropy falls. Huffman codes use short words for frequent symbols; the comparison excludes headers and the codebook.

The second sweep gives all four new draws equal probability and increases repetition. Long runs reward run-length coding, even when a symbol histogram cannot describe the dependence.

Method. The histogram gives an order-zero Shannon entropy. Huffman coding repeatedly joins the two least frequent branches to build a prefix code. The run-length format stores a two-bit symbol and an eight-bit count; counts run from 1 to 255, and a longer run uses another packet.

Read the supporting material.

  1. A Mathematical Theory of Communication

    Nokia Bell Labs · Communication entropy, coding, and noise; does not turn statistical information into a theory of semantic truth.

  2. Communication in the Presence of Noise

    Claude E. Shannon / MIT-hosted original paper · Band-limited sampling and communication; sampling examples here are editorial calculations.

Continue through the versioned study records.

Follow the comparisons.

Read the neighboring questions.