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 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as random code — the same set of essays touches all of them, so they are one junction rather than several.

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

Named alongside it

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

Error-correcting code Hamming code Random code Binomial distribution Entropy Erasure Hamming distance Linear code Rank Reed solomon

All concepts