An Improvement of Non-binary Code Correcting Single
b-Burst of Insertions or Deletions
Toyohiko Saeki,Takayuki Nozaki

Yamaguchi University

ISITA2018
Oct. 29th, 20181 / 15

Background (1: Purpose)b-burst insertion/deletion channel
Exactly b consecutive insertions/deletions occurs to x
Example: 3-burst deletion

Received word y becomes the concatenation of remaining sequence

Purpose of this research
Constructing non-binary (q-ary) code correcting b-burst insertion/deletion2 / 15

Background (2: Existing works, Contribution, Outline)
Existing works of I/D codesSingle I/DBurst I/DBinary
VT code [Varshamov1965](proved by [Levenshtein1966])[Cheng2014]⇓ Improve[Schoney2017-04]

Non-binary
qVT code [Tenengolts1984][Schoney2017-10]⇓ Improve
This work

Contributions of this research
Constructing non-binary burst I/D code with larger cardinality
Devising decoding algorithm for the code
Evaluating number of codewords (Numerical and Asymptotic)
Outline1 Existing works
2 Code construction
3 Number of Codewords

3 / 15

Existing Work (1: Single I/D codes)
VT code: Binary single I/D codea ∈ [n + 1] := {0, 1, 2, . . . , n}{}∑VTa (n) = x ∈ {0, 1}n | ni=1 ixi ≡ a (mod n + 1) .

n: code length,Non-binary VT code: non-binary single I/D code
q: number of alphabet,a ∈ [n], c ∈ [q]{}∑nqVTa,c (n, q) = x ∈ [q]n |i=1 xi ≡ c (mod q), σ(x) ∈ VTa (n − 1) .
Ascent sequence σ(x)xσ(x)==30133212
0110001

