Data compression

The formula

The floor everything else is measured against is Shannon entropy — the average number of bits per symbol you cannot beat with lossless coding:

H(X) = - sum over i of  p_i · log2(p_i)     [bits per symbol]

Reading: for a source that emits symbol i with probability p_i, H is the average information content. A rare symbol (p_i small) carries many bits; a common one carries few. Sum weighted by how often each shows up.

Shannon's source coding theorem says the average codeword length L of any uniquely decodable code obeys:

L >= H(X)     and you can get within one bit:  H(X) <= L < H(X) + 1

Reading: you can compress down toward H, never below it, and a good code gets you within a bit of it per symbol.

One validity limit worth flagging: H(X) as written assumes symbols are independent. For real data streams with memory — correlated samples, repeated structure — the true floor is the entropy rate, which is lower, and that gap between per-symbol entropy and entropy rate is precisely what dictionary coders like LZ77 harvest. (A stream of ABABAB... has 1 bit/symbol of marginal entropy but compresses to nearly nothing.)

Any prefix code (no codeword is the start of another) must satisfy the Kraft inequality on its codeword lengths L_i:

sum over i of  2^(-L_i)  <=  1

Reading: short codewords are a budget. Spend a 1-bit code and you have used half the budget; you cannot hand out short codes to everything.

Where you meet it

Telemetry through a thin downlink. A test stand or a flight article produces more channels at higher rates than the link can carry. Lossless compression on the source side buys margin: if your data has structure — slowly varying temperatures, repeated sync words, mostly-zero status fields — its entropy per sample is well under the 16 or 32 bits you allocated, and you can pack it. What compression cannot do is beat entropy, so a stream of true white noise from a fully-exercised ADC will not shrink. That is a useful sanity check, not a failure.
ZIP and gzip on the bench. Every time you zip a deliverable, gzip a log tarball, or pull a .tar.gz from a build server, you are running DEFLATE. It is LZ77 plus Huffman coding under the hood, and it is why a directory of text logs collapses to a fraction of its size while a directory of JPEGs barely moves — the JPEGs are already near their entropy floor.
PNG in the review package. PNG stores images with DEFLATE after a per-row prediction filter. This is why a screenshot of a schematic (large flat color regions, low entropy) compresses hard, while a photograph in PNG stays large. Reach for PNG when you need lossless and pixel-exact; reach for JPEG only when you can accept lossy.
Firmware and config images. Compressing a firmware payload to fit a flash budget, or a filesystem image for an embedded target, is the same math on a fixed-size constraint instead of a rate constraint.

How it works

Two ideas do most of the work, and real compressors stack them.

Model, then code. A compressor first models the data — how likely is the next symbol — then assigns short codes to likely symbols and long codes to unlikely ones. Entropy coding (Huffman, arithmetic) does the second step optimally given the model. The model is where the wins actually come from. Better model, better compression; the coder is nearly a solved problem.

Huffman builds an optimal prefix code by merging the two least-likely symbols repeatedly into a binary tree, from the bottom up. It is provably optimal among codes that use a whole number of bits per symbol. That integer-bit constraint is also its ceiling: for a source with probabilities [0.5, 0.25, 0.125, 0.125] the entropy is exactly 1.75 bits/symbol, and Huffman hits it exactly with codeword lengths 1, 2, 3, 3 (Kraft sum 2^-1 + 2^-2 + 2^-3 + 2^-3 = 1.0). But for a source where the ideal code length is fractional — a symbol wanting 0.3 bits — Huffman must round up to 1 bit and loses.

Arithmetic coding removes the whole-bit restriction. It encodes an entire message as a single fraction in [0, 1), narrowing the interval by each symbol's probability, so the per-symbol cost approaches the true entropy including fractional bits. That is why modern codecs that need every last percent (and don't mind the CPU) use arithmetic or range coding instead of Huffman.

