1

Efficient Systematic Encoding of
Non-binary VT Codes

arXiv:1708.04071v2 [cs.IT] 30 Aug 2017

Mahed Abroshan, Ramji Venkataramanan and Albert Guillén i Fàbregas

Abstract
Varshamov-Tenengolts (VT) codes are a class of codes which can correct a single deletion or
insertion with a linear-time decoder. This paper addresses the problem of efficient encoding of nonbinary VT codes, defined over an alphabet of size q > 2. We propose a simple linear-time encoding
method to systematically map binary message sequences onto VT codewords. The method provides a
new lower bound on the size of q-ary VT codes of length n.

I. I NTRODUCTION
Designing codes for correcting deletions or insertions is well known to be a challenging
problem; see, e.g., [1]–[8]. For the special case of correcting one insertion or deletion, there
exists an elegant class of codes called Varshamov-Tenengolts (VT) codes. Binary VT codes
were first introduced by Varshamov and Tenengolts in [9] for channels with asymmetric errors.
Later, Levenshtein [10] showed that they can be used for correcting a single deletion or insertion
with a simple decoding algorithm whose complexity is linear in the code length [1]. Tenengolts
subsequently introduced a non-binary version of VT codes, defined over a q-ary alphabet for any
q > 2 [11]. The q-ary VT codes retain many of the attractive properties of the binary codes. In
particular, they can correct deletion or insertion of a single symbol from a q-ary VT codeword
with a linear-time decoder.
M. Abroshan and R. Venkataramanan are with the Department of Engineering, University of Cambridge, UK,
(ma675@cam.ac.uk, ramji.v@eng.cam.ac.uk).
A. Guillén i Fàbregas is with the Department of Information and Communication Technologies, Universitat Pompeu Fabra,
Barcelona 08018, Spain, also with the Institució Catalana de Recerca i Estudis Avançats (ICREA), Barcelona 08010, Spain, and
also with the Department of Engineering, University of Cambridge, Cambridge CB2 1PZ, U.K. (e-mail: guillen@ieee.org).
This work was supported in part by the European Research Council under Grants 259663 and 725411, in part by the Spanish
Ministry of Economy and Competitiveness under Grant Grant TEC2016-78434-C3-1-R.

2

Given the simplicity of VT decoding, a natural question is: can one construct a linear-time
encoder to efficiently map binary message sequences onto VT codewords? For binary VT codes,
such an encoder was proposed by Abdel-Ghaffar and Ferriera [12]. (A similar encoder was also
described in [13].) However, the issue of efficient encoding for non-binary VT codes has not
been addressed previously, to the best of our knowledge. In this paper, we propose an efficient
systematic encoder for non-binary VT codes. The encoder has complexity that is linear in the
code length, and is systematic in the sense that the message bits are assigned to pre-specified
positions in the codeword. The encoder also yields a new lower bound on the size of q-ary VT
codes, for q > 2.
VT codes are a key ingredient of recent code constructions for channels with segmented
deletions and insertions [14], [15], and the proposed VT encoder can be applied to these
constructions. VT codes have also recently been used in algorithms for synchronization from
deletions and insertions, e.g., [16]–[19].
In [11, Sec. 5], Tenengolts introduced a systematic non-binary code that can correct a single
deletion or insertion. However, this code is not strictly a VT code as its codewords do not
necessarily share the same VT parameters. (Formal definitions of VT codes and their parameters
are given in the next two sections.) In this paper, we propose an encoder for VT codes defined
in the standard way, noting that using standard VT codes is a key requirement in some of the
code constructions mentioned above.
Notation: Sequences are denoted by capital letters, and scalars by lower-case letters. Throughout, we use n for the code length and k for the number of message bits mapped to the codeword.
The set Zq = {0, 1, · · · , q − 1} is the finite integer ring of size q. We consider the natural order
for the elements of Zq , i.e., 0 < 1 . . . < (q − 1). The term dyadic index will be used to refer to
an index that is a power of 2.
The rest of the paper is organized as follows. In the next section, we formally define binary
VT codes and briefly review the systematic encoder from [12]. In Section III, we define the
q-ary VT codes, and describe the systematic encoding method and the resulting lower bound on
the size of the codes.

