# Block-Wise Dynamic-Precision Neural Network Training Acceleration via Online
Quantization Sensitivity Analytics

Ruoyang Liu  0000-0001-9873-6574 ,  Chenhan Wei  0000-0003-2683-9835 ,
Yixiong Yang  0000-0002-3035-709X Tsinghua UniversityBeijingChina100084 ,
Wenxun Wang  0000-0002-9213-5257 Tsinghua UniversityBeijingChina100084 ,
Huazhong Yang  0000-0003-2421-353X Tsinghua UniversityBeijingChina100084 and
Yongpan Liu<EMAIL_ADDRESS>0000-0002-4892-2309 Tsinghua
UniversityBeijingChina100084

(2023)

###### Abstract.

Data quantization is an effective method to accelerate neural network training
and reduce power consumption. However, it is challenging to perform low-bit
quantized training: the conventional equal-precision quantization will lead to
either high accuracy loss or limited bit-width reduction, while existing
mixed-precision methods offer high compression potential but failed to perform
accurate and efficient bit-width assignment. In this work, we propose DYNASTY,
a block-wise dynamic-precision neural network training framework. DYNASTY
provides accurate data sensitivity information through fast online analytics,
and maintains stable training convergence with an adaptive bit-width map
generator. Network training experiments on CIFAR-100 and ImageNet dataset are
carried out, and compared to 8-bit quantization baseline, DYNASTY brings up to
$5.1\times$ speedup and $4.7\times$ energy consumption reduction with no
accuracy drop and negligible hardware overhead.

fully-quantized network training, mixed-precision quantization, neural network
training acceleration

††copyright: acmcopyright††journalyear: 2023††doi:
XXXXXXX.XXXXXXX††conference: ACM Asia South Pacific Design Automation
Conference; Janurary 16–19, 2023; Tokyo, Japan††price: 15.00††isbn:
978-1-4503-XXXX-X/18/06††ccs: Computing methodologies Neural networks††ccs:
Computing methodologies Philosophical/theoretical foundations of artificial
intelligence

##  1\. Introduction

Neural networks(NN) have been widely adopted in many fields, including
computer vision(Krizhevsky et al., 2012), speech recognition(Abdel-Hamid et
al., 2014), and natural language processing(Vaswani et al., 2017). However,
training NN usually needs large computing power, which requires high-cost
cloud servers and makes it infeasible to train on low-power edge devices.
Researchers have been studying various methods for NN training acceleration,
such as exploiting data pruning algorithm(Dai et al., 2020) and developing
more efficient hardware accelerators(Zhao et al., 2021).

As NN training is usually carried out with 32-bit float point data, low-bit
network quantization can be an effective way for NN training acceleration.
There are 3 ways for NN quantization: post-training quantization(Banner et
al., 2019), quantization aware training(Jacob et al., 2018), and fully-
quantized training(Zhou et al., 2016). The first 2 methods only quantize
network inference data and do not accelerate training process, and they
usually need to train auxiliary NN or use methods like evolutionary search,
leading to even longer training time(Wang et al., 2020). Meanwhile, fully-
quantized training aims at online quantization of all training data, which can
significantly reduce the computation cost needed for training.

Figure 1. Mixed-precision quantization in NN training

Early works on fully-quantized training adopt an equal bit-width for the
entire network(Zhou et al., 2016), which leads to either high accuracy loss or
limited bit-width reduction. Later works utilize mixed-precision training to
provide better acceleration while maintaining network accuracy. Some works
like (Dong et al., 2019) assign different bit-widths to each network layer,
and state-of-the-art quantization results are acquired through block-wise
mixed-precision training(Chen et al., 2021a). As shown in Fig. 1, block-wise
mixed-precision training divides training data into small blocks, and
quantizes them into different bit-widths. Whether layer-wise or block-wise,
mixed-precision training is challenging in how to perform online precision
assignment for each layer/block of data. Some of the existing works use data
quantization sensitivity acquiring algorithms such as calculating Hessian
eigenvalue and trace(Dong et al., 2019, 2020), which are too complicated for
hardware implementation; other works utilize heuristic methods like greedy
search(Chen et al., 2021a), which does not generate accurate bit-width
distribution.

To address the aforementioned weakness, we propose DYNASTY (DYNamic Analytics
of SensitiviTY), a block-wise dynamic-precision NN training framework. By
using analytics methods, DYNASTY performs fast dynamic data bit-width
assignment, and achieves average 2-bit quantization with minimum accuracy
drop. Key contributions of the work are concluded as follows:

  * •

A software-hardware co-designed block-wise fully-quantized mixed-precision NN
training framework named DYNASTY. It provides a block-float-point quantized
training algorithm with 0-8 bits dynamic block precision, and extends an
online bit-width assignment module to the NN acceleration hardware
architecture.

  * •

A Relative Quantization Sensitivity Analytics algorithm. By applying relaxed
Lagrange duality, it transforms the NP-hard bit-width searching problem into
$O(N)$ complexity, providing fast but still accurate online data quantization
sensitivity analysis.

  * •

An Adaptive Bit-Width Map Generator that maps data sensitivity to bit-width.
It performs online tuning of algorithm hyperparameter to maintain stable
average bit-width, and employs bit-width map temporal smoothing to furtherly
enhance network accuracy.

  * •

Experiments on our algorithm show $5.1\times$ training speedup with no
accuracy drop on CIFAR-100, and $1.9\times$ speedup with 0,39 accuracy drop on
ImageNet, compared to 8-bit quantization baseline. Our hardware architecture
shows minimum overhead on die area ([retain-explicit-plus]+1,4) and brings at
most 78,8 energy consumption reduction.

##  2\. Preliminary & Related Works

###  2.1. Quantized NN Training Basics

While NN inference requires only one forward pass computation, training
involves three different stages: forward, backward and weight update. Each
stage includes multiply-accumulate(MAC) operations on different data: for the
forward stage, they are activations and weights; for the backward stage, they
are activation gradients (also called errors) and weights; and for the
backward stage, they are activations and activation gradients.

Researchers have found training quantization to be more challenging than
inference. Xiao Sun et al. (Sun et al., 2019) point out that quantization
saturation can be severe in training due to the large dynamic range of
gradient data in the backward stage. Later work(Sun et al., 2020) furtherly
discover that different network layers show widely different ranges of
gradients across training epochs.

To better suit these different data distributions, either handcrafted
quantization formats for different layers and stages need to be carefully
designed as having been done in (Sun et al., 2019, 2020), or better we employ
mixed-precision quantization that adaptively adjusts the quantization method
for different parts of data in networks.

###  2.2. Mixed-Precision NN Training

Early works of mixed-precision fully-quantized training such as HAWQ(Dong et
al., 2019) and AdaQS(Guo et al., 2020) only calculate a relative ordering of
the importance of each data block. They require empirically assigning bit-
width to each block, making their method design include trial and error and
hard to be accurate.

A better way to get bit-width distribution is through analytics methods, where
the bit-width distribution solving is formulated as an optimization problem to
minimize impacts brought by quantization noise. ActNN(Chen et al., 2021a)
proposes to define the mean square of weight gradients as the optimization
target, but this optimization is hard to solve and they have to use greedy
search for a heuristic result. HAWQ-V3(Yao et al., 2021) needs to solve an
integer linear programming problem, and MPQCO(Chen et al., 2021b) formulates
it into a multiple-choice knapsack problem, both of which are NP-hard to
solve.

##  3\. Block-Wise Dynamic-Precision NN Training Framework

###  3.1. Quantization Training Framework

Figure 2. Proposed block-wise dynamic-precision NN training framework

Figure 2 depicts the overall framework of our system, where the DYNASTY module
extends an NN accelerator for block-wise dynamic-precision training. Input
data of all training stages are quantized by Block-Float-Point(BFP) format,
which divides data into $4\times 4$ blocks111Block division is along $C_{in}$
and $C_{out}$ dimensions for weight and weight gradients, $C_{in}$ and $Batch$
dimensions for activations, and $C_{out}$ and $Batch$ dimensions for
activation gradients.. Data in each block have mantissa quantized into a same
bit-width, and they also share a single 8-bit exponent. Two strategies are
used for mantissa bit-width assignment: in each training stage, one of the
input data is statically quantized to 8-bit mantissa; sensitivity analytics is
performed for the other input data, whose mantissa is dynamically quantized
into 0-8 bits according to the bit-width map generated by the DYNASTY module.

The DYNASTY module is in charge of the dynamic bit-width assignment, and
consists of two sub-modules. The first sub-module, named Relative Quantization
Sensitivity Analytics, receives the current quantization range together with
data gradients, and generates a relative quantization sensitivity value for
each block. This analytics happens at the end of the training of each mini-
batch. This sub-module will be detailed in Section 3.2. The second sub-module,
the Adaptive Bit-Width Map Generator, works at the end of each training epoch.
It maps the sensitivities into a bit-width distribution and maintains stable
training. This mapping happens at the end of each training epoch. Details of
this sub-module will be provided in Section 3.3.

###  3.2. Relative Quantization Sensitivity Analytics

To perform fast online data analysis and dynamically identify which data is
more important and need larger quantization bit-width than others, the
Relative Quantization Sensitivity Analytics module is designed to calculate
data quantization sensitivity based on their quantization range and
corresponding gradients. We first establish an optimization problem based on
the minimization of first-order mean square loss noise. Then we propose to
solve the optimization by relaxed Lagrange duality method and get the
sensitivity values.

Figure 3. An example of per-layer relative sensitivity distribution. Red
markers represent the mean sensitivity per layer, and different colored
squares represent the proportion of different sensitivity ranges in each
layer.

####  3.2.1. Optimization Problem Based On First-Order Mean Square Loss Noise

Quantization brings noise to network training process, leading to less stable
training and lower network accuracy. An ideal bit-width assignment should
minimize this noise and bring minimum perturbation to the train loss. We
propose to use the first-order mean square loss noise($\Delta L^{2}$) to
quantify this perturbation. The math formula of $\Delta L^{2}$ caused by
weight quantization is shown as Eq. 1. It is calculated as the mean square
value of first-order loss noise caused by each quantized data. And we use
$S_{i}$ to denote the ratio of loss noise to quantization levels in each data
block. In Eq. 1, $\Delta W_{i,j}$ is the gradient of the $j$th weight of the
$i$th block; $\sigma_{i,j}$ is the quantization noise of corresponding data;
$N$ is the total number of data blocks; $B$ is the number of values inside
each block; $b_{i}$ is the quantization bit-width of the mantissa of the $i$th
block of weights; and $e_{i}$ is the exponent of each block so that
$2^{e_{i}}$ is the corresponding quantization range. Note that, $\Delta L^{2}$
brought by activation quantization can also be calculated in the same way, and
we omit its formula here for simplicity. With our formulation, $\Delta L^{2}$
is calculated from the quantization range of each block and their
corresponding gradient values, both of which are already known during NN
training.

(1) $\displaystyle\Delta L^{2}$
$\displaystyle=\frac{1}{NB}\sum_{i=1}^{N}\sum_{j=1}^{B}\left(\Delta
W_{i,j}\cdot\sigma_{i,j}\right)^{2}=\frac{2}{3NB}\sum_{i=1}^{N}S_{i}\left(2^{-b_{i}}\right)^{2}$
$\displaystyle S_{i}$
$\displaystyle=\frac{\left(2^{e_{i}}\right)^{2}}{16}\sum_{j=1}^{B}\Delta
W_{i,j}^{2}$

The full optimization is shown as Eq. 2. Aside from $\Delta L^{2}$ as our
optimization target function, we also specify the optimization constraints.
The $\alpha$ denotes the desired average computation bit-width, which is the
$T_{i}$ weighted average of block bit-width $b_{i}$, where $T_{i}$ represents
the amount of computation associated with corresponding data. Bit-width lower
bound $0$ and upper bound $\beta$ are also specified.

(2a) $\displaystyle\\!\operatorname*{arg\,min}_{\bm{b}}$ $\displaystyle
f\\!\left(\bm{b}\right)=\Delta L^{2}$ (2b) subject to
$\displaystyle\frac{\sum_{i=1}^{N}{T_{i}b_{i}}}{\sum T_{i}}\leq\alpha$ (2c)
$\displaystyle b_{i}\in\mathbb{Z}$ (2d) $\displaystyle 0\leq b_{i}\leq\beta$

####  3.2.2. Problem Solving for Relative Quantization Sensitivity

Optimization in Eq. 2 is a mixed integer convex programming problem. It is NP-
hard to solve and too complicated for hardware implementation. Thus we propose
to relax the restriction in Eq. 2c to the $\mathbb{R}$ set, and then apply
Lagrange duality to this problem. This leads to the solution shown in Eq. 3.
The bit-width is calculated from value $\bm{r}$ and a hyperparameter
$\lambda$. $\bm{r}$ is easy to compute based on Eq. 3b. It is positively
correlated with $S_{i}$ and negatively correlated with $T_{i}$, and only
requires $O(N)$ time complexity for weights and activations of the entire
network. $\bm{r}$ tells the relative bit-width between data blocks, and we
call it the relative quantization sensitivity. Though we still do not know the
value of $\lambda$, we successfully transform the searching of bit-width of N
different blocks into the searching of only a single hyperparameter. We call
$\lambda$ the global quantization coefficient.

(3a) $\displaystyle b_{i}$
$\displaystyle=\max\\!\left(0,\min\\!\left(r_{i}-\lambda,\beta\right)\right)$
(3b) $\displaystyle r_{i}$
$\displaystyle=\frac{1}{2}\log_{2}\frac{S_{i}}{T_{i}}$

An example of $\bm{r}$ distribution during training of ResNet-18 is shown as
Fig. 3. We can see that the desired bit-width distribution should be different
across network layers. Data in several layers requires much larger bit-widths
than others, including weights in the first, the last, and the 3 shortcut
layers, and activation in the last layer. Bit-width distribution inside each
layer is also different, and activations’ bit-widths tend to be more spread
out and reside in larger ranges than weights’. These observations suggest that
manually setting bit-width can hardly suit the data requirement, and online
bit-width assignment based on data sensitivity is needed.

Figure 4. Data bit-width fluctuation reduces network accuracy.

However, though Eq. 3b uncovers the relative bit-widths between data blocks,
it still does not give us the absolute bit-width of each block of data. Two
problems remain to be solved. The first is how to search the value of
$\lambda$. The second is that the sensitivities of some blocks are unstable
across training epochs, leading to bit-width fluctuating periodically as shown
in Fig. 4, which brings 0,4 to 1 network accuracy drop in our experiment. Both
of these problems are addressed in Section 3.3.

###  3.3. Adaptive Bit-Width Map Generator

The Adaptive Bit-Width Map Generator aims to solve the remaining problems
mentioned in Section 3.2 and maps the relative sensitivities $\bm{r}$ of each
block to their exact quantization bit-widths.

####  3.3.1. Dertermine the Value of $\lambda$

To find the exact global quantization coefficients $\lambda$, we develop an
adaptive quantization coefficient adjustment algorithm to dynamically
determine the coefficient during training. In theory, if we ignore these upper
and lower bounds constraints in Eq. 3a, an approximate of $\lambda$ can be
easily deduced as $\hat{\lambda}=\sum_{i}B_{i}-N\alpha$, where $N$ is the
number of blocks. With experiments, we discover that in the initial training
of a network, differences in the importance of data in the network are not
much and seldomly make $b_{i}$ reach the lower or upper bound, thus
$\hat{\lambda}$ is a good estimation of the initial $\lambda$ value.

However, as shown in Fig. 5, using only $\hat{\lambda}$ leads to the average
bit-width becoming larger than desired as training continues, especially for
activation data. To prevent $\lambda$ drifting away from the desired value, we
design Algorithm 1, which tunes $\lambda$ with linear interpolation using the
last $\lambda$ value as the start point of the interpolation. The number of
interpolation iterations $L$ is empirically set to 3. By using this method,
average bit-width can be maintained stably at the target bit-width, as the
blue lines show in Fig. 5.

Figure 5. Real network bit-width when targeting 3-bit quantization. Without
linear interpolation-based tuning of $\lambda$, the average bit-width tends to
become larger than desired. Algorithm 1 Global Quantization Coefficient Tuning

1:$\lambda_{in}$: the last global quantization coefficient

2:$\bm{r}$: relative sensitivity

3:$\alpha$: target averaged quantization bit-width

4:$\lambda_{out}$: the tuned global quantization coefficient

5:$L$: number of interpolation iterations

6:begin

7: $\lambda_{out}=\lambda_{in}$

8:
$\lambda_{0},\lambda_{1}\leftarrow\min\\!\left(\bm{r}\right)-\alpha,\max\\!\left(\bm{r}\right)-\alpha$

9: for $l=1$ to $L$ do

10:
$b_{0}\leftarrow\frac{1}{N}\sum_{i}\max\\!\left(\min\\!\left(r_{i}-\lambda_{0},\beta\right),0\right)$

11:
$b_{1}\leftarrow\frac{1}{N}\sum_{i}\max\\!\left(\min\\!\left(r_{i}-\lambda_{1},\beta\right),0\right)$

12:
$\overline{b}\leftarrow\frac{1}{N}\sum_{i}\max\\!\left(\min\\!\left(r_{i}-\lambda,\beta\right),0\right)$

13: if $\overline{b}>\alpha$ then

14:
$t\leftarrow\left(\overline{b}-\alpha\right)/\left(\overline{b}-b_{1}\right)$

15:
$\lambda_{0},\lambda_{out}\leftarrow\lambda_{out},\left(1-t\right)\lambda_{out}+t\cdot\lambda_{1}$

16: else

17:
$t\leftarrow\left(\overline{b}-\alpha\right)/\left(\overline{b}-b_{0}\right)$

18:
$\lambda_{out},\lambda_{1}\leftarrow\left(1-t\right)\lambda_{out}+t\cdot\lambda_{0},\lambda_{out}$

19: end if

20: end for

21:end

####  3.3.2. Prevent Bit-Width Fluctuatation

To solve the bit-width fluctuation problem, we propose a bit-width map
temporal smoothing method: at every epoch, an exponential moving average is
performed on the bit-width map, shown as Eq. 4. This prevents sudden changes
in data bit-width caused by any calculation error. The smooth factor $\gamma$
is empirically set to $0.5$.

(4) $b_{i,\text{smoothed}}=\gamma\cdot
b_{i,\text{last}}+\left(1-\gamma\right)b_{i,\text{new}}$

Note that, during the first training epoch when we have not got the value of
$\hat{\lambda}$, we assign 4 bits to every block as the initial bit-width map.
And for hardware simplicity, we perform rounding on the bit-width map to only
use 0,2,4,6,8 as possible quantized bit-widths. Specially, when a block is
quantized to 0 bit, we skip the computation of this block. The smoothed bit-
width map is then sent to the accelerator computing cores for dynamic data
quantization.

##  4\. Hardware Architecture

Figure 6. DYNASTY module hardware architecture

Support of variable bit-width operation has been realised through NN
accelerators with bit-serial-based computation array(Lee et al., 2019; Zhao et
al., 2021). These accelerators get linear speedup as the operation bit-width
shrinks. The DYNASTY hardware architecture extends such accelerators with
online bit-width assignment ability.

Fig. 6 shows the hardware architecture of the DYNASTY module. The use of 16
parallel sensitivity analytics units makes it capable of calculating the
sensitivities and generating bit-width map for 16 blocks, i.e. 256 weights or
activations in one cycle. Note that, the DYNASTY module is running in parallel
with the main array of the accelerator. A recovery remainder-based divider is
used in the Bit-Width Map Generator, but since there is only one divider, and
the divisions only happen at the end of each training epoch, it does not bring
much area and power overhead.

##  5\. Experimental Results

###  5.1. Experiment Setup

In our experiments, we train ResNet-18 network(He et al., 2016) on the
CIFAR-100(Krizhevsky et al., ) and ImageNet(Deng et al., 2009) dataset. For
both datasets, we adopt a batch size of 128, and use SGD as the optimizer with
an initial learning rate of $0.1$. For CIFAR-100, we train the network for 200
epochs; learning rate linear warming up is used in the 1 epoch; and we perform
learning rate decay at the 60, 120, and 160 epochs with a decay factor of
$0.2$. For ImageNet, we train the network for 95 epochs; learning rate linear
warming up is used in the first 5 epochs; and we perform learning rate decay
at the 30, 60, and 80 epoch with a decay factor of $0.1$.

We also perform training with 2 other methods aside from DYNASTY as our
baseline. The first method is to train with float-32 format without
quantization; the second is 8-bit quantized training according to the work of
Ron Banner et al. (Banner et al., 2018).

We implement the DYNASTY module in Verilog and get its area and power
information by synthesizing it in Synopsys Design Compiler with TSMC 65nm CMOS
technology. The hardware metrics of other modules in a full accelerator are
taken from the UNPU accelerator(Lee et al., 2019).

Table 1. Network accuracy with different average quantization bit-width Dataset | Method |  Average Bit-Width∗ |  Top 1 Validation Accuracy (%)
---|---|---|---
CIFAR-100 | Float-Point | All Float-32 | $76.54$
Banner et al. | 8 |  $74.77$ ($-1.77$)
DYNASTY | 6 |  $76.57$ ($+0.03$)
4 |  $76.55$ ($+0.01$)
3 |  $75.81$ ($-0.73$)
2 |  $75.14$ ($-1.40$)
ImageNet | Float-Point | All Float-32 | $68.77$
Banner et al. | 8 |  $68.28$ ($-0.49$)
DYNASTY | 6 |  $68.60$ ($-0.17$)
4 |  $67.89$ ($-0.88$)
3 |  $65.84$ ($-2.93$)
2 |  $62.52$ ($-6.25$)
∗Average bit-width refers to the bit-width of dynamic quantized training data.

###  5.2. Algorithm Evaluation

####  5.2.1. Network Accuracy

Table 1 shows the validation accuracy that DYNASTY gets with different
quantization bit-width. On CIFAR-100, we achieve 4-bit quantization with no
accuracy drop compared to float-32 training; even with 2-bit quantization, we
only get an accuracy drop of 1,40 compared to float-32 training and get better
accuracy than the 8-bit baseline. On ImageNet, while the accuracy drop with
2-bit quantization is not small (6,25), the 4-bit training experiment still
reveals good accuracy with only 0,88 accuracy drop.

####  5.2.2. Training Convergence Speed Improvement

Figure 7. Training convergence speed improvement with DYNASTY

Figure 7 presents the accuracy-time curve in the experiments. Note that, the
training speed for unquantized float-32 training is not compared here, as the
cores of the UNPU accelerator cannot handle float-32 operations.

Because the DYNASTY module runs in parallel with the accelerator cores, we
enjoy a linear speedup as the quantization bit-width decreases. Compared to
8-bit training baseline, for CIFAR-100, DYNASTY reaches the same validation
accuracy (74) in 58,3, 38,9, 29,2, and 19,6 training time with 6, 4, 3, 2-bit
quantization, respectively; because the better convergence than baseline, the
speedup ($5.1\times$ with 2-bit) is even higher than expectation ($4\times$).
For ImageNet, DYNASTY needs 75,0 and 52,5 time to get 67 accuracy with 6 and
4-bit quantization, respectively.

###  5.3. Architecture Evaluation

Table 2. Area and power overhead of DYNASTY Module |  Area () |  Power Consumption (@200)
---|---|---
DYNASTY | $0.219$ |  $10.3$ (4-bit, ImageNet)
Main Accelerator | 16 | 297

Table 2 shows the area and power of the DYNASTY module compared to other
modules in the accelerator. We can see that DYNASTY brings no more than 1,4
area overhead.

Figure 8. Energy consumption reduction with DYNASTY

The average power consumption of DYNASTY varies with the network scale and
quantization bit-width as these factors affect the duty cycle of the DYNASTY
module, and we only show the value in a typical situation in Table 2. Details
on the energy consumption overhead can be seen in Fig. 8. DYNASTY brings at
most 7,9 power consumption overhead to the accelerator, but this overhead is
overcome by the energy saving due to shorter training time with lower-bit
quantization. When targeting 74 accuracy on CIFAR-100, we get 40,0, 59,5,
69,2, and 78,8 energy consumption reduction when quantizing to average 6, 4,
3, and 2 bits. For ImageNet, we also achieve 23,2 and 45,7 energy reduction
with 6 and 4-bit quantization when targeting 67 accuracy.

##  6\. Conclusion

In this paper, we propose DYNASTY, a software-hardware co-designed block-wise
dynamic-precision neural network training framework. We utilize an analytics
method based on network first-order mean square loss noise to efficiently
generate data quantization sensitivity online, and develop an Adaptive Bit-
Width Map Generator to accurately map sensitivity to bit-width distribution
that maintains desired computation reduction and high network accuracy at the
same time. Experiments on CIFAR-100 and ImageNet dataset are carried out, and
compared to 8-bit quantization baseline, we achieve up to $5.1\times$ speedup
and $4.7\times$ energy consumption reduction with no accuracy drop and
negligible hardware overhead.

## References

  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.  URL https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf.
  * Abdel-Hamid et al. [2014] Ossama Abdel-Hamid, Abdel-rahman Mohamed, Hui Jiang, Li Deng, Gerald Penn, and Dong Yu.  Convolutional neural networks for speech recognition.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 22(10):1533–1545, Oct 2014.  ISSN 2329-9304.  doi: 10.1109/TASLP.2014.2339736.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.
  * Dai et al. [2020] Pengcheng Dai, Jianlei Yang, Xucheng Ye, Xingzhou Cheng, Junyu Luo, Linghao Song, Yiran Chen, and Weisheng Zhao.  Sparsetrain: Exploiting dataflow sparsity for efficient convolutional neural networks training.  In _2020 57th ACM/IEEE Design Automation Conference (DAC)_ , pages 1–6, July 2020.  doi: 10.1109/DAC18072.2020.9218710.
  * Zhao et al. [2021] Yongwei Zhao, Chang Liu, Zidong Du, Qi Guo, Xing Hu, Yimin Zhuang, Zhenxing Zhang, Xinkai Song, Wei Li, Xishan Zhang, Ling Li, Zhiwei Xu, and Tianshi Chen.  Cambricon-q: A hybrid architecture for efficient training.  In _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_ , pages 706–719, June 2021.  doi: 10.1109/ISCA52012.2021.00061.
  * Banner et al. [2019] Ron Banner, Yury Nahshan, and Daniel Soudry.  Post training 4-bit quantization of convolutional networks for rapid-deployment.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/c0a62e133894cdce435bcb4a5df1db2d-Paper.pdf.
  * Jacob et al. [2018] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko.  Quantization and training of neural networks for efficient integer-arithmetic-only inference.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * Zhou et al. [2016] Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou.  DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients.  _arXiv e-prints_ , art. arXiv:1606.06160, June 2016.
  * Wang et al. [2020] Tianzhe Wang, Kuan Wang, Han Cai, Ji Lin, Zhijian Liu, Hanrui Wang, Yujun Lin, and Song Han.  Apq: Joint search for network architecture, pruning and quantization policy.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Dong et al. [2019] Zhen Dong, Zhewei Yao, Amir Gholami, Michael W. Mahoney, and Kurt Keutzer.  Hawq: Hessian aware quantization of neural networks with mixed-precision.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , October 2019.
  * Chen et al. [2021a] Jianfei Chen, Lianmin Zheng, Zhewei Yao, Dequan Wang, Ion Stoica, Michael Mahoney, and Joseph Gonzalez.  Actnn: Reducing training memory footprint via 2-bit activation compressed training.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 1803–1813. PMLR, 18–24 Jul 2021a.  URL https://proceedings.mlr.press/v139/chen21z.html.
  * Dong et al. [2020] Zhen Dong, Zhewei Yao, Daiyaan Arfeen, Amir Gholami, Michael W Mahoney, and Kurt Keutzer.  Hawq-v2: Hessian aware trace-weighted quantization of neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 18518–18529. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/d77c703536718b95308130ff2e5cf9ee-Paper.pdf.
  * Sun et al. [2019] Xiao Sun, Jungwook Choi, Chia-Yu Chen, Naigang Wang, Swagath Venkataramani, Vijayalakshmi (Viji) Srinivasan, Xiaodong Cui, Wei Zhang, and Kailash Gopalakrishnan.  Hybrid 8-bit floating point (hfp8) training and inference for deep neural networks.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/65fc9fb4897a89789352e211ca2d398f-Paper.pdf.
  * Sun et al. [2020] Xiao Sun, Naigang Wang, Chia-Yu Chen, Jiamin Ni, Ankur Agrawal, Xiaodong Cui, Swagath Venkataramani, Kaoutar El Maghraoui, Vijayalakshmi (Viji) Srinivasan, and Kailash Gopalakrishnan.  Ultra-low precision 4-bit training of deep neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 1796–1807. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/13b919438259814cd5be8cb45877d577-Paper.pdf.
  * Guo et al. [2020] Jinrong Guo, Wantao Liu, Wang Wang, Jizhong Han, Ruixuan Li, Yijun Lu, and Songlin Hu.  Accelerating distributed deep learning by adaptive gradient quantization.  In _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 1603–1607, 2020.  doi: 10.1109/ICASSP40776.2020.9054164.
  * Yao et al. [2021] Zhewei Yao, Zhen Dong, Zhangcheng Zheng, Amir Gholami, Jiali Yu, Eric Tan, Leyuan Wang, Qijing Huang, Yida Wang, Michael Mahoney, and Kurt Keutzer.  Hawq-v3: Dyadic neural network quantization.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 11875–11886. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/yao21a.html.
  * Chen et al. [2021b] Weihan Chen, Peisong Wang, and Jian Cheng.  Towards mixed-precision quantization of neural networks via constrained optimization.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 5350–5359, October 2021b.
  * Lee et al. [2019] Jinmook Lee, Changhyeon Kim, Sanghoon Kang, Dongjoo Shin, Sangyeob Kim, and Hoi-Jun Yoo.  Unpu: An energy-efficient deep neural network accelerator with fully variable weight bit precision.  _IEEE Journal of Solid-State Circuits_ , 54(1):173–185, Jan 2019.  ISSN 1558-173X.  doi: 10.1109/JSSC.2018.2865489.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2016.
  * [20] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Cifar-100 (canadian institute for advanced research).  URL http://www.cs.toronto.edu/~kriz/cifar.html.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 248–255, June 2009.  doi: 10.1109/CVPR.2009.5206848.
  * Banner et al. [2018] Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry.  Scalable methods for 8-bit training of neural networks.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/e82c4b19b8151ddc25d4d93baf7b908f-Paper.pdf.


11institutetext: Institute of Mathematical Sciences, HBNI, Chennai
11email<EMAIL_ADDRESS>
# Real-time error correction codes for deletable errors

Ghurumuruhan Ganesan

###### Abstract

In this paper we study codes for correcting deletable errors in binary words,
where each bit is either retained, substituted, erased or deleted and the
total number of errors is much smaller compared to the length of the codeword.
We construct codes capable of correcting errors in the received codeword in
real-time with small delay and low probability of decoding error.

Key words: Deletable errors, redundancy of codes, real-time correction.

##  1 Introduction

Consider recovery of a binary word corrupted by deletable errors, where each
error could either be an erasure, bit substitution (i.e., a one is converted
to a zero and vice versa) or deletion. Regarding deletions, [5] used
Varshamov-Tenengolts codes (VT codes) for correcting a single deletion. Later
[3] described codes for correcting arbitrary number of deletions and recently,
in [7], codes with near optimal redundancy for combating fixed number of
deletions are constructed using hash functions. Error correction codes with
time constraints have also been studied before. For example [9] focused on
developing bidirectional interactive algorithms with low information exchange
for correcting deletions. An estimate on the number of rounds needed for
synchronization was obtained using a divide and conquer strategy. Streaming
codes with delay constraints for erasure and burst channels have been studied
in [4] (see also references therein).

In this paper, we seek codes with low redundancy that are capable of
correcting deletable errors (that could be an erasure, substitution or
deletion) in real-time with low delay, a notion made precise in the next
section. We use modified Varshamov-Tenengolt codes to construct the desired
codes and also obtain an estimate on the fraction of error patterns that are
correctable by the proposed codes.

The paper is organized as follows: In Section 2 we state our main result
Theorem 2.1 regarding codes capable of real-time correction with small delay
and also Theorem 2.2 describing codes for correcting $P-$far deletable error
patterns. In Section 3, we prove Theorem 2.2 and also describe an error
correction algorithm ${\cal A}$ for correcting $P-$far errors. In Section 4,
we use the correction algorithm ${\cal A}$ to construct codes with real-time
correction capability and prove Theorem 2.1.

##  2 Main results

A word of length $n$ is a vector
$\mathbf{x}=(x_{1},\ldots,x_{n})\in\\{0,1\\}^{n}.$ A deletable error pattern
of length $n$ is an element
$\mathbf{g}=(\mathbf{e},\mathbf{v})=((e_{1},\ldots,e_{n}),(s_{1},\ldots,s_{n}))\in\\{0,1\\}^{n}\times\\{D,E,F\\}^{n},$
with $D,E$ and $F$ denoting deletion, erasure and substitution, respectively.
The word $\mathbf{y}=F_{\mathbf{g}}(\mathbf{x})$ obtained after $\mathbf{x}$
is corrupted by the error pattern $\mathbf{g}$ is defined as follows: If
$e_{i}=1,$ then the bit $x_{i}$ is deleted, erased or substituted depending on
whether $s_{i}=D,E$ or $F,$ respectively. If $e_{i}=0,$ no change occurs to
the bit $x_{i}.$ For integer $1\leq t\leq n$ we define
$F_{\mathbf{e}}(\mathbf{x},t)$ to be the result of corrupting the first $t$
bits of $\mathbf{x}$ according to the first $t$ entries in $\mathbf{e}.$

For example, if $n=5$ and $\mathbf{g}=((1,0,1,1,1),(F,E,D,F,E)),$ then
$F_{\mathbf{g}}(\mathbf{x})=(1-x_{1},x_{2},1-x_{4},\varepsilon),$ where
$\varepsilon$ is the erasure symbol and
$F_{\mathbf{g}}(\mathbf{x},3)=(1-x_{1},x_{2}).$ For $r\geq 1,$ we define
${\cal E}_{n}(r):=\left\\{(\mathbf{e},\mathbf{v}):\sum_{i=1}^{n}e_{i}\leq
r\right\\}$ to be the set of all possible $n-$length patterns containing at
most $r$ deletable errors. We also let ${\cal E}_{n}:=\cup_{1\leq r\leq
n}{\cal E}_{n}(r)$ be the set of all possible $n-$length error patterns.

An $n-$length code ${\cal C}$ of size $\\#{\cal C}=q$ is a set
$\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{q}\\}\subset\\{0,1\\}^{n}.$ We define
the redundancy of ${\cal C}$ to be