Dictionary coding attacks a different redundancy: repetition. LZ77 keeps a sliding window of recently seen bytes and replaces a repeated run with a back-reference — "go back 214 bytes, copy 9." In DEFLATE that window is up to 32 KB (32,768 bytes). LZ77 finds the repeats, Huffman then codes the resulting stream of literals and back-references. This is the one-two punch in ZIP, gzip, and PNG.

The gotchas that bite:

You cannot beat entropy, and you cannot compress everything. By counting, no lossless scheme shrinks every possible input — if some inputs get shorter, others must get longer. Compressing already-compressed data (zipping a JPEG, gzipping a .zip) usually adds a few bytes of overhead for nothing.
Random-looking is not compressible. Encrypted data and good PRNG output have entropy at the maximum, so they will not shrink. If your "compressor" claims to shrink random data, it is either lossy or wrong.
Lossless vs lossy is a hard line. DEFLATE, ZIP, PNG, FLAC are lossless — bit-exact round trip. JPEG, MP3, and H.264 throw away data you supposedly won't miss. Never run a lossy codec on data you have to reconstruct exactly (measurement records, checksummed payloads, source code).
Small files pay overhead. Headers, Huffman tables, and dictionary startup cost mean a 40-byte file can grow when compressed. Compression pays off in bulk.
Model mismatch kills ratio. A compressor tuned for English text does poorly on binary sensor data, and vice versa. The entropy floor depends on the true statistics; if your model is wrong, you leave bits on the table.

The practical rule for an engineer sizing a downlink or a flash budget: estimate the entropy of your actual data, not its raw bit width. Sixteen-bit samples that only ever move a few counts carry maybe 4 or 5 bits of real information each. That gap is your compression headroom, and no tool will give you more than it.

History

The whole field starts with one paper. Claude Shannon, working at Bell Labs, published "A Mathematical Theory of Communication" in two parts in the Bell System Technical Journal in 1948 ^[1]^[2]. In it he defined entropy as the measure of information, and proved the source coding theorem: entropy is the hard floor for lossless compression, and you can code arbitrarily close to it ^[1]. Everything since is engineering toward that floor.

The first practical optimal code came from a student. In 1951 at MIT, Robert Fano gave his information-theory class a choice between a final exam and a term paper on finding the most efficient binary code — without mentioning it was an open problem he and Shannon had already struggled with. David Huffman worked at it, nearly gave up, then hit on building the tree from the bottom up by merging the least-likely symbols, and proved it optimal. He published "A Method for the Construction of Minimum-Redundancy Codes" in 1952 ^[3]^[4]. The student's bottom-up method beat the top-down Shannon-Fano code his professor had co-invented ^[3].

Two decades later, Abraham Lempel and Jacob Ziv introduced the dictionary approach: LZ77 in 1977 and LZ78 in 1978, giving compressors a way to exploit repetition without knowing the statistics in advance ^[5]^[6]. Around the same time, Jorma Rissanen at IBM published the modern form of arithmetic coding in 1976, generalizing the Kraft inequality to reach the fractional-bit performance Huffman couldn't ^[7].

The piece most engineers touch daily came from Phil Katz. For version 2 of his PKZIP tool (shipped as PKZIP 2.04 in December 1992–January 1993, after first appearing in a 1991 alpha) he designed DEFLATE, combining LZ77-style back-references with Huffman coding ^[5]^[8]. It was later written up as RFC 1951 in 1996 and became the engine inside gzip, PNG, and the ZIP format ^[8]. When you zip a folder in Huntsville or anywhere else, you are running Katz's combination of Huffman's 1952 code and Lempel and Ziv's 1977 dictionary — all measured against Shannon's 1948 floor.

Related tools

/tools/snr-enob — signal-to-noise and effective bits; entropy of a sample stream tracks its real ENOB, not its nominal bit width
/tools/adc-resolution — how many bits a converter actually delivers, which bounds how much telemetry there is to compress
/tools/link-budget — the downlink margin that compression is bought to protect
/tools/free-space-path-loss — the loss that sets how thin the link is in the first place
/tools/db-converter — decibels and ratios, the neighboring language for talking about margins

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →