1

Codes Correcting Two Deletions
Ryan Gabrys∗ and Frederic Sala†
∗ Spawar

† University

Systems Center
ryan.gabrys@navy.mil

of California, Los Angeles
fredsala@ucla.edu

Abstract

I. I NTRODUCTION
This paper is concerned with deletion-correcting codes. The problem of creating error-correcting codes that correct one or more
deletions (or insertions) has a long history, dating back to the early 1960’s [12]. The seminal work in this area is by Levenshtein,
who showed in [9] that the Varshamov-Tenengolts asymmetric error-correcting code (introduced in [13]) also corrects a single
deletion or insertion. For single deletion-correcting codes, Levenshtein introduced a redundancy lower bound of log2 (n) − O(1)
bits, demonstrating that the VT code, which requires at most log2 (n) redundancy bits, is nearly optimal.
The elegance of the VT construction has inspired many attempts to extend this code to correct multiple deletions. Such an
approach is found in [7] where the authors introduce a number-theoretic construction that was later shown in [1] to be capable
of correcting two or more deletions. Unfortunately, even for the case of just two deletions, the construction from [7] has a rate
which does not converge to one. Other constructions for multiple insertion/deletion-correcting codes such as those found in [10],
[11] rely on (d, k)-constrained codes, and consequently, these codes also have rates less than one.
To the best of the authors’ knowledge, the best known construction for two deletions (in terms of the minimum redundancy
bits) can be found in the recent work by Brakensiek et al. [2]. The authors show that it possible to construct a t deletion-correcting
code with ct · log2 n bits of redundancy where ct = O(t2 log2 t). The construction from [2] is for general t and does not report
any improved results for the case where t is small. However, it can be shown that their methods result in a construction requiring
at least 128 log2 n bits of redundancy for the case of t = 2.
The best known lower bound for the redundancy of a double deletion-correcting code is 2 log2 n − O(1) ( [8]) bits; thus, there
remains a significant gap between the upper and lower bounds for t deletion-correcting codes even for the case where t = 2. This
motivates the effort to search for more efficient codes.
We note that using a counting argument such as the one found in [9], one can show that there exists a t deletion-correcting
code with redundancy at most 2t log2 n − O(t). However, these codes require the use of a computer search to form the codebooks
along with a lookup table for encoding/decoding. Such codes do not scale as n becomes large and there is no efficient search
mechanism that scales sub-exponentially with n.
The contribution of the present work is a double deletion-correcting code construction that requires 8 log2 n + O(log2 log2 n)
bits of redundancy. To the best of the authors’ knowledge this represents the best construction for a double deletion-correcting
Redudancy of Codes
1600
Our Two Deletion Code
Codes from [2]

1400
1200

Bits of Redudancy

arXiv:1712.07222v1 [] 19 Dec 2017

In this work, we investigate the problem of constructing codes capable of correcting two deletions. In particular, we construct a
code that requires redundancy approximately 8 log2 n + O(log2 log2 n) bits of redundancy, where n denotes the length of the code.
To the best of the author’s knowledge, this represents the best known construction in that it requires the lowest number of redundant
bits for a code correcting two deletions.

1000
800
600
400
200
0

0

500

1000

1500

2000

2500

Code Length

Fig. 1. Comparison of new codes with codes from [2].

3000

3500

4000

4500

2

Rate of Codes
1
0.9
0.8
0.7

Rate

0.6
0.5
0.4
0.3
0.2
Our Two Deletion Code
Codes from [2]

0.1
0

0

500

1000

1500

2000

2500

3000

3500

4000

4500

Code Length

Fig. 2. Comparison of rate of new codes with codes from [2].

code in terms of the redundancy; it is within a factor of four of the optimal redundancy. In Figures 1 and 2, we compare
our construction and the construction from [2]. Although both constructions approach rate 1 for long enough code lengths, our
construction approaches rate one much faster than the construction from [2]. For example, for n = 1024, our construction has
rate approximately 0.86 whereas the construction from [2] has rate at most 0.62.
The paper is organized as follows. In Section II, we provide the main ideas behind our construction and provide an outline of
our approach. Section III introduces our first construction. Afterwards, an improved construction is described in Section IV. We
discuss the issue of run-length-limited constrained codes in Section V and conclude with Section VI.
II. M AIN I DEAS AND O UTLINE
The idea behind our approach is to isolate the deletions of zeros and ones into separate sequences of information, and to then
use error correction codes on the substrings appearing in the string. We also use a series of constraints that allow us to detect
what types of deletions occurred, and consequently we are able to reduce the number of codes in the Hamming metric which are
used as part of the construction. As a result, we present a construction which achieves the advertised redundancy.
Let C(n) ∈ Fn2 denote our codebook of length n that is capable of correcting two deletions. Suppose y ∈ Fn−2
is received
2
where y is the result of two deletions occurring to some vector x ∈ C(n), denoted y ∈ D2 (x). Then, we have the following 6
scenarios:
1) Scenario 1: Two zeros were deleted from x.
2) Scenario 2: Two ones were deleted from x.
3) Scenario 3: A zero was deleted from a run of of length > 4 and a one was deleted from a run of length > 4 in x.
4) Scenario 4: A symbol b ∈ F2 was deleted from a run of length > 4 and another symbol b̄ was deleted from a run of length
` ∈ {1, 2, 3}. Furthermore, if ` = 1, then b̄ is adjacent to runs of lengths `1 , `2 where `1 + `2 < 4.
5) Scenario 5: A symbol b ∈ F2 was deleted from a run of length > 4, and a symbol b̄ is deleted from a run of length 1, where
b̄ is adjacent to runs of lengths `1 , `2 where `1 + `2 = 4.
6) Scenario 6: Scenarios 1)-5) do not occur.
The first 5 of these scenarios are shown in Figure 3.
Our approach is to use a series of detection codes to attempt to delineate between the 6 scenarios enumerated above. In addition,
and similar to [2], we make use of substrings that are not affected by the deletions. The main difference between our approach
here and the one used by [2] is that we use a series of detection codes that allow us to place error-correcting codes on fewer
substrings occuring in our codewords. We provide an example which illustrates the basic ideas behind the approach in [2] and it
highlights some subsequent notation used throughout the paper.
Example 1. Suppose x = (0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0) is transmitted. Let L(x, 00) be an integer which denotes the maximum
number of bits between any two occurrences of the substring 00 in x. Notice that L(x, 00) = 4. For shorthand, let L(x, 00) = s
and let fs : {∅} ∪ F12 ∪ · · · ∪ Fs2 → [2s+1 − 1] be an injective mapping where ∅ denotes the null string. Then,
Ffs (x, 00) = Ff4 (x, 00) = (f4 (0, 1, 1), f4 (∅), f4 (1, 0, 1, 1), f4 (∅)).
Thus, if there are k occurrences of the substring 00, then the sequence Ff4 (x, 00) has length k + 1.
Suppose y = (1, 1, 0, 0, 0, 1, 0, 1, 0, 0) is received where y is the result of two deletions occurring to x. Notice that
Ff4 (y, 00) = (f4 (1, 1), f4 (∅), f4 (1, 0, 1), f4 (∅)).

