Concept

Redundancy

The part of a coded message that carries no new information, added so that errors in transmission can be detected or corrected. A code with more redundancy has fewer codewords for its length but can survive more damage, and the art of coding is getting the most protection for the least of it.

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

A four-by-four array holding every two-by-two block. A binary array, cyclic in both directions, drawn with its wrapped row and column, in which each of the sixteen two-by-two blocks appears exactly once.

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

computation · De bruijn

A word that survives losing any one of its bits. codeword 100110010110, a=0 mod 13; deletions at 1..12 all decoded.

A code that survives a lost bit

A flipped bit leaves the word the right length and wrong in one place; a lost bit leaves it one short, with no sign of where the gap was. Keep only the words whose 1s sit at positions adding up to a multiple of n + 1, and any single lost bit can be put back. The price is about log₂(n + 1) bits, the same as the Hamming code pays for a flip.

computation · Error-correcting codes

Named alongside it

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

Error-correcting code Construction Counting argument De bruijn sequence De bruijn torus Eulerian path Exhaustive search Graph Hamming code Modular arithmetic Necklace Torus

All concepts