Concept

Channel capacity

The greatest rate, in message bits per transmitted symbol, at which a noisy channel can carry information with an error probability as small as desired. Shannon computed it in 1948 and proved it is both achievable and impossible to beat, which fixed a hard limit on every coding scheme.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

Channel capacity 1 − H(p), and three codes at p = 0.1. The capacity of the binary symmetric channel plotted against its flip probability, with the rates of repetition, the Hamming code and no coding marked at one flip probability.

The rate a noisy channel allows

A channel that flips one bit in ten can still carry messages with as few errors as anyone likes — at up to 0.531 message bits per transmitted bit, and at no rate above that. The number is Shannon's capacity, 1 − H(p). Repetition reaches reliability only by sending nothing; a code chosen at random gets there at any rate below the limit; and the reason there is a limit at all is a count of how many flip patterns a block of noise can hold.

computation · Error-correcting codes

Decoding from 20 + m random combinations: the chance it works. Bars for the exact probability that 20 plus m random binary combinations of 20 message bits have full rank, with simulated frequencies as dots, for m from zero upwards.

Erasures a code can see

If a channel loses bits instead of flipping them, and says which ones it lost, its limit rises from 1 − H(p) to 1 − p — and reaching it needs nothing cleverer than a random matrix and the solution of simultaneous equations. A random code needs, on average, 1.607 symbols more than the message it carries, whatever the message's length, and that number is a constant Erdős proved irrational.

computation · Error-correcting codes

A code made of the flats of a space. All 32 words of the Reed–Muller code RM(1, 4), each drawn on the sixteen points of the affine space of four dimensions over two elements: one word of weight 0, one of weight 16 and thirty of weight 8.

Parallel planes take a vote

Draw a four-dimensional space with two values to a coordinate as a 4 × 4 grid, and mark its hyperplanes: thirty-two patterns any two of which differ on eight of sixteen squares. A polynomial's top coefficient can be read off any plane, and parallel planes do not overlap, so an error spoils only one vote. One of them flew to Mars, and in 2016 it turned out to reach Shannon's limit.

computation · Finite geometry

Named alongside it

The objects these essays reach for when they reach for this one.

Error-correcting code Hamming code Hamming distance Random code Binomial distribution Entropy Erasure Exhaustive search Finite field Finite geometry Linear code Polynomial

All concepts