Two lost bits

A code that survives a lost bit built the Varshamov–Tenengolts codes: the binary words $x_1 x_2 \ldots x_n$ with $\sum i\,x_i$ divisible by $n + 1$. When a bit goes missing in transit — not flipped, but gone, so that the word arrives one bit shorter and nobody says where — a single number repairs it: the count of ones says whether a 0 or a 1 was lost, and the shortfall in the weighted sum says where. That code is optimal at every length anyone has checked. It ended on a sentence that is the subject here: two lost bits defeat it completely.

They do, and the reason is visible in a single pair of codewords. The question after that is what does survive two lost bits, how large such a code can be, and what it costs.

When two codewords meet #

A code survives two deletions exactly when no two of its codewords can be damaged into the same word. Delete two bits from a word of length $n$ and what remains is a subsequence of length $n - 2$; two words can be damaged into the same thing exactly when they share a common subsequence of that length. So a set of words corrects two deletions if and only if every pair has a longest common subsequence shorter than $n - 2$. The test is about pairs, and it can be computed for every pair in a fraction of a second at the lengths drawn here: the length of the longest common subsequence is a dynamic programme over two strings, filling in a table one cell at a time.

The single-deletion code fails at the first opportunity. Its length-8 version has 30 words, among them $00000000$ and $00011000$ — the second has ones at positions 4 and 5, and $4 + 5 = 9$ — and deleting the two ones from the second leaves six zeros, which is also what deleting any two bits from the first leaves. Across the whole code there are 240 such confusable pairs. The congruence was designed to locate one gap from one number, and two gaps make that number ambiguous: a shortfall of 9 in the weighted sum could be one bit at position 9, or two bits at positions 4 and 5, or many other pairs.

How many words two deletions can leave #

Before any code can be designed, there is the question of how much room each codeword occupies. A word of length $n$, with two of its bits deleted, can become many different words of length $n - 2$, and those are the words its neighbours must avoid.

The count depends on the number of runs, the maximal blocks of equal bits. Deleting any bit of a run gives the same result as deleting any other bit of it, so a word made of few long runs has few distinct damaged versions: $000000000000$, one run, can only become $0000000000$. The alternating word $010101010101$, twelve runs of length one, can become 56 different words, more than any other word of that length. Vladimir Levenshtein proved in 1966 that a word with $r$ runs leaves between $\binom{r - 1}{2}$ and $\binom{r + 1}{2}$ words after two deletions, and every word of length 12 sits between those curves.

That uneven occupancy is what makes deletion codes hard to analyse. For codes against flipped bits, every word’s ball of damaged versions has the same size, and the best a code can be follows from counting how many balls fit — a count that, for the Hamming code, comes out exact, sixteen balls filling the whole cube. Here the balls vary in size by a factor of fifty, and a code can save room by choosing words whose balls are small — words with few runs — though there are few such words to choose from.

The largest codes, by exhaustion #

At small lengths the largest two-deletion code can be found outright. Make a graph whose vertices are the $2^n$ words, joining two words when they are compatible — longest common subsequence below $n - 2$ — and a code is a set of words all joined to one another, a clique. The largest clique is found by branch and bound: build cliques one word at a time, and abandon a branch whenever a quick colouring of the remaining candidates shows they cannot add enough words to beat the best clique already found.

The hero’s top curve is the result: the largest codes have 2, 2, 4, 5, 7 and 11 words for lengths 4 to 9. At length 9 the search examines a graph of 512 words and proves that no 12 can be pairwise compatible. The middle curve is the simplest construction there is — take the words in numerical order and keep each one that is compatible with everything kept so far — and it matches the optimum up to length 7, falls one short at 8 and two short at 9 with 9 words, and continues to 46 words at length 13, where exhaustive search is out of reach.

The eleven words of the largest code of length 9 that the search returns show how the optimum uses the uneven balls. They are $000000000$ and $111111111$, one run each; $000000111$, $111000000$ and $000111111$, two runs each; $111000111$ and $011111000$, three; and only four words with five or more runs, $001100010$, $000101100$, $110110110$ and $101001001$. Seven of the eleven are made of long blocks, whose damaged versions are few, and they leave room for the four busy words to keep apart from them and from each other. A code that took only typical words would be keeping apart much larger balls: seven in ten words of length 9 have four to six runs, and each of them can typically be damaged into several times as many different words as a word of two or three runs. The same tendency is visible in the first-fit code, which starts from $000\ldots0$ and so takes the long-block words first, and it is one reason the first-fit code does so well. Whether the largest codes at every length lean on long-block words in the same way, or whether this is a feature of short lengths where long blocks are a large share of all words, the searches are too small to say.

