Data Compression
Introduction
Compression reduces the number of bits needed to represent data — for storage on flash, bandwidth on serial links, or streaming on networks. Lossless compression recovers the exact original (firmware images, logs); lossy compression discards detail humans barely notice (audio, video, images).
Embedded systems use compression when RAM and bandwidth are tight but content is large — OTA updates, SD card logs, camera streams on edge devices.
Lossless vs lossy
| Lossless | Lossy | |
|---|---|---|
| Reconstruction | Bit-exact | Approximate |
| Ratio | Moderate | High |
| Examples | gzip, LZ4, Huffman | JPEG, MP3, H.264 |
| Use when | Code, text, sensor archives | Multimedia, previews |
Entropy and Huffman coding
Frequent symbols get shorter codes — Morse code is the intuition.
Huffman algorithm (outline):
- Count symbol frequencies in input.
- Build a binary tree merging lowest two nodes repeatedly.
- Assign 0/1 to left/right branches → variable-length codes.
- Prefix-free codes — no ambiguity when decoding.
| Symbol | Frequency | Huffman code (example) |
|---|---|---|
| A | 45% | 0 |
| B | 30% | 10 |
| C | 25% | 11 |
Average bits per symbol drops below fixed 8-bit ASCII for skewed distributions.
Tools: gzip uses Huffman + LZ77; understand principles, use libraries in production.
Dictionary / LZ methods
LZ77 / LZ78 family replace repeated phrases with (distance, length) pointers to earlier data.
| Variant | Notes |
|---|---|
| LZ77 | Sliding window — DEFLATE (gzip, zlib) |
| LZ4 | Very fast decompress — embedded logs |
| LZMA | High ratio, slow — firmware distribution |
Embedded tip: prefer LZ4 or heatshrink when decompress RAM and CPU are limited.
Run-length encoding (RLE)
Simple lossless: AAAABBC → 4A2B1C. Works on icon fonts, sparse bitmaps — poor on noisy sensor data.
Lossy: images and video (overview)
JPEG (still images)
- Block DCT (frequency domain)
- Quantize coefficients (lossy step)
- Zigzag + Huffman
Video frames
| Frame type | Content |
|---|---|
| I-frame | Keyframe — standalone image |
| P-frame | Predicted from previous |
| B-frame | Bidirectional prediction |
GOP (Group of Pictures): I P P P I ... — trade seek latency vs compression.
H.264 / H.265: DCT + motion compensation — standard for IP cameras; hardware encoder on many SoCs.
Embedded: offload to VPU if available; MCU cannot encode 1080p in software realistically.
Choosing a scheme
| Scenario | Suggestion |
|---|---|
| OTA firmware | gzip or xz on host; decompress in bootloader if space allows |
| Serial telemetry | delta encoding + variable int, or CBOR/MessagePack |
| SD card CSV logs | LZ4 stream |
| Camera module on Pi | H.264 hardware path |
Always measure CPU, RAM, and latency on target hardware.
Relevant topics
Starting points
- Compress a repetitive log file with gzip and LZ4 — compare size and time.
- Hand-encode a tiny Huffman tree for 4 symbols with given frequencies.
- Estimate whether your MCU has RAM for a 32 KB LZ window.
- Inspect JPEG with a tool showing DCT blocks (e.g. online JPEG analyzer).
Focus points
- Lossless required for executable firmware — bit errors brick devices.
- Decompress buffer size must fit RAM — streaming APIs help.
- Compression bombs — cap input size when decompressing untrusted OTA.
- Lossy parameters (JPEG quality) affect ML vision pipelines downstream.
Key points
- Lossless preserves exact data; lossy trades quality for size.
- Huffman assigns short codes to frequent symbols.
- LZ family exploits repeated substrings — gzip, LZ4, LZMA.
- Video uses I/P/B frames and motion compensation — usually needs hardware on embedded.