3

II. B INARY VT

CODES

The VT syndrome of a binary sequence S = s1 s2 · · · sn ∈ Zn2 is defined as
syn(S) ,

n
X

i si

mod (n + 1).

(1)

i=1

For positive integers n and 0 ≤ a ≤ n, the VT code of length n and syndrome a, is defined as

VTa (n) = S ∈ Zn2 : syn(S) = a ,

(2)

i.e., the set of binary sequences S of length n that satisfy syn(S) = a. For example, the VT
code of length 3 and syndrome 2 is
3
n
o
X
3
VT2 (3) = s1 s2 s3 ∈ Z2 :
j sj = 2 mod 4
j=1

(3)

= {010, 111}.
Each of the sets VTa (n), 0 ≤ a ≤ n, is a code that can correct a single deletion or insertion
with a decoder whose complexity is linear in n. The details of the decoding algorithm can be
found in [1].
The (n + 1) sets VTa (n), 0 ≤ a ≤ n, partition the set of all binary sequences of length n, i.e.,
each sequence S ∈ Zn2 belongs to exactly one of the sets. Therefore, the smallest of the codes
VTa (n) will have at most

2n
n+1

min

sequences. Hence

0≤a≤n

1
1
log2 |VTa (n)| ≤ 1 − log2 (n + 1).
n
n

(4)

An exact formula for the size |VTa (n)| was given by Ginzburg [20]. The formula [1, Theorem
2.2] does not give an analytical expression for general n, but it shows that if (n + 1) is a power
of 2, then |VTa (n)| = 2n /(n + 1), for 0 ≤ a ≤ n. Moreover, for general n, the formula can be
used to deduce that the sizes of the codes VTa (n) are all approximately 2n /(n + 1). In particular,
2n
2n
− 2(n+1)/3 ≤ |VTa (n)| ≤
+ 2(n+1)/3 ,
(n + 1)
(n + 1)

for a ∈ {0, . . . , n}.

(5)

Abdel-Ghaffar and Ferriera [12] proposed a systematic encoder to map k-bit message sequences onto codewords in |VTa (n)|, where k = n − ⌈log2 (n + 1)⌉. We briefly review the
encoding procedure as it is an ingredient of our systematic q-ary VT encoder. Consider a k-bit
message M = m1 · · · mk to be encoded into a codeword C = c1 · · · cn ∈ VTa (n), for some
a ∈ {0, 1, · · · , n}. The number of “parity” bits is denoted by t = n − k = ⌈log2 (n + 1)⌉. The

4

idea is to use the code bits in dyadic positions, i.e., c2i , for 0 ≤ i ≤ (t − 1), to ensure that
syn(C) = a. The encoding steps are:
1) Denote the first k non-dyadic indices by {j1 , · · · , jk }, where the indices are in ascending
order, i.e., j1 = 3, j2 = 5, . . . We set cji equal to the message bit mi , for 1 ≤ i ≤ k.
2) First set the bits in all the dyadic positions to be zero and denote the resulting sequence
by C ′ = c′1 · · · c′n (so that we have c′2i = 0 for 0 ≤ i ≤ t − 1 and c′jl = ml for 1 ≤ l ≤ k =
(n − t)). Define the deficiency d as the difference between the desired syndrome a and the
syndrome of C ′ . That is,
d = a − syn(C ′ ) mod (n + 1).
3) Let the binary representation of d be dt−1 . . . d1 d0 , i.e., d =
0 ≤ i ≤ (t − 1), to obtain C.

(6)
Pt−1
i=0

2i di . Set c2i = di , for

The rate of this systematic encoder is R = 1 − n1 ⌈log2 (n + 1)⌉, regardless of the syndrome
a ∈ {0, . . . , n}. Comparing with (4), we observe that the rate loss for the smallest VT code of
length n is less than

1
.
n

On the other hand, if (n + 1) is not a power of two, the rate loss for