For a single deletion the same comparison is striking: the Varshamov–Tenengolts code equals the largest code at every length checked, and the first-fit code is not far behind. For two deletions nothing comparable is known. No formula is known that produces the largest code at every length, and the optimal sizes are known only for small lengths by searches like this one.

The first-fit code has a famous relative #

The middle curve of the hero deserves a second look, because the rule behind it is older than it seems. Taking words in numerical order and keeping each one compatible with all those kept is the lexicographic code, or lexicode, for whatever notion of compatibility is in force. For codes against flipped bits, where compatibility means differing in at least $d$ places, John Conway and Neil Sloane showed in 1986 that lexicodes are always linear — closed under adding codewords bit by bit — and that the lexicodes of the right lengths and distances are exactly the Hamming codes and the Golay code. The greedy rule that knows nothing finds the most structured codes there are.

For deletions there is no such theorem, and no algebraic structure has been found in the two-deletion lexicodes. They fall short of the optimum from length 8. But they come close, and they are the best codes known at lengths where exhaustive search cannot reach, which is a measure of how little structure the deletion problem has been found to have. For substitutions, the first-fit rule rediscovers algebra. For deletions, it is most of what there is.

Where the gap is, and where it is not #

A lost bit is harder than an erased one, and the difference has a price that can be stated. An erasure is a bit that arrives as a blank: the receiver knows its position and only its value is missing. Erasures a code can see showed that $e$ erasures can be filled exactly when the codewords differ in at least $e + 1$ places, so two erasures need words at distance three, which the Hamming code provides with about $\log_2 n$ redundant bits. Two deletions need at least about $2\log_2 n$. The extra $\log_2 n$ is the price of not being told where the gaps are: to locate two missing bits among $n$ positions is to name a pair of positions, which takes about $2\log_2 n$ bits of information, and a code must carry that information somehow.

The same accounting explains the single-deletion case. The Varshamov–Tenengolts code spends $\log_2(n+1)$ bits, which is exactly what naming one position among $n + 1$ costs, and the syndrome of a Hamming code spends the same amount to name one flipped bit. One deletion and one substitution cost the same. Two deletions cost at least what two substitutions cost, and the open question is whether they cost twice as much again.

A congruence with Fibonacci-like weights #

A code that is guaranteed to work at every length needs a rule, and the natural rule extends the Varshamov–Tenengolts congruence with heavier weights. In 1993 Albertus Helberg proposed weights

$$v_1 = 1, \quad v_2 = 2, \quad v_i = 1 + v_{i-1} + v_{i-2},$$

so $1, 2, 4, 7, 12, 20, 33, 54, 88, 143, \ldots$, each one more than the sum of the two before, and the codes

$$\Big\{x : \sum_{i=1}^{n} v_i x_i \equiv a \pmod{v_{n+1}}\Big\}.$$

The weights grow fast enough that the weighted sums of any two different ways of losing two bits differ, so the shortfall identifies the loss. Helberg’s codes were proved to correct two deletions — and their generalisation with $s$ previous weights to correct $s$ deletions — by Khaled Abdel-Ghaffar, Filip Paluncic, Hendrik Ferreira and Willem Clarke in 2012. The figures check it directly: every class, at every length up to 11, is pairwise compatible.

The price is visible in the class sizes. At length 10 the modulus is 232, so the 1,024 words are spread over 232 classes and the average class has under four and a half words; the largest has 8. The exhaustive search found 11 at length 9, where Helberg’s best class has 6.

Repairing a word #

Decoding a Helberg code needs nothing cleverer than trying. A received word of length $n - 2$ can have its two missing bits put back in a limited number of ways, and exactly one of the results lands in the right class.