$R({\cal C}):=n-\log\left(\\#{\cal C}\right),$ (2.1)

where all logarithms are to the base $2$ throughout.

Let ${\cal F}\subseteq{\cal E}_{n}$ be any set of $n-$length error patterns.
The code ${\cal C}$ is said to be capable of correcting all error patterns in
${\cal F}$ if for any $\mathbf{x}_{1}\neq\mathbf{x}_{2}\in{\cal C}$ and any
$\mathbf{g}_{1},\mathbf{g}_{2}\in{\cal F},$ we must have that the corruptions
$F_{\mathbf{g}_{1}}(\mathbf{x}_{1})\neq F_{\mathbf{g}_{2}}(\mathbf{x}_{2}).$
We have the following definition regarding real-time error correction.

###### Definition 1

For integer $d\geq 1$ we say that ${\cal C}$ can correct all error patterns in
${\cal F}\subseteq{\cal E}_{n}$ in real-time with delay at most $d$ if for any
$1\leq z\leq n-d,\mathbf{g}_{1},\mathbf{g}_{2}\in{\cal F}$ and
$\mathbf{x}_{1}\neq\mathbf{x}_{2}\in{\cal C},$ we have that

$F_{\mathbf{g}_{1}}(\mathbf{x}_{1},z+d)\neq
F_{\mathbf{g}_{2}}(\mathbf{x}_{2},z+d)$

The consequence of Definition 1 is this: Suppose the word $\mathbf{x}$ is
transmitted and is corrupted by the error pattern $\mathbf{g}.$ Given the
partial word $F_{\mathbf{g}}(\mathbf{x},z+d)$ obtained by corrupting the first
$z+d$ bits of $\mathbf{x}$ for any $1\leq z\leq n-d,$ we must be able to
determine the first $z$ bits of $\mathbf{x}.$

For integers $t,d\geq 1$ let ${\cal F}(t,d)\subset{\cal E}_{n}(t)$ be a set of
maximum size containing at most $t$ errors, that are correctable by the code
${\cal C}$ in real-time with delay $d.$ We define the $(t,d)-$_real-time error
probability_ of ${\cal C}$ to be

$\rho(t,d):=\frac{\\#\left({\cal E}_{n}(t)\setminus{\cal
F}(t,d)\right)}{\\#{\cal E}_{n}(t)}.$

If all error patterns in ${\cal E}_{n}(t)$ are equally likely, then
$\rho(t,d)$ could be interpreted as the decoding error probability.

For a given $t,$ we are interested in studying the tradeoff involved in
choosing the delay parameter $d.$ If $d=\infty,$ then we simply require a code
that corrects $t$ errors and we know (see for e.g. [7]) there are codes with
negligible redundancy for correcting any fraction of errors. Intuitively
therefore if $d$ is large, then our code should have small redundancy since
the effect of the delay becomes lesser and lesser as $d$ increases. What about
the redundancy when $d$ is small? In the extreme case of $d=1,$ we must simply
have a code that is equivalent to a repetition code since the first bit must
be deductable using the second bit and the first two bits must be inferred
using the first three bits and so on. In this case, the redundancy is
$1-\frac{1}{n}.$ In general, for small $d$ therefore we expect the code to
have a large redundancy.

The following result obtains bounds on the delay, redundancy and the error
probability of codes capable of correcting deletable errors, as a function of
the total number of errors.

###### Theorem 2.1

Let $1\leq t_{n}\leq\frac{n^{\frac{1}{3}}}{6}$ be any integer. For every
integer $d_{n}$ satisfying $4t_{n}\leq d_{n}\leq\frac{2n}{3t_{n}^{2}}$ there
is an $n-$length code ${\cal C}_{frac}={\cal C}_{frac}(n)$ with a real-time
delay $d_{n},$ redundancy

$R({\cal C}_{frac})\leq n\cdot\frac{4\log(2d_{n})}{d_{n}},$ (2.2)

and a $(t_{n},d_{n})-$real-time error probability

$\rho(t_{n},d_{n})\leq 11\frac{t_{n}^{2}d_{n}}{n}.$ (2.3)

Thus if the maximum number of deletable errors in an $n-$length word is
$t_{n},$ then for every $d_{n}$ satisfying the bounds in the Theorem, we can
obtain a code capable of real-time correction with delay at most $d_{n},$
redundancy as in (2.2) and total error probability as in (2.3). Ideally we
prefer that $d_{n}\longrightarrow\infty$ and
$\frac{t_{n}^{2}d_{n}}{n}\longrightarrow 0$ as $n\rightarrow\infty$ so that
for all $n$ large the code ${\cal C}_{frac}$ has redundancy $o(n)$ and an
error probability of $o(1),$ using the standard $o(.)$ notations. Theorem 2.1
also illustrates the redundancy-error probability tradeoff in terms of the
desired delay $d_{n}.$ Choosing larger $d_{n}$ reduces redundancy but
increases the error probability. We illustrate our result with some examples.

_Example 1_ : Suppose we have a communication channel that introduces at most
$n^{\alpha}$ deletable errors in an $n-$length word for some constant
$\alpha<\frac{1}{3}.$ Setting $t_{n}=n^{\alpha},$ choosing
$d_{n}=4n^{\alpha}\cdot\log{n}$ and using $\alpha<\frac{1}{3},$ we see that
the conditions in Theorem 2.1 are satisfied for all $n$ large. From Theorem
2.1 we therefore see that there exists an $n-$length code with real-time delay
$d_{n},$ redundancy $o(n^{1-\alpha})$ and a real-time error probability of at
most $\frac{42\log{n}}{n^{1-3\alpha}}.$

_Example 2_ : For a numerical example, suppose that an encoded file containing
$n=10^{8}$ bits is to be transmitted across a channel that introduces at most
$t_{n}=10$ deletable errors. Setting $d_{n}=4000$ we see that the redundancy
of the code ${\cal C}_{frac}$ is at most $10^{6}\cdot\log(2000)\leq 12\cdot
10^{6}$ and so the rate of ${\cal C}_{frac}$ is at least $1-\frac{12\cdot
10^{6}}{10^{8}}=0.88.$ If all error patterns are equally likely then the real-
time error probability is also the decoding error probability and is at most
$\frac{44}{10000}=4.4\cdot 10^{-3}.$

The main ingredient in the construction of the real-time error correction code
in Theorem 2.1 is $P-$far deletable error patterns which we describe next. Let
$n\geq P\geq 2$ be any integers. If
$\mathbf{g}=(\mathbf{e},\mathbf{v}),\mathbf{e}=(e_{1},\ldots,e_{n})\in\\{0,1\\}^{n}$
is an error pattern such that $|i-j|\geq P$ for any two non zero
$e_{i},e_{j},$ we then say that $\mathbf{g}$ is an $n-$length $P-$_far
deletable error pattern_. Letting

$\delta(P):=\frac{2P+1}{2^{P-1}},$ (2.4)

we have the following result regarding codes capable of correcting $3P-$far
deletable error patterns.

###### Theorem 2.2

For all integers $n\geq P\geq 2$ there exists a $n-$length code ${\cal
C}_{far}={\cal C}_{far}(n,P)$ with redundancy

$R({\cal
C}_{far})\leq\left(\frac{n}{P}-1\right)\log\left(\frac{2P+1}{1-\delta(P)}\right)+\log{P}+2$
(2.5)

that is capable of correcting all $3P-$far deletable error patterns.

Conversely, if ${\cal A}$ is any $n-$length code capable of correcting all
$3P-$far deletable error patterns, then

$R({\cal A})\geq\frac{n}{64(3P+6)}-3$ (2.6)

for all large $n.$

Suppose $\\{P_{n}\\}$ is a sequence satisfying

$\frac{P_{n}}{\log{n}}\longrightarrow\infty\text{ and
}\frac{P_{n}}{\sqrt{n\log{n}}}\longrightarrow 0$ (2.7)

as $n\rightarrow\infty.$ If ${\cal B}$ is any $n-$length code capable of
correcting all $3P_{n}-$far deletable error patterns, then

$R({\cal
B})\geq\left(\frac{n}{6P_{n}}-1\right)\log\left(\frac{3P_{n}}{64}\right)-2$
(2.8)

for all large $n.$

For $P=P_{n}$ growing with $n$ we see from Theorem 2.2 that the redundancy
grows at least of the order of $n\cdot\frac{\log{P_{n}}}{P_{n}}=o(n).$ For
this range of $P,$ we also see from the upper bound (2.5) that the code ${\cal
C}_{far}$ has near optimal redundancy.

Before we proceed with the proofs, we briefly contrast and compare our results
with related existing schemes for deletion correction. In our proof of Theorem
2.1 below, we use Theorem 2.2 to first construct a block code that is capable
of correcting all $P_{n}-$far deletable errors and then choose $P_{n}$
appropriately so as to obtain the desired delay $d_{n}.$ The advantage of
using $P_{n}-$far deletable errors is that we can ensure that at most one
deletable error occurs within any one block (defined formally in the next
section). Such an approach is known as _segmentation_ and has been studied
before for edit channels (i.e. channels allowing only deletion or insertion of
bits). The Liu-Mitzenmacher construction [6] employs a segment-by-segment code
specified via sufficient conditions and finds a maximum size code by
converting into an independent set problem. Recently, [1] has studied coding
for segmented edit channels by using subsets of Varshamov-Tenengolts (VT)
codes and obtained bounds on the maximum possible size of such a code.

The approaches described above are not directly applicable for compound
channels allowing deletable errors because, in the case of segmentation, we
can no longer interpret a substitution as a deletion followed by insertion as
this would cause two errors within a block. Below, we use a modified form of
VT codes to obtain our desired codes and demonstrate how deletable error
correction can be performed in a sequential manner.

In the next two sections, we prove Theorems 2.2 and 2.1 in that order.

##  3 Proof of Theorem 2.2

We begin with a description of codes capable of correcting $P-$far errors.

### Codes for correcting $P-$far errors

For integers $m\geq 3$ and $0\leq a\leq m,$ we define the modified Varshamov-
Tenengolts (VT) code $VT_{a}(m)$

$VT_{a}(m):=\left\\{\mathbf{x}=(x_{1},\ldots,x_{m})\in\\{0,1\\}^{m}:\sum_{i=1}^{m}i\cdot
x_{i}\equiv a\mod{2m+1}\right\\}.\\\ $

Arguing as in [8], the code $VT_{a}(m)$ is capable of correcting a single
deletable error.

For integers $P\geq 2$ and $n\geq P,$ write $n=tP+s$ where $0\leq s<P-1.$ Let
$\mathbf{0}$ and $\mathbf{1}$ denote the all zero and all ones words with
length depending on the context. For integers $0\leq a_{1}\leq 2P$ and $0\leq
a_{2}\leq 2(P+s),$ define the code ${\cal C}_{far}={\cal
C}_{far}(a_{1},a_{2},P,s,n)$ as

$\displaystyle{\cal C}_{far}$ $\displaystyle:=$
$\displaystyle\\{\mathbf{x}=(\mathbf{x}(1),\ldots,\mathbf{x}(t)):\mathbf{x}(i)\in
VT_{a_{1}}(P)\setminus\\{\mathbf{0},\mathbf{1}\\}$ (3.1)
$\displaystyle\;\;\;\;\;\;\;\;\text{ for }1\leq i\leq t-1,\mathbf{x}(t)\in
VT_{a_{2}}(P+s)\\},$

so that ${\cal C}_{far}$ is obtained by appending together $t-1$ words from
the code
$VT_{a_{1}}(P)\setminus\\{\mathbf{0},\mathbf{1}\\}$ and then appending a word
containing $P+s$ bits from the code $VT_{a_{2}}(P+s).$ We denote the bits in
the $i^{th}$ word as $\mathbf{x}(i)=(x_{1}(i),\ldots,x_{P}(i))$ for $1\leq
i\leq t-1$ and let $\mathbf{x}(t)=(x_{1}(t),\ldots,x_{P+s}(t)).$ We choose
optimal values of $a_{1}$ and $a_{2}$ later for minimizing the redundancy. The
encoding and decoding described in this subsection hold for all values of
$a_{1}$ and $a_{2}.$

We see below that the code ${\cal C}_{far}$ is capable of correcting all
$3P-$far deletable patterns. The main idea is that if $\mathbf{x}$ is
corrupted by a $3P-$far deletable error pattern, then at most one deletable
error occurs in each word $\mathbf{x}(j)$ in (3.1). This allows us to correct
the errors in a sequential manner. Let $\mathbf{y}=F_{\mathbf{g}}(\mathbf{x})$
where $\mathbf{g}=(\mathbf{e},\mathbf{v})$ be the received word and suppose
that $\mathbf{x}(j),j\leq t-2$ is the first block of $\mathbf{x}$ to be
corrupted by an error in $\mathbf{g};$ i.e., $\mathbf{e}=(e_{1},\ldots,e_{n})$
is such that if $u=\min\\{i:e_{i}=1\\},$ then $(j-1)P+1\leq u\leq jP.$ We
consider the cases $j=t-1$ or $j=t$ at the end.

Divide the corrupted word
$\mathbf{y}=(\mathbf{y}(1),\ldots,\mathbf{y}(t_{1}))$ into blocks where the
$j^{th}$ block $\mathbf{y}(j)=(y_{1}(j),\ldots,y_{P}(j)),1\leq j\leq t_{1}-1$
has $P$ bits and $\mathbf{y}(t_{1})$ has at least $P$ and at most $2P-1$ bits.
Since the first error position $(j-1)P+1\leq u\leq jP$ falls in block
$\mathbf{x}(j),$ the blocks $\mathbf{x}(i),1\leq i\leq j-1$ are uncorrupted
and $\mathbf{y}(i)=\mathbf{x}(i),1\leq i\leq j-1.$ Consequently, the checksum

$CS(l):=\sum_{i=1}^{P}i\cdot y_{i}(l)\equiv a_{1}\mod(2P+1)$ (3.2)

for $1\leq l\leq j-1$ and so the checksum difference
$|CS(l)-a_{1}|\mod(2P+1)\equiv 0$ for all blocks $1\leq l\leq j-1.$

If the error corrupting the block $\mathbf{x}(j)$ is an erasure, then
$y_{u}(j)=\varepsilon$ (the erasure symbol) and $y_{k}(j)=x_{k}(j)$ for all
$1\leq k\neq u\leq P.$ Therefore the modified checksum

$CS_{er}(j):=\sum_{i=1,i\neq u}^{P}i\cdot y_{i}(j)=\sum_{i=1,i\neq
u}^{P}i\cdot x_{i}(j).$ (3.3)

If $x_{u}(j)=0,$ then $CS_{er}(j)-a_{1}\equiv 0\mod(2P+1)$ and if
$x_{u}(j)=1,$ then
$CS_{er}(j)-a_{1}\equiv-u\mod(2P+1)\neq 0$ and so the modified checksum
difference $|CS_{er}(j)-a_{1}|\mod(2P+1)\equiv u1{1}(x_{u}(j)=1)$ is nonzero
if and only if the erased bit is a one. This allows us to correct the erasure.

If the error corrupting the block $\mathbf{x}(j)$ is a substitution or
deletion, then it is not directly detectable as in the case of erasure above.
We therefore use the checksums of both $\mathbf{y}(j)$ and $\mathbf{y}(j+1)$
to indirectly deduce the nature of the error. Indeed, if the error is a
substitution then $y_{u}(j)=1-x_{u}(j)$ and $y_{k}(j)=x_{k}(j)$ for $1\leq
k\neq u\leq P$ and so the checksum of the block $\mathbf{y}(j)$ is

$CS(j):=\sum_{i=1}^{P}i\cdot y_{i}(j)=\sum_{i=1,i\neq u}i\cdot
x_{i}(j)+u\cdot(1-x_{u}(j)).$ (3.4)

Thus $CS(j)-a_{1}\equiv u(1-2x_{u}(j))$ and so the checksum difference for the
block $\mathbf{y}(j),$

$|CS(j)-a_{1}|\equiv u\mod(2P+1)$

is nonzero. Moreover, since the errors are $3P-$far apart, no errors have
corrupted the block $\mathbf{x}(j+1)$ of the original word (which also
contains $P$ bits since $j\leq t-2$). Therefore the block
$\mathbf{y}(j+1)=\mathbf{x}(j+1)$ and the checksum difference
$|CS(j+1)-a_{1}|\mod(2P+1)$ for the block $\mathbf{y}(j+1)$ is zero.

If on the other hand the error corrupting the block $\mathbf{x}(j)$ is a
deletion, we may or may not get a nonzero checksum difference in block
$\mathbf{y}(j).$ But we are guaranteed a nonzero checksum difference in block
$\mathbf{y}(j+1).$ This is because in the block $\mathbf{y}(j+1),$ the
corresponding bits of $\mathbf{x}(j+1)$ are shifted one position to the left;
i.e., $y_{i}(j)=x_{i+1}(j)$ for $1\leq i\leq P-1.$ Therefore the checksum

$\displaystyle CS(j+1)$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{P-1}i\cdot
x_{i+1}(j+1)+P\cdot y_{P}(j+1)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{P-1}(i+1)\cdot x_{i+1}(j+1)+P\cdot
y_{P}(j+1)-\sum_{i=2}^{P}x_{i}(j+1)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{P}i\cdot x_{i}(j+1)+P\cdot
y_{P}(j+1)-\sum_{i=1}^{P}x_{i}(j+1)$

and the checksum difference

$CS(j+1)-a_{1}\equiv P\cdot y_{P}(j+1)-\sum_{i=1}^{P}x_{i}(j+1)\mod(2P+1).$

If $y_{P}(j+1)=1,$ then $P\geq P-\sum_{i=1}^{P}x_{i}(j+1)\geq 1,$ since not
all bits in a block can be one. If $y_{P}(j+1)=0,$ then
$-P\leq-\sum_{i=1}^{P}x_{i}(j+1)\leq-1,$ since not all bits in a block can be
zero. In other words, the checksum difference for the block $\mathbf{y}(j+1),$
$|CS(j+1)-a_{1}|\mod(2P+1)\neq 0.$

Summarizing, suppose we get the first nonzero checksum difference (mismatch)
at some block $\mathbf{y}(j)$ containing $P$ bits. The mismatch may be because
of an error either in block $\mathbf{y}(j-1)$ or block $\mathbf{y}(j).$ If
indeed the mismatch was because of an error in block $\mathbf{y}(j-1),$ then
the error must be a deletion since a substitution would have already caused a
mismatch for block $\mathbf{y}(j-1)$ (see discussion following (3.4)). We
therefore remove the last bit of the block $j-1$ and perform single deletion
correction to get a new word $\mathbf{\hat{x}}(j-1).$ If
$\mathbf{\hat{x}}(j-1)\neq\mathbf{y}(j-1),$ we replace the first $P-1$ bits of
the block $\mathbf{y}(j-1)$ with the block $\mathbf{\hat{x}}(j-1).$

If $\mathbf{\hat{x}}(j-1)=\mathbf{y}(j-1),$ then we can assume that the error
has occurred in block $\mathbf{y}(j)$ and use block $\mathbf{y}(j+1)$ to
determine the nature of error: If $\mathbf{y}(j+1)$ is not the final block in
$\mathbf{y},$ then we proceed as above and deduce that the error in
$\mathbf{y}(j)$ is either a substitution or deletion depending on whether the
checksum difference of the block $\mathbf{y}(j+1)$ is zero or not,
respectively.

If on the other hand $\mathbf{y}(j+1)$ is the final block in $\mathbf{y},$
then it is necessarily true that $\mathbf{y}$ is obtained after corrupting
$\mathbf{x}$ by a single error occurring in one of the last two blocks
$\mathbf{x}(t-1)$ or $\mathbf{x}(t);$ i.e., the first error position $u$
defined in the paragraph prior to (3.2) falls in one of the last two blocks
$\mathbf{x}(t-1)$ or $\mathbf{x}(t).$ Since errors are $3P-$far apart, the
error at position $u$ is the only error corrupting $\mathbf{x}$ and so the
corrupted word $\mathbf{y}$ has either $n$ or $n-1$ bits.

Split $\mathbf{y}=(\mathbf{y}(1),\ldots,\mathbf{y}(t-1),\mathbf{y}(t))$ where
the first $t-1$ blocks contain $P$ bits each and the final block
$\mathbf{y}(t)$ has either $P+s$ or $P+s-1$ bits. One of the blocks in
$\\{\mathbf{y}(t-1),\mathbf{y}(t)\\}$ has been corrupted by an error and we
perform correction as follows. If the error is an erasure, then we correct the
erased bit simply by computing the checksum difference as described before
(see discussion prior to (3.3)). If there is no erasure but the received word
$\mathbf{y}$ has $n$ bits, then the error is a substitution and we obtain the
location of the substitution by computing the checksum difference for each of
the blocks $\mathbf{y}(t-1)$ and $\mathbf{y}(t),$ as described in the
paragraph containing (3.4).

Finally, if $\mathbf{y}$ has $n-1$ bits, then the error is a deletion and we
determine the block where the deletion has occurred as follows. We perform
single deletion correction on the first $P~{}-~{}1$ bits
$\\{\mathbf{y}_{i}(t-1)\\}_{1\leq i\leq P-1}$ of $\mathbf{y}(t-1)$ and get a
new $P$ bit word $\mathbf{\hat{w}}.$ If $\mathbf{\hat{w}}\neq\mathbf{y}(t-1),$
then the deletion necessarily has occurred in the block $\mathbf{x}(t-1)$ of
the original word $\mathbf{x}.$ We therefore finish the iteration by inserting
$\mathbf{\hat{w}}$ into the word $\mathbf{y}$ giving the output
$\mathbf{\hat{x}}=\left(\mathbf{y}(1),\ldots,\mathbf{y}(t-2),\mathbf{\hat{w}},\right.$$\left.y_{P}(t-1),\mathbf{y}(t)\right).$

If on the other hand $\mathbf{\hat{w}}=\mathbf{y}(t-1),$ then we assume that
the deletion has occurred in the final block $\mathbf{x}(t)$ of the original
word $\mathbf{x}.$ We then perform single deletion correction on the $P+s-1$
bits of $\mathbf{y}(t)$ to get a new word $\mathbf{\hat{z}}$ containing $P+s$
bits and output
$\mathbf{\hat{x}}=(\mathbf{y}(1),\ldots,\mathbf{y}(t-1),\mathbf{\hat{z}}).$

The procedure described above corrects a single error in the corrupted word
$\mathbf{y}$ and after the iteration, the first error occurring at position
$u$ in the error pattern $\mathbf{g}$ (see discussion prior to (3.2)) is
corrected. The received word after the first iteration
$\mathbf{y}^{(1)}=F_{\mathbf{g}(1)}(\mathbf{x})$ is a lesser corrupted version
of $\mathbf{x}$ than $\mathbf{y}$ and
$\mathbf{g}(1)=(\mathbf{e}(1),\mathbf{v})$ is an error pattern whose first
error occurs strictly after the first error in $\mathbf{g};$ i.e., if
$\mathbf{e}(1)=(e_{1}(1),\ldots,e_{n}(1))$ and $u_{1}=\min\\{i:e_{i}(1)=1\\},$
then $u_{1}>u.$

We now repeat the above procedure to correct the error at position $u_{1}$ and
continuing iteratively, we sequentially correct all the remaining errors. The
procedure stops if there is no checksum mismatch and we output the final word
as our estimate of $\mathbf{x}.$ We summarize the above method as an Algorithm
before the Appendices, where the function $BlockSplit(.,P)$ splits the input
into blocks of length $P$ with the last block containing between $P$ and
$2P-1$ bits.

From the description, we also see that the above algorithm is capable of
correcting any $P-$far error pattern in real-time with a delay of at most
$4P.$ This is because knowing the corruption of the first $z+4P$ bits of the
codeword $\mathbf{x}$ for any integer $1\leq z\leq n-4P,$ we can determine the
value of the bits $x_{i},1\leq i\leq z.$

### Redundancy of the code ${\cal C}_{far}$

To compute an upper bound on the redundancy of the code ${\cal C}_{far},$ we
choose $a_{1}$ and $a_{2}$ above such that

$\\#VT_{a_{1}}(P)\geq\frac{2^{P}}{2P+1}\text{ and
}\\#VT_{a_{2}}(s)\geq\frac{2^{P+s}}{2(P+s)+1}.$ (3.5)