σ : [q]n → {0, 1}n−1{1 (xi < xi+1 )σ(x)i =0 (xi ≥ xi+1 )ascent sequence
4 / 15

Existing Work (2: Burst I/D codes 1)
b-Interleave (Matrix representation of x)x1 xb+1 · · · xn−b+1
x2 xb+2 · · · xn−b+2 Ab (x) =  .
..
..  .
..
 ..
.
.
. 
xb x2b · · ·xn

Example: 3-interleaving x = (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 , x10 , x11 , x12 )
x1 x4 x7 x10
A3 (x) = x2 x5 x8 x11 x3 x6 x9 x12Each row contains single deletion
The deletion position of 1st row gives deletion range of other rows
5 / 15

Existing Work (3: Burst I/D codes 2)
Detection of Deletion Position:
Even if we correct a deletion, we cannot detect deletion positionx = (1, 0, 0, 1, 1, 1)x¬2 = (1 , 0, 1, 1, 1)
x¬3 = (1, 0 , 1, 1, 1)
The received words are same if a deletion occurs in a same run.
One cannot detect which symbol in a run is deleted
runrange of deletion position

We need to limit the run length of 1st row
We use a code correcting single deletion with given deletion range

6 / 15

Existing Work (4: Burst I/D codes 3)
Framework of b-burst deletion correcting code
Single I/D code with maximum run length r
 (r + 1)-bounded single deletion correcting code Ab (x) = 

..

.
|(r + 1)-bounded single deletion correcting code{z}n/b(r + 1)-bounded single deletion correcting code
Correcting single deletion with side information of deletion position(Side information) (r + 1)-consecutive deletion positions

7 / 15

Existing Work (5: Burst I/D codes 4)b-burst I/D code [Schonery2017-04]
C2,b = {x ∈ {0, 1}n |Ab (x)1 ∈ VTa (n/b) ∩ S2 (n/b, r),Ab (x)2 ∈ SVTd,e (n/b, r + 1),..
.
Ab (x)b ∈ SVTd,e (n/b, r + 1)}
S2 (n/b, r): set of binary sequence of length n/b with maximum run length
at most r

Shifted VT (SVT) code
r-bounded single deletion code{∑SVTd,e (n, r) = x ∈ {0, 1}n | ni=1 ixi ≡ d (mod r),}∑ni=1 xi ≡ e (mod 2)d ∈ [r], e ∈ {0, 1}8 / 15

Existing Work (6: Non-binary Burst I/D codes)
Non-binary SVT code{∑qSVTd,e,f (n, r, q) := x ∈ [q]n | ni=1 xi ≡ f(mod q),σ(x) ∈ SVTd,e (n − 1, r)}[Schoney2017-11, Lemma 1] Correction capability of NB-SVT code
qSVTd,e,f (n, r, q) is (r − 1)-bounded single deletion correcting code
Non-binary b-burst I/D code [Schoney2017-11]
Čq,b = {x ∈ [q]n |Ab (x)1 ∈ qVTa,b (n/b, q) ∩ Sq (n/b, r),Ab (x)2 ∈ qSVTd,e,f (n/b, r + 2, q),..
.
Ab (x)b ∈ qSVTd,e,f (n/b, r + 2, q)}

9 / 15Main Result
Non-binary SVT code{∑qSVTd,e,f (n, r, q) := x ∈ [q]n | ni=1 xi ≡ f(mod q),σ(x) ∈ SVTd,e (n − 1, r)}[Theorem 2] Correction capability of NB-SVT code
qSVTd,e,f (n, r, q) is

r-bounded single deletion correcting code

Non-binary b-burst I/D code [This work]
Cq,b = {x ∈ [q]n |Ab (x)1 ∈ qVTa,b (n/b, q) ∩ Sq (n/b, r),
Ab (x)2 ∈ qSVTd,e,f (n/b, r + 1, q),..
.
Ab (x)b ∈ qSVTd,e,f (n/b, r + 1, q)}(Proof of Theorem 2) Straightforward but long... See arXiv:1804.04824
10 / 15

Number of Codewords (1: Lower bound 1)
Cq,b = {x ∈ [q]n |Ab (x)1 ∈ qVTa,b (n/b, q) ∩ Sq (n/b, r),
Ab (x)i ∈ qSVTd,e,f (n/b, r + 1, q) for i ∈ [2, b]}[Lemma 5] Lower bound of # of run length limited sequences|Sn,q (r)| ≥ (q r − n)q n−r .

[Lemma 6] Lower bound of |Ab (x)1 |maxa∈[n],c∈[q]|qVTa,c (n/b, q) ∩ Sq (n/b, r)| ≥(q r − n)q n−r(q r − n)q n−r−1=.
nqn[Lemma 7] Lower bound of non-binary SVT codemax

d∈[r+1],e∈[2],f ∈[q]

|qSVTd,e,f (n, r + 1, q)| ≥(Lemma 5) From Union boundqnq n−1=.
2(r + 1)q2(r + 1)

(Lemma 6,7) Pigeonhole principle

11 / 15

Number of Codewords (2: Lower bound 2)
Cq,b = {x ∈ [q]n |Ab (x)1 ∈ qVTa,b (n/b, q) ∩ S2 (n/b, r),Ab (x)i ∈ qSVTd,e,f (n/b, r + 1, q) for i ∈ [2, b]}[Theorem 4] Lower bound of |Cq,b |For all r, the cardinality of Cq,b satisfies
max |Cq,b | ≥q n−b b − nq −r.
n 2b−1 (r + 1)b−1

Substituting r = logq n, we getmax |Cq,b | ≥b−1
2q n−b.
· bn2 (logq n + 1)b−1

Its redundancy (the number of extra symbols: n − logq |C|) isb + logq n − logq (b − 1) + (b − 1) logq 2 + (b − 1) logq (logq n + 1).
12 / 15

Number of Codewords (3: Upper bound of the best code)
Mq,b (n): q-ary b-burst I/D code with largest cardinality[Theorem 5]
For enough large n, the following holds:|Mq,b (n)| ≤q n−b+1(q − 1)nUpper bound of redundancy for Mq,b (n) isb − logq 2 + logq n
Gap of redundancy between Cq,b and Mq,b (n) is
1 − logq (q − 1) − logq (b − 1) + (b − 1) logq 2 + (b − 1) logq [logq n + 1]
=O(logq logq n)
Fraction of gap of redundancy O(logq logq n)
n13 / 15

Number of Codewords (4: Numerical Example)
Number of Codewords

100000

Cardinality of qSVT(10,r,4)

80000

n = 10, q = 4

60000
40000
20000
0
1

2

3

4

5

6

7

8

910r

The number of codewords decreases for small r⇒ For r = logq n, |qSVTd,e,f (n, r, q)| > |qSVTd,e,f (n, r + 1, q)|⇒ The proposed code has larger cardinality than [Schoney2017-11]
14 / 15

ConclusionWe construct non-binary b-burst I/D code
We refine the correction capability of non-binary SVT code

We devise its decoding algorithm
We evaluate the cardinality of the code

15 / 15