Efficiently decodable codes for the binary deletion channel ∗

arXiv:1705.01963v2 [] 26 Jul 2017

Venkatesan Guruswami†

Ray Li‡

Carnegie Mellon University
Pittsburgh, PA 15213

Abstract
In the random deletion channel, each bit is deleted independently with probability p. For the random
deletion channel, the existence of codes of rate (1 − p)/9, and thus bounded away from 0 for any p < 1,
has been known. We give an explicit construction with polynomial time encoding and deletion correction
algorithms with rate c 0 (1 − p) for an absolute constant c 0 > 0.

1 Introduction
We consider the problem of designing error-correcting codes for reliable and efficient communication on the
binary deletion channel. The binary deletion channel (BDC) deletes each transmitted bit independently with
probability p, for some p ∈ (0, 1) which we call the deletion probability. Crucially, the location of the deleted
bits are not known at the decoder, who receives a subsequence of the original transmitted sequence. The
loss of synchronization in symbol locations makes the noise model of deletions challenging to cope with.
As one indication of this, we still do not know the channel capacity of the binary deletion channel. Quoting
from the first page of Mitzenmacher’s survey [17]: “Currently, we have no closed-form expression for the
capacity, nor do we have an efficient algorithmic means to numerically compute this capacity.” This is in
sharp contrast with the noise model of bit erasures, where each bit is independently replaced by a ’?’ with
probability p (the binary erasure channel (BEC)), or of bit errors, where each bit is flipped independently
with probability p (the binary symmetric channel (BSC)). The capacity of the BEC and BSC equal 1 − p and
1 − h(p) respectively, and we know codes of polynomial complexity with rate approaching the capacity in
each case.
The capacity of the binary deletion channel is clearly at most 1 − p, the capacity of the simpler binary
erasure channel. Diggavi and Grossglauser [3] establish that the capacity of the deletion channel for p ≤ 12
is at least 1 − h(p). Kalai, Mitzenmacher, and Sudan [11] proved this lower bound is tight as p → 0, and
Kanoria and Montanari [12] determined a series expansion that can be used to determine the capacity exactly.
Turning to large p, Rahmati and Duman [18] prove that the capacity is at most 0.4143(1 − p) for p ≥ 0.65.
Drinea and Mitzenmacher [4, 5] proved that the capacity of the BDC is at least (1 − p)/9, which is within a
constant factor of the upper bound. In particular, the capacity is positive for every p < 1, which is perhaps
surprising. The asymptotic behavior of the capacity of the BDC at both extremes of p → 0 and p → 1 is
thus known.
∗ Research

supported in part by NSF grant CCF-1422045.
venkatg@cs.cmu.edu
‡ Email: ryli@andrew.cmu.edu
† Email:

This work is concerned with constructive results for coding for the binary deletion channel. That is, we
seek codes that can be constructed, encoded, and decoded from deletions caused by the BDC, in polynomial
time. Recently, there has been good progress on codes for adversarial deletions, including constructive
results. Here the model is that the channel can delete an arbitrary subset of pn bits in the n-bit codeword. A
code capable of correcting pn worst-case deletions can clearly also correct deletions caused by a BDC with
deletion probability (p − ϵ) with high probability, so one can infer results for the BDC from some results
√
for worst-case deletions. For small p, Guruswami and Wang [9] constructed binary codes of rate 1 − O( p)
to efficiently correct a p fraction worst-case deletions. So this also gives codes of rate approaching 1 for
the BDC when p → 0. For larger p, Kash et al. [13] proved that randomly chosen codes of small enough
rate R > 0 can correctly decode against pn adversarial deletions when p ≤ 0.17. Even non-constructively,
this remained the best achievability result in terms of correctable deletion fraction until the recent work of
Bukh, Guruswami, and Håstad [2]√who constructed codes of positive rate efficiently decodable against pn
adversarial deletions for any p < 2 − 1. For adversarial deletions, it is impossible to correct a deletion
fraction of 1/2, whereas the capacity of the BDC is positive for all p < 1. So solving the problem for the
much harder worst-case deletions is not a viable approach to construct positive rate codes for the BDC for
p > 1/2.
To the best of our knowledge, explicit efficiently decodable code constructions were not available for the
binary deletion channel for arbitrary p < 1. We present such a construction in this work. Our rate is worse
than the (1 − p)/9 achieved non-constructively, but has asymptotically the same dependence on p for p → 1.
Theorem 1.1. Let p ∈ (0, 1). There is an explicit a family of binary codes that (1) has rate (1 − p)/110, (2)
is constructible in polynomial time, (3) encodable in time O(N ), and (3) decodable with high probability on
the binary deletion channel with deletion probability p in time O(N 2 ). (Here N is the block length of the
code)