Since we append together $t-1$ words each chosen from
$VT_{a_{1}}(P)\setminus\\{\mathbf{0},\mathbf{1}\\}$ and one word from
$VT_{a_{2}}(P+s),$ we have that

$\\#{\cal
C}_{far}\geq\left(\frac{2^{P}}{2P+1}-2\right)^{t-1}\frac{2^{P+s}}{(2P+2s+1)}=2^{n}\left(\frac{1-\delta(P)}{2P+1}\right)^{t-1}\frac{1}{2P+2s+1},$
(3.6)

where $\delta(P)=\frac{2P+1}{2^{P-1}}$ is as in (2.4) and relation (3.6) is
true since $Pt+s=n.$ Using $s+1\leq P,$ we further get

$\\#{\cal C}_{far}\geq
2^{n}\left(\frac{1-\delta(P)}{2P+1}\right)^{t-1}\frac{1}{4P}\geq
2^{n}\left(\frac{1-\delta(P)}{2P+1}\right)^{\frac{n}{P}-1}\frac{1}{4P},$

since $t\leq\frac{n}{P}$ and $\frac{1-\delta(P)}{2P+1}<1.$ From (2.1) we then
get (2.5).

To obtain the redundancy lower bounds in Theorem 2.2, we use the fact that any
code capable of correcting $t$ deletable errors must also be capable of
corrected $t$ deletions. We also remark that redundancy lower bounds for
segmented deletion channels have been studied in [9] and so for completeness,
we give our proofs in the Appendix $1.$

##  4 Proof of Theorem 2.1

Let

$\omega_{n}:=\frac{4n}{t_{n}^{2}\cdot d_{n}}\text{ and
}P_{n}:=\frac{n}{t_{n}^{2}\omega_{n}}=\frac{d_{n}}{4}$ (4.1)

so that $6\leq\omega_{n}\leq\frac{n}{t_{n}^{3}}$ and assume that $P_{n}$ is an
integer greater than or equal to $6.$ Let ${\cal C}_{frac}:={\cal
C}_{far}(n,P_{n})$ be the code defined in Theorem 2.2 so that ${\cal
C}_{frac}$ is capable of real-time correction of all $3P_{n}-$far deletable
error patterns with a delay of at most $4P_{n}$ (see the final paragraph in
the code description subsection of Section 3). Using (2.5), $P_{n}\geq 6$ and
$\delta(P_{n})\leq\frac{1}{2}$ we also get that the redundancy of ${\cal
C}_{frac}$ is

$R({\cal
C}_{frac})\leq\left(\frac{n}{P_{n}}-1\right)\log\left(\frac{2P_{n}+1}{1-\delta(P_{n})}\right)+\log{P_{n}}+2\leq
n\cdot\frac{\log{8P_{n}}}{P_{n}}$ (4.2)

where the second inequality in (4.2) above follows from $P_{n}\geq 6.$ Setting
$P_{n}=\frac{d_{n}}{4},$ we get the redundancy estimate (2.2) in Theorem 2.1.

We show below that if ${\cal F}_{n}$ is the set of all $3P_{n}-$far error
patterns, then