3

0,1,0,0,0,1,1,1,1,0,1,0,1,0,0

Scenario 1
0,1,0,0,0,1,1,1,1,0,1,0,1,0,0

Scenario 2
0,1,0,0,0,1,1,1,1,0,1,0,1,0,0

Scenario 3
0,1,0,0,0,1,1,1,1,0,1,0,1,0,0

Scenario 4
0,1,0,0,0,1,1,1,1,0,1,0,1,0,0

Scenario 5

Fig. 3. First 5 scenarios

In particular, notice that dH (Ff4 (x, 00), Ff4 (y, 00)) = 2, where dH denotes the Hamming distance. Thus, if Ff4 (x, 00) belongs
to a double error-correcting code, it is possible to recover Ff4 (x, 00) from y and in particular, it is possible to then recover x.
Notice in the previous example that all occurrences of the substring 00 were preserved (we will more rigorously define this
notation shortly). It is not too hard to see that if (in the previous example) a deletion occurred where a substring 00 is deleted
in x and therefore does not appear in y, then we can no longer claim dH (Ff4 (x, 00), Ff4 (y, 00)) = 2.
In order to overcome this issue, the approach taken in [2] was to require that the sequence Ff4 (x, w) belongs to a double
error-correcting code for many different choices of w. In particular, the approach in [2] is to enforce that Ffs (x, w) holds for
every binary string w of length m where according to Theorem 5 from [2] we need 2m > 2t · (2m − 1). Since any two-error
correcting code of length n requires approximately 2 log2 n bits of redudancy and t = 2 for our setup, this implies that using the
construction from [2], we need m > 6 and so the overall construction requires approximately 26 · (2 log2 n) = 128 log2 n bits of
redudancy.
The approach taken here is to use a series of detection codes along with different mappings and more carefully choose which
substrings to place error-correcting codes on. Consequently, we show it is possible to construct a code with fewer redundant bits
than the approach outlined in [2] for the case of two deletions.
From the above example if we use the constraints Ffs (x, w1 ), Ffs (x, w2 ), Ffs (x, w3 ) , and Ffs (x, w4 ) (for some appropriately chosen substrings w1 , . . . , w4 ), then this would require the use of a series of double error-correcting codes defined over an
alphabet of size approximately 2s . To reduce the size of this alphabet, we make use of the following lemma.
Lemma 1. (c.f., [2]) There is a hash function hs : {0, 1}s → {0, 1}v for v 6 4 log2 s + O(1), such that for all x ∈ {0, 1}s , given
any y ∈ D2 (x) and hs (x), the string x can be recovered.
Codes constructed according to Lemma 1 can be found using brute force attempts such as finding an independent set on a
graph with 2n vertices for which no polynomial-time algorithms (with respect to n) exist. Note, however, that if s = O(log2 n),
then using an algorithm for determining a maximal independent set on a graph which is polynomial with respect to the number
of vertices in the graph (such as [6] for instance) results in a code of length s that can be constructed in polynomial time with
respect to n.
At first, we will make use of the sequences Fhs (x, 0000), Fhs (x, 1111), Fhs (x, 11011), and Fhs (x, 110011) where x ∈ C(n).
In particular, we will require that each of these sequences belongs to a code with minimum Hamming distance 5 over an alphabet
of size approximately s. Assuming s = O(log2 n), then these constraints together require approximately 4 · 37 log2 (n) bits of
redundancy if we use the non-binary codes from Dumer [5]. Afterwards, we alter one of the maps used in conjunction with our
Hamming codes and show it is possible construct a code with 8 log2 n + O(1) bits of redudancy. We now turn to some additional
notation before presenting the construction.
For a vector x ∈ Fn2 , let D(i1 , i2 , x) ∈ Fn−2
be the result of deleting the symbols in x in positions i1 and i2 where 1 6
2
i1 < i2 6 n. For example if x = (0, 1, 0, 1, 0, 0), then D(2, 4, x) = (0, 0, 0, 0). Using this notation, we have D2 (x) = {y :
∃i1 , ∃i2 , y = D(i1 , i2 , x)}.
Let w ∈ {0, 1}m . Suppose y ∈ D2 (x). Then we say that the substring w ∈ {0, 1}m is preserved from x to y if, for every
occurrence of w, there exists indices i1 and i2 such that D(i1 , i2 , x) = y and the following holds:

4

1) w 6∈ {(xi1 , xi1 +1 , . . . , xi1 +m−1 ), (xi1 −1 , xi1 , . . . , xi1 +m−2 ),
. . . , (xi1 −m+1 , xi1 −m+2 ,. . . , xi1 )},
2) w 6∈ {(xi2 , xi2 +1 , . . . , xi2 +m−1 ), (xi2 −1 , xi2 , . . . , xi2 +m−2 ),
. . . , (xi2 −m+1 , xi2 −m+2 ,. . . , xi2 )},
3) w 6∈ {(yi1 −1 , yi1 , . . . , yi1 +m−2 ), (yi1 −2 , yi1 −1 , . . . , yi1 +m−3 ),. . . , (yi1 −m+1 , yi1 −m+2 ,. . . , yi1 )},
4) w 6∈ {(yi2 −2 , yi2 −1 , . . . , yi2 +m−3 ), (yi2 −3 , yi2 −2 , . . . , yi1 +m−4 ),. . . , (yi2 −m , yi1 −m+1 ,. . . , yi2 −1 )}.
In words, the first two statements above require that any substring w is not deleted from x and the last two statements require
that no new appearances of w are in y that were not also in x. If w is not preserved from x to y, and the first two conditions
above are violated, then we say that w was destroyed from x to y. If w is not preserved, and the last two conditions above are
violated, then we say that w was created from x to y. Notice that in order for w to be preserved from x to y, 1)-4) has to hold
for at least one pair of i1 , i2 such that we can write y = D(i1 , i2 , x) since the choice of i1 , i2 may not be unique. The following
example shows this.
Example 2. Suppose x = (0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0) and y = (0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0). Then we say that
(1, 0, 1) is preserved from x to y since there are three occurrences of 101 in x and D(6, 15, x) = D(5, 15, x) = y. Notice that
(1, 1, 1) is not preserved from x to y and in particular (1, 1, 1) is destroyed.
For a vector x ∈ Fn2 , let N0 (x) denote the number of zeros in x. Similarly, let N1 (x) be the number of ones that appear in x.
Furthermore, let N0 (x), N1 (x), N11011 (x) be the number of appearances of the substrings 0000, 1111, and 11011 respectively.
We illustrate these notations in the following example.
Example 3. Let x = (0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1 , 1, 0, 0, 0). Then, N0 (x) = 11, N1 (x) = 10, N0 = 2, N1 = 1, and
N11011 (x) = 1. Notice that two occurrences of the substring 0000 overlap.
III. C ONSTRUCTION - F IRST ATTEMPT
We now turn to describing out code. Let CT (n, s) denote the following set
CT (n, s) = {x ∈ Fn2 : L(x, 0000) 6 s, L(x, 1111) 6 s, L(x, 110011) 6 s, L(x, 11011) 6 s}.
As we will see shortly, our main construction will be a sub-code of CT (n, s).
Let c ∈ F57 . Suppose q the smallest odd prime greater than the size of the image of the map hs . Suppose N is the smallest
positive integer such that q N −1 > n. Let a0 , a1 , a110011 , a11011 ∈ Frq where r 6 2N + d N 3−1 e. Our construction is the following:
n
C(n,a0 , a1 , a110011 , a11011 , c, s) = x ∈ CT (n, s) :
N0 (x) mod 7 = c1 , N1 (x) mod 7 = c2 ,
N1 (x) mod 7 = c3 , N0 (x) mod 7 = c4 ,
N11011 (x) mod 7 = c5 ,
Fhs (x, 0000) ∈ C2 (n, q, a0 ), Fhs (x, 1111) ∈ C2 (n, q, a1 ),
Fhs (x, 110011) ∈ C2 (n, q, a110011 ),
o
Fhs (x, 11011) ∈ C2 (n, q, a11011 ) ,
where C2 (n, q, a) is a code over Fq of length n. If any of the sequences above that are required to be in codes of length n have
lengths M < n, then we simply assume the last n − M components of the sequences are equal to zero.
Let H be a parity check matrix for a double error-correcting code (minimum Hamming distance 5) from [5] so that H ∈
N −1
Fqr×q
. We define the double error correcting code C2 (n, q, a) so that
C2 (n, q, a) = {x ∈ Fqq

N −1

: H · x = a}.