1.1 Some other related work
One work that considers efficient recovery against random deletions is by Yazdi and Dolecek [20]. In their
setting, two parties Alice and Bob are connected by a two-way communication channel. Alice has a string X ,
Bob has string Y obtained by passing X through a binary deletion channel with deletion probability p ≪ 1,
and Bob must recover X . They produce a polynomial-time synchronization scheme that transmits a total of
O(pn log(1/p)) bits and allows Bob to recover X with probability exponentially approaching 1.
For other models of random synchronization errors, Kirsch and Drinea [14] prove information capacity
lower bounds for channels with i.i.d deletions and duplications. Fertonani et al. [6] prove capacity bounds
for binary channels with i.i.d insertions, deletions, and substitutions.
For deletion channels over non-binary alphabets, Rahmati and Duman [18] prove a capacity upper bound
of C 2 (p) + (1 − p) log(|Σ|/2), where C 2 (p) denotes the capacity of the binary deletion channel with deletion
probability p, when the alphabet size |Σ| is even. In particular, using the best known bound for C 2 (p) of
C 2 (p) ≤ 0.4143(1 − p), the upper bound is (1 − p)(log |Σ| − 0.5857).
In [8], the authors of this paper consider the model of oblivious deletions, which is in between the BDC
and adversarial deletions in power. Here, the channel can delete any pn bits of the codeword, but must do
so without knowledge of the codeword. In this model, they prove the existence of codes of positive rate for
correcting any fraction p < 1 of oblivious deletions.

2

1.2 Our construction approach
Our construction concatenates a high rate outer code over a large alphabet that is efficiently decodable against
a small fraction of adversarial insertions and deletions, with a good inner binary code. For the outer code, we
can use the recent construction of [10]. To construct the inner code, we first choose a binary code correcting
a small fraction of adversarial deletions. By concentration bounds, duplicating bits of a codeword in a
disciplined manner is effective against the random deletion channel, so we, for some constant B, duplicate
every bit of the binary code B/(1 −p) times. We further ensure our initial binary code has only runs of length
1 and 2 to maximize the effectiveness of duplication. We add small buffers of 0s between inner codewords
to facilitate decoding.
One might wonder whether it would be possible to use Drinea and Mitzenmacher’s existential result
[4, 5] of a (1 − p)/9 capacity lower bound as a black box inner code to achieve a better rate together with
efficient decodability. We discuss this approach in §3.2 and elaborate on what makes such a construction
difficult to implement.

2 Preliminaries
General Notation. Throughout the paper, log x refers to the base-2 logarithm.
We use interval notation [a, b] = {a, a + 1, . . . , b} to denote intervals of integers, and we use [a] = [1, a] =
{1, 2, . . . , a}.
Let Binomial(n, p) denote the Binomial distribution.
Words. A word is a sequence of symbols from some alphabet. We denote explicit words using angle
brackets, like h01011i. We denote string concatenation of two words w and w ′ with ww ′. We denote
w k = ww · · · w where there are k concatenated copies of w.
A subsequence of a word w is a word obtained by removing some (possibly none) of the symbols in w.
Let ∆i/d (w 1 , w 2 ) denote the insertion/deletion distance between w 1 and w 2 , i.e. the minimum number of
insertions and deletions needed to transform w 1 into w 2 . By a lemma due to Levenshtein [15], this is equal
to |w 1 | + |w 2 | − 2 LCS(w 1 , w 2 ), where LCS denotes the length of the longest common subsequence.

Define a run of a word w to be a maximal single-symbol subword. That is, a subword w ′ in w consisting
of a single symbol such that any longer subword containing w ′ has at least two different symbols. Note the
runs of a word partition the word. For example, 110001 has 3 runs: one run of 0s and two runs of 1s.
We say that c ∈ {0, 1}m and c ′ ∈ {0, 1}m are confusable under δm deletions if it is possible to apply δm
deletions to c and c ′ and obtain the same result. If δ is understood, we simply say c and c ′ are confusable.
Concentration Bounds. We use the following forms of Chernoff bound.
Lemma 2.1 (Chernoff). Let A1 , . . . , An be i.i.d random variables taking values in [0, 1]. Let A =
and δ ∈ [0, 1]. Then


Pr[A ≤ (1 − δ ) E[A]] ≤ exp −δ 2 E[A]/2
Furthermore,

Pr[A ≥ (1 + δ ) E[A]] ≤



eδ
(1 + δ )1+δ

 E[A]

We also have the following corollary, whose proof is in Appendix A.
3

.

Ín

i=1 Ai

(1)

(2)

Lemma 2.2. Let 0 < α < β. Let A1 , . . . , An be independent random variables taking values in [0, β] such
that, for all i, E[Ai ] ≤ α. For γ ∈ [α, 2α], we have
" n
#


Õ
(γ − α)2n
Pr
.
(3)
Ai ≥ nγ ≤ exp −
3α β
i=1

3 Efficiently decodable codes for random deletions with p approaching 1
3.1 Construction
We present a family of constant rate codes that decodes with high probability on a binary deletion channel
with deletion fraction p (BDCp ). These codes have rate c 0 (1 − p) for an absolute positive constant c 0 , which
is within a constant of the upper bound (1 − p), which even holds for the erasure channel. By Drinea and
Mitzenmacher [4] the maximum known rate of a non-efficiently correctable binary deletion channel code is
(1 − p)/9.
The construction is based on the intuition that deterministic codes are better than random codes for the
deletion channel. Indeed, for adversarial deletions, length n √
random codes correct at most 0.22n deletions
[13], while explicitly constructed codes can correct close to ( 2 − 1)n deletions [2].
We begin by borrowing a result from [9].
Lemma 3.1 (Corollary of Lemma 2.3 of [9]). Let 0 < δ < 12 . For every binary string c ∈ {0, 1}m , there are
m 2
at most δm (1−δ
strings c ′ ∈ {0, 1}m such that c and c ′ are confusable under δm deletions.
)m