$\frac{\\#{\cal F}_{n}}{\\#{\cal E}_{n}(t_{n})}\geq 1-\frac{42}{\omega_{n}}.$
(4.3)

for all $n\geq 10.$ Since ${\cal C}_{frac}$ is capable of correcting all
$3P_{n}-$far deletable error patterns, this proves the estimate on the
fraction of deletable errors corrected in Theorem 2.1. In what follows we
prove (4.3). First, the total number of error patterns in ${\cal
E}_{n}(t_{n})$ is $\\#{\cal E}_{n}(t_{n})=\sum_{k=0}^{t_{n}}{n\choose
k}3^{k}.$ Suppose
$\mathbf{g}=(\mathbf{e},\mathbf{v}),\mathbf{e}=(e_{1},\ldots,e_{n})$ is not a
$3P_{n}-$far deletable error pattern. Let $n=3LP_{n}+s,0\leq s\leq 3P_{n}-1$
and split $\mathbf{e}=(\mathbf{e}(1),\ldots,\mathbf{e}(L))$ into $L$ blocks,
where the first $L-1$ blocks each have length $3P_{n}$ and the final block has
length $3P_{n}+s.$ Since $\mathbf{g}$ is not a $3P_{n}-$far error pattern,
there are only two possibilities:
$(p1)$ One of the $L$ blocks in $\mathbf{e}$ contains at least two nonzero
entries.
$(p2)$ Two consecutive blocks in $\mathbf{e}$ contain exactly one nonzero
entry each.
We bound the number of patterns for each possibility.

To bound the number of patterns $\\#{\cal F}(p1)$ in possibility $(p1),$ we
argue as follows: If ${\cal S}(l),1\leq l\leq L$ is the set of error patterns
$\mathbf{g}=(\mathbf{e},\mathbf{v})$ where the $l^{th}$ block $\mathbf{e}(l)$
of $\mathbf{e}$ has two or more nonzero entries, then

$\\#{\cal F}(p1)\leq\sum_{l=1}^{L}\\#{\cal S}(l)=(L-1)\\#{\cal S}(1)+\\#{\cal
S}(L).$ (4.4)

In the Appendix $2$ below we use Binomial coefficient estimates to show that

$\\#{\cal S}(l)\leq\frac{84P_{n}^{2}t_{n}^{2}+8t_{n}^{4}}{n^{2}}(\\#{\cal
E}_{n}(t_{n}))$ (4.5)

for all $1\leq l\leq L$ and since $L\leq\frac{n}{3P_{n}},$ we get from (4.4)
that

$\\#{\cal
F}(p1)\leq\frac{n}{3P_{n}}\left(\frac{84P_{n}^{2}t_{n}^{2}+8t_{n}^{4}}{n^{2}}\right)(\\#{\cal
E}_{n}(t_{n}))=\left(\frac{28P_{n}t_{n}^{2}}{n}+\frac{8t_{n}^{4}}{3nP_{n}}\right)(\\#{\cal
E}_{n}(t_{n})).$

Since $P_{n}=\frac{n}{t_{n}^{2}\omega_{n}}$ we get that
$\frac{28P_{n}t_{n}^{2}}{n}+\frac{4t_{n}^{4}}{3nP_{n}}=\frac{28}{\omega_{n}}+\frac{4}{3\omega_{n}}\left(\frac{\omega_{n}t_{n}^{3}}{n}\right)^{2}\leq\frac{28+\frac{4}{3}}{\omega_{n}}$
by (4.1) and so

$\\#{\cal F}(p1)\leq\frac{30}{\omega_{n}}\cdot\left(\\#{\cal
E}_{n}(t_{n})\right).$ (4.6)

To bound the number of patterns $\\#{\cal F}(p2)$ in possibility $(p2)$
described prior to (4.4), we argue as follows: If ${\cal T}(l)$ is the set of
error patterns $\mathbf{g}=(\mathbf{e},\mathbf{v})$ where the blocks
$\mathbf{e}(l)$ and $\mathbf{e}(l+1),1\leq l\leq L-1$ each have exactly one
nonzero entry each, then

$\\#{\cal F}(p2)\leq\sum_{l=1}^{L-1}\\#{\cal T}(l)=(L-2)\\#{\cal
T}(1)+\\#{\cal T}(L-1).$ (4.7)

We estimate $\\#{\cal T}(1)$ as follows. Suppose
$\mathbf{g}=(\mathbf{e},\mathbf{v})\in{\cal T}(1)$ and suppose that
$\mathbf{e}=(e_{1},\ldots,e_{n})$ has $k$ nonzero entries. We split
$\mathbf{e}=(\mathbf{e}(1),\ldots,\mathbf{e}(L))$ into $L$ blocks as before.
Among the $3P_{n}$ bits in the first block $\mathbf{e}(1),$ we choose one bit,
among the $3P_{n}$ bits of $\mathbf{e}(2)$ we choose one bit and choose $k-2$
bits from the remaining $n-6P_{n}$ bits of $\mathbf{e}(j),j\neq 1,2.$ This can
be done in ${3P_{n}\choose 1}{3P_{n}\choose 1}{n-6P_{n}\choose k-2}$ ways and
so

$\\#{\cal T}(1)=\sum_{k=2}^{t_{n}}9P_{n}^{2}{n-6P_{n}\choose k-2}3^{k}\leq
9P_{n}^{2}\sum_{k=2}^{t_{n}}{n\choose k-2}3^{k}.$ (4.8)

For $k\leq t_{n}$ the ratio

$\frac{{n\choose k-2}}{{n\choose
k}}=\frac{k(k-1)}{(n-k+2)(n-k+1)}\leq\frac{t_{n}^{2}}{(n-t_{n})^{2}}=\left(\frac{t_{n}}{n}\right)^{2}\left(1-\frac{t_{n}}{n}\right)^{-2}$
(4.9)

and using $\frac{t_{n}}{n}\leq\frac{1}{\sqrt{n}}$ (see statement of Theorem),
we also have that
$\left(1-\frac{t_{n}}{n}\right)^{-2}\leq\frac{n}{(\sqrt{n}-1)^{2}}\leq 4$ for
all $n\geq 4.$ From (4.8), we therefore get that

$\\#{\cal
T}(1)\leq\frac{36P_{n}^{2}t_{n}^{2}}{n^{2}}\sum_{k=2}^{t_{n}}{n\choose
k}3^{k}\leq\frac{36P_{n}^{2}t_{n}^{2}}{n^{2}}(\\#{\cal E}_{n}(t_{n})).$ (4.10)

Performing an analogous analysis as above for the last two blocks with length
$3P_{n}$ and $3P_{n}+s,$ we get

$\\#{\cal T}(L-1)=\sum_{k=2}^{t_{n}}3P_{n}(3P_{n}+s){n-6P_{n}-s\choose
k-2}3^{k}\leq 18P_{n}^{2}\sum_{k=2}^{t_{n}}{n\choose k-2}3^{k},$ (4.11)

since $s\leq 3P_{n}.$ Again using (4.9), we get

$\\#{\cal
T}(L-1)\leq\frac{36P_{n}^{2}t_{n}^{2}}{n^{2}}\sum_{k=2}^{t_{n}}{n\choose
k}3^{k}\leq\frac{36P_{n}^{2}t_{n}^{2}}{n^{2}}(\\#{\cal E}_{n}(t_{n})).$ (4.12)

Using (4.10) and (4.12) in (4.7) and we therefore get that

$\\#{\cal F}(p2)\leq L\cdot\frac{36P_{n}^{2}t_{n}^{2}}{n^{2}}(\\#{\cal
E}_{n}(t_{n}))\leq\frac{12P_{n}t_{n}^{2}}{n}(\\#{\cal
E}_{n}(t_{n}))=\frac{12}{\omega_{n}}(\\#{\cal E}_{n}(t_{n})),$ (4.13)

where the second inequality in (4.13) is true since $L\leq\frac{n}{3P_{n}}$
and the final estimate in (4.13) is true since
$P_{n}=\frac{n}{t_{n}^{2}\omega_{n}}$ (see (4.1)).

Recall from discussion prior to (4.4) that ${\cal F}_{n}$ denotes the set of
all $3P_{n}-$far error patterns and using (4.6) and (4.13), we get that
$\frac{\\#{\cal F}_{n}}{\\#{\cal E}_{n}(t_{n})}\geq 1-\frac{42}{\omega_{n}},$
proving (4.3). ∎

### Conclusion

In this paper, we have studied redundancy of codes capable of correcting
deletable errors in real time with low probability of error. We have also
provided decoding algorithms that recover the errors in real time. It would be
interesting to extend our results to other channel models, like for example,
magnetic channels with possible additional constraints.

#### Acknowledgements

I thank Professors Alberto Gandolfi, Federico Camia, C. R. Subramanian and the
referees for crucial comments that led to an improvement of the paper. I also
thank Professors Federico Camia, C. R. Subramanian and IMSc for my
fellowships.

## References

  * [1] Abroshan, M., Venkataramanan, R. and Guillén i Fàbregas, A.,  Coding for Segmented Edit Channels,  IEEE Transactions on Information Theory, 64, 3086–3098 (2018).
  * [2] Alon, N. and Spencer, J.,  The Probabilistic Method,  Wiley Interscience.
  * [3] Helberg, A. S. J. and Ferreira, H. C.,  On Multiple Insertion/Deletable Error Correcting Codes,  IEEE Transactions on Information Theory, 48, 305–308 (2002).
  * [4] Krishnan, M. N., Shukla, D. and Vijay Kumar, P.,  Rate-Optimal Streaming Codes for Channels with Burst and Random Erasures,  IEEE Transactions on Information Theory, 66, 4869–4891 (2020).
  * [5] Levenshtein, V. I.,  Binary Codes Capable of Correcting Deletable Errors, Insertions and Reversals,  Doklady Akademii Nauk SSSR, 163, 845–848 (1965).
  * [6] Liu, Z. and Mitzenmacher, M.,  Codes for Deletion and Insertion Channels with Segmented Errors,  IEEE Transactions on Information Theory, 56, 224–232 (2010).
  * [7] Sima, J. and Bruck, J.,  Optimal $k-$Deletion Correcting Codes,  Internation Symposium on Information Theory, 847–851 (2019).
  * [8] Tatwawadi, K. and Chandak, S.,  Tutorial on Algebraic Deletion Correction Codes,  Arxiv Link: https://arxiv.org/pdf/1906.07887.pdf (2019).
  * [9] Venkataramanan, R., Swamy, V. N. and Ramchandran, K.,  Low Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions,  IEEE Transactions on Information Theory, 61, 5670–5689 (2015).

1

Input : Received word $\mathbf{y}$

Output : Estimated word $\mathbf{\hat{x}}$

2SequentialDecode  __

3 _Initialization_ : $\mathbf{\hat{x}}\leftarrow\mathbf{y},j\leftarrow
0,CS\leftarrow 0.$

4 _Preprocessing_ :
$(\mathbf{\hat{x}}(1),\ldots,\mathbf{\hat{x}}(t-1),\mathbf{\hat{x}}(t))\leftarrow
BlockSplit(\mathbf{\hat{x}},P),$

5 _where $P\leq Length(\mathbf{\hat{x}}(t))<2P$ _.

/* Pass all blocks with checksum match */

6 while  _$CS=0$ and $j\leq t$ _ do

7 $j\leftarrow j+1,CS\leftarrow-1$;

8 if  _erasure in $j^{th}$ block_ then

9 $\mathbf{\hat{x}}(j)\leftarrow CorrectErasure(\mathbf{\hat{x}}(j))$;

10 if  _$j <t$ or $j=t$ and $Length(\hat{\mathbf{x}}(t))=P+s$_ then

11 $CS\leftarrow CheckSumDifference(\mathbf{\hat{x}}(j))$;

12

13

14 if  _$CS=0$ and $j=t$ _ then

15 output
$(\mathbf{\hat{x}}(1),\ldots,\mathbf{\hat{x}}(t-1),\mathbf{\hat{x}}(t))$;

16

17

/* Checksum mismatch in $j^{th}$ block; Check if deletion in $(j-1)^{th}$
block */

18 $l\leftarrow\min(j-1,1),\mathbf{T}\leftarrow
CorrectDeletion(RemoveLastBit(\mathbf{\hat{x}}(l)))$;

19 if  _$\mathbf{T}\neq\mathbf{\hat{x}}(l)$_ then

20 $\mathbf{T}\leftarrow(\mathbf{T},LastBit(\mathbf{\hat{x}}(l)))$;

21 else

/* Error in $j^{th}$ block; If final block then directly perform correction */

22 if  _$j=t$_ then

23 if  _$\mathbf{\hat{x}}(j)$ has $P+s$ bits_ then

24 $\mathbf{T}\leftarrow CorrectFlip(\mathbf{\hat{x}}(j))$;

25 else

26 $\mathbf{T}\leftarrow CorrectDeletion(\mathbf{\hat{x}}(j))$;

27 output $(\mathbf{\hat{x}}(1),\ldots,\mathbf{\hat{x}}(t-1),\mathbf{T})$;

28

29

/* In all other cases, determine if error is flipping or deletion using block
$j+1$ */

30 $l\leftarrow j,ErrorType\leftarrow 1$;

31 if  _$l <t-1$ or $l=t-1$ and $Length(\mathbf{\hat{x}}(l+1))=P+s$_ then

32 $ErrorType\leftarrow CheckSumDifference(\mathbf{\hat{x}}(l+1))$;

33 if  _$ErrorType=0$_ then

34 $\mathbf{T}\leftarrow CorrectFlip(\mathbf{\hat{x}}(l))$;

35 else

36 $\mathbf{T}\leftarrow CorrectDeletion(RemoveLastBit(\mathbf{\hat{x}}(l)))$;

37 $\mathbf{T}\leftarrow(\mathbf{T},LastBit(\mathbf{\hat{x}}(l)))$;

38

39

40

/* Update the estimate $\mathbf{\hat{x}}$ with the new block $\mathbf{T}$ */

41
$\mathbf{\hat{x}}\leftarrow(\mathbf{\hat{x}}(1),\ldots,\mathbf{\hat{x}}(l-1),\mathbf{T},\mathbf{\hat{x}}(l+1),\ldots,\mathbf{\hat{x}}(t))$;

42 goto _Preprocessing_ ;

43

Algorithm 1 Correcting a $3P-$far deletable error pattern

## Appendix 1: Redundancy lower bounds

In our proofs below, we use the following large deviation estimate. Let
$\\{X_{j}\\}_{1\leq j\leq m}$ be independent Bernoulli random variables with

$\mathbb{P}(X_{j}=1)=p_{j}=1-\mathbb{P}(X_{j}=0)$

and fix $0<\epsilon\leq\frac{1}{2}.$ If $T_{m}=\sum_{j=1}^{m}X_{j}$ and
$\mu_{m}=\mathbb{E}T_{m},$ then

$\mathbb{P}\left(\left|T_{m}-\mu_{m}\right|\geq\mu_{m}\epsilon\right)\leq
2\exp\left(-\frac{\epsilon^{2}}{4}\mu_{m}\right)$ (4.1)

for all $m\geq 1.$ For a proof of (4.1), we refer to Corollary A.1.14, pp. 312
of [2].

_Proof of ( 2.6) in Theorem 2.2_: Let ${\cal D}$ be any code capable of
correcting all $3P-$far deletable error patterns. The code ${\cal D}$ is
capable of correcting all $3P-$far deletable error patterns consisting only of
deletions and so we henceforth consider only deletions. Let ${\cal F}$ be the
set of all $3P-$far deletable error patters consisting only of deletions and
for $\mathbf{x}\in{\cal D},$ set ${\cal
N}(\mathbf{x})=\cup_{\mathbf{g}\in{\cal F}}F_{\mathbf{g}}(\mathbf{x}).$ Since
the deletable errors are at least $3P$ apart, there are at most $\frac{n}{3P}$
deletable errors in $\mathbf{x}$ and so if $T$ is the largest integer less
than or equal to $\frac{n}{3P},$ then ${\cal
N}(\mathbf{x})\subseteq\cup_{0\leq r\leq T}\\{0,1\\}^{n-r}.$ Moreover, if
$\mathbf{x}_{1}\neq\mathbf{x}_{2}\in{\cal D},$ then
$F_{\mathbf{e}}(\mathbf{x}_{1})\neq F_{\mathbf{e}}(\mathbf{x}_{2})$ by
definition. So the sets $\\{{\cal N}(\mathbf{x})\\}$ are all disjoint and
therefore

$\sum_{\mathbf{x}\in{\cal D}}\\#{\cal
N}(\mathbf{x})\leq\sum_{r=0}^{T}2^{n-r}=2^{n+1}\left(1-\frac{1}{2^{T+1}}\right)\leq
2^{n+1}.$ (4.2)

In what follows, we estimate the size of ${\cal N}(\mathbf{x})$ for each
$\mathbf{x}$ belonging to a certain “nice” subset of ${\cal D}.$ For
$\mathbf{x}\in\\{0,1\\}^{n}$ and integer $r\geq 1,$ let

$\mathbf{x}_{r}:=\mathbf{x}_{r}(\mathbf{x})=\mathbf{x}((3P+5)(r-1)+1,(3P+5)(r-1)+5)$
(4.3)

be a sequence of five bits of $\mathbf{x}.$ Say that $\mathbf{x}_{r}$ is a
good $5-$block if the first and last bits are one and the remaining three bits
are zero. Let $Q(\mathbf{x})$ be the number of good $5-$blocks in
$\\{\mathbf{x}_{r}\\}_{1\leq r\leq W}$ where $W$ is the largest integer $x$
satisfying $x\cdot(3P+5)\leq n$ so that

$\frac{n}{3P+6}\leq\frac{n}{3P+5}-1\leq W\leq\frac{n}{3P+5},$ (4.4)

for all $n$ large.

Defining

${\cal
Y}_{n}:=\left\\{\mathbf{x}\in\\{0,1\\}^{n}:Q(\mathbf{x})\geq\frac{n}{64(3P+6)}\right\\},$
(4.5)

we show at the end of this proof that

$\\#{\cal Y}_{n}\geq
2^{n}\left(1-\exp\left(-\frac{n}{16(3P+6)}\right)\right),$ (4.6)

for all $n$ large.

If $\mathbf{x}\in{\cal Y}_{n}\cap{\cal D},$ then there are at least
$\frac{n}{64(3P+6)}$ good $5-$blocks in $\mathbf{x}.$ Let $m_{P}$ be the
largest integer less than or equal to $\frac{n}{64(3P+6)}.$ For every one of
the $m_{P}$ good $5-$blocks, we can either choose to remove a zero bit or not.
There are $2^{m_{P}}$ ways of performing such a procedure and the resulting
set of corrupted words are all distinct. Therefore $\\#{\cal
N}(\mathbf{x})\geq 2^{m_{P}}$ and using (4.2) we get