the larger VT codes may be higher due to codewords that are unused by the encoder. However
this rate loss is unavoidable with any systematic encoder [12].
We remark that the dyadic positions are not the only set of positions that can be used for
syndrome bits. For instance, the following set of indices also produce all syndromes:
{ci0 , · · · , cit−1 } where

ij = −2j

(mod n + 1) for 0 ≤ j ≤ t − 1.

This can be helpful in some applications (see e.g. [15]) where some code bits are already reserved
for prefixes or suffixes, and thus cannot be used as syndrome bits. In general, a set of positions
{p1 , p2 , · · · , pr } can be used for syndrome bits if for each syndrome a ∈ {0, · · · , n}, there exists
a subset P ⊆ {p1 , p2 , · · · , pr } such that
X
pj = a (mod n + 1).

(7)

j∈P

In other words, for each a ∈ {0, · · · , n}, there should exist binary coefficients b1 , · · · , br such
that

r
X
j=1

bj pj = a

(mod n + 1).

(8)

5

III. E FFICIENT E NCODING

FOR

N ON - BINARY VT

CODES

For any code length n, the VT codes over Zq , for q > 2 are defined as follows [11]. For each
q-ary sequence S = s0 s1 · · · sn−1 ∈ Znq , define a corresponding length (n − 1) auxiliary binary
sequence AS = α1 α2 . . . αn−1 as follows1. For 1 ≤ i ≤ n − 1,


1
if si ≥ si−1
αi =

0
if si < si−1 .

(9)

We also define the modular sum of S as

sum(S) =

n−1
X

si

(mod q).

(10)

i=0

For 0 ≤ a ≤ n − 1 and b ∈ Zq , the q-ary VT code with length n and parameters (a, b) is defined
as

VTa,b (n) = S ∈ Znq : syn(AS ) = a, sum(S) = b .

(11)

Each of the sets VTa,b (n) is a code that can correct deletion or insertion of a single symbol
with a decoder whose complexity is linear in the code length n. The details of the decoding
algorithm can be found in [11, Sec. II].
Similarly to the binary case, the codes VTa,b (n), for 0 ≤ a ≤ n − 1 and b ∈ Zq , partition the
space Znq of all q-ary sequences of length n. For a given n, there are nq of these codes, and
hence the smallest of them will have no more than

qn
nq

sequences. Let Rmin be the rate of the

smallest of these codes, i.e.,
Rmin , min
a,b

log2 |VTa,b (n)|
,
n

(12)

where the minimum is over 0 ≤ a ≤ n − 1 and b ∈ Zq . We then have the bound
Rmin ≤ log2 q −

1
1
log2 n − log2 q bits/symbol.
n
n

(13)

The encoding procedure described below yields a lower bound on the size of |VTa,b (n)| (see
Proposition 1), which shows that for q ≥ 4,
1
1
Rmin ≥ log2 q− ⌈log2 n⌉(3 log2 q−2 log2 (q−1))− (5 log2 (q−1)−3 log 2 q) bits/symbol. (14)
n
n
1

For non-binary sequences, we start the indexing from 0 as this makes it convenient to describe the encoding procedure in

Section III.

6

Kulkarni and Kiyavash [21] have shown that the size of any single deletion correcting q-ary
code of length n is bounded by

q n −q
.
(q−1)(n−1)

This yields a rate upper bound Rmax for any single

deletion correcting code, where
Rmax ≤ log2 q −

log2 (n − 1) log2 (q − 1)
−
.
n
n

(15)

We now describe the encoder to map a sequence of message bits to a codeword of the q-ary
VT code VTa,b (n). For simplicity, we first assume that q is a power of two, and address the case
of general q at the end of this section. We will map a k-bit message M = m1 m2 · · · mk to a
codeword in VTa,b (n), where
k = (n − 3t + 3) log2 q + (t − 3)(2 log2 q − 1) + (log2 q − 1)
= n log2 q − t(log2 q + 1) − 2(log2 q − 1),

(16)
(17)

with t = ⌈log2 n⌉. Therefore, the rate of our encoding scheme is
R = log2 q −