We now show that given any y ∈ D2 (x), it is possible to recover x ∈ C(n, a0 , a1 , a110011 , a11011 , c, s). For shorthand, we
refer to C(n, a0 , a1 , a110011 , a11011 , c, s) as C(n). For the remainder of the section, we always assume x is a codeword from
C(n) and y ∈ D2 (x).
The following claims will be used throughout the section.
Claim 1. Suppose a zero is deleted from a run of length one in x and the deletion causes
1) 11011 to be created/destroyed,
2) 1111 to be created,
then the substring 110011 is preserved from x to y.

5

As an example, the previous claim will be concerned with the following type of deletion:
(×, ×, ×, 1, 0, 1, 1, 0, 1, 1, ×, ×, ×, ×, ×),
where 0 ×0 indicates a symbol which is either a zero or a one and 0 represents a deletion (in this case of a symbol with value 0).
Proof: The deletion of a zero from a run of length 1 can destroy a 11011 substring only if the middle zero is deleted. In
this case, the 110011 substring is preserved. The deletion of a zero from a run of length 1 can create a 11011 substring only if
either the first zero is deleted from the substring 11101011 in x or if the second zero is deleted from the substring 11010111 in
x. In either case, the substring 110011 is preserved from x to y.
Claim 2. Suppose a symbol with value b ∈ F2 is deleted from a run of length > 4 and a symbol with value b is deleted from a run of
length 1 where
N1 (x) 6= N1 (y), N0 (x) 6= N0 (y).
Under this setup, if b = 1, the substring 110011 is preserved. Otherwise, if b = 0 and 11011 is not preserved from x to y, then
110011 is preserved.
For example, the previous claim will be concerned with the following setups. If b = 0, then one instance of the setup from this
claim is
(×, ×, 0, 0
, 0, 0, ×, ×, ×, ×, ×, 1, 0, 1, ×, ×, ×)
and if b = 1, then another example is
(×, ×, 1, 
1, 1, 1, ×, ×, ×, ×, ×, 0, 1, 0, ×, ×, ×).
Proof: Suppose that a symbol with value b = 0 is deleted from a run of length > 4 and another symbol with value 0 is
deleted from a run of length 1. To begin, notice that the zero which was deleted from the run of length > 4 cannot create/destroy
the substrings 11011, 110011, 1111 from x to y. Then, according to Claim 1, if the deletion of a zero from a run of length 1 a)
creates/destroys the substring 11011 and b) creates the substring 1111 from x to y, then the substring 110011 is preserved from
x to y.
Suppose b = 1. Under this setup, the substring 110011 is preserved, and so we can recover x from the constraint Fhs (x, 110011) ∈
C2 (n, q, a110011 ). To see this, we first note that an occurrence of the substring 110011 is destroyed only if a one is deleted from
a run of length 2 which is not possible under this setup. In addition, an occurrence of the substring 110011 cannot be created
by deleting a one from a run of length 1 (since this would require that the one is also adjacent to runs of lengths `1 , `2 with
`1 + `2 > 4 since a 0000 substring is created from x to y) or by deleting a one from a run of length 4. Therefore, 110011 is
preserved from x to y when b = 1.
We begin with the cases where either y is the result of deleting two zeros or two ones from x. The first two lemmas handle
Scenarios 1) and 2) from the previous section.
Lemma 2. Suppose N1 (x) − N1 (y) mod 7 = 2. Then, x can be recovered from y.
For example, the previous claim will be concerned with the following setup:
(×, ×, ×, ×, 1, ×, ×, ×, ×, ×, ×, ×, ×, 1, ×, ×, ×).
Proof: Since N1 (x) − N1 (y) mod 7 = 2, two ones were deleted from x to obtain y. If N0 (x) − N0 (y) ≡ 0 mod 7, then
0000 is preserved since the deletion of a 1 can create at most 3 0000s and so the deletion of two ones can create at most 6 0000s.
Thus, we conclude that 0 is preserved from x to y. Since two ones were deleted, clearly no 0000 substrings were destroyed.
Therefore, 0000 is preserved from x to y, and so we can recover x from y using the constraint Fhs (x, 0000) ∈ C2 (n, q, a0 ).
If N1 (x) − N1 (y) ≡ 0 mod 7, then 1111 is preserved, and so we can recover x from y using the constraint Fhs (x, 1111) ∈
C2 (n, q, a1 ).
Now we assume that both N1 (x) − N1 (y) 6≡ 0 mod 7 and N0 (x) − N0 (y) 6≡ 0 mod 7. Note that this is only possible if a
one is deleted from a run of length > 4 and a one is deleted from a run of length 1. According to Claim 2, we can determine x
from Fhs (x, 110011) ∈ C2 (n, q, a110011 ).
Next we turn to the case where two zeros have been deleted.
Lemma 3. Suppose N0 (x) − N0 (y) mod 7 = 2. Then, x can be recovered from y.
For example, we will be concerned with the following setup:
(×, ×, ×, ×, 0, ×, ×, ×, ×, ×, ×, ×, ×, 0, ×, ×, ×).

