Lesson plan

Compression, encoding and checksums lesson plan

Get a space probe's telemetry and pictures home over a noisy link, in Python on a Raspberry Pi: bits and bytes, run length and Huffman coding, Base64, parity, checksums and CRC-32, ending in a file transfer that survives the noise.

4 chapters, 7 lessons, about 6 hours, on the Raspberry Pi 4 Model B. Every lesson runs in the browser, with nothing to install.

The unit

Objectives and materials

By the end, students can

  • What the probe sends, packed tight, and the simplest compression.
  • Shorter codes for common letters, and safe characters for any bytes.
  • Catch the bit flips: parity, checksums and the CRC.
  • A picture home, intact.

Materials for the whole unit

  • Pushbutton
  • Raspberry Pi 4 Model B
  • Traffic light module

Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.

Chapter 1. About 1 h 40 min

Bytes

What the probe sends, packed tight, and the simplest compression.

LessonTimeWhat students do
Bits and bytesEverything a space probe sends home is bytes. Text as bytes, binary and hex, packing telemetry into 5 bytes instead of 11 with struct, and eight on-off flags squeezed into a single byte with shifts and masks.50 min
  1. Run it: text is numbers
  2. Hex: binary for people
  3. Pack the telemetry
  4. Unpack it at mission control
  5. Eight flags in one byte
Run lengthThe simplest compression there is: a picture of space is mostly black, so say "37 dark pixels" instead of listing them. Runs, packing them into bytes, decoding to prove nothing was lost, and the input that makes it worse than nothing.50 min
  1. Run it: a picture of space
  2. Find the runs
  3. Pack the runs into bytes
  4. Decode, and prove it
  5. When compression makes it bigger

Materials

  • Pushbutton
  • Raspberry Pi 4 Model B
  • Traffic light module

Check for understanding

Each student finishes "Run length" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "When compression makes it bigger".

Chapter 2. About 1 h 40 min

Codes

Shorter codes for common letters, and safe characters for any bytes.

LessonTimeWhat students do
HuffmanGive common letters short codes and rare ones long codes: count letters, build a Huffman tree with a priority queue, encode a status report in far fewer than 8 bits a letter, and decode it by walking the tree.50 min
  1. Run it: some letters are common
  2. Build the tree
  3. Encode the report
  4. Decode by walking the tree
  5. Bits per letter
Base64Some links only carry text: email, JSON, a URL, an old radio modem. Base64 turns any bytes into 64 safe characters, 3 bytes to 4 at a time. Write the encoder and decoder from the bits up, with padding, and check them against Python's own.50 min
  1. Run it: bytes a text link breaks
  2. 3 bytes in, 4 characters out
  3. Padding
  4. Decode
  5. The price of safety

Materials

  • Pushbutton
  • Raspberry Pi 4 Model B
  • Traffic light module

Check for understanding

Each student finishes "Base64" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "The price of safety".

Chapter 3. About 1 h 40 min

Checks

Catch the bit flips: parity, checksums and the CRC.

LessonTimeWhat students do
Parity and checksumsSpace is noisy, and a flipped bit turns -12 into -76. Simulate the link with seeded bit flips, catch single flips with a parity bit, watch two flips sneak past, then add a checksum, find its blind spot, and close it with Fletcher's checksum.50 min
  1. Run it: a noisy link
  2. A parity bit
  3. Two flips
  4. A checksum, and its blind spot
  5. Fletcher: a sum that sees order
CRC checksThe check inside Ethernet, ZIP, PNG and spacecraft links: a cyclic redundancy check is the remainder of a polynomial division done with XOR. Write CRC-8 and CRC-32 bit by bit, prove CRC-32 against binascii, speed it up with a table, and test it against a thousand noisy frames.50 min
  1. Run it: division with XOR
  2. CRC-32
  3. Check it against binascii
  4. Faster with a table
  5. A thousand noisy frames

Materials

  • Pushbutton
  • Raspberry Pi 4 Model B
  • Traffic light module

Check for understanding

Each student finishes "CRC checks" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "A thousand noisy frames".

Chapter 4. About 1 h

Project

A picture home, intact.

LessonTimeWhat students do
Project: a reliable file transferBring the course together and get a picture home over a link that corrupts a third of everything: frames with a sequence number and a CRC-32, a receiver that rejects bad ones, stop-and-wait resends until every frame arrives, run length compression to send fewer frames, and lamps that show each frame land.60 min
  1. Run it: frames
  2. The receiver checks every frame
  3. Ask again
  4. Compress first
  5. Lamps for every frame
  6. Share the mission

Materials

  • Pushbutton
  • Raspberry Pi 4 Model B
  • Traffic light module

Check for understanding

Each student finishes "Project: a reliable file transfer" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Share the mission".

Your class

Teach this unit as a class

Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.

The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.