⌈log2 n⌉(log2 q + 1) 2 log2 q − 2
−
bits/symbol.
n
n

(18)

Our encoding method gives a lower bound on the size of any non-binary VT code of length
n. An immediate lower bound on the size is 2k , with k given by (17). The proposition below
gives a slightly better bound, which is obtained by modifying the encoding method to map q-ary
message sequences to q-ary VT codewords, rather than a binary message sequence to a q-ary
VT codeword.
Proposition 1. For n ≥ 6, q ≥ 4, and any 0 ≤ a ≤ n, and b ∈ Zq , we have
|VTa,b (n)| ≥ (q − 1)2t−5 q n−3t+3 ,
= q n(1− n [3 log2 q−2 log2 (q−1)]− n [5 log2 (q−1)−3 log2 q])
t

1

where t = ⌈log2 n⌉.
The proof of the proposition is given at the end of this section, after describing the encoding
procedure. We emphasize that we use t = ⌈log2 n⌉ throughout this section (as opposed to
⌈log2 (n + 1)⌉ used for binary VT encoding) because the binary auxiliary sequence has length
(n − 1).

7

A. Encoding procedure
The high level idea for mapping a k-bit message to a codeword C ∈ VTa,b (n) is the following.
Similarly to the binary case, we reserve the t dyadic positions in the binary auxiliary sequence
AC to ensure that syn(AC ) = a. Recall from (9) that each bit of AC is determined by comparing
two adjacent symbols of the q-ary sequence C. Therefore, to ensure that syn(AC ) = a we not
only reserve the symbols in the dyadic positions of C, but also place some restrictions on the
symbols adjacent to the dyadic positions. Finally, we use the first three symbols of C to ensure
that sum(C) = b. We explain the method in six steps with the help of the following running
example.
Example 1. Let q = 8, n = 16, and suppose that we wish to encode a binary message M to a
codeword C in VT0,1 (16). We have t = ⌈log2 n⌉ = 4 and log2 q = 3. Therefore, from (17) the
length of M is k = 3(n − 3t + 3) + 5(t − 3) + 2 = 25 bits. Let
M = 110 001 000 111 010 101 000 11100 11.

(19)

Step 1. Let S be the set of pairs of symbols adjacent to a dyadic symbol, i.e.,
S = {(c2j −1 , c2j +1 ), for 2 ≤ j ≤ (t − 1)}.

(20)

There are |S| = (t − 2) pairs of symbols in S. Excluding c0 , the number of symbols in C that
are neither in dyadic positions nor in S is
(n − 1) − 2|S| − t = (n − 3t + 3).

(21)

Assign the first (n − 3t + 3) log2 q bits of the message M to these symbols, by converting each
set of log2 q bits to a q-ary symbol. This corresponds to the first term in (16).
In Example 1, (n − 3t + 3) log2 q = 18, and the representation of first 18 bits of M in Z8 is
6 1 0 7 2 5 0. Therefore the sequence C is
C = c0 c1 c2 c3 c4 c5 6 c7 c8 c9 1 0 7 2 5 0.

(22)

Step 2. In this step, we assign the remaining bits of the message to the symbols in S. For
a given dyadic position c2j , j = 2, 3, · · · , (t − 1), we constrain the pair of adjacent symbols
(c2j −1 , c2j +1 ) to belong to the following set
T = {(r, l) ∈ Zq × Zq : r 6= 0, l 6= (r − 1)}.

(23)

8

