Concept

Erasure

A transmission error in which a symbol arrives marked as missing rather than as a wrong value. Erasures are easier to correct than errors, since the location is known and only the value has to be recovered, and a code that corrects any e errors handles 2e 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

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 Reed solomon Channel capacity Finite field Hamming code Interpolation Linear code Minimum distance Polynomial Random code Rank Singleton bound

All concepts