A code that survives a lost bit

Every code met so far has been built against one kind of damage: a symbol that arrives wrong. Distance is a picture drew a message as a corner of a cube and an error as a step to a neighbouring corner; finding the error without reading the message located a single wrong bit by the Hamming code’s syndrome; erasures a code can see handled symbols known to be missing, at known places. All of them assume the word arrives at its proper length, so that bit five of what was received is bit five of what was sent.

Reed–Solomon codes, which a polynomial through the gaps built, make the same assumption. A different and nastier failure breaks it. A bit is not changed but lost — a clock slips, a reader skips a mark, a molecule in a DNA strand is not copied — and the received word is one bit short, with every bit after the gap shifted one place left and nothing to show where the gap was. Against this, a substitution-correcting code is useless: a lost bit near the start changes almost every position of the received word, which is far from every codeword. This essay is about the family of codes that answers it, found by Rom Varshamov and Grigory Tenengolts in 1965 for a different purpose, and shown by Vladimir Levenshtein the same year to correct a single lost bit or a single inserted one.

One congruence on the positions of the ones #

Number the bits of a word $x_1 x_2 \ldots x_n$ from the left, and add up the positions that hold a 1: the weighted sum $\sum i\,x_i$. The Varshamov–Tenengolts code $\mathrm{VT}_a(n)$ is every word of length $n$ whose weighted sum leaves remainder $a$ on division by $n + 1$. The first figure’s codeword is $100110010110$, with ones at positions 1, 4, 5, 8, 10 and 11, adding to 39, which is three times 13. It belongs to $\mathrm{VT}_0(12)$.

That is the whole definition, and it is not obvious that it should do anything. The Hamming code, by contrast, is a carefully designed linear subspace whose parity checks are the binary digits of the positions; here there is one congruence on one number. Its power comes from a fact about what a deletion does to the weighted sum. Suppose a bit is lost, and suppose $w$ ones and some number of zeros lie to its right. Every bit to the right moves one place left, so each of the ones there loses one from its position, and the weighted sum falls by $w_\text{right}$, the number of ones to the right. If the lost bit was itself a 1 at position $p$, the sum falls by $p$ as well. Either way the receiver can compute the shortfall $D$ — the remainder $a$ minus the weighted sum of what arrived, modulo $n + 1$ — and that shortfall is a number between 0 and $n$ that encodes where the bit went.

Levenshtein’s rule for putting it back #

Levenshtein’s decoder reads two numbers off the received $n - 1$ bits: the number of ones $w$ and the shortfall $D$. The rule is then mechanical:

• if $D \le w$, a 0 was lost, and it goes back in at a place with exactly $D$ ones to its right;
• if $D > w$, a 1 was lost, and it goes back in at a place with exactly $D - w - 1$ zeros to its left.

The first case is the arithmetic above: a lost 0 costs the sum nothing itself, only the $D$ ones to its right that shifted. In the second case a lost 1 at position $p$ costs $p$ plus the ones to its right, and $p$ equals one more than the zeros to its left plus the ones to its left; adding the ones on both sides gives $w$, so the shortfall is $w + 1$ plus the zeros to the left, which is why the count is $D - w - 1$.

The hero runs the rule on all twelve deletions. Losing bit 1, a 1 with five ones after it, leaves $D = 6 > 5$, so a 1 goes back with no zeros before it: the front. Losing bit 9, a 0, leaves $D = 2 \le 6$, so a 0 goes back with two ones to its right. The repair is not always at the position the bit came from. Losing bit 2 or bit 3, both 0s in the run $00$, gives the same received word, and the decoder puts a 0 back somewhere in that run; the result is the same codeword either way, because removing any bit of a run of equal bits gives the same string. A decoder for deletions does not need to know which bit was lost, only what the word was.

Every codeword, every deletion #

A rule derived in a paragraph should be tested exhaustively, and at these lengths it can be. For each $n$ from 4 to 16 the figure lists every word of $\mathrm{VT}_0(n)$, deletes each of its $n$ bits in turn, decodes, and compares — 61,696 deletions at $n = 16$ alone, from 3,856 codewords — and not one is decoded wrongly. A second, independent check confirms the property the decoder relies on: for every $n$ up to 12, no word of length $n - 1$ can be reached by one deletion from two different codewords, so the received word always determines the codeword uniquely, whatever decoder is used.