6

Proof: Since N0 (x)−N0 (y) mod 7 = 2, two zeros were deleted from x to obtain y. If N1 (x)−N1 (y) ≡ 0 mod 7, then we
can recover x from y using the constraint Fhs (x, 1111) ∈ C2 (n, q, a1 ) using the same logic as the previous lemma. In addition,
if N0 (x) − N0 (y) ≡ 0 mod 7, then 0000 is preserved, and so we can recover x from y using the constraint Fhs (x, 0000) ∈
C2 (n, q, a0 ).
Now we assume that both N1 (x) − N1 (y) 6≡ 0 mod 7 and N0 (x) − N0 (y) 6≡ 0 mod 7. Similar to the previous lemma, this
is only possible if a zero is deleted from a run of length > 4 and a zero is deleted from a run of length 1. We can use the
constraint N11011 (x) mod 7 = c5 to determine whether the substring 11011 is preserved from x to y. If 11011 is preserved,
then we can determine x from Fhs (x, 11011) ∈ C2 (n, q, a11011 ). If 11011 is not preserved then we can determine x from
Fhs (x, 110011) ∈ C2 (n, q, a110011 ) according to Claim 2.
As a result of the previous two lemmas, we assume in the remainder of this section that y is the result of deleting a symbol
with a value 1 and a symbol with a value 0. The next 3 lemmas handle the case where N0 (x) > N0 (y) or N1 (x) > N1 (y).
The next lemma covers Scenario 3).
Lemma 4. Suppose N0 (x) − N0 (y) mod 7 = 1, and N1 (x) − N1 (y) mod 7 = 1. Then, x can be recovered from y.
For example, we will be concerned with the following setup:
(×, ×, 0, 0, 0, 0, ×, ×, ×, ×, ×, ×, 1, 1, 1, 1, ×).
Proof: Since N0 (x) − N0 (y) mod 7 = 1 and N1 (x) − N1 (y) mod 7 = 1, y is the result of deleting a 1 and a 0 from x
where both symbols belong to runs of lengths > 4. Since both symbols were deleted from runs of lengths at least 4, it follows
that no 110011 substrings were created/destroyed and so we can recover x from Fhs (x, 110011) ∈ C2 (n, q, a110011 ).
The next two lemmas handle Scenario 4).
Lemma 5. Suppose N0 (x) − N0 (y) mod 7 = 1 and N1 (x) − N1 (y) mod 7 = 0. Then, x can be recovered from y.
For example, we will be concerned with the following setup:
(×, ×, 0, 0, 0, 0, ×, ×, ×, ×, ×, ×, 0, 1, 1, 0, ×).
Proof: Since N0 (x) − N0 (y) mod 7 = 1, clearly a zero was deleted from a run of zeros of length at least 4 in x. Since
N1 (x) − N1 (y) mod 7 = 0 and there are exactly two deletions (of a zero and a one), no ones were deleted from runs of ones
of length > 4. Thus, we can recover x from Fhs (x, 1111) ∈ C2 (n, q, a1111 ).
Lemma 6. Suppose N1 (x) − N1 (y) mod 7 = 1 and N0 (x) − N0 (y) mod 7 = 0. Then, x can be recovered from y.
For example, the previous lemma is concerned with the following setup:
(×, ×, 1, 1, 1, 1, ×, ×, ×, ×, ×, ×, 1, 0, 0, 1, ×).
Finally, we turn to the case where either Scenario 5) or Scenario 6) occurs. The next two lemmas handle the case where either
N0 (y) > N0 (x) or N1 (y) > N1 (x).
Lemma 7. Suppose N0 (y) − N0 (x) mod 7 ∈ {1, 2, 3} or N1 (y) − N1 (x) mod 7 ∈ {1, 2, 3}. Then, x can be recovered from y.
For example, we will be concerned with the following setup:
(×, 0, 0, 0, 1, 0, ×, ×, ×, ×, ×, ×, 1, 0, 0, 1, ×),
or
(×, 1, 1, 1, 0, 1, ×, ×, ×, ×, ×, ×, 0, 1, 1, 0, ×).
Proof: Suppose first that N0 (y) − N0 (x) mod 7 ∈ {1, 2, 3}. Then, clearly a one from a run of length 1 was deleted in x
resulting in the creation of new 0000 substrings. If N1 (y) − N1 (x) mod 7 = 0, then 1111 is preserved from x to y and so we
can recover x.
Otherwise, if N0 (y) − N0 (x) mod 7 ∈ {1, 2, 3} and N1 (y) − N1 (x) mod 7 ∈ {1, 2, 3}, it follows that a one was deleted
from a run of length 1 and also a zero was deleted from a run of length 1, so that we have the following type of setup:
(×, 0, 0, 0, 1, 0, ×, ×, ×, ×, ×, 1, 1, 0, 1, 1, ×),
The deletion of a one from a run of length 1 cannot or create destroy a 110011 substring or a 11011 substring since the 1 needs to
be adjacent to two runs of lengths `1 , `2 where `1 + `2 > 4 since at least one 0000 substring is created from x to y. Furthermore,
the deletion of the one from a run of length 1 clearly cannot create a 1111 substring from x to y. Therefore, the deletion of
the zero from a run of length 1 creates a 1111 substring from x to y and from Claim 1, if 11011 is not preserved from x to

7

