Reed solomon
Named by 3 essays across one field — each of them below, with the objects they name alongside it.
A polynomial through the gaps
Write the message as the coefficients of a polynomial and send its values instead. Any k of them determine the polynomial, so it does not matter which ones are lost — and it does not matter how many, as long as k survive.
![How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked.](/f/how-many-codewords-lie-within-each-radius-for-a-7-3-code-e1fb4777.svg)
Past half the distance
A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Error-correcting codeErasureBoundChannel capacityExhaustive searchFinite fieldHamming codeHamming distanceInterpolationLinear codeList decodingMinimum distance