Via (23), we enforce c2j −1 6= 0 because if c2j −1 were 0, then we necessarily have c2j ≥ c2j −1
which constrains the value of a2j to 1. However, a2j needs to be unconstrained in order to
guarantee that any desired syndrome can be generated. Furthermore, we will see in Step 5 that if
c2j +1 = c2j −1 −1, then we may be unable find a suitable symbol c2j compliant with the restrictions
induced by the auxiliary sequence. We therefore enforce the constraint c2j +1 6= c2j −1 − 1 using
(23). It is easy to see that |T | = (q − 1)2 .
Excluding the pair (c3 , c5 ), there are (t − 3) pairs in S. If we were encoding q-ary message
symbols, each of these (t − 3) pairs could take any pair of symbols in T . Since we are encoding
message bits, we use a look up table to map ⌊log2 |T |⌋ = 2 log2 q − 1 bits to each of the pairs in
S excluding (c3 , c5 ). We thus map (t − 3)(2 log2 q − 1) bits to the pairs in S excluding (c3 , c5 ).
This corresponds to the second term in (16).
Next, set c3 = q − 1. This choice is important as it will facilitate step 6. Since (c3 , c5 ) ∈ T ,
when c3 = q − 1, then c5 has to be such that c5 6= q − 2. Hence, there are q − 1 possible values
for c5 . As we are encoding a binary message, we map ⌊log2 (q − 1)⌋ = log2 q − 1 bits to c5 using
a look-up table. This corresponds to the third term in (16). We note that the two look-up tables
used in this step have sizes at most (q − 1)2 and q, respectively. Thus, in steps one and two in
total we have mapped the claimed k message bits to the symbols of C.
In Example 1, as seen from (22), (c7 , c9 ) is the only pair in S different from (c3 , c5 ). We can
assign 2 log2 q − 1 = 5 bits to (c7 , c9 ). After the first 18 message bits mapped in Step 1, the next
five bits in M are 11100. Suppose that in our look-up table these bits correspond to the pair
(3, 5). We then have (c7 , c9 ) = (3, 5). Also, we fix c3 = q − 1 = 7, and the last two message
bits determine c5 . The last two message bits are 11. Suppose that 3 is the corresponding symbol
in the look-up table. We therefore set c5 = 3. Therefore, we have
C = c0 c1 c2 7 c4 3 6 3 c8 5 1 0 7 2 5 0.

(24)

Up to this point, we have mapped our k message bits to a partially filled q-ary sequence. In the
following steps we ensure that the resulting sequence lies in the correct VT code by carefully
choosing remaining (t+1) symbols to obtain the auxiliary sequence syndrome a and the modular
sum b.
Step 3. In this step, we specify the bits in the non-dyadic locations of the auxiliary sequence
AC . Notice that according to (9), in order to define a2j +1 , the value of c2j should be known. This
is not the case here as the dyadic positions in C have been reserved to generate the required

9

syndrome. To circumvent this issue, we determine a2j +1 (for 1 < j < t) by comparing c2j +1
with c2j −1 as follows:
a2j +1 =



1


0

if c2j +1 ≥ c2j −1 ,

(25)

if c2j +1 < c2j −1 .

As we shall show in step 5, we will be able to make these choices for the auxiliary sequence
compatible with the definition of a valid auxiliary sequence in (9).
Next, since we have chosen c3 = q − 1, from the rule in (9) we have a3 = 1, regardless of
what c2 is. The other non-dyadic positions of the auxiliary sequence AC can be filled in using
(9), i.e., ai = 1 if ci ≥ ci−1 , and 0 otherwise.
For our example with C shown in (24), at the end of this step we have
AC = a1 a2 1 a4 0 1 0 a8 1 0 0 1 0 1 0.

(26)

Step 4. In this step, we use the binary encoding method described in Section II to find the bits
in the dyadic positions a20 , · · · , a2t−1 such that syn(AC ) = a. With this, the auxiliary sequence
AC is fully determined.
In the example, we need to find a1 , a2 , a4 and a8 such that syn(AC ) = 0. First, we set the
syndrome bits a1 = a2 = a4 = a8 = 0, and denote the resulting sequence by
A′C = 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0.

(27)

Now, syn(A′C ) = 12, and the deficiency d = 0 − 12 (mod 6) = 4. The binary representation of
d is d3 d2 d1 d0 = 0100. Hence, a1 = a2 = a8 = 0 and a4 = 1 will produce the desired syndrome.
Summarizing, we have the following auxiliary sequence
AC = 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0.

(28)