The next lemma gives codes against a small fraction of adversarial deletions with an additional run-length
constraint on the codewords.

Lemma 3.2. Let δ > 0. There exists a length m binary code of rate R = 0.6942 − 2h(δ ) − O(log(δm)/m)
correcting a δ fraction of adversarial insertions and deletions such that each codeword contains only runs
of size 1 and 2. Furthermore this code is constructible in time Õ(2(0.6942+R)m ).
Proof. It is easy to show that the number of codewords with only runs of 1 and 2 is Fm , the mth Fibonacci
number, and it is well known that Fm = φm + o(1) ≈ 20.6942m where φ is the golden ratio. Now we construct
m 2
the code by choosing it greedily. Each codeword is confusable with at most δm (1−δ
other codewords,
)m
so the number of codewords we can choose is at least
20.6942m
δm

m 2
(1−δ )m

= 2m(0.6942−2h(δ )−O (log(δm)/m)) .

(4)

We can find all words of length m whose run lengths are only 1 and 2 by recursion in time O(Fm ) =
O(20.6942m ). Running the greedy algorithm, we need to, for at most Fm · 2 Rm pairs of such words, determine
whether the pair is confusable (we only need to check confusability of a candidate word with words already
added to the code). Checking confusability of two words under adversarial deletions reduces to checking
whether the longest common subsequence is at least (1 − δ )m, which can be done in time O(m 2 ). This gives
an overall runtime of O(m 2 · Fm · 2 Rm ) = Õ(2(0.6942+R)m ).

Corollary 3.3. There exists a constant m ∗0 such that for all m ≥ m ∗0 , there exists a length m binary code of
rate Rin = 0.555 correcting a δ in = 0.0083 fraction of adversarial insertions and deletions such that each
4

codeword contains runs of size 1 and 2 only and each codeword starts and ends with a 1. Furthermore this
code is constructible in time O(21.25m ).
Our construction utilizes the following result as a black box for efficiently coding against an arbitrary
fraction of insertions and deletions with rate approaching capacity.
Theorem 3.4 (Theorem 1.1 of [10]). For any 0 ≤ δ < 1 and ϵ > 0, there exists a code C over alphabet Σ,
with |Σ| = poly(1/ϵ), with block length n, rate 1 − δ − ϵ, and is efficiently decodable from δn insertions and
deletions. The code can be constructed in time poly(n), encoded in time O(n), and decoded in time O(n 2 ).
We apply Theorem 3.4 for small δ , so we also could use the high rate binary code construction of [7] as
an outer code.
We now turn to our code construction for Theorem 1.1.
1
1
The code. Let B = 60, B ∗ = 1.43̄B = 86, η = 1000
, δ out = 1000
. Let m 0 = max(α log(1/δ out )/η, m ∗0 ),
∗
where α is a sufficiently large constant and where m 0 is given by Corollary 3.3. Let ϵout > 0 be small enough
such that the alphabet Σ, given by Theorem 3.4 with ϵ = ϵout and δ = δ out , satisfies |Σ| ≥ m 0 , and let Cout
be the corresponding code.

