Information Theory

Shannon entropy is the average surprisal of a field's values in bits: the sum of p times log2(1/p) over every value. It measures how uncertain the next value is, not how many distinct values exist.

Ten bits is the surprisal of an outcome with probability 1/1024, since -log2(1/1024) = 10. One bit is the uncertainty resolved by one fair yes/no answer, so rarer outcomes carry more bits and a certain one carries zero.

The chain rule prices a column pair as the first column's entropy plus whatever surprise the second still holds: H(X,Y) = H(X) + H(Y|X). Storing both together therefore never costs more than storing each separately, and usually costs less.

Conditional entropy H(data centre | region) is the data-centre uncertainty left, on average, once the region is known. At 0.54 bits against 2 bits unconditioned, the region nearly fixes the data centre, but not completely.

Zero mutual information means the signal and the label are independent in the distribution you measured: observing one removes none of the other's uncertainty. The reading is symmetric, it is an estimate, and it says nothing about the signal's value alongside other signals.

Lossless compression must be reversible, so distinct inputs need distinct outputs. There are more n-bit inputs than shorter strings, so no map can shrink them all; a scheme that shrinks one input must expand another.

Already-compressed and encrypted blocks have no repeated sequences and a near-uniform byte distribution, so the coder finds nothing to exploit and emits at least as much as it read, plus headers — a few bytes of growth per block.

Kraft's inequality: sum two to the minus each codeword length and compare with 1. For 1, 2, 3, 3 and 3 that sum is 1.125, above the budget, so no prefix code has those lengths.

Prefix-free means no codeword is the opening of another, so a decoder reading bit by bit knows a symbol has ended the instant it recognises one. Without that property it must look ahead or carry explicit lengths and separators.

A stored-raw block lets the writer emit a block's original bytes whenever coding them would be bigger, so worst-case expansion is capped by that block's small header rather than by the coder's behaviour — usually a small fraction of a percent.

Run-length encoding expands any input whose symbols rarely repeat: a single symbol still costs a count plus the symbol, so alternating bytes double in size. It pays only when the average run is longer than one pair.

An arithmetic coder starts with [0,1) and narrows it once per symbol, keeping the slice whose width is that symbol's probability. The final interval's width is the message's probability, and a number inside it identifies the whole message.

A sliding-window compressor keeps the most recent N bytes it has already produced as its window. When the next bytes repeat something inside that window, it emits a pair of numbers, a distance back and a match length, instead of the bytes.

Huffman coding repeatedly removes the two lowest-frequency trees and joins them under a new node weighted by their sum, until one tree remains. Each symbol's code is its root-to-leaf path, so rare symbols sink deepest and frequent ones stay shallow.

Nothing by themselves — they remove no bytes at all. They reshape the symbol distribution so that the entropy coder behind them, which is the stage that actually removes bits, meets a far more skewed and predictable stream.

Anything whose value is its exact bits must stay lossless: executables, archives, source, ledgers, and anything later checked by a digest or signature. Lossy fits terminal media a human tolerates approximately, never the master copy everything else is derived from.

Bit depth b splits a fixed range R into 2^b levels, so the uniform step is R divided by 2^b and round-to-nearest keeps every in-range sample within half a step. Each added bit halves the step and drops the error floor by about 6 dB.

Re-rounding values that already sit on the same grid changes nothing. Any gain change, resample or range change moves the grid under them, so each such pass can add another half step, and the coarsest stage in the chain dominates the total.

R(D) is the lowest average rate, in bits per source symbol, at which a source can be reproduced with average distortion at most D under a chosen distortion measure. It is a bound no scheme beats, non-increasing and convex, so extra bits buy steadily less.

Rounding error is bounded by half a quantization step and sits at a fixed low level. Clipping is unbounded: samples outside the input range flatten onto the endpoint, producing signal-correlated distortion that extra bits cannot reduce.

A parity recheck catches every odd number of flipped bits in the codeword and misses every even number. It cannot say which bit flipped, cannot repair anything, and is blind to bits that were reordered rather than flipped.

Channel capacity is a reliable-rate ceiling. Any code carrying fewer than 0.53 data bits per channel use can be made as close to error-free as you like by using long enough blocks; no code above that rate can, however much redundancy it adds.

A binary symmetric channel flips each transmitted bit independently with probability p, and the receiver cannot see which bits changed. With p = 0.001 a thousand-bit block averages one flip, yet only about 37 percent of blocks arrive clean.

Repair has two halves: finding the damaged position and fixing its value. An erasure hands you the position for free, so only the value must be recovered, which takes roughly half the redundancy a silent flip of unknown location needs.

An additive sum is unchanged by reordering whole words, by inserting or deleting a word that adds nothing, and by two changes that cancel each other. Any change confined to a single word is caught, which is what makes the holes structural rather than random.