y, then 110011 is preserved. Thus, we can use the constraints N11011 (x) mod 7 = c5 , Fhs (x, 110011) ∈ C2 (n, q, a110011 ) and
Fhs (x, 11011) ∈ C2 (n, q, a11011 ) to determine x.
Notice that it is not possible to have N0 (y) − N0 (x) mod 7 ∈ {1, 2, 3} and N1 (x) − N1 (y) mod 7 ∈ {1, 2, 3}. This is because
in order to have N0 (y) − N0 (x) mod 7 ∈ {1, 2, 3}, a one is deleted from a run of length 1 and this creates a new run of zeros
of length at least 4. Then, the deletion of the zero (which also occurs by assumption) can only create 1111 substrings from x to
y and so N1 (x) − N1 (y) mod 7 6∈ {1, 2, 3}.
The case where N1 (y) − N1 (x) mod 7 ∈ {1, 2, 3}, but N0 (y) − N0 (x) mod 7 6∈ {1, 2, 3} can be handled using the same
logic as before.
We have one case left to consider.
Lemma 8. Suppose N1 (x) − N1 (y) mod 7 = 0, and N0 (x) − N0 (y) mod 7 = 0. Then, x can be recovered from y.
Proof: Since N1 (x) − N1 (y) mod 7 = 0 and N0 (x) − N0 (y) mod 7 = 0, there are two setups to consider:
1) A symbol b was deleted from a run of length > 4 and another symbol b̄ from a run of length 1 was deleted which was
adjacent to a run of length `1 and another run of length `2 such that `1 + `2 = 4, so that we have the following type of
setup:
(×, 0, 0, 0, 1, 0, ×, ×, ×, ×, ×, 0, 0, 0, 0, ×, ×).
2) The 0000 and 1111 substrings were preserved from x to y.
We first discuss the decoding procedure and then show that the decoding is correct given that either 1) or 2) hold. Suppose
that N11011 (x) ≡ nN11011 (y) mod 7. Then we estimate x to be the sequence which agrees with at least two of
o the following
three constraints: Fhs (x, 0000) ∈ C2 (n, q, a0 ), Fhs (x, 1111) ∈ C2 (n, q, a1 ), Fhs (x, 11011) ∈ C2 (n, q, a11011 ) . Otherwise, if
N11011 (x) 6≡ N11011 (y) mod 7, we estimate x to be the sequence which agrees with the constraint Fhs (x, 0000) ∈ C2 (n, q, a0 ).
First suppose that N11011 (x) ≡ N11011 (y) mod 7 and suppose that 1) holds. If b = 0, then the decoding is correct since in this
case x agrees with the constraints Fhs (x, 1111) ∈ C2 (n, q, a1 ) and Fhs (x, 11011) ∈ C2 (n, q, a11011 ), since 11011 can be created
only if a 0 is deleted from a run of length 1. Notice that if b = 0, then the substring 11011 cannot be destroyed. Now, suppose
b = 1. In this case, if N11011 (x) ≡ N11011 (y) mod 7, then the deletion of a zero from
n a run of length 1 did not create/destroy the
substring 11011 and so x agrees with at least two of the three constraints from Fhs (x, 0000) ∈ C2 (n, q, a0 ), Fhs (x, 1111) ∈
o
C2 (n, q, a1 ), Fhs (x, 11011) ∈ C2 (n, q, a11011 ) . Thus, the decoding is correct when N11011 (x) ≡ N11011 (y) mod 7 and 1) holds.
Next consider the n
case where N11011 (x) ≡ N11011 (y) mod 7 and suppose that 2) holds. Then clearly, x agreesowith two of
the three constraints Fhs (x, 0000) ∈ C2 (n, q, a0 ), Fhs (x, 1111) ∈ C2 (n, q, a1 ), Fhs (x, 11011) ∈ C2 (n, q, a11011 ) and so the
decoding is correct in this case.
Suppose now that N11011 (x) 6≡ N11011 (y) mod 7 and that 1) holds. Notice that under this setup, b 6= 0, since the deletion of a
0 from a run of length at least 4 and the deletion of a 1 from a run of length 1 cannot create/destroy any substrings 11011 from
x to y. If b = 1 and N11011 (x) 6≡ N11011 (y) mod 7, then a zero was deleted from a run of length one and a one was deleted
from a run of length > 4 so that the substring 0000 was preserved and so the decoding is correct in this case.
Finally, we consider the case where N11011 (x) 6≡ N11011 (y) mod7 and 2) holds. If 2) holds and the 0000 substring is preserved then clearly x agrees with the constraint Fhs (x, 0000) ∈ C2 (n, q, a0 ), and so the decoding procedure is correct in this
case as well.
As a consequence of Lemmas 2-8, we have the following theorem.
Theorem 9. The code C(n, a0 , a1 , a110011 , a11011 , c, s) can correct two deletions.
In the next section, we make some modifications to the code discussed in this section and afterwards we discuss the redudancy
of the resulting code.
IV. A N I MPROVED C ONSTRUCTION
In this section, we modify the construction in the previous section to obtain a code with redudancy 8 log2 n + O(log2 log2 n).
Our construction uses the same substrings to partition our codewords as in the previous section, but we make use of a different hash
(R)
function in place of hs from Lemma 1, denoted hs . Consequently we show that we can replace the constraint Fhs (x, 11011) ∈
C2 (n, q, a11011 ) with the constraint that Fh(R) (x, 11011) belongs to a code with Hamming distance 3 (rather than Hamming
s
distance 5). Our analysis and the subsequent proof will mirror the previous section in light of these modifications. This section is
organized as follows. We first describe our code construction in detail and then show it has the advertised redudancy. Afterwards,
we prove the code can correct two deletions.

8

Let CT 2 (n, s) denote the following set where for a binary vector v, τ (v) is the length of the longest run of of zeroes or ones
in v,
CT 2 (n, s) = {x ∈ Fn2 : L(x, 0000) 6 s, L(x, 1111) 6 s,
L(x, 110011) 6 s, L(x, 11011) 6 s,
τ (x) 6 s}.
In the following, for a vector v ∈ Fn2 , let r1 (x) denote the run-length representation of the runs of ones in x. For example, if
v = (1, 1, 0, 1, 0, 1, 1, 1), then r1 (v) = (2, 1, 3). Furthermore, let r>2 be the run-length representation of ones in x with lengths
at least 2. For example, r>2 (v) = (2, 3).
(R)
Let Q be the smallest prime greater than s. We now turn to describing the map hs : Fs2 → F2Q . Let HR1 ∈ F2×s
be the
Q
(R)
s
parity check matrix for a code CL with Hamming distance at least 3 over FQ . For a vector v ∈ {0, 1} we define hs as the
vector which results by considering the run-length representation (as a vector) of the runs of ones in v of length at least 2 and
multiplying HR1 by this vector. We provide an example of this map next.
Example 4. Suppose v = (0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0). Then, the vector representing the runs of ones in v is r1 (v) = (2, 1, 2).
(R)
Notice that r1 (v) has an alphabet size which is equal to the length of the longest run in v. Then, hs (v) = HR1 · r>2 (v) =
HR1 · (2, 2).
Let c ∈ F67 . Suppose q1 the smallest odd prime greater than the size of the image of the map hs , and let q2 be the smallest
(R)
prime greater than the size of the image of the map hs . As before, let N1 be the smallest positive integer such that q1N1 −1 > n,
and suppose N2 is the smallest positive integer such that q2N2 − 1 > n. Let a0 , a1 , a110011 ∈ Frq11 and let a11011 ∈ Frq22 where
r1 6 2N1 + d N13−1 e and r2 6 1 + N2 . In the following, let b ∈ Zs+1 .
Our construction is the following:
n
C (2) (n,a0 , a1 , a110011 , a11011 , c, b, s) = x ∈ CT 2 (n, s) :
N0 (x) mod 7 = c1 , N1 (x) mod 7 = c2 ,
N0 (x) mod 7 = c3 , N1 (x) mod 7 = c4 ,
N110011 (x) mod 7 = c5 , N11011 (x) mod 7 = c6
Fhs (x, 0000) ∈ C2 (n, q1 , a0 ),
Fhs (x, 1111) ∈ C2 (n, q1 , a1 ),
Fhs (x, 110011) ∈ C2 (n, q1 , a110011 ),
Fh(R) (x, 11011) ∈ C1 (n, q2 , a11011 ),
s
o
X
r1 (x)i = b mod s + 1 ,
i odd

