Lessons and the learning game

Compression, encoding and checksums

Get a space probe's telemetry and pictures home over a noisy radio link, in Python on a Raspberry Pi.

The course

Compression, encoding and checksums is an advanced Coding course in seven lessons. The probe is called Kestrel, and every lesson runs on the gallery's traffic light circuit on a Raspberry Pi 4. Each step is checked against what the Pi prints or which lamp it lights.

  1. Bits and bytes: text as bytes, binary and hex, telemetry packed from 11 bytes of text into 5 with struct, and eight system flags in one byte.
  2. Run length: a star field picture shrunk from 128 bytes to 22, decoded to prove nothing was lost, and the noise that doubles it.
  3. Huffman: letter counts, a Huffman tree built with heapq, a status report coded in 290 bits instead of 592, and a decoder that walks the tree.
  4. Base64: an encoder and decoder written from the bits up, with padding, checked against Python's base64, and the one-third size cost.
  5. Parity and checksums: a seeded noisy link, a parity bit that catches every single flip and misses some doubles, a checksum fooled by swapped digits, and Fletcher-16, which is not.
  6. CRC: CRC-8 and CRC-32 bit by bit, checked against the published values and binascii.crc32, a table-driven version, and 1,000 noisy frames that CRC-32 catches every time.
  7. Project: a reliable file transfer.

The project

The finale sends a 24 by 8 picture over a link that damages about one frame in three. Each frame carries a sequence number, a length, 8 bytes of picture and a CRC-32. The receiver rejects any frame whose CRC does not match, and stop-and-wait resends repeat it until it arrives. Run length compression first cuts the picture from 24 frames to 4, and the lamps flash green for each frame that lands and red for each one rejected.

What the Pi's engine does differently

The Pi runs MicroPython 1.29, not CPython:

  • random is MicroPython's own generator. The noisy link is seeded, so it flips the same bits on every run, but not the bits CPython would flip.
  • binascii.crc32, base64 and struct behave as in CPython, so the course checks its hand-written versions against them.
  • int.to_bytes takes no signed argument here, so signed values are packed with struct (which is the better tool anyway).
  • time.monotonic_ns() follows the simulated clock, which charges every turn of a Python loop the same cost, so the CRC timings repeat exactly.

The catalog line also names an Arduino Uno. The course runs on the Pi only, where Python's bytes make every bit visible.