Step 5. In this step, we specify the symbols of C in the dyadic positions (except c1 and c2 ).
This will be done by ensuring that AC is a valid auxiliary sequence consistent with the definition
in (9). In particular, the choice of c2j for j = 2, · · · , t − 1, should be consistent with a2j +1 and
a2j . We ensure this by choosing c2j (for 1 < j < t) as follows:


c2j −1 − 1
if a2j = 0,
c2j =

c2j −1
if a2j = 1.

(29)

From the definition in (9), this choice is consistent with a2j . Now we show that it is also
consistent with a2j +1 . If a2j +1 = 1, then according to (25), c2j +1 ≥ c2j −1 ; then the choice of c2j

10

in (29) always guarantees that c2j −1 ≥ c2j , and thus c2j +1 ≥ c2j . Next suppose that a2j +1 = 0.
Then according to (25), c2j +1 < c2j −1 . We need to verify that c2j +1 < c2j Now, if a2j = 1, then
c2j = c2j −1 and c2j +1 < c2j . Also, if a2j = 0, from (29) we have c2j = c2j −1 − 1. Since symbols
adjacent to dyadic positions (c2j −1 , c2j +1 ) are chosen from T (see step 2), then c2j +1 6= c2j −1 −1.
Thus, we have that c2j +1 < c2j −1 − 1 = c2j . Therefore, in either case the choice is consistent
with (9).
For the example, using (29) and (28) we obtain
C = c0 c1 c2 7 7 3 6 3 2 5 1 0 7 2 5 0.

(30)

Step 6. Finally, we need to find c0 , c1 and c2 that are compatible with a1 , a2 , a3 (the first three
bits of the auxiliary sequence), and such that sum(C) = b. Let
n
X
w ,b−
ci (mod q).

(31)

i=3

Hence we need c0 + c1 + c2 = w (mod q). We will show that when q ≥ 4, we can find three
distinct integers (x, y, z) such that 0 ≤ x < y < z < q and x + y + z = w (mod q). We will
assign these numbers to c0 , c1 and c2 . Also recall that we set c3 = q − 1; hence we always have
x, y, z ≤ c3 , which is consistent with a3 = 1.
The triplet with smallest numbers that we can choose is x = 0, y = 1, z = 2. For this choice,
w = 0 + 1 + 2 = 3 (mod q). By increasing z from 2 to q − 1 with x = 0 and y = 1, we can
produce any value of w from 3 to q − 1 as well as w = 0. Finally, the only remaining values
are w = 1, 2. To obtain these values, we choose x, y, z as follows.
1) w = 1: Choose x = 0, y = 2, z = q − 1.
2) w = 2: Choose x = 1, y = 2, z = q − 1.
Hence, we have shown that for q ≥ 4, any w ∈ Zq can be expressed as the (mod q) sum
of three distinct elements of Zq . Assigning these elements to c0 , c1 , c2 in the order required
by the auxiliary sequence completes the encoding procedure. We now have sum(C) = b and
syn(AC ) = a, and thus C ∈ VTa,b (n) as required.
In our example, from (30) we have
15
X

ci = 48 = 0 (mod 8),

(32)

i=3

and b = 1. Therefore we need c0 + c1 + c2 = 1 (mod 8). We have a1 = a2 = 0 so c0 > c1 > c2
is the correct order. We therefore assign c0 = 7, c1 = 2, and c2 = 0 to obtain the codeword.
C = 7 2 0 7 7 3 6 3 2 5 1 0 7 2 5 0 ∈ VT0,1 (16).

(33)

11

It can be verified that sum(C) = 1, and the auxiliary sequence syndrome syn(AC ) = 0.
B. The case where q is not a power of two
When log2 q is not an integer, the main difference is that we map longer sequences of bits to
sequences of q-ary symbols. Recall that in step 1, we determine (n − 3t + 3) symbols of the
q-ary codeword. One can map ⌊(n − 3t + 3) log2 q⌋ bits to these (n − 3t + 3) symbols using
standard methods to convert an integer expressed in base 2 into base q. In the second step,
as described earlier we can map ⌊log2 (q − 1)2 ⌋ bits to (t − 3) pairs in S (excluding (c3 , c5 )).
Moreover ⌊log2 (q − 1)⌋ bits can be mapped to c5 . Therefore, in total we can map k bits to a
q-ary VT codeword of length n, where
k = ⌊(n − 3t + 3) log2 q⌋ + (t − 3)⌊log2 (q − 1)2 ⌋ + ⌊log2 (q − 1)⌋
≥ n log2 q − t(log2 q + 2) − (2 log2 q − 4).