$2^{m_{P}}\\#\left({\cal D}\bigcap{\cal
Y}_{n}\right)\leq\sum_{\mathbf{x}\in{\cal D}\bigcap{\cal Y}_{n}}\\#{\cal
N}(\mathbf{x})\leq 2^{n+1}.$

From (4.6) we therefore get

$\\#{\cal D}\leq\frac{2^{n+1}}{2^{m_{P}}}+\\#{\cal
Y}^{c}_{n}\leq\frac{2^{n+1}}{2^{m_{P}}}+2^{n}\exp\left(-\frac{n}{16(3P+6)}\right)\leq\frac{2^{n+2}}{2^{m_{P}}}$

for all $n$ large, since
$m_{P}\leq\frac{n}{64(3P+6)}\leq\frac{n\log{e}}{16(3P+6)}.$ Therefore the
redundancy of ${\cal D}$ is at least $m_{P}-\log{4}\geq\frac{n}{64(3P+6)}-3$
for all $n$ large, since $m_{P}\geq\frac{n}{64(3P+6)}-1.$ ∎

_Proof of ( 4.6)_: Let $\mathbf{X}=(X_{1},\ldots,X_{n})$ be a uniformly
randomly chosen word in $\\{0,1\\}^{n}$ so that $X_{i},1\leq i\leq n$ are
independent and identically distributed (i.i.d.) with
$\mathbb{P}(X_{1}=0)=\frac{1}{2}=\mathbb{P}(X_{1}=1).$

To lower bound $Q(\mathbf{X}),$ let $r\geq 1$ be an integer and define

$I_{r}:=\\{X_{(3P+5)(r-1)+1}=1\\}\bigcap_{i=2}^{4}\\{X_{(3P+5)(r-1)+i}=0\\}\bigcap\\{X_{(3P+5)(r-1)+5}=1\\}$
(4.7)

be the event that $\mathbf{X}_{r}$ defined in (4.3) is a good block. The
events $\\{I_{r}\\}$ are i.i.d with $\mathbf{P}(I_{1})=\frac{1}{32}$ and so
$Q(\mathbf{x})=\sum_{r=1}^{W}I_{r}$ where $W$ is as in (4.4) has mean
$\frac{W}{32}.$ Therefore using the deviation estimate (4.1) with
$\epsilon=\frac{1}{2}$ we get

$\mathbb{P}\left(Q\left(\mathbf{x}\right)\geq\frac{W}{64}\right)\geq
1-\exp\left(-\frac{W}{16}\right).$

Using (4.4) we have that $\frac{W}{64}\geq\frac{n}{64(3P+6)}$ for all $n$
large and so

$\mathbb{P}\left(Q\left(\mathbf{x}\right)\geq\frac{n}{64(3P+6)}\right)\geq
1-\exp\left(-\frac{n}{16(3P+6)}\right)$

for all $n$ large. ∎

_Proof of ( 2.6) in Theorem 2.2_: Let ${\cal D}$ be any code capable of
correcting all $3P_{n}-$far deletable error patterns. The code ${\cal D}$ is
capable of correcting all $3P_{n}-$far deletable error patterns consisting
only of deletions and so we henceforth consider only deletions. Let ${\cal F}$
be the set of all $3P_{n}-$far deletable error patters consisting only of
deletions and for $\mathbf{x}\in{\cal D},$ set ${\cal
N}(\mathbf{x})=\cup_{\mathbf{e}\in{\cal F}}F_{\mathbf{e}}(\mathbf{x}).$ Since
the deletions are at least $3P_{n}$ apart, there are at most
$\frac{n}{3P_{n}}$ deletable errors in $\mathbf{x}$ and so if $L$ is the
largest integer less than or equal to $\frac{n}{3P_{n}},$ then ${\cal
N}(\mathbf{x})\subseteq\cup_{0\leq r\leq L}\\{0,1\\}^{n-r}.$ Moreover, if
$\mathbf{x}_{1}\neq\mathbf{x}_{2}\in{\cal D},$ then
$F_{\mathbf{e}}(\mathbf{x}_{1})\neq F_{\mathbf{e}}(\mathbf{x}_{2})$ by
definition. So the sets $\\{{\cal N}(\mathbf{x})\\}$ are all disjoint and
therefore

$\sum_{\mathbf{x}\in{\cal D}}\\#{\cal
N}(\mathbf{x})\leq\sum_{r=0}^{L}2^{n-r}=2^{n+1}\left(1-\frac{1}{2^{L+1}}\right)\leq
2^{n+1}.$ (4.8)

As before, we estimate the size of ${\cal N}(\mathbf{x})$ for a nice subset of
${\cal D}.$ Let $W$ be the largest integer $x$ such that $x\cdot 3P_{n}\leq n$
so that

$\frac{n}{3P_{n}}-1\leq W\leq\frac{n}{3P_{n}}.$ (4.9)

For integer $1\leq r\leq W$ and $\mathbf{x}\in\\{0,1\\}^{n},$ let

$\mathbf{x}_{r}:=\mathbf{x}_{r}(\mathbf{x})=\mathbf{x}(3P_{n}(r-1)+1,3rP_{n})$
(4.10)

be a sequence of $3P_{n}$ bits of $\mathbf{x}.$ We have thus divided the first
$3WP_{n}$ bits of $\mathbf{x}$ into $W$ disjoint blocks
$\\{\mathbf{x}_{r}\\}_{1\leq r\leq W},$ each containing $3P_{n}$ bits.

Let $U$ be the largest integer $y$ such that $5\cdot y\leq 3P_{n}$ so that
$\frac{3P_{n}}{5}-1\leq U\leq\frac{3P_{n}}{5}.$ Divide the first $5U$ bits of
each block $\mathbf{x}_{r}$ into disjoint blocks
$\\{\mathbf{x}_{r,j}\\}_{1\leq j\leq U}$ of five bits each. Say that
$\mathbf{x}_{r,j}$ is a good $5-$block if the first and last bits are one and
the remaining three bits are zero. Let $T_{r}(\mathbf{x})$ be number of good
$5-$blocks in $\mathbf{x}_{r}$ and let

${\cal
V}_{n}:=\left\\{\mathbf{x}\in\\{0,1\\}^{n}:T_{r}(\mathbf{x})\geq\frac{3P_{n}}{64}\text{
for all }1\leq r\leq W\right\\}.$ (4.11)

At the end of this proof, we prove that there are positive constants
$\beta_{i},i=1,2$ such that for all integers $n\geq\beta_{1},$

$\\#{\cal V}_{n}\geq 2^{n}(1-e^{-\beta_{2}P_{n}}).$ (4.12)