With 10 bits received, there are 79 distinct words of length 12 that contain them as a subsequence, and only one of them has weighted sum congruent to the codeword’s class modulo 609. That uniqueness is the theorem; the trying is merely its most literal use. Efficient decoders compute the position of the loss from the shortfall directly, as the Varshamov–Tenengolts decoder does, but the principle is the same: the class determines the word.

What protection costs #

A code of $M$ words of length $n$ carries $\log_2 M$ bits of information, and the remaining $n - \log_2 M$ are the price of protection, its redundancy.

For one deletion the Varshamov–Tenengolts code’s redundancy is about $\log_2 n$: the class of a word is a number below $n + 1$, which costs that many bits to fix. For two deletions Levenshtein’s counting arguments put the optimal redundancy between about $2\log_2 n$ and $4\log_2 n$, and the exhaustive and first-fit codes sit near the lower curve at the lengths drawn — slightly below it at the shortest, where bounds that hold for large $n$ do not yet bind. Helberg’s codes do not. Their modulus $v_{n+1}$ grows like the $n$-th power of the golden ratio, the growth rate of the recurrence that defines the weights, so their redundancy grows like $n\log_2 \varphi \approx 0.694\,n$ — in proportion to the length, not its logarithm. At length 20 they spend 13.9 bits, still under $4\log_2 n$; near length 27 they cross it; and for long words they carry only about 0.3 bits of information per bit sent.

That is the general shape of the subject. Codes that provably correct $s$ deletions were long either simple and wasteful, like Helberg’s, or efficient and existing only by counting. The gap was closed for two deletions in 2021, when Venkatesan Guruswami and Johan Håstad gave explicit codes with redundancy $4\log_2 n$ plus lower-order terms, matching what counting guarantees exists, and later constructions have pushed further. Whether $2\log_2 n$, the lower bound, can be reached is not known.

Where bits go missing #

A deletion sounds like an exotic fault, and it is the ordinary one whenever a receiver must keep time with a sender. A clock that drifts by a fraction of a cycle eventually reads one cycle twice or skips one, and the receiver sees an inserted or a deleted bit with no indication of where. Magnetic recording, where bits are read off a moving surface, and racetrack memories, where they are pushed along a wire, both suffer from it. The most demanding modern case is storage in DNA: the chemistry of writing and reading long molecules produces insertions and deletions far more often than substitutions, and every scheme for storing data in DNA must handle them, usually by cutting the data into short strands and protecting each one separately — which is exactly the regime of short lengths and a few deletions where the figures here are drawn.

For random deletions at a steady rate the question changes from correcting every pattern of a few losses to communicating reliably in spite of many, and the best possible rate — the capacity of the deletion channel — is still unknown, with upper and lower bounds that do not meet. The worst-case question of this essay, a fixed number of losses anywhere, is the one that combinatorics can answer exactly, and even it is answered only at small lengths.

Optimal sizes only to length nine #

The optimal sizes stop at length 9. The branch and bound proves optimality there in under a second and slows sharply beyond: at length 10 the graph has 1,024 vertices and the search has to rule out every clique of the next size among them. The largest codes at length 10 and above are known from longer searches and from the literature for a few more lengths, and not from the figures.

Helberg’s codes are checked, not proved, in the figures. Every class up to length 11 was compared pair by pair; the theorem that every class works at every length is the 2012 proof, and the figures are a check on it at the lengths where checking is cheap.

Deletions only. A channel that also inserts bits is handled by the same codes — Levenshtein showed that a code correcting $s$ deletions corrects any mixture of $s$ insertions and deletions — but a channel that also flips bits needs more, and so does one that loses bits in bursts.

Still open: the factor of two #

The question the single-deletion essay ended on stands in a sharper form. For one deletion the best codes cost $\log_2 n$ bits and the Varshamov–Tenengolts congruence achieves it. For two, the lower bound from counting is about $2\log_2 n$ and the best explicit constructions spend about $4\log_2 n$. Can two lost bits be repaired with $2\log_2 n + O(1)$ bits of redundancy? The exhaustive codes at small lengths sit close to $2\log_2 n$, which suggests that the answer might be yes; small lengths have misled before. The single congruence is the cleanest construction in coding theory, and nobody has found a two-deletion analogue as clean — a single weighted sum, or a pair of them, whose classes are as large as the best codes. Helberg’s weights show that one weighted sum can work if the weights grow fast enough, and the hero shows how much that speed costs.