The last column is the cost. A code with $|C|$ words of length $n$ carries $\log_2|C|$ bits of message, and the rest, $n - \log_2|C|$, is redundancy. For $\mathrm{VT}_0(n)$ it is 2.00 bits at length 4, 3.00 at 7, 4.09 at 16 — always close to $\log_2(n + 1)$, which is exactly the redundancy of the Hamming code of length $n$, the best possible for correcting one substituted bit. Correcting a lost bit, whose position the received word does not even reveal, costs no more than correcting a flipped one. Levenshtein proved that this is the right order: no code correcting one deletion can have redundancy less than about $\log_2 n$.

The Hamming syndrome, added instead of combined #

The congruence has a twin that the earlier essays already met. The Hamming code of length $n = 2^m - 1$ is also defined by the positions of a word’s ones: write each position $i$ in binary, as a string of $m$ bits, and combine the positions of the ones by adding their binary digits without carrying — the exclusive or. The result is the syndrome, and finding the error without reading the message showed that the codewords are exactly the words whose syndrome is zero, and that a single flipped bit at position $p$ changes the syndrome by exactly $p$, which is how the decoder finds it.

The Varshamov–Tenengolts code is the same recipe with ordinary arithmetic. Combine the positions of the ones by adding them with carrying, modulo $n + 1$, and keep the words whose total is zero. A flip at position $p$ would change this sum by $\pm p$ as well — so the same set of words also corrects a single flip that changes a 0 to a 1 or a 1 to a 0, when the receiver knows which direction is possible, which is the asymmetric problem Varshamov and Tenengolts were solving. But ordinary addition has a property the exclusive or lacks: it respects order. Shifting every bit after a gap one place to the left subtracts a predictable amount from an ordinary sum, the number of ones that moved, and the exclusive or of shifted positions has no such regularity at all. That one property, the compatibility of the sum with sliding, is what makes the construction correct deletions, and it is why the Hamming code, built on carry-less addition over the field of two elements, cannot.

So two of the most useful codes for single errors are one formula, $\sum i\,x_i$, evaluated in two different number systems. In the field of $2^m$ elements it corrects a substitution and nothing else; in the integers modulo $n + 1$ it corrects a deletion, an insertion, or a one-directional flip. The redundancy is $\log_2(n + 1)$ in both, because both store one number between 0 and $n$ — the size of the syndrome — and that number is all that either decoder needs.

How many words one deletion can reach #

Codes for substitutions are understood through balls: around each codeword, the words one flip away, $n$ of them, and a code works if the balls do not overlap. The best a code can be turned that into the Hamming bound, $2^n/(n + 1)$ codewords at most. Deletions have balls too — around each word, the shorter words one deletion can produce — but the balls are not all the same size.

The figure counts them for every word of 12 bits. Deleting a bit inside a run of equal bits gives the same result wherever in the run the deletion happens, so the number of distinct results is exactly the number of runs. The word $000000000000$ has one run and one result. The word $010101010101$ has twelve runs and twelve results. A random word has about half its positions at the start of a new run, so the average is 6.5 — the bell in the figure, which is the binomial distribution of the number of places where adjacent bits differ.

The unequal balls change the counting argument. A code may hold more words where the balls are small, among the words with few runs, so the sphere-packing estimate is not a bound in the same way, and Levenshtein’s asymptotic answer — the largest code correcting one deletion has about $2^n/n$ words — comes from a more careful argument that weights each word by its run count. The ball of a word with few runs is small because deletions inside long runs are indistinguishable, which is the same reason the decoder could not and did not need to tell bits 2 and 3 apart.

Fifteen codes for the price of one #

The residue $a$ was arbitrary, and every choice works: the decoder only needs to know which $a$ the sender used. So the $2^n$ words of length $n$ fall into $n + 1$ codes, each correcting a single deletion, and they share out the words almost evenly. The figure draws the fifteen codes of length 14. The largest is $\mathrm{VT}_0(14)$ with 1,096 words, the others have between 1,091 and 1,094, and $2^{14}/15 \approx 1092.3$ is the average.