where C1 (n, q2 , a11011 ) is either a primitive BCH code with roots {1, α} (α ∈ FqN2 is an element of order q2N2 − 1) or a coset
2
of such a code. If any of the sequences above that are required to be in codes of length n have lengths M < n, then we simply
assume the last n − M components of the sequences are equal to zero.
Since the parameters c, a0 , a1 , a110011 , a11011 , and b can be chosen arbitrarily, it follows using an averaging argument that
there exists a choice of c, a0 , a1 , a110011 , a11011 , and b that gives
|C (2) (n,a0 , a1 , a110011 , a11011 , c, b, s)| >
|CT 2 (n, s)|
.
76 q13r1 q2r2 (s + 1)
Assuming that the image of the map hs has cardinality 24 log2 (s) and s = 128 log2 (n) then we can approximate q1 =
7
2 (n+1)
(128 log2 n)4 . In addition, if q1N1 −1 = n + 1, then N1 = 4 loglog
(128 log (n)) + 1. Then, r1 6 3 · N1 , and so
2

log2 q1r1 =

2

7
log2 (n + 1) + O(log2 log2 n).
3

Assuming Q = s + 1 = 128 log2 (n) + 1, then we approximtae q2 = 256 log2 (n) + 2. In addition if q2N2 = n + 2, then N2 =
log2 (n+2)
log (256 log (n)+2) . Since r2 6 1 + N2 , we have
2

2

log q2r2 6 log2 (n + 2) + O(log2 log2 (n)).

9

Thus,
log2 |C (2) (n,a0 , a1 , a110011 , a11011 , c, b, s)| >
log2 |CT 2 (n, s)| − 8 log n − O(log2 log2 n).
In the next section, we show that when s > 128 log2 (n), log2 |CT 2 (n, s)| > n − O(1) and so there exists a code which meets
our lower bound.
We now prove that the code C (2) (n, a0 , a1 , a110011 , a11011 , c, b, s) can correct two deletions by considering the same scenarios
as in the previous section. With a slight abuse of notation, in this section C(n) will denote C (2) (n, a0 , a1 , a110011 , a11011 , c, b, s)
and NOT C(n, a0 , a1 , a110011 , a11011 , c, s) from the previous section.
Analagous to the previous section, we begin with the following claim and throughout we assume x ∈ C(n).
Claim 3. Suppose a zero is deleted from a run of length one in x and the deletion causes
1) 110011 to be created/destroyed,
2) 1111 to be created,



then the substring 11011 is preserved from x to y, and dH Fh(R) (x, 11011), Fh(R) (y, 11011) = 1.
s

s

Proof: The deletion of a zero from a run of length 1 can destroy a 110011 substring only if one of the middle zeros is
deleted. In this case, the substring 1111 cannot be created from x to y. The only other case to consider is when a substring 110011
is created and also the substring 1111 is created. Notice that this is only possible when the first zero is deleted from the substring
111010011 or if the last zero is deleted from the substring 110010111. Notice that under
 either setup, the substring 11011
 is
preserved. In addition r>2 (111010011) = (3, 2) and r>2 (11110011) = (4, 2) so that dH Fh(R) (x, 11011), Fh(R) (y, 11011) = 1
s
s
(notice r>2 (110010111) = (2, 3) and r>2 (11001111) = (2, 4) ).
Claim 4. Suppose that y is the result of deleting
P a zero in x from a run of length 1 where the zero is adjacent to runs of length 1 and
length ` where ` > 3. Then, given r>2 (x), i odd r1 (x)i mod s + 1, and y, it is possible to determine r1 (x).
Proof: Since y is the result of deleting a zero from a run of length 1 where the zero is adjacent to runs of length 1 and
` > 3, it follows that r>2 (y) can be obtained by substituting a symbol in r>2 (y) which has value ` with another symbol which
has value ` + 1. Since ` + 1 > 3, it follows that dH (r>2 (y), r>2 (x)) = 1 and so we can determine the location of the symbol in
r>2 (y) that was altered as a result of the deletion to y. To obtain r1 (x) from r1 (y), r>2 (x), r2 > 2(y), we replace the symbol,
say a, that has value ` + 1 in r1 (y) which corresponds to the same symbol in r>2 (x) (that was
P affected by the deletion of the
zero in x) and we replace the symbol a in r1 (y) with 2 adjacent symbols 1 and `. Given i odd r1 (x)i mod s + 1, we can
determine whether the symbol 1 should be inserted before the symbol ` or whether ` comes before the symbol 1. Thus, we can
recover r1 (x) as stated in the claim.
We have the following lemmas which mirror the logic from the previous section. The first lemma follows immediately using
the same logic as in the proof of Lemma 2.
Lemma 10. Suppose N1 (x) − N1 (y) mod 7 = 2. Then, x can be recovered from y.
The next lemma requires a little more work.
Lemma 11. Suppose N0 (x) − N0 (y) mod 7 = 2. Then, x can be recovered from y.
Proof: Similar to the proof of Lemma 3, we focus on the case where both N1 (x) − N1 (y) 6≡ 0 mod 7 and N0 (x) −
N0 (y) 6≡ 0 mod 7, since if at most one of these two conditions hold then we can determine x from y given Fhs (x, 0000) ∈
C2 (n, q, a0 ), Fhs (x, 1111) ∈ C2 (n, q, a1 ).
Since N1 (x) − N1 (y) 6≡ 0 mod 7 and N0 (x) − N0 (y) 6≡ 0 mod 7 hold, it follows that y is the result of deleting a zero from
a run of length 1 and another zero from a run of length at least 4. Notice that the deletion of the zero from a run of length 4
cannot create/destroy the substrings 110011, 1111. Thus, if the substring 110011 is not preserved
from x to y, it is a resultof the

deletion of the zero from a run of length 1. According to Claim 3, under this setup, dH Fh(R) (x, 11011), Fh(R) (y, 11011) = 1.
s
s
Thus, we can determine r>2 (x) from Fh(R) (x, 11011) ∈ C1 (n, q2 , a11011 ). According to Claim 4, we can then determine r1 (x)
s
so that we can correct the deletion of the zero from a run of length 1. The remaining deletion (of a zero from a run of length
> 4) can be corrected using the constraint Fhs (x, 1111) ∈ C2 (n, q1 , a2 ).
Thus, we can determine x from y as follows. Suppose N1 (x) − N1 (y) 6≡ 0 mod 7, N0 (x) − N0 (y) 6≡ 0 mod 7, and
N110011 (x) 6≡ N110011 (y) mod 7. Then, x can be recovered as described in the previous paragraph using the constraints Fh(R) (x, 11011) ∈
s
C1 (n, q2 , a11011 ), Fhs (x, 1111) ∈ C2 (n, q1 , a1 ). Otherwise, if N1 (x) − N1 (y) 6≡ 0 mod 7, N0 (x) − N0 (y) 6≡ 0 mod 7, and
N110011 (x) ≡ N110011 (y) mod 7, x can be recovered from y using Fhs (x, 110011) ∈ C2 (n, q1 , a110011 ).

