Concept

Reed solomon code

An error-correcting code whose codewords are the values of low-degree polynomials at distinct points of a finite field. Any k of its n symbols recover a message of k symbols, so it survives the loss of any n minus k of them.

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

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

The longest code that survives every erasure

A Reed–Solomon code of k symbols can lose any n − k of its n and still be read. Over an alphabet of q symbols it can be at most q + 1 long — and it is conjectured that no code with the same perfect tolerance can ever be longer, apart from one family of exceptions in even characteristic. A search through every possible code for small alphabets confirms it cell by cell, a proof exists when q is prime, and for every other q the question is open.

computation · Error-correcting codes

Named alongside it

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

Error-correcting code Finite field Duality Erasure Exhaustive search Hamming distance Latin square Linear algebra Orthogonal latin squares Projective plane Singleton bound

All concepts