Let Cin : |Σ| → {0, 1}m be the code given by Corollary 3.3, and let Rin = 0.555, δ in = 0.0083,
and m = R1i n log |Σ| = O(log(1/ϵ)) be the rate, tolerable deletion fraction, and block length of the code,
respectively (Rin and δ in are given by Corollary 3.3). Each codeword of Cin has runs of length 1 and 2 only,
and each codeword starts and ends with a 1. This code is constructed greedily.
Our code is a modified concatenated code. We encode our message as follows.
• Outer Code. First, encode the message into the outer code, Cout , to obtain a word c (out ) = σ1 . . . σn .
• Concatenation with Inner Code. Encode each outer codeword symbol σi ∈ Σ by the inner code Cin .
• Buffer. Insert a buffer of ηm 0s between adjacent inner codewords. Let the resulting word be c (cat ) .
Let ci(in) = Cin (σi ) denote the encoded inner codewords of c (cat ) .
• Duplication. After concatenating the codes and inserting the buffers, replace each character (including
characters in the buffers) with ⌈B/(1 − p)⌉ copies of itself to obtain a word of length N := Bnm/(1 −p).
(dup)
}.
Let the resulting word be c, and the corresponding inner codewords be {ci
Rate. The rate of the outer code is 1 − δ out − ϵout , the rate of the inner code is Rin , the buffer and
1
and (1 − p)/B respectively. This gives a total rate that is slightly greater
duplications multiply the rate by 1+η
than (1 − p)/110.
Notation. Let s denote the received word after the codeword c is passed through the deletion channel.
Note that (i) every bit of c can be identified with a bit in c (cat ) , and (ii) each bit in the received word s can
be identified with a bit in c. Thus, we can define relations f (dup) : c (cat ) → c, and f (del) : c → s (that is,
relations on the indices of the strings). These are not functions because some bits may be mapped to multiple
(for f (dup) ) or zero (for f (del) ) bits. Specifically, f (del) and f (dup) are the inverses of total functions. In this
way, composing these relations (i.e. composing their inverse functions) if necessary, we can speak about
the image and pre-image of bits or subwords of one of c (cat ) , c, and s under these relations. For example,
during the Duplication step of encoding, a bit hb j i of c (cat ) is replaced with B/(1 − p) copies of itself, so the
corresponding string hb j i B/(1−p) in c forms the image of hb j i under f (dup) , and conversely the pre-image of
the duplicated string hb j i B/(1−p) is that bit hb j i.
Decoding algorithm.
5

• Decoding Buffer. First identify all runs of 0s in the received word with length at least Bηm/2. These
are our decoding buffers that divide the word into decoding windows, which we identify with subwords
of s.
• Deduplication. Divide each decoding window into runs. For each run, if it has strictly more than
B ∗ copies of a bit, replace it with as two copies of that bit, otherwise replace it with one copy. For
example, h0i 2B gets replaced with h00i while h0i B gets replaced with h0i. For each decoding window,
concatenate these runs of length 1 and 2 in their original order in the decoding window to produce a
deduplicated decoding window.
• Inner Decoding. For each deduplicated decoding window, decode an outer symbol σ ∈ Σout from
each decoding window by running the brute force deletion correction algorithm for Cin . That is, for
each deduplicated decoding window s ∗(in) , find by brute force a codeword c ∗(in) in Cin that such that
∆i/d (c ∗(in) , s ∗(in) ) ≤ δ inm. If c ∗(in) is not unique or does not exist, do not decode an outer symbol σ from
this decoding window. Concatenate the decoded symbols σ in the order in which their corresponding
decoding windows appear in the received word s to obtain a word s (out ) .
• Outer Decoding. Decode the message m from s (out ) using the decoding algorithm of Cout in Theorem 3.4.
(dup)

the decoding window whose pre-image under f (del) contains indices
For purposes of analysis, label as si
(dup)
(dup)
contains bits in multiple decoding
. If this decoding window is not unique (that is, the image of ci
in ci
(dup)
arbitrarily. Note this labeling may mean some decoding windows are unlabeled,
windows), then assign si
and also that some decoding windows may have multiple labels. In our analysis, we show both occurrences
(dup)
(dup)
after Deduplication to be si(in) .
, denote the result of si
are rare. For a decoding window si
The following diagram depicts the encoding and decoding steps. The pair ({ci(in) }i , c (cat ) ) indicates
that, at that step of encoding, we have produced the word c (cat ) , and the sequence {ci(in) }i are the “inner
codewords” of c (cat ) (that is, the words in between what would be identified by the decoder as decoding
(dup)
}i , c) is used similarly.
buffers). The pair ({ci
Cout

Ci n , Buf

m −−−−→ c (out ) −−−−−−−→

o
n
 Dup n
o 
(dup)
(in)
ci
, c (cat ) −−−→ ci
,c
i

i

BDC

DeBuf n (dup) o DeDup n (in) o Deci n (out ) Decout
−−−−−→ s
−−−−−→ m
−−−−−−→ si
s −−−−−→ si
i

i

Runtime. The outer code is constructible in poly(n) time and the inner code is constructible in time
O(21.25m ) = poly(1/ϵ), which is a constant, so the total construction time is poly(N ).
Encoding in the outer code is linear time, each of the n inner encodings is constant time, and adding the
buffers and applying duplications each can be done in linear time. The overall encoding time is thus O(N ).
The Buffer step of the decoding takes linear time. The Deduplication step of each inner codeword
takes constant time, so the entire step takes linear time. For each inner codeword, Inner Decoding takes
time O(m 2 2m ) = poly(1/ϵ) by brute force search over the 2m possible codewords: checking each of the 2m
codewords is a longest common subsequence computation and thus takes time O(m 2 ), giving a total decoding
time of O(m 2 2m ) for each inner codeword. We need to run this inner decoding O(n) times, so the entire
6

Inner Decoding step takes linear time. The Outer Decoding step takes O(n 2 ) time by Theorem 3.4. Thus the
total decoding time is O(N 2 ).
Correctness. Note that, if an inner codeword is decoded incorrectly, then one of the following holds.
1. (Spurious Buffer) A spurious decoding buffer is identified in the corrupted codeword during the Buffer
step.
2. (Deleted Buffer) A decoding buffer neighboring the codeword is deleted.
(dup)

3. (Inner Decoding Failure) Running the Deduplication and Inner Decoding steps on si
inner codeword incorrectly.

computes the

We show that, with high probability, the number of occurrences of each of these events is small.
The last case is the most nontrivial, so we deal with it first, assuming the codeword contains no spurious
decoding buffers and the neighboring decoding buffers are not deleted. In particular, we consider an i such
(dup)
(dup)
that our decoding window si
whose pre-image under f (del) only contains bits in ci
(because no
(dup)
appear in any other decoding window (because no spurious
deleted buffer) and no bits in the image of ci
buffer).
Recall that the inner code Cin can correct against δ in = 0.0083 fraction of adversarial insertions and
deletions. Suppose an inner codeword ci(in) = r 1 . . . rk ∈ Cin has k runs r j each of length 1 or 2, so that
m/2 ≤ k ≤ m.
Definition 3.5. A subword of α identical bits in the received word s is
• type-0 if α = 0
• type-1 if α ∈ [1, B ∗ ]
• type-2 if α ∈ [B ∗ + 1, ∞).
By abuse of notation, we say that a length 1 or 2 run r j of the inner codeword ci(in) has type-t j if the image
of r j in s under f (del) ◦ f (dup) forms a type-t j subword.
Let t 1 , . . . , tk be the types of the runs r 1 , . . . , rk , respectively. The image of a run r j under f (del) ◦ f (dup)
has length distributed as Binomial(B|r j |/(1 − p), 1 − p). Let δ = 0.43̄ be such that B ∗ = (1 + δ )B. By the
Chernoff bounds in Lemma 2.1, the probability that a run r j of length 1 is type-2 is
Pr

Z ∼Binomial(B/(1−p),1−p)


B
[Z > B ∗ ] < e δ /(1 + δ )1+δ < 0.0071.

(5)

Similarly, the probability that a run r j of length-2 is type-1 is at most
Pr

Z ∼Binomial(2B/(1−p),1−p)

2B

[Z ≤ B ∗ ] < e −((1−δ )/2)

< 0.0081.

The probability any run is type-0 is at most PrZ ∼Binomial(B/(1−p),1−p) [Z = 0] < e −B < 10−10 .

(6)

We now have established that, for runs r j in ci(in) , the probability that the number of bits in the image of
r j in s under f (del) ◦ f (dup) is “incorrect” (between 1 and B ∗ for length 2 runs, and greater than B ∗ for length
1 runs), is at most 0.0081, which is less than δ in . If the only kinds of errors in the Local Decoding step
7

were runs of c of length 1 becoming runs of length 2 and runs of length 2 become runs of length 1, then we
have that, by concentration bounds, with probability 1 − 2−Ω(m) , the number of insertions deletions needed
to transform si(in) back into ci(in) is at most δ inm, in which case si(in) gets decoded to the correct outer symbol
using Cin .
However, we must also account for the fact that some runs r j of ci(in) may become deleted completely
after duplication and passing through the deletion channel. That is, the image of r j in s under f (del) ◦ f (dup)
is empty, or, in other words, r j is type-0. In this case the two neighboring runs r j−1 and r j+1 appear merged
together in the Deduplication step of decoding. For example, if a run of 1s was deleted completely after
duplication and deletion, its neighboring runs of 0s would be interpreted by the decoder as a single run.
Fortunately, as we saw, the probability that a run is type-0 is extremely small (< 10−10 ), and we show each
type-0 run only increases ∆i/d (ci(in) , si(in) ) by a constant. We show this constant is at most 6.
To be precise, let Yj be a random variable that is 0 if |r j | = t j , 1 if {|r j |, t j } = {1, 2}, and 6 if t j = 0. We
Í
claim kj=1 Yj is an upper bound on ∆i/d (ci(in) , si(in) ). To see this, first note that if t j , 0 for all i, then the
number of runs of ci(in) and si(in) are equal, so we can transform ci(in) into si(in) by adding a bit to each length-1
(in)
(in)
type-2 run of ci and deleting a bit from each length-2 type-1 run of si .
(in)

Now, if some number, ℓ, of the t j are 0, then at most 2ℓ of the runs in ci become merged with some
other run (or a neighboring decoding buffer) after duplication and deletion. Each set of consecutive runs
r j , r j+2 , . . . , r j+2j ′ that are merged after duplication and deletion gets replaced with 1 or 2 copies of the
corresponding bit. For example, if r 1 = h11i, r 2 = h0i, r 3 = h11i, and if after duplication and deletion, 2B
bits remain in the image of each of r 1 and r 3 , and r 2 is type-0, then the image of r 1r 2r 3 under f (del) ◦ f (dup)
is h1i 4B , which gets decoded as h11i in the Deduplication step because h1i 4B is type-2. To account for the
type-0 runs in transforming ci(in) into si(in) , we (i) delete at most two bits from each of the ℓ type-0 runs in ci(in)
and (ii) delete at most two bits for each of at most 2ℓ merged runs in ci(in) . The total number of additional
insertions and deletions required to account for type-0 runs of c is thus at most 6ℓ, so we need at most 6
insertions and deletions to account for each type-0 run.
Our analysis covers the case when some bits in the image of ci(in) under f (del) ◦ f (dup) are interpreted
as part of a decoding buffer. Recall that inner codewords start and end with a 1, so that r 1 ∈ {h1i, h11i} for
every inner codeword. If, for example, t 1 = 0, that is, the image under f (del) ◦ f (dup) of the first run of 1s,
r 1 , is the empty string, then the bits of r 2 are interpreted as part of the decoding buffer. In this case too, our
analysis tells us that the type-0 run r 1 increases ∆i/d (ci(in) , si(in) ) by at most 6.
Í
We conclude kj=1 Yj is an upper bound for ∆i/d (ci(in) , si(in) ).
Note that if r j has length 1, then by (5) we have

E[Yj ] = 1 · Pr[r j is type-2] + 6 · Pr[r j is type-0] < 1 · 0.0071 + 6 · 10−9 < 0.0082.

(7)

Similarly, if r j has length 2, then by (6) we have
E[Yj ] = 1 · Pr[r j is type-1] + 6 · Pr[r j is type-0] < 1 · 0.0081 + 6 · 10−9 < 0.0082.

(8)

Thus E[Yj ] < 0.0082 for all i. We know the word si(in) is decoded incorrectly (i.e. is not decoded as σi ) in

8

the Inner Decoding step only if ∆i/d (ci(in) , si(in) ) > δ inm. The Yj are independent, so Lemma 2.2 gives
Pr[si(in) decoded incorrectly] ≤ Pr[Y1 + Y2 + · · · + Yk ≥ δ inm]
≤ Pr[Y1 + Y2 + · · · + Yk ≥ δ in k]


(δ in − 0.0082)2 k
≤ exp −
3 · 6 · δ in

≤ exp (−Ω(m))

(9)

where the last inequality is given by k ≥ m/2. Since our m ≥ Ω(log(1/δ out )) is sufficiently large, we have
the probability si(in) is decoded incorrectly is at most δ out /10. If we let Yj(i) denote the Yj corresponding to
Í (i)
(in)
inner codeword ci , the events Ei given by j Yj ≥ δ inm are independent. By concentration bounds on
the events Ei , we conclude the probability that there are at least δ out n/9 incorrectly decoded inner codewords
that are not already affected by spurious buffers and neighboring deleted buffers is 2−Ω(n) .
Our aim is to show that the number of spurious buffers, deleted buffers, and inner decoding failures is
small with high probability. So far, we have shown that, with high probability, assuming a codeword is not
already affected by spurious buffers and neighboring deleted buffers, the number of inner decoding failures
is small. We now turn to showing the number of spurious buffers is likely to be small.
A spurious buffer appears inside an inner codeword if many consecutive runs of 1s are type-0. A spurious
buffer requires at least one of the following: (i) a codeword contains a sequence of at least ηm/5 consecutive
type-0 runs of 1s, (ii) a codeword contains a sequence of ℓ ≤ ηm/5 consecutive type-0 runs of 1s, such that,
for the ℓ + 1 consecutive runs of 0s neighboring these type-0 runs of 1s, their image under f (del) ◦ f (dup) has
at least 0.5ηm 0s. We show both happen with low probability within a codeword.
A set of ℓ consecutive type-0 runs of 1s occurs with probability at most 10−10ℓ . Thus the probability
an inner codeword has a sequence of ηm/5 consecutive type-0 runs of 1s is at most m 2 · 10−10ηm/5 =
exp(−Ω(ηm)). Now assume that in an inner codeword, each set of consecutive type-0 runs of 1s has
size at most ηm/5. Each set of ℓ consecutive type-0 runs of 1s merges ℓ + 1 consecutive runs of 0s
in c, so that they appear as a single longer run in s. The sum of the lengths of these ℓ + 1 runs is
some number ℓ ∗ that is at most 2ℓ + 2. The number of bits in the image of these runs of ci(in) under
f (del) ◦ f (dup) is distributed as Binomial(ℓ ∗B/(1 − p), 1 − p). This has expectation ℓ ∗ B ≤ 0.41Bηm, so
by concentration bounds, the probability this run of s has length at least 0.5Bηm, i.e. is interpreted as
a decoding buffer, is at most exp(−Ω(ηm)). Hence, conditioned on each set of consecutive type-0 runs
of 1s having size at most ηm/5, the probability of having no spurious buffers in a codeword is at least
1 − exp(−Ω(ηm)). Thus the overall probability there are no spurious buffers a given inner codeword is at
least (1 − exp(−Ω(ηm))(1 − exp(−Ω(ηm))) = 1 − exp(−Ω(ηm)). Since each inner codeword contains at most
m candidate spurious buffers (one for each type-0 run of 1s), the expected number of spurious buffers in an
inner codeword is thus at most m · exp(−Ω(ηm)). By our choice of m ≥ Ω(log(1/δ out )/η), this is at most
δ out /10. The occurrence of conditions (i) and (ii) above are independent between buffers. The total number
of spurious buffers thus is bounded by the sum of n independent random variables each with expectation at
most δ out /10. By concentration bounds, the probability that there are at least δ out n/9 spurious buffers is
2−Ω(n) .
A deleted buffer occurs only when the image of the ηm 0s in a buffer under f (del) ◦ f (dup) is at most
Bηm/2. The number of such bits is distributed as Binomial(Bηm/(1 − p), 1 − p). Thus, each buffer is deleted
with probability exp(−Bηm) < δ out /10 by our choice of m ≥ Ω(log(1/δ out )/η). The events of a buffer
receiving too many deletions are independent across buffers. By concentration bounds, the probability that
there are at least δ out n/9 deleted buffers is thus 2−Ω(n) .
Each inner decoding failure, spurious buffer, and deleted buffer increases the distance ∆i/d (ci(out ) , si(out ) )
9

by at most 3: each inner decoding failure causes up to 1 insertion and 1 deletion; each spurious buffer causes
up to 1 deletion and 2 insertions; and each deleted buffer causes up to 2 deletions and 1 insertion. Our
message is decoded incorrect if ∆i/d (ci(out ) , si(out ) ) > δ out n. Thus, there is a decoding error in the outer code
only if at least one of (i) the number of incorrectly decoded inner codewords without spurious buffers or
neighboring deleted buffers, (ii) the number of spurious buffers, or (iii) the number of deleted buffers is at
least δ out n/9. However, by the above arguments, each is greater than δ out n/9 with probability 2−Ω(n) , so
there is a decoding error with probability 2−Ω(n) . This concludes the proof of Theorem 1.1.

3.2 Possible Alternative Constructions
As mentioned in the introduction, Drinea and Mitzenmacher [4, 5] proved that the capacity of the BDCp
is at least (1 − p)/9. However, their proof is nonconstructive and they do not provide an efficient decoding
algorithm.
One might think it is possible to use Drinea and Mitzenmacher’s construction as a black box. We could
follow the approach in this paper, concatenating an outer code given by [10] with the rate (1 − p)/9 randomdeletion-correcting code as a black box inner code. The complexity of the Drinea and Mitzenmacher’s
so-called jigsaw decoding is not apparent from [5]. However, the inner code has constant length, so
construction, encoding, and decoding would be constant time. Thus, the efficiency of the inner code would
not affect the asymptotic runtime.
The main issue with this approach is that, while the inner code can tolerate random deletions with
probability p, inner codeword bits are not deleted in the concatenated construction according to a BDCp ;
the 0 bits closer to the buffers between the inner codewords are deleted with higher probability because they
might be “merged” with a buffer. For example, if an inner codeword is h101111i, then because the codeword
is surrounded by buffers of 0s, deleting the leftmost 1 effectively deletes two bits because the 0 is interpreted
as part of the buffer. While this may not be a significant issue because the distributions of deletions in this
deletion process and BDCp are quite similar, much more care would be needed to prove correctness.
Our construction does not run into this issue, because our transmitted codewords tend to have many 1s
on the ends of the inner codewords. In particular, each inner codeword of Cin has 1s on the ends, so after the
Duplication step each inner codeword has B/(1 − p) or 2B/(1 − p) 1s on the ends. The 1s on the boundary of
the inner codeword will all be deleted with probability ≈ exp(−B), which is small. Thus, in our construction,
it is far more unlikely that bits are merged with the neighboring decoding buffer, than if we were to use
a general inner code construction. Furthermore, we believe our construction based on bit duplication of a
worst-case deletion correcting code is conceptually simpler than appealing to an existential code.
As a remark, we presented a construction with rate (1 −p)/110, but using a randomized encoding we can
improve the constant from 1/110 to 1/60. We can modify our construction so that, during the Duplication
step of decoding, instead of replacing each bit of c (cat ) with a fix number B/(1 −p) copies of itself, we instead
replaced each bit independently with Poisson(B/(1 − p)) copies of itself. Then the image of a run r j under
duplication and deletion is distributed as Poisson(B), which is independent of p. Because we don’t have a
dependence on p, we can tighten our bounding in (5) and (6). To obtain (1 − p)/60, we can take B = 28.12
and set B ∗ = 40, where B ∗ is the threshold after which runs are decoded as two bits instead of one bit in the
Deduplication step. The disadvantage of this approach is that we require our encoding to be randomized,
whereas the construction presented above uses deterministic encoding.

10

4 Future work and open questions
A lemma due to Levenshtein [15] states that a code C can decode against pn adversarial deletions if and
only if it can decode against pn adversarial insertions and deletions. While this does not automatically
preserve the efficiency of the decoding algorithms, all the recent efficient constructions of codes for worstcase deletions also extend to efficient constructions with similar parameters for recovering from insertions
and deletions [1, 7].
In the random error model, decoding deletions, insertions, and insertions and deletions are not the same.
Indeed, it is not even clear how to define random insertions. One could define insertions and deletions via
the Poisson repeat channel where each bit is replaced with a Poisson many copies of itself (see [4, 17]).
However, random insertions do not seem to share the similarity to random deletions that adversarial deletions
share with adversarial insertions; we can decode against arbitrarily large Poisson duplication rates, whereas
for codes of block length n we can decode against a maximum of n adversarial insertions or deletions [5].
Alternatively one can consider a model of random insertions and deletions where, for every bit, the bit is
deleted with a fixed probability p1 , a bit is inserted after it with a fixed probability p2 , or it is transmitted
unmodified with probability 1 − p1 − p2 [19]. One could also investigate settings involving memoryless
insertions, deletions, and substitutions [16].
There remain a number of open questions even concerning codes for deletions only. Here are a few
highlighted by this work.
1. Can we close the gap between
deletions?

√

2 − 1 and

1
2

on the maximum correctable fraction of adversarial

2. Can we construct efficiently decodable codes for the binary deletion channel with better rate, perhaps
reaching or beating the best known existential capacity lower bound of (1 − p)/9?
3. Can we construct efficient codes for the binary deletion channel with rate 1 − O(h(p)) for p → 0?

References
[1] Joshua Brakensiek, Venkatesan Guruswami, and Samuel Zbarsky. Efficient low-redundancy codes for
correcting multiple deletions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1884–1892, 2016.
[2] Boris Bukh, Venkatesan Guruswami, and Johan Håstad. An improved bound on the fraction of
correctable deletions. IEEE Trans. Information Theory, 63(1):93–103, 2017.
[3] Suhas Diggavi and Matthias Grossglauser. On transmission over deletion channels. In Proceedings
of the 39th Annual Allerton Conference on Communication, Control, and Computing, pages 573–582,
2001.
[4] Eleni Drinea and Michael Mitzenmacher. On lower bounds for the capacity of deletion channels. IEEE
Transactions on Information Theory, 52(10):4648–4657, 2006.
[5] Eleni Drinea and Michael Mitzenmacher. Improved lower bounds for the capacity of i.i.d. deletion and
duplication channels. IEEE Trans. Information Theory, 53(8):2693–2714, 2007.

11

[6] Dario Fertonani, Tolga M. Duman, and M. Fatih Erden.
Bounds on the capacity of channels with insertions, deletions and substitutions.
IEEE Trans. Communications, 59(1):2–6, 2011. URL: http://dx.doi.org/10.1109/TCOMM.2010.110310.090039,
doi:10.1109/TCOMM.2010.110310.090039.
[7] Venkatesan Guruswami and Ray Li.
Efficiently decodable insertion/deletion codes for
high-noise and high-rate regimes.
In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 620–624, 2016.
URL:
http://dx.doi.org/10.1109/ISIT.2016.7541373, doi:10.1109/ISIT.2016.7541373.
[8] Venkatesan Guruswami and Ray Li. Coding against deletions in oblivious and online models.
abs/1612.06335, 2017. Manuscript. URL: http://arxiv.org/abs/1612.06335.
[9] Venkatesan Guruswami and Carol Wang.
Deletion codes in the high-noise and highrate regimes.
IEEE Trans. Information Theory, 63(4):1961–1970, 2017.
URL:
http://dx.doi.org/10.1109/TIT.2017.2659765, doi:10.1109/TIT.2017.2659765.
[10] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: codes for insertions and
deletions approaching the singleton bound. In Proceedings of the 49th Annual ACM SIGACT Symposium
on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 33–46, 2017.
[11] Adam Kalai, Michael Mitzenmacher, and Madhu Sudan. Tight asymptotic bounds for the deletion
channel with small deletion probabilities. In IEEE International Symposium on Information Theory, ISIT 2010, June 13-18, 2010, Austin, Texas, USA, Proceedings, pages 997–1001, 2010. URL:
http://dx.doi.org/10.1109/ISIT.2010.5513746, doi:10.1109/ISIT.2010.5513746.
[12] Yashodhan Kanoria and Andrea Montanari. Optimal coding for the binary deletion channel with
small deletion probability. IEEE Trans. Information Theory, 59(10):6192–6219, 2013. URL:
http://dx.doi.org/10.1109/TIT.2013.2262020, doi:10.1109/TIT.2013.2262020.
[13] Ian Kash, Michael Mitzenmacher, Justin Thaler, and John Ullman. On the zero-error capacity threshold
for deletion channels. In Information Theory and Applications Workshop (ITA), pages 1–5, January
2011.
[14] Adam Kirsch and Eleni Drinea. Directly lower bounding the information capacity for channels
with i.i.d.deletions and duplications. IEEE Trans. Information Theory, 56(1):86–102, 2010. URL:
http://dx.doi.org/10.1109/TIT.2009.2034883, doi:10.1109/TIT.2009.2034883.
[15] Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals.
Dokl. Akad. Nauk, 163(4):845–848, 1965 (Russian). English translation in Soviet Physics Doklady,
10(8):707-710, 1966.
[16] Hugues Mercier, Vahid Tarokh, and Fabrice Labeau. Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors. IEEE Trans. Information Theory, 58(7):4306–4330, 2012. URL: http://dx.doi.org/10.1109/TIT.2012.2191682,
doi:10.1109/TIT.2012.2191682.
[17] Michael Mitzenmacher. A survey of results for deletion channels and related synchronization channels.
Probability Surveys, 6:1–33, 2009.
[18] Mojtaba Rahmati and Tolga M. Duman. Upper bounds on the capacity of deletion channels
using channel fragmentation. IEEE Trans. Information Theory, 61(1):146–156, 2015. URL:
http://dx.doi.org/10.1109/TIT.2014.2368553, doi:10.1109/TIT.2014.2368553.
12

[19] Ramji Venkataramanan, Sekhar Tatikonda, and Kannan Ramchandran. Achievable rates for channels
with deletions and insertions. IEEE Trans. Information Theory, 59(11):6990–7013, 2013. URL:
http://dx.doi.org/10.1109/TIT.2013.2278181, doi:10.1109/TIT.2013.2278181.
[20] S. M. Sadegh Tabatabaei Yazdi and Lara Dolecek. A deterministic polynomial-time protocol for
synchronizing from deletions. IEEE Trans. Information Theory, 60(1):397–409, 2014. URL:
http://dx.doi.org/10.1109/TIT.2013.2279674, doi:10.1109/TIT.2013.2279674.

A

Proof of Lemma 2.2

Proof. For each i, we can find a random variable Bi such that Bi ≥ Ai always, Bi takes values in [0, β], and
E[Bi ] = α. Applying Lemma 2.1 gives
#
#
" n
" n
Õ
Õ
Bi ≥ nγ
Ai ≥ nγ ≤ Pr
Pr
i=1

"

i=1
n
Õ


 γ − α  nα
Bi
≤ Pr
≥ 1+
β
α
β
i=1
γ −α  2 nα
· β ª
α
©
≤ exp ­−
®
3
«
 ¬
2
(γ − α) n
.
= exp −
3α β

#

(10)


13