The sizes are not arbitrary either. Counting the words whose weighted sum has a given remainder is counting subsets of $\{1, \ldots, n\}$ with a given sum modulo $n + 1$, and it has an exact answer, found by Ginzburg in 1967: a sum over the odd divisors of $n + 1$ of Euler’s $\varphi$, the Möbius function and a power of two. Every count in the figure, and every count for every length from 4 to 16 and every $a$, equals that divisor sum. It has precisely the shape of the formula that counts necklaces — binary strings up to rotation — which every necklace in order used to list Lyndon words. The resemblance is not a coincidence: rotating a subset of $\mathbb{Z}/(n+1)$ shifts its sum by a multiple of its size, so the codes and the necklaces are two ways of grouping the same subsets. A code against lost bits turns out to be a question about how $n + 1$ factors.

Nothing larger exists, at these lengths #

A code defined by one congruence ought to be beaten by something cleverer. The figure looks for something cleverer by brute force: among all $2^n$ words of length $n$, the largest set in which no two words share a word one deletion away. That is a maximum independent set in a graph of $2^n$ vertices, and branch and bound finds it for every length up to 7. The answers are 2, 2, 4, 6, 10 and 16 — exactly the sizes of $\mathrm{VT}_0(n)$ at every length. At these lengths, the one-line code is as large as any code that corrects a lost bit can be.

The search stops at 7 because the graph grows quickly; at length 8 it has 256 vertices and the bound that makes the search fast becomes weak. Neil Sloane, surveying these codes in 2002, recorded that searches by others had confirmed the same equality a few lengths further, and conjectured that it holds at every length. The conjecture is open: nobody has proved that $\mathrm{VT}_0(n)$ is the largest single-deletion code for every $n$, and nobody has found a length where it is not. The figure is a proof of the statement for $n \le 7$ and evidence beyond.

What one congruence cannot do #

The congruence corrects one deletion, or one insertion — Levenshtein showed the two are equivalent, since a code that separates the deletion balls of its words also separates their insertion balls — and nothing more. Two lost bits defeat it completely. Codes correcting several deletions exist, and are much harder to build: for $s$ deletions the best known constructions use redundancy around $c\,s \log n$ for constants $c$ that have been coming down only recently, and the optimal constant is not known even for two. A substitution and a deletion together, or a burst of adjacent losses, need yet other designs.

The figures also say nothing about random deletions at a steady rate, which is how a real channel behaves. A channel that loses each bit independently with probability $p$ has a capacity — the best rate of reliable communication — and, unlike the erasure channel’s $1 - p$, nobody knows what it is. Upper and lower bounds have been proved and computed, and they do not meet for any $p$ strictly between 0 and 1. That the simplest synchronisation error has an unknown capacity, sixty years after Shannon computed the capacity of every memoryless channel, is because a deletion couples every position to every other, and the received sequence of a deletion channel is a random subsequence of what was sent — the object the longest thread between two random strings studied, whose own growth constants are unknown.

Still open: two lost bits #

The cleanest open question is about two deletions. A congruence on $\sum i\,x_i$ handles one; adding a congruence on $\sum i^2 x_i$, or on sums over runs, handles two in several published constructions, with redundancy about $4\log_2 n$ or better. The lower bound for two deletions is about $2\log_2 n$. Whether the factor of two can be closed — whether two deletions can be corrected as cheaply, relative to one, as several substitutions can be by the cyclic codes of the BCH family and their relative built from an icosahedron — is not known, and the constructions that come closest are recent and intricate.

For a single deletion the remaining question is the one Sloane posed. $\mathrm{VT}_0(n)$ is optimal at every length anyone has checked and has never been beaten. A proof would need a way of showing that a deletion code cannot be enlarged that works at every length at once — an argument from the structure of deletion balls, which vary in size, rather than from a count of them — and no such argument is known.

A sum that remembers where the gap was #

Keep the words of length $n$ whose ones sit at positions adding up to a multiple of $n + 1$, and any single lost bit can be put back: the number of ones received and the shortfall in the weighted sum say whether a 0 or a 1 went, and where. Every codeword up to length 16 survives every deletion, and the redundancy is about $\log_2(n + 1)$, the same as the Hamming code pays for a flipped bit. One deletion can leave only as many words as a word has runs, so these balls vary in size where Hamming balls do not; the $n + 1$ codes share out all the words, with sizes given by a divisor sum shaped like the necklace count; and no larger code correcting one deletion exists at any length up to seven, though whether that holds at every length is still unproved.