10

The next lemma can be proven in the same manner as Lemma 4.
Lemma 12. Suppose N0 (x) − N0 (y) mod 7 = 1, and N1 (x) − N1 (y) mod 7 = 1. Then, x can be recovered from y.
The proofs of the next two lemmas are the same as Lemma 5 and Lemma 6.
Lemma 13. Suppose N0 (x) − N0 (y) mod 7 = 1 and N1 (x) − N1 (y) mod 7 = 0. Then, x can be recovered from y.
Lemma 14. Suppose N1 (x) − N1 (y) mod 7 = 1 and N0 (x) − N0 (y) mod 7 = 0. Then, x can be recovered from y.
Next, we consider the case where either N0 (y) > N0 (x) or N1 (y) > N1 (x). The result can be proven using ideas similar to
Lemma 7 and Lemma 11. The proof can be found in Appendix A.
Lemma 15. Suppose N0 (y) − N0 (x) mod 7 ∈ {1, 2, 3} or N1 (y) − N1 (x) mod 7 ∈ {1, 2, 3}. Then, x can be recovered from y.
The next lemma follows using similar ideas as from Lemma 8. The proof can be found in Appendix B.
Lemma 16. Suppose N1 (x) − N1 (y) mod 7 = 0, and N0 (x) − N0 (y) mod 7 = 0. Then, x can be recovered from y.
V. C ONSTRAINT R EDUNDANCY
The purpose of this section is to show that there is no asymptotic rate loss incurred by starting with our constrained sequence
space where there are no more than s symbols between consecutive appearances of v1 = 0000, v2 = 1111, v3 = 11011,
v4 = 110011, v 5 = 1 and v 6 = 0. Our goal will be to show that the probability a sequence of length n satisfies these constraints
converges to a constant for n → ∞. Let Ei be the event that P
constraint i is met by some sequence a selected uniformly at
6
random from {0, 1}n . We show that for all sufficiently large n, i=1 P r(Ei ) > 5. Then, we have by union bound
P r(E1 ∩ · · · ∩ E6 ) = 1 − P r(E¯1 ∪ · · · ∪ E¯6 )
>1−

6
X

P r(Ēi ) > 0.

(1)

i=1

This implies that the redundancy incurred is indeed a constant number of bits.
To compute Ei , we use the following argument. Set Xi to be a random variable counting the number of appearances of the
constraint sequence vi in a. Let Yi be the number of symbols between two consecutive appearances of the constraint. Then,
conditioning on Xi ,
X
P r(Ei ) =
P r(Yi 6 s)x P r(Xi = x) = E[P r(Yi 6 s)Xi ].
x
x

The next step is to use the fact that c is convex and apply Jensen’s inequality:
E[P r(Yi 6 s)Xi ] > P r(Yi 6 s)E[Xi ] .
First, we can easily compute the E[Xi ] terms. Let us set M = |vi | to be the constraint sequence length. In our case, M ∈
{1, 4, 5, 6}. Let aji = (ai , ai+1 , . . . , aj ) be a subsequence of a. Then, using linearity of expectation, we have that E[Xi ] =
Pn−M +1
P r(aji = vi ) = (n − M + 1)/2M .
i=1
Next, we consider the P r(Yi 6 s) probabilities; these probabilities measure waiting times. A useful observation is that constraint sequences such as 110011 have lower waiting times compared to the equal-length pattern 111111. This can be easily
formalized through a Markov chain analysis: we model the appearance of a constraint sequence through a series of states forming
a Markov chain. In the case of 111111, the appearance of any 0 prior to the final state takes us back to the initial state. However, this is not the case for 110011 (or any other mixed-run sequence of the same length), since, among other examples, the
appearance of a 1 in state 11 takes us back to the 11 state rather than the initial state. Therefore, since we are lower bounding
our probability, we may directly work with the constraint sequences 1111, 111111, and 111111. The 0000 constraint is identical
to 1111.
Next, observe that the waiting times satisfy the stochastic recursion YM +1 = YM + 1 + B YeM +1 , where B is a Bernoulli random
variable with parameter 1/2, all variables are independent, and YeM +1 is distributed like YM +1 . It can be shown that the solutions
to this recursion are exponential random variables; more specifically, 2−M YM converges (in distribution) to an exponential r.v.
with parameter 1/2. Then, we may write, for sufficiently large n,
P r(Yi 6 s) = P r(2−M Yi 6 2−M s)
>1 − exp(−2−(M +1) s).

11

Thus, for constraint i with length M , the probability P r(Ei ) is lower bounded as
n−M +1


s  2M
P r(Ei ) > 1 − exp − M +1
.
2
We can safely ignore the terms in the exponent that are not n/2M , since the resulting expression goes to 1.
Next, we substitute the value of s. Since s = 2M +1 log2 (n), we have that


n
s  2nM
1 − exp − M +1
= (1 − exp (− log2 (n))) 2M
2

 n
1 2M
= 1−
n

 n
2−M 2M
= 1− n
2M

=e

−2−M

.

For our constraints, we have M = (4, 4, 5, 6, 1, 1), yielding lower bounds on
is met.

P6

i=1

P r(Ei ) of 5.046 so that the condition in (1)

