Teaching objectives
What is information? How much does it "weigh"? Which codes are better? Can we correct errors in the transmission of information? This upper-secondary/university-level lab walks through information theory from its foundations to error-correcting codes, following in the footsteps of Hartley, Shannon, and Hamming. It consists of 22 rooms with a total estimated duration of about half an hour. We recommend using it alongside our game Oráculo Mentiroso.
What you'll learn
Students develop the ability to quantify uncertainty, design efficient coding systems, and reason about reliability when data becomes corrupted. The journey moves from observing to building: students design probability urns, a Huffman tree, prefix codes, and finally their own error-correcting code.
- Block A — Measuring information: the formula
i = −log₂ pand Shannon entropy are introduced through sliders; students design distributions with a given entropy and rank experiments by uncertainty. - Block B — Encoding: from decoding tables to the ambiguous-code problem; students build a prefix code by hand and use the Huffman machine to compress skewed messages (80/20) to below 0.78 bits/symbol.
- Block C — Guessing and lying: the student guesses using binary search, then faces an adversary who lies once; they learn that more questions are needed and discover Berlekamp's strategy.
- Block D — Errors and robustness: introduces Hamming distance, codes with
d_min = 3, the hypercube{0,1}⁴, and ends with designing an error-correcting code that withstands 10 % bit corruption.
Key mathematical ideas
- The information of an event is
i = −log₂ pbits; rare events carry more information. - Shannon entropy
H = −Σ pᵢ log₂ pᵢmeasures the average uncertainty of a source; it is the lower bound for any lossless code. - A prefix code guarantees unique decoding; the Huffman algorithm builds the optimal one by iteratively merging the two smallest probabilities.
- The Hamming distance between two binary words is the number of bits that differ; a code with
d_min = 2t + 1can correct t errors. - The hypercube
{0,1}^nis the natural space for binary codes: codewords are vertices separated by non-overlapping Hamming balls.
Room-by-room contents
Room 1 · What is information?
Introduces the central idea of the lab: receiving a message means ruling out possible worlds. A slider shows how many "worlds" remain after each message and how many bits it cost.
Student tasks
- Move the slider to see how possible worlds are reduced.
- Observe the relationship between discarded worlds and bits of information.
Room 2 · The surprise scales
Presents the formula i = −log₂ p: the more unlikely an event, the more bits it contributes. The student practises the calculation by solving three exercises in a row.
Student tasks
- Apply the formula i = −log₂ p to the given events.
- Solve three consecutive calculations correctly.
Room 3 · The entropy laboratory
Explores entropy H as the average uncertainty of a binary distribution. An interactive slider shows the H(p) curve from end to end.
Student tasks
- Move the slider from 0 to 1 to see how entropy changes.
- Find the value of p such that H = 0.5 bits.
Room 4 · Design an urn
A design challenge: the student distributes balls among three jars to reach exactly H = 1.24 bits. Connects the entropy formula to a concrete choice.
Student tasks
- Distribute the balls among the three jars.
- Verify that the resulting entropy is 1.24 bits.
Room 5 · Sort by uncertainty
Four experiments with different probability distributions. The student sorts them from lowest to highest entropy by dragging the cards.
Student tasks
- Visually analyse the distribution of each experiment.
- Drag them into the correct order from lowest to highest entropy.
Room 6 · Encoding = translating into bits
Introduction to the encoding block: not all codes cost the same, and entropy sets a floor that no efficient code can break. Introductory / visual room.
Student tasks
- Read the explanation and study the examples of codes with different costs.
Room 7 · Decode this
Direct practice: given a binary code table, the student receives a bit string and must write the original word it represents.
Student tasks
- Apply the code table to the received bit string.
- Write the decoded word correctly.
Room 8 · The ambiguous code trap
A bit string has more than one valid decoding. The student must find two different interpretations, motivating the need for prefix-free codes.
Student tasks
- Find two different decodings for the same string.
- Understand why this code cannot be used for unambiguous communication.
Room 9 · The Huffman machine
Animated visualisation of the Huffman algorithm: probability sliders show how the two smallest probabilities are merged at each step. The student looks for a nearly optimal distribution (L − H < 0.05).
Student tasks
- Move the probability sliders and observe the tree merges.
- Find a distribution where the average length L is nearly equal to H.
Room 10 · Build a prefix code
A construction challenge: the student invents a binary code for 4 letters such that no codeword is a prefix of another.
Student tasks
- Assign bit strings to the 4 letters.
- Verify that no string is a prefix of another.
Room 11 · Assign codes to letters
Drag-and-drop: the student drags bit strings onto each letter. The code must be prefix-free and the average length must be ≤ 1.85 bits/letter.
Student tasks
- Drag the correct bit string to each letter.
- Check that the average length satisfies ≤ 1.85 bits/letter and that the code is prefix-free.
Room 12 · Compress a skewed message
The source emits 80 % zeros and 20 % ones. The student works with pairs of symbols and designs a prefix code that compresses to ≤ 0.78 bits/symbol.
Student tasks
- Design a code for pairs of symbols (00, 01, 10, 11).
- Verify that the average length per symbol is ≤ 0.78 bits.
Room 13 · Guess with "less than N"
The lab thinks of a number between 1 and 8; the student must guess it in exactly 3 questions of the form "is it less than N?". Connects binary search with bits of information.
Student tasks
- Ask the 3 questions in the optimal order.
- Guess the number in no more than 3 attempts.
Room 14 · Now the computer guesses
The student thinks of a number between 1 and 8 and the computer asks questions following the optimal binary search strategy. The student observes how it halves the range each time.
Student tasks
- Think of a number and answer "Yes/No" honestly.
- Observe the computer's strategy and notice the bisection of the range.
Room 15 · Guess even if it lies
The lab may lie once. The student must guess a number between 1 and 4 in 5 yes/no questions despite that possible lie. Introduces the need for redundancy.
Student tasks
- Design a questioning strategy that tolerates one lie.
- Guess the number in 5 questions or fewer.
Room 16 · You guess, you can lie
The student is the one who may lie once; the computer applies the Berlekamp strategy and guesses it anyway. A first encounter with the robustness of error-correcting codes.
Student tasks
- Think of a number between 1 and 4 and answer, lying if you wish.
- Watch how the computer guesses it even with the lie.
Room 17 · Hamming distance
Defines the Hamming distance between binary strings of the same length as the number of positions where they differ. The student calculates distances on concrete examples.
Student tasks
- Read the examples of pairs of strings.
- Calculate the requested Hamming distance.
Room 18 · The Berlekamp strategy
Reveals how the computer guessed the number in Room 16 using 6 questions despite the lie: the trick is an error-correcting code with d_min = 3. Explanatory room.
Student tasks
- Read the explanation of the error-correcting code with d_min = 3.
- Connect the 6 questions from the previous room with the codewords.
Room 19 · When the channel lies
The channel corrupts 1 bit in each message. The student receives several strings with 1 error and must decide which original word each belongs to using minimum distance.
Student tasks
- Receive each corrupted message and calculate its distance to each codeword.
- Decide which word each message came from.
Room 20 · Design your own code
The student designs from scratch: first they choose the shortest codewords for three letters, then calculate what minimum distance is needed to survive three errors.
Student tasks
- Build the shortest codewords for three letters.
- Determine the minimum distance needed to correct three errors.
Room 21 · The hypercube
Geometric visualisation: the student selects vertices of the hypercube {0,1}⁴ maximising the minimum distance between them. Three difficulty levels (d ≥ 2, d ≥ 3, maximum number of vertices with d = 3).
Student tasks
- Select vertices of the hypercube with minimum distance 2 between them.
- Repeat with minimum distance 3 and find the maximum number of vertices.
Room 22 · Design an error-correcting code
Final challenge: the channel corrupts 10 % of bits. The student designs a binary code for 4 messages that decodes correctly at least 90 % of the time, penalising length.
Student tasks
- Define 4 codewords and the decoding rule.
- Verify that the success rate is ≥ 90 % and that the length is as short as possible.
Rooms to project
The most striking ones to show and discuss in class.