(34)
(35)

For q ≥ 4, the remaining steps are identical to the case where q is a power of two. The case of
q = 3 is slightly different and it is discussed in Appendix A.
C. Proof of Proposition 2
The result can be directly derived from steps one and two of our encoding method by mapping
sequences of q-ary message symbols (rather than sequences of message bits) to distinct codewords
in |VTa,b (n)|. In step 1, we can assign (n − 3t + 3) arbitrary symbols to positions that are neither
dyadic nor in S. There are q n−3t+3 ways to choose these symbols. Then in step two, we can
choose (q − 1)2 pairs for each of the (t − 3) specified pairs of positions; furthermore, there are
(q − 1) choices for c5 . According to steps 3 to 6, we can always choose the remaining symbols
such that resulting codeword lies in VTa,b (n). Therefore, we can map q n−3t+3 (q −1)2t−5 different
sequences of message symbols to distinct codewords in VTa,b (n). This yields the lower bound
on |VTa,b (n)|.
A PPENDIX
A. Encoding for q = 3
For q = 3, we need to slightly modify the proposed algorithm. The first step is as described in
Section III-B. The difference in the second step is that we do not embed data in c5 and simply

12

choose c5 = c3 = 2. Steps three to five remain the same. In the sixth step, we compute w as in
(31), and choose c0 , c1 , c2 as follows depending on the values of a0 and a1 :
1) a1 = a2 = 1: Choose c2 = c1 = 2 and c0 = w − 4 (mod 3).
2) a1 = 1, a2 = 0: Choose c2 = 1 and c1 = 2 and c0 = w − 4 (mod 3).
3) a1 = 0, a2 = 1: Choose c2 = 2. If w = 1, then c1 = 0, c0 = 2. If w = 0, then c1 = 0, c0 = 1.
If w = 2, then c1 = 1, c0 = 2.
The only remaining case is when a1 = a2 = 0. For this case, we need to change c3 and c4 , and
also the first three bits of AC . Since c3 has been set to 2, the first three bits of AC in this case
are 001. If we change these three bits to 110, syn(AC ) will remain unchanged. We therefore set
a1 = a2 = 1 and a3 = 0. Now we update c0 , c1 , c2 , c3 to be compatible with the new auxiliary
sequence. Set c3 = 1, recall that c5 = 2 so we still have c5 ≥ c3 and hence this change will not
affect a5 . Update c4 according to (29). Set c2 = c1 = 2, and c0 = w − 4 (mod 3). Now we have
c3 < c2 which is consistent with a3 = 0. Also c2 ≥ c1 ≥ c0 is consistent with a1 = a2 = 1.
Hence, for q = 3, we have mapped k = ⌊log2 3(n−3t+ 3)⌋+ 2(t−3) bits to a q-ary codeword
C. This induces following rate:
⌊log2 3 (n − 3⌈log2 n⌉ + 3)⌋ 2(⌈log2 n⌉ − 3)
+
n
n
2.76 ⌈log2 n⌉ 2.25
−
≥ log2 3 −
n
n

R=

(36)
(37)

Similarly to Proposition 2, we can show that for q = 3 there are at least 22(t−3) 3n−3t+3 codewords
in each of the VT codes.
Acknowledgement
The authors thank Andreas Lenz for pointing them to the references [12] and [13].
R EFERENCES
[1] N. J. A. Sloane, “On single-deletion-correcting codes,” in Codes and Designs, Ohio State University (Ray-Chaudhuri
Festschrift), pp. 273–291, 2000. Online: https://arxiv.org/abs/math/0207197.
[2] M. C. Davey and D. J. C. MacKay, “Reliable communication over channels with insertions, deletions, and substitutions,”
IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 687–698, 2001.
[3] E. A. Ratzer, “Marker codes for channels with insertions and deletions,” Ann. Telecommn., vol. 60, no. 1, pp. 29–44, 2005.
[4] K. A. 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 Trans. Inf. Theory, vol. 58, no. 3, pp. 1804–1808, 2012.
[5] T. A. Le and H. D. Nguyen, “New multiple insertion/deletion correcting codes for non-binary alphabets.,” IEEE Trans.
Inf. Theory, vol. 62, no. 5, pp. 2682–2693, 2016.