VI. C ONCLUSION
In this work, we provided a construction for a code capable of correcting two deletions improved upon existing art in terms of
the number of redundant bits. Open problems include extending these techniques to codes capable of correcting multiple deletions
as well as developing simple encoding techniques.
R EFERENCES
[1] K.A.S. Abdel-Ghaffar, F. Paluncic, H.C. Ferreira, and W.A. Clarke, “On Helberg’s generalization of the Levenshtein code for multiple deletion/insertion
error correction,” IEEE Transactions on Information Theory, vol. 58, no. 3, pp. 1804-1808, 2012.
[2] J. Brakensiek, V. Guruswami, and S. Zbarsky, “Efficient low-redundancy codes for correcting multiple deletions,” in Proceedings of the Twenty-Seventh
Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1884-1892, SIAM, 2016.
[3] S. Datta and S. W. McLaughlin, “An enumerative method for runlength-limited codes: permutation codes,” IEEE Transactions on Information Theory, vol.
45, no. 6, pp. 2199-2204, 1999.
[4] S. Datta and S. W. McLaughlin, “Optimal block codes for M -ary runlength-constrained channels,” IEEE Transactions on Information Theory, vol. 47, no.
5, pp. 2069-2078, 2001.
[5] I. Dumer, “Nonbinary double-error-correcting codes designed by means of algebraic varieties,” IEEE Trans. Inf. Theory, vol. 41, no. 6, pp. 1657–1666, Nov.
1995.
[6] F. V. Fomin, F. Grandoni, and D. Kratsch, “A measure & conquer approach for the analysis of exact algorithms,” Journal of the ACM (JACM), vol. 56, no.
5, pp. 25, 2009
[7] A.S.J. Helberg and H.C. Ferreira, “On multiple insertion/deletion correcting codes,” IEEE Transactions on Information Theory, vol. 48, no. 1, pp. 305-308,
2002.
[8] A.A. Kulkarni, and N. Kiyavash, “Nonasymptotic upper bounds for deletion correcting codes,” IEEE Transactions on Information Theory, vol. 59, no. 8,
pp. 5115-5130, 2013.
[9] V.I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals” Soviet Physics-Doklady, vol. 10, no. 8, pp. 707-710, 1966.
[10] F. Paluncic, Khaled A.S. Abdel-Ghaffar, H.C. Ferreira, and W.A. Clarke, “A multiple insertion/deletion correcting code for run-length limited sequences,”
IEEE Transactions on Information Theory, vol. 58 no. 3, pp. 1809-1824, 2012.
[11] R. M. Roth and P.H. Siegel, “Lee-metric BCH codes and their application to constrained and partial-response channels,” vol. 40, no. 4, pp. 1083-1096,
1994.
[12] F. F. Sellers, Jr., “Bit loss and gain correction codes,” IRE Transactions on Information Theory, vol. 8, no. 1, pp. 35-38, 1962.
[13] R. R. Varshamov and G. M. Tenengolts, “A code for correcting a single asymmetric error,” Avtomatika i Telemekhanika, vol. 26, no. 2, pp. 288-292, 1965.

A PPENDIX A
P ROOF OF L EMMA 15
Lemma 15. Suppose N0 (y) − N0 (x) mod 7 ∈ {1, 2, 3} or N1 (y) − N1 (x) mod 7 ∈ {1, 2, 3}. Then, x can be recovered from
y.
Proof: We consider the case where N0 (y)−N0 (x) mod 7 ∈ {1, 2, 3} and N1 (y)−N1 (x) mod 7 ∈ {1, 2, 3} since otherwise
x can be recovered from y using the same ideas as in the proof of Lemma 7. The deletion of a one from a run of length 1
cannot create/destroy a 110011 substring or a 11011 substring since the 1 needs to be adjacent to two runs of lengths `1 , `2
where `1 + `2 > 4 since at least one 0000 substring is created from x to y. Furthermore, the deletion of the one from a run of
length 1 clearly cannot create a 1111 substring from x to y. Therefore, the deletion of the zero from a run of length 1 creates
a 1111 substring from x to y. If, in addition, the deletion of the zero does also does not
 x
 preserve the 110011 substring from
to y, then according to Claim 3, the substring 11011 is preserved from x to y and dH Fh(R) (x, 11011), Fh(R) (y, 11011) = 1.
s
s
Using the same logic as in the proof of Lemma 11, according to Claim
P4 we can correct the deletion of a zero from a run of
length 1 using the constraints Fh(R) (x, 11011) ∈ C1 (n, q2 , a11011 ) and i odd r1 (x)i = b mod s + 1 and the deletion of the one
s
from a run of length > 4 can be corrected with the constraint Fhs (x, 0000) ∈ C2 (n, q1 , a0 ). Thus, the decoding in this case is
the same as described in the last paragraph of Lemma 11.

12

A PPENDIX B
P ROOF OF L EMMA 16
Lemma 16. Suppose N1 (x) − N1 (y) mod 7 = 0, and N0 (x) − N0 (y) mod 7 = 0. Then, x can be recovered from y.
Proof: Using the same logic as before, N1 (x) − N1 (y) mod 7 = 0 and N0 (x) − N0 (y) mod 7 = 0, there are two setups
to consider:
1) A symbol b was deleted from a run of length > 4 and another symbol b̄ from a run of length 1 was deleted which was
adjacent to a run of length `1 and another run of length `2 such that `1 + `2 = 4.
2) The 0000 and 1111 substrings were preserved from x to y.
The decoding procedure is the following. Suppose N110011n(x) ≡ N110011 (y) mod 7. Then we estimate x to be the sequence which
agrees with at least two of the following three constraints: Fhs (x, 0000) ∈ C2 (n, q1 , a0 ), Fhs (x, 1111) ∈ C2 (n, q1 , a1 ), Fhs (x, 110011) ∈
o
C2 (n, q1 , a110011 ) . Otherwise, if N110011 (x) 6≡ N110011 (y) mod 7, we estimate x to be the sequence which agrees with the
constraint Fhs (x, 0000) ∈ C2 (n, q1 , a0 ).
First suppose that N110011 (x) ≡ N110011 (y) mod 7 and suppose that 1) holds. If b = 0, then the decoding is correct since
in this case x agrees with the constraints Fhs (x, 1111) ∈ C2 (n, q1 , a2 ) and Fhs (x, 110011) ∈ C2 (n, q1 , a110011 ), since it is
not possible to create a 0000 substring and also to create/destroy 110011. Now, suppose b = 1. In this case, if N110011 (x) ≡
N110011 (y) mod 7, then the deletion of a zero from
n a run of length 1 did not create/destroy the substring 110011 and so x agrees
with at least two of the three constraints from Fhs (x, 0000) ∈ C2 (n, q1 , a0 ), Fhs (x, 1111) ∈ C2 (n, q1 , a1 ), Fhs (x, 110011) ∈
o
C2 (n, q1 , a110011 ) . Thus, the decoding is correct when N110011 (x) ≡ N110011 (y) mod 7 and 1) holds.
Next consider the case
n where N110011 (x) ≡ N110011 (y) mod 7 and suppose that 2) holds. Then clearly, x agrees with
o two of
the three constraints Fhs (x, 0000) ∈ C2 (n, q1 , a0 ), Fhs (x, 1111) ∈ C2 (n, q1 , a1 ), Fhs (x, 110011) ∈ C2 (n, q1 , a110011 ) and so
the decoding is correct in this case.
Suppose now that N110011 (x) 6≡ N110011 (y) mod 7 and that 1) holds. Notice that under this setup, b 6= 0, since the deletion of
a 0 from a run of length at least 4 and the deletion of a 1 from a run of length 1 that creates a 0000 substring cannot create/destroy
any substrings 110011 from x to y. If b = 1 and N110011 (x) 6≡ N110011 (y) mod 7, then a zero was deleted from a run of length
one and a one was deleted from a run of length > 4 so that the substring 0000 was preserved and so the decoding is correct in
this case.
Finally, we consider the case where N110011 (x) 6≡ N110011 (y) mod7 and 2) holds. If 2) holds and the 0000 substring is
preserved then clearly x agrees with the constraint Fhs (x, 0000) ∈ C2 (n, q1 , a0 ), and so the decoding procedure is correct in this
case as well.