Let $W$ be as in (4.9) and as before, split the first $3WP_{n}$ bits of
$\mathbf{x}$ into $W$ blocks $\\{\mathbf{x}_{r}\\}_{1\leq r\leq W}$ of length
$3P_{n}$ each. If $\mathbf{x}\in{\cal V}_{n}\cap{\cal D},$ then there at least
$\frac{3P_{n}}{64}$ good $5-$blocks in each $\mathbf{x}_{r}.$ Choosing one
good $5-$block from each of $\mathbf{x}_{1},\mathbf{x}_{3},\ldots$ and
deleting a middle zero from each such good block, we get a set of distinct
words. Since there are at least $\frac{W-1}{2}$ blocks in
$\mathbf{x}_{1},\mathbf{x}_{3},\ldots,$ the number of corrupted words obtained
as above is at least $\left(\frac{3P_{n}}{64}\right)^{(W-1)/2}.$ The deletable
error patterns giving rise to these words are all $3P_{n}-$far apart and so we
get

$\\#{\cal
N}(\mathbf{x})\geq\left(\frac{3P_{n}}{64}\right)^{(W-1)/2}\geq\left(\frac{3P_{n}}{64}\right)^{\frac{n}{6P_{n}}-1},$
(4.13)

since $W\geq\frac{n}{3P_{n}}-1,$ (see (4.9)).

Letting

$\Delta=\left(\frac{n}{6P_{n}}-1\right)\log\left(\frac{3P_{n}}{64}\right)$

and using (4.13) in (4.8) we get

$2^{\Delta}\\#\left({\cal D}\bigcap{\cal
V}_{n}\right)\leq\sum_{\mathbf{x}\in{\cal C}\bigcap{\cal V}_{n}}\\#{\cal
N}(\mathbf{x})\leq 2^{n+1}$

and so from (4.12) we get

$\\#{\cal D}\leq\frac{2^{n+1}}{2^{\Delta}}+\\#{\cal
V}^{c}_{n}\leq\frac{2^{n+1}}{2^{\Delta}}+2^{n}e^{-\beta_{2}P_{n}}\leq\frac{2^{n+2}}{2^{\Delta}}$

for all $n$ large, since using the second relation in (2.7) that
$\frac{P_{n}^{2}}{n\log{n}}\longrightarrow 0$ as $n\rightarrow\infty,$ we have

$\Delta\leq\frac{n}{P_{n}}\log(3P_{n})\leq\frac{n\log{n}}{P_{n}}\leq\beta_{2}P_{n}\log{e}$

for all $n$ large. Therefore the redundancy of ${\cal D}$ is at least
$\Delta-\log{4}$ for all $n$ large. This proves the redundancy lower bounds
with the exception of (4.6) and (4.12), which we prove separately below. ∎

_Proof of ( 4.12)_: Let $\mathbf{X}=(X_{1},\ldots,X_{n})$ be a uniformly
randomly chosen word in $\\{0,1\\}^{n}$ so that $X_{i},1\leq i\leq n$ are
independent and identically distributed (i.i.d.) with
$\mathbb{P}(X_{1}=0)=\frac{1}{2}=\mathbb{P}(X_{1}=1).$

To lower bound $T_{r}(\mathbf{X})$ for $1\leq r\leq W,$ let $I_{r,j}$ be the
event that $\mathbf{X}_{r,j}$ is a good $5-$block. The events
$\\{I_{r,j}\\}_{1\leq j\leq U}$ are i.i.d with
$\mathbf{P}(I_{r,j})=\frac{1}{32}$ and so
$T_{r}(\mathbf{X})=\sum_{j=1}^{U}I_{r,j}$ has mean $\frac{U}{32}.$ Therefore
from the deviation estimate (4.1), we get that

$\mathbb{P}\left(T_{r}\left(\mathbf{X}\right)\geq\frac{U}{64}\right)\geq
1-e^{-C_{1}U}$ (4.14)

for all $n$ large and some constant $C_{1}>0.$ Since
$U\geq\frac{3P_{n}}{5}-1\geq\frac{3P_{n}}{8}$ for all large $n,$ we get

$\mathbb{P}\left(T_{r}\left(\mathbf{X}\right)\geq\frac{3P_{n}}{2^{9}}\right)\geq
1-e^{-4C_{2}P_{n}}$ (4.15)

for some constant $C_{2}>0$ and all large $n.$ The constant $C_{2}$ does not
depend on $r$ and so

$\mathbb{P}\left(\bigcap_{1\leq r\leq
W}\left\\{T_{r}\left(\mathbf{X}\right)\geq\frac{3P_{n}}{2^{9}}\right\\}\right)\geq
1-W\cdot e^{-4C_{2}P_{n}}.$ (4.16)

Using (4.9) and the first relation in (2.7) that
$\frac{P_{n}}{\log{n}}\longrightarrow\infty,$ we get that

$W\cdot e^{-4C_{2}P_{n}}\leq\frac{n}{2P_{n}}\cdot e^{-4C_{2}P_{n}}\leq
e^{-2C_{2}P_{n}}$

for all $n$ large. ∎

## Appendix 2: Proof of (4.5)

We estimate $\\#{\cal S}(1)$ as follows. Suppose
$\mathbf{g}=(\mathbf{e},\mathbf{v})\in{\cal S}(1)$ and suppose that
$\mathbf{e}=(e_{1},\ldots,e_{n})$ has $k\leq t_{n}$ nonzero entries. We split
$\mathbf{e}=(\mathbf{e}(1),\ldots,\mathbf{e}(L))$ into $L$ blocks as before.
Among the $3P_{n}$ bits in the first block $\mathbf{e}(1),$ we choose $2\leq
r\leq k$ of the bits in ${3P_{n}\choose r}$ ways and choose $k-r$ bits of the
remaining $n-3P_{n}$ bits in ${n-3P_{n}\choose k-r}$ ways. The binomial
coefficient ${3P_{n}\choose r}$ is nonzero since $r\leq k\leq t_{n}$ and
$P_{n}=\frac{n}{t_{n}^{2}\omega_{n}}\geq t_{n}$ (see (4.1)). Thus $\\#{\cal
S}(1)=\sum_{k=2}^{t_{n}}\sum_{r=2}^{k}{n-3P_{n}\choose k-r}{3P_{n}\choose
r}3^{k}$ and using $\sum_{k=0}^{r}{x\choose k-r}{y\choose r}={x+y\choose k}$
with $x=n-3P_{n}$ and $y=3P_{n},$ we get

$\\#{\cal S}(1)=\sum_{k=2}^{t_{n}}\left(1-S(n,k)\Delta\right){n\choose
k}3^{k},$ (4.1)

where $S(n,k)=\frac{{n-3P_{n}\choose k}}{{n\choose k}}$ and

$\Delta=1+\frac{{3P_{n}\choose 1}\cdot{n-3P_{n}\choose k-1}}{{n-3P_{n}\choose
k}}=1+\frac{3P_{n}k}{n-3P_{n}-k+1}\geq 1+\frac{3P_{n}k}{n}.$ (4.2)

We now evaluate $S(n,k)$ by letting $x=n-3P_{n}$ to get

$S(n,k)=\frac{{x\choose k}}{{n\choose
k}}=\frac{x(x-1)\ldots(x-k+1)}{n(n-1)\ldots(n-k+1)}=\left(\frac{x}{n}\right)^{k}\frac{L(x,k)}{L(n,k)},$
(4.3)

where $1\geq
L(x,k):=\prod_{i=0}^{k-1}\left(1-\frac{i}{x}\right)\geq\left(1-\frac{1}{x}\sum_{i=1}^{k-1}i\right)=1-\frac{k(k-1)}{2x}.$
The term $x=n-3P_{n}=n-\frac{3n}{t_{n}^{2}\omega_{n}}\geq
n-\frac{3n}{\omega_{n}}\geq\frac{n}{2}$ since $\omega_{n}\geq 6$ (see
statement of Theorem) and so

$1-\frac{k(k-1)}{2x}=1-\frac{k(k-1)}{2n}-\frac{3P_{n}k(k-1)}{2nx}\geq
1-\frac{k(k-1)}{2n}-\frac{3P_{n}k^{2}}{n^{2}}$

and

$L(x,k)\geq 1-\frac{k(k-1)}{2n}-\frac{3P_{n}k^{2}}{n^{2}}.$ (4.4)

To find an upper bound for $L(n,k),$ we use the fact that $1-y<e^{-y}$ for
$0<y<1$ to get
$\log{L(n,k)}\leq-\sum_{i=1}^{k-1}\frac{i}{n}=-\frac{k(k-1)}{2n}.$ But
$\frac{k(k-1)}{2n}\leq\frac{t_{n}^{2}}{2n}\leq\frac{1}{2}$ since
$t_{n}\leq\sqrt{n}$ (see statement of Theorem) and so using $e^{-z}\leq
1-z+z^{2}$ for $z<\frac{1}{2},$ we get

$L(n,k)\leq\exp\left(-\frac{k(k-1)}{2n}\right)\leq
1-\frac{k(k-1)}{2n}+\left(\frac{k(k-1)}{2n}\right)^{2}\leq
1-\frac{k(k-1)}{2n}+\frac{k^{4}}{n^{2}}.$ (4.5)

Using (4.5) and the lower bound (4.4) we have

$\frac{L(x,k)}{L(n,k)}-1\geq\frac{1-\frac{k(k-1)}{2n}-\frac{3P_{n}k^{2}}{n^{2}}}{1-\frac{k(k-1)}{2n}+\frac{k^{4}}{n^{2}}}-1=-\frac{3P_{n}k^{2}+k^{4}}{n^{2}}\left(1-\frac{k(k-1)}{2n}+\frac{k^{4}}{n^{2}}\right)^{-1}$
(4.6)

Since $k\leq t_{n}\leq\sqrt{n}$ (see statement of Theorem) we have

$1-\frac{k(k-1)}{2n}+\frac{k^{4}}{n^{2}}\geq
1-\frac{t_{n}(t_{n}-1)}{2n}\geq\frac{1}{2}$

and so we get from (4.6) that
$\frac{L(x,k)}{L(n,k)}-1\geq-2\frac{3P_{n}k^{2}+k^{4}}{n^{2}}.$ Substituting
this estimate into (4.3) and using $\left(1-\frac{3P_{n}}{n}\right)^{k}\geq
1-\frac{3P_{n}k}{n}$ we get

$S(n,k)\geq\left(1-\frac{3P_{n}k}{n}\right)\left(1-2\frac{3P_{n}k^{2}+k^{4}}{n^{2}}\right)\geq
1-\frac{3P_{n}k}{n}-2\frac{3P_{n}k^{2}+k^{4}}{n^{2}}.$ (4.7)

Using (4.7) and (4.2), we therefore get that $S(n,k)\cdot\Delta$ is bounded
below by

$1-\left(\frac{3P_{n}k}{n}\right)^{2}-2\frac{3P_{n}k^{2}+k^{4}}{n^{2}}\left(1+\frac{3P_{n}k}{n}\right).$

Since $k\leq t_{n}$ we have that
$\frac{P_{n}k}{n}\leq\frac{P_{n}t_{n}}{n}=\frac{1}{t_{n}\omega_{n}}\leq 1,$
because $\omega_{n}$ and $t_{n}$ are both at least one. Thus
$1+\frac{3P_{n}k}{n}\leq 4$ and so

$S(n,k)\Delta\geq
1-\frac{9P_{n}^{2}k^{2}}{n^{2}}-8\frac{3P_{n}k^{2}+k^{4}}{n^{2}}.$

Substituting this into (4.1) and using $k\leq t_{n}$ we get

$\\#{\cal S}(1)\leq\theta\cdot\sum_{k=2}^{t_{n}}{n\choose
k}3^{k}\leq\theta\cdot\\#{\cal E}_{n}(t_{n}),$

where
$\theta:=\frac{9P_{n}^{2}t_{n}^{2}}{n^{2}}+8\frac{3P_{n}t_{n}^{2}+t_{n}^{4}}{n^{2}}.$
The above estimate holds for all the sets ${\cal S}(l),1\leq l\leq L-1$ (see
discussion prior to (4.4)). Performing the same analysis with $3P_{n}+s$
instead of $3P_{n}$ we get

$\\#{\cal
S}(L)\leq\left(\frac{(3P_{n}+s)^{2}t_{n}^{2}}{n^{2}}+8\frac{(3P_{n}+s)t_{n}^{2}+t_{n}^{4}}{n^{2}}\right)(\\#{\cal
E}_{n}(t_{n}))$

and using the fact that $s\leq 3P_{n},$ we therefore get

$\\#{\cal
S}(l)\leq\left(\frac{(6P_{n})^{2}t_{n}^{2}}{n^{2}}+8\frac{6P_{n}t_{n}^{2}+t_{n}^{4}}{n^{2}}\right)(\\#{\cal
E}_{n}(t_{n}))\leq\frac{84P_{n}^{2}t_{n}^{2}+8t_{n}^{4}}{n^{2}}(\\#{\cal
E}_{n}(t_{n}))$

for all $1\leq l\leq L$