13

[6] J. Brakensiek, V. Guruswami, and S. Zbarsky, “Efficient low-redundancy codes for correcting multiple deletions,” in Proc.
ACM-SIAM Symp. on Discrete Algorithms, pp. 1884–1892, 2016.
[7] V. Guruswami and C. Wang, “Deletion codes in the high-noise and high-rate regimes,” IEEE Trans Inf. Theory, vol. 63,
no. 4, pp. 1961–1970, 2017.
[8] S. K. Hanna and S. E. Rouayheb, “Guess & check codes for deletions and synchronization,” in Proc. IEEE Int. Symp. Inf.
Theory, 2017.
[9] R. R. Varshamov and G. M. Tenengolts, “Codes which correct single asymmetric errors,” Automatica i Telemekhanica,
vol. 26, no. 2, pp. 288–292, 1965.
[10] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals,” Doklady Akademii Nauk SSSR,
vol. 163, no. 4, pp. 845–848, 1965.
[11] G. Tenengolts, “Nonbinary codes, correcting single deletion or insertion,” IEEE Trans. Inf. Theory, vol. 30, no. 5, pp. 766–,
1984.
[12] K. A. S. Abdel-Ghaffar and H. C. Ferreira, “Systematic encoding of the Varshamov-Tenengolts codes and the ConstantinRao codes,” IEEE Trans Inf. Theory, vol. 44, pp. 340–345, Jan 1998.
[13] K. Saowapa, H. Kaneko, and E. Fujiwara, “Systematic deletion/insertion error correcting codes with random error correction
capability,” in Int. Symp. Defect and Fault Tolerance in VLSI Systems, pp. 284–292, Nov. 1999.
[14] Z. Liu and M. Mitzenmacher, “Codes for deletion and insertion channels with segmented errors,” IEEE Trans Inf. Theory,
vol. 56, no. 1, pp. 224–232, 2010.
[15] M. Abroshan, R. Venkataramanan, and A. Guillén i Fàbregas, “Codes for channels with segmented edits,” in Proc. IEEE
Int. Symp. Inf. Theory, 2017. Extended version: http://arxiv.org/abs/1701.06341.
[16] R. Venkataramanan, V. N. Swamy, and K. Ramchandran, “Low-complexity interactive algorithms for synchronization from
deletions, insertions, and substitutions,” IEEE Trans Inf. Theory, vol. 61, no. 10, pp. 5670–5689, 2015.
[17] S. M. S. Tabatabaei Yazdi and L. Dolecek, “Synchronization from deletions through interactive communication,” IEEE
Trans. Inf. Theory, vol. 60, pp. 397–409, Jan. 2014.
[18] F. Sala, C. Schoeny, N. Bitouzé, and L. Dolecek, “Synchronizing files from a large number of insertions and deletions,”
IEEE Trans. Commun., vol. 64, no. 6, pp. 2258–2273, 2016.
[19] M. Abroshan, R. Venkataramanan, and A. Guillén i Fàbregas, “Multilayer codes for synchronization from deletions,” in
To appear in Proc. IEEE Inf. Theory Workshop, 2017. Online: https://arxiv.org/abs/1705.06670.
[20] B. D. Ginzburg, “A number-theoretic function with an application in the theory of coding,” Problemy Kibernet., pp. 249–
252, 1967.
[21] A. A. Kulkarni and N. Kiyavash, “Nonasymptotic upper bounds for deletion correcting codes,” IEEE Trans Inf. Theory,
vol. 59, pp. 5115–5130, Aug. 2013.

