Concept

Singleton bound

The limit that a code of length n over q symbols, with any two words differing in at least d places, holds at most q to the power n − d + 1 words. Deleting d − 1 positions leaves every word distinct, which is the whole proof, and codes that meet it exactly are called maximum distance separable.

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

3 orthogonal squares of order 4, read as a code. A table of 16 words of length 5 over 4 symbols, one per cell of 3 orthogonal Latin squares of order 4: row, column and the entry in each square. Any two words agree in at most one position.

Orthogonal squares are a code

Write down each cell of a set of orthogonal Latin squares as a word — its row, its column, and its entry in each square — and no two words agree in more than one place. That is not a pleasant accident of the squares. It is exactly what being Latin and being orthogonal say, it makes the list an error-correcting code as good as any code of its size can be, and the squares a field builds turn out to be a Reed–Solomon code, the one on every compact disc.

computation · Latin squares

Named alongside it

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

Erasure Error-correcting code Finite field Hamming distance Interpolation Latin square Minimum distance Orthogonal latin squares Polynomial Projective plane Reed solomon Reed solomon code

All concepts