Concept

Reed solomon

A code whose messages are the coefficients of a polynomial and whose words are its values at fixed points. Any k of the values recover the message, so it meets the Singleton bound exactly and loses nothing to erasures.

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

A degree-2 polynomial over GF(11), and the 7 values sent. A grid of the finite field with the polynomial's value at each point marked, and the transmitted symbols picked out.

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.

computation · Error-correcting codes

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.

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.

computation · Error-correcting codes

Named alongside it

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

Error-correcting code Bound Erasure Exhaustive search Finite field Hamming distance Interpolation List decoding Minimum distance Polynomial Singleton bound Uniqueness

All concepts