# Generalized Simple Streaming Codes
from MDS Codes

Vinayak Ramkumar, Myna Vajha, P. Vijay Kumar This research is supported by the
J C Bose National Fellowship JCB/2017/000017.  Department of Electrical
Communication Engineering, IISc Bangalore
{vinram93, mynaramana<EMAIL_ADDRESS>
###### Abstract

Streaming codes represent a packet-level FEC scheme for achieving reliable,
low-latency communication. In the literature on streaming codes, the commonly-
assumed Gilbert-Elliott channel model, is replaced by a more tractable, delay-
constrained, sliding-window (DCSW) channel model that can introduce either
random or burst erasures. The known streaming codes that are rate optimal over
the DCSW channel model are constructed by diagonally embedding a scalar block
code across successive packets. These code constructions have field size that
is quadratic in the delay parameter $\tau$ and have a somewhat complex
structure with an involved decoding procedure. This led to the introduction of
simple streaming (SS) codes in which diagonal embedding is replaced by
staggered-diagonal embedding (SDE). The SDE approach reduces the impact of a
burst of erasures and makes it possible to construct near-rate-optimal
streaming codes using Maximum Distance Separable (MDS) code having linear
field size. The present paper takes this development one step further, by
retaining the staggered-diagonal feature, but permitting the placement of more
than one code symbol from a given scalar codeword within each packet. These
generalized, simple streaming codes allow us to improve upon the rate of SS
codes, while retaining the simplicity of working with MDS codes. We
characterize the maximum code rate of streaming codes under a constraint on
the number of contiguous packets over which symbols of the underlying scalar
code are dispersed. Such a constraint leads to simplified code construction
and reduced-complexity decoding.

###### Index Terms:

Streaming codes, low-latency communication, packet-level FEC, MDS codes.

##  I Introduction

The availability of a reliable, low-latency communication system is key to
many envisaged 5G applications such as telesurgery, augmented and virtual
reality. Packet drops are commonplace in a communication network and can arise
due to congestion in the network, a weak wireless link or delayed packet
arrival. There is need for a communication scheme that can recover from such
packet losses in a timely fashion [1]. Packet duplication amounts to using a
repetition code and is clearly inefficient. Instantaneous-feedback-based
approaches such as ARQ incur an undesired round-trip delay. Streaming codes
represent a packet-level Forward Error Correction (FEC) scheme that is both
efficient and of low latency.

The study of streaming codes began in [2, 3] where packet-level FEC codes
capable of handling an erasure burst within a decoding-delay-window were
investigated. Here, encoding is carried out using a packet-expansion
framework, a feature that has been retained in the subsequent literature as
well, including the present paper. At any time $t$, if
$\underline{m}(t)\in\mathbb{F}_{q}^{k}$ is the message packet, then the coded
packet $\underline{x}(t)=\left[\underline{m}(t)^{T}\
\underline{p}(t)^{T}\right]^{T}\in\mathbb{F}_{q}^{n}$, where
$\underline{p}(t)\in\mathbb{F}_{q}^{n-k}$ represents parity. A decoding-delay
constraint of $\tau$, is construed as requiring that $\underline{m}(t)$ be
decoded by time $(t+\tau)$.

In [4], a delay-constrained sliding-window (DCSW) channel model was introduced
as a tractable deterministic approximation to the more realistic Gilbert-
Elliott erasure channel model [5, 6, 7, 8] that is capable of causing burst
and random erasures. An $(a,b,w,\tau)$ DCSW channel imposes a decoding-delay
constraint of $\tau$ and permits either at most $a$ random erasures or else, a
burst of $b$ erasures within any sliding window of size $w$ time slots, where
$0<a\leq b\leq\tau$. Without loss of generality we can set $w=\tau+1$ (see [4,
9]). A packet-level code will be referred to as an $(a,b,\tau)$ streaming code
if it can recover under decoding-delay $\tau$ from all the admissible erasure
patterns of the $(a,b,w=\tau+1,\tau)$ DCSW channel. An upper bound on the rate
of $(a,b,\tau)$ streaming code was derived in [4] and codes achieving this
rate for all possible parameters were first presented in [10, 11], thereby
characterizing the optimal rate
$R_{\text{opt}}(a,b,\tau)=\frac{\tau+1-a}{\tau+1-a+b}$. These initial rate-
optimal codes are over a finite field of size exponential in $\tau$.
Currently, the known [9, 12] rate-optimal streaming code constructions have
field size $q$ that is quadratic in the delay parameter $\tau$. In [13], rate-
optimal streaming codes with rate at least $\frac{1}{2}$ are constructed by
combining Maximum Distance Separable (MDS) codes and Maximum Rank Distance
codes, but this construction requires a large field size of $O((2a)^{\tau})$.
Streaming codes for variable size message packets are studied in [14]. Other
FEC schemes suitable for streaming setting can be found in [15, 16, 17, 18,
19, 20, 21, 22, 23].

Constructions of streaming codes were originally based on diagonal embedding
(DE) of a scalar block code $\mathcal{C}$ within the packet stream and these
codes have a complex structure that could make implementation challenging.
Under DE, every diagonal in the packet stream is a codeword in $\mathcal{C}$.
In [24], a variant of DE called staggered-diagonal embedding (SDE) is
introduced which reduces the impact of burst erasures.

(a) DE associated of an $[8,3]$ scalar code over $\mathbb{F}_{q}$, $q\geq 25$,
leading to a rate-optimal streaming code [9].

(b) SDE of a $[4,1]$ scalar MDS code leading to a SS code [24] having rate
$\frac{1}{4}$.

(c) GSDE of a $[10,3]$ scalar MDS code with dispersion vector $(3,1,1,1,1,3)$
leading to a GSS code of rate $\frac{3}{10}$.

Figure 1: Three constructions of $(a=3,b=5,\tau=5)$ streaming code. Each
column represents a coded packet and symbols bearing the same color belong to
the same scalar codeword. The black dotted box indicates a burst erasure of
$b=5$ packets and red line is the decoding deadline for packet $0$.

In SDE framework a coded packet can contain atmost one symbol from a codeword.
Dispersion span $N$ is defined as the number of contiguous packets over which
code symbols of the underlying scalar code $\mathcal{C}$ are dispersed. If
$N\leq\tau+1$, then decoding is simplified as each codeword in $\mathcal{C}$
can be block decoded. For example, in Fig. 1(b) the dispersion span is
$N=\tau+1=6$. Simple Streaming (SS) codes are constructed by SDE with
$N\leq\tau+1$ and the underlying scalar code $\mathcal{C}$ is chosen to be a
Reed-Solomon or other MDS code over a finite field $\mathbb{F}_{q}$ of size
$q=O(\tau)$. MDS codes are widely used in practice and low-complexity
algorithms and libraries for encoding and decoding MDS codes are available
[25, 26]. The maximum possible rate of a streaming code obtained through SDE
with $N\leq\tau+1$ is characterized in [24] and SS codes achieve it. In [27],
SDE with dispersion span larger than $\tau+1$ is explored.

In the present paper, we take the development of streaming codes one step
further by allowing within the SDE framework, the embedding of more than one
code symbol form the underlying scalar code $\mathcal{C}$ within a coded
packet. We refer to this form of embedding as Generalized SDE (GSDE). Under
the condition that the dispersion span $N$ satisfies $N\leq\tau+1$, we
characterize the maximum possible rate of an streaming code constructed via
GSDE. We show that the underlying scalar code $\mathcal{C}$ can always be
chosen to be an MDS code and hence these codes are simpler to implement. The
resultant streaming codes are referred to as Generalized Simple Streaming
(GSS) codes. Clearly, the rate of a GSS code can be no smaller than that of a
SS code and we characterize the improvement in code rate over than of an SS
code.

###  I-A Motivating Example: $(a=3,b=5,\tau=5)$

For $(a=3,b=5,\tau=5)$, the best possible rate of a streaming code is
$R_{opt}=\frac{3}{8}$. This rate can be achieved by DE of $[8,3]$ scalar code
presented in [9], see Fig. 1(a). A field of size $\geq 25$ is required and
this code is not easy to implement. The rate achievable using an SS code is
$R_{SS}=\frac{1}{4}$, obtained by SDE of $[4,1]$ MDS code as illustrated in
Fig. 1(b). We now describe the construction of an $(a=3,b=5,\tau=5)$ streaming
code constructed using GSDE of an $[n=10,k=3]$ MDS code $\mathcal{C}$ having
rate $\frac{3}{10}$, as shown in Fig. 1(c). Here the $n=10$ code symbols are
dispersed across $N=6$ consecutive packets. The embedding can be described
using dispersion vector $(3,1,1,1,1,3)$ which indicates the number of symbols
assigned to successive packets within which the symbols of the MDS codeword
are embedded. If $\underline{x}(t)=[x_{1}(t)\dots x_{10}(t)]^{T}$ denotes the
coded packet at time $t$, then
$\big{(}x_{1}(t),x_{2}(t),x_{3}(t),x_{4}(t+1),x_{5}(t+2),x_{6}(t+3),x_{7}(t+4),x_{8}(t+5),x_{9}(t+5),x_{10}(t+5)\big{)}$
is a codeword of $\mathcal{C}$, for all $t$. It can be seen that the erasure
of any $a=3$ packets or $b=5$ consecutive packets will result in the loss of
at most $(n-k)=7$ code symbols which is within the erasure-recovery capability
of the scalar MDS code. Since $N=\tau+1$ here, the decoding-delay constraint
is trivially satisfied.

Figure 2: Rate comparison between rate-optimal streaming codes in [11, 10, 9,
12], SS codes in [24] and GSS codes presented here.

This example illustrates the possibility of improving upon the rate of SS
codes by embedding more than one symbol of an MDS codeword within a single
packet. Fig. 2 shows the rate of various streaming code constructions for two
different parameter settings and the rate gain of GSS code over SS code can be
observed in it.

The GSDE framework is formally introduced in Section II and the construction
of a GSS code is linked to an interesting combinatorial problem. An upper
bound on the rate of streaming codes constructed through GSDE with
$N\leq\tau+1$ is derived in Section III. The streaming code constructions are
presented in Section IV and it is shown that the rate bound derived in Section
III is always achievable.

##  II Generalized Staggered Diagonal Embedding

Let $\mathcal{C}$ be an $[n,k]$ scalar linear code which is systematic, with
message symbols appearing as first $k$ code symbols. Let
$\underline{\Delta}=(n_{1},\dots,n_{N})$ be an $N-$tuple of non-negative
integers with $\sum\limits_{i=1}^{N}n_{i}=n$. With out loss of generality we
assume $n_{1}\neq 0$. We will refer to $\mathcal{C}$ as the base code and
$\underline{\Delta}$ as the dispersion vector. The parameter $N$ is referred
to as the dispersion span. Let the coded packet at time $t$ be denoted by
$\underline{x}(t)=[x_{1}(t),\dots,x_{n}(t)]^{T}$. Set
$m_{j}=\sum\limits_{i=1}^{j}n_{i}$ for all $j\in[1,N]$. We say that the
packet-level code is constructed by GSDE of base code $\mathcal{C}$ with
dispersion vector $\underline{\Delta}$ if for every $t$,

are code symbols of a codeword in $\mathcal{C}$. The packet-level code thus
obtained has rate $\frac{k}{n}$. Under the GSDE framework, symbols from a
codeword in the base code are dispersed across at most $N$ successive packets.
Consider a codeword $\underline{c}\in\mathcal{C}$ and let
$[t+1,t+2,\dots,t+N]$ be the time indices of the $N$ consecutive packets
across which this codeword is dispersed. Then, coded packet $(t+i)$ contains
$n_{i}$ code symbols of $\underline{c}$. The GSDE framework can be viewed as a
generalization of DE and SDE frameworks. For all $i\in[1,N]$, $n_{i}=1$ for
DE, whereas $n_{i}$ can take values only in $\\{0,1\\}$ for SDE. In GSDE, we
allow $n_{i}$ to be any non-negative integer.

In this paper we focus on the $N\leq\tau+1$ case. This restriction ensures
that it suffices to decode each scalar codeword in the conventional block-
decoding way, i.e., decode all underlying message symbols after receiving all
code symbols belonging to unerased packets. We note that since $n_{i}=0$ is
permitted for $i>1$, $N\leq\tau+1$ is equivalent to setting $N=\tau+1$.
Throughout the remainder of the paper, when we speak of GSDE, we mean GSDE
with $N=\tau+1$. We will now reduce the problem of streaming code construction
using GSDE with $N=\tau+1$ to a combinatorial problem.

######  Definition 1.

Given positive integers $a,b,\tau,n$ and $r$, we say that
$\underline{\Delta}=(n_{1},\dots,n_{\tau+1})$, $n_{i}\geq 0$, is an
$(a,b,\tau,n,r)-$dispersion vector if:

$\displaystyle\sum\limits_{i=1}^{\tau+1}n_{i}=n,$ (1)
$\displaystyle\sum\limits_{i\in A}n_{i}\leq r,~{}~{}~{}\forall
A\subseteq[1,\tau+1]~{}\text{with}~{}|A|=a,$ (2)
$\displaystyle\sum\limits_{i=j}^{j+b-1}n_{i}\leq r,~{}~{}~{}\forall
j\in[1,\tau+2-b],$ (3)

and additionally at least one inequality in (2) or (3) holds with equality. We
attach a rate $R$ to an $(a,b,\tau,n,r)$-dispersion vector, given by
$R=\frac{n-r}{n}$.

For example, $(3,1,1,1,1,3)$ is a $(3,5,5,10,7)-$dispersion vector. Now let
$\underline{\Delta}$ be an $(a,b,\tau,n,r)$-dispersion vector. Pick an
$[n,k=n-r]$ MDS code $\mathcal{C}$ and construct a packet-level code by GSDE
of $\mathcal{C}$ with dispersion vector $\underline{\Delta}$. We now argue
that the packet-level code thus constructed is an $(a,b,\tau)$ streaming code.
An $[n,n-r]$ MDS code can recover from erasure of any $r$ code symbols. If any
arbitrary $a$ coded packets are erased, then by (2) at most $r$ symbols of any
codeword of $\mathcal{C}$ are erased. If $b$ consecutive packets are erased,
then once again, no more than $r$ code symbols are lost from any codeword,
since (3) holds for $\underline{\Delta}$. Thus (2) guarantees recovery from
$a$ random erasures whereas (3) assures recovery in the presence of a burst of
$b$ erasures. The delay constraint is trivially met since symbols of a
codeword are spread across consecutive $\tau+1$ packets. Hence, we have the
following Lemma.

######  Lemma 1.

If there exists an $(a,b,\tau,n,r)$-dispersion vector $\underline{\Delta}$,
then an $(a,b,\tau)$ streaming code of rate $R=\frac{n-r}{n}$ can be
constructed through GSDE of $[n,n-r]$ MDS code with dispersion vector
$\underline{\Delta}$.

We complete the description of relation between dispersion vector and
streaming code construction through GSDE by establishing the converse.

######  Lemma 2.

If GSDE of an $[n,n-r]$ base code $\mathcal{C}$ with dispersion vector
$\underline{\Delta}$ results in an $(a,b,\tau)$ streaming code, then
$\underline{\Delta}$ is an $(a,b,\tau,n,s)$-dispersion vector, where $s\leq
r$.

Proof: An $[n,n-r]$ code can not recover from more than $r$ erasures. Hence,
from the $b$-burst erasure and $a$-random erasure correction property of an
$(a,b,\tau)$ streaming code, it follows that $\underline{\Delta}$ is an
$(a,b,\tau,n,\leq r)$-dispersion vector. $\Box$

Let $R_{\max}(a,b,\tau)$ denote the maximum rate possible of an $(a,b,\tau)$
streaming codes constructed through GSDE with $N=\tau+1$. It can be inferred
from Lemma 2 that the rate of a GSDE based streaming code can not exceed the
rate associated to the underlying dispersion vector. Thus, from Lemma 1 and
Lemma 2 it follows that $R_{\max}(a,b,\tau)$ can be determined by finding out
the maximum rate associated to an $(a,b,\tau,n,r)$-dispersion vector, i.e.,

In our search for maximum rate under GSDE, it suffices to restrict our
attention to MDS codes. This can be seen as follows. Let $\mathcal{C}$ be an
$[n,n-r]$ scalar code that is not an MDS code. Consider an $(a,b,\tau)$
streaming code of rate $\frac{n-r}{n}$ constructed by GSDE of $\mathcal{C}$
using dispersion vector $\underline{\Delta}$. By Lemma 2, $\underline{\Delta}$
is necessarily an $(a,b,\tau,n,s)$-dispersion vector for some $s\leq r$. The
GSDE of an $[n,n-s]$ MDS code with dispersion vector $\underline{\Delta}$ will
result in an $(a,b,\tau)$ streaming code of rate
$\frac{n-s}{n}\geq\frac{n-r}{n}$. Thus it is not possible to outperform an MDS
base code in terms of rate.

We next state our main result, which is the characterization of the maximum
possible rate of streaming codes constructed via GSDE and with $N=\tau+1$.

######  Theorem 3.

Let $\tau+1=mb+\delta$, where $m\in\mathbb{N},\delta\in[0,b-1]$. Then,
$R_{\max}(a,b,\tau)=\frac{m-1+\mu}{m+\mu}$ where

$\displaystyle\mu=\begin{cases}\frac{b-a+m\delta}{(m+1)b-a}~{}~{}~{}\text{if}~{}~{}~{}a>(m+1)\delta>0,\\\
\ \\\ \frac{\min\\{\delta,a\\}}{a}~{}~{}~{}\text{else}.\end{cases}$

The rate upper bound, corresponding to the theorem above, is derived in
Section III. Constructions of dispersion vectors that achieve this rate are
presented in Section IV.

##  III Rate Upper Bound

We establish the rate upper bound separately for two regimes, in Theorems 4
and 6 respectively.

######  Theorem 4.

Let $\tau+1=mb+\delta$, where $m\in\mathbb{N},\delta\in[0,b-1]$. If
$a\leq(m+1)\delta$ or $\delta=0$, then $R_{\max}(a,b,\tau)\leq
R_{SS}(a,b,\tau)=\frac{m-1+\frac{\min\\{\delta,a\\}}{a}}{m+\frac{\min\\{\delta,a\\}}{a}}$.

Proof: Let $\underline{\Delta}=(n_{1},\dots,n_{\tau+1})$ be an
$(a,b,\tau,n,r)$-dispersion vector with rate $R_{\max}(a,b,\tau)$. Suppose
$\delta\geq a$. Since $\underline{\Delta}$ obeys (3) we have

$\displaystyle\sum\limits_{i=jb+1}^{(j+1)b}n_{i}\leq r,\forall
j\in[0,m-1]~{}~{}\text{and}~{}~{}\sum\limits_{i=mb+1}^{mb+\delta}n_{i}\leq r.$

Hence $n=\sum\limits_{i=1}^{\tau+1}n_{i}\leq(m+1)r$ and therefore
$R_{\max}(a,b,\tau)=\frac{n-r}{n}\leq\frac{m}{m+1}=R_{SS}(a,b,\tau)$ when
$\delta\geq a$. Proof for remaining parameter ranges can be found in Appendix
-A. $\Box$

To derive rate upper bound for the case $a>(m+1)\delta>0$, we first show the
existence of a maximum-rate dispersion vector having a specific structure.

######  Lemma 5.

For any valid $\\{a,b,\tau\\}$, there exists an $(a,b,\tau,n,r)$-dispersion
vector $\underline{\Delta}=(n_{1},\dots,n_{\tau+1})$ of rate
$R_{\max}(a,b,\tau)$ with $\sum\limits_{i=t_{0}}^{t_{0}+b-1}n_{i}=r$ for some
$t_{0}\in[1,\tau+2-b]$.

Proof: See Appendix -B. $\Box$

From Lemma 5, it can be inferred that in order to determine
$R_{\max}(a,b,\tau)$ one needs to look at only the $(a,b,\tau,n,r)$-dispersion
vectors for which (3) is satisfied with equality for at least one case.

######  Theorem 6.

Let $\tau+1=mb+\delta$, where $m\in\mathbb{N},\delta\in[0,b-1]$. If
$\delta\neq 0$ and $a>(m+1)\delta$, then
$R_{\max}(a,b,\tau)\leq\frac{m-1+\theta}{m+\theta}$, where
$\theta=\frac{b-a+m\delta}{(m+1)b-a}$.

Proof: Let $q=a-(m+1)\delta$ and $\underline{\Delta}=(n_{1},\dots,n_{\tau+1})$
be an $(a,b,\tau,n,r)$-dispersion vector of rate $R_{\max}(a,b,\tau)$ with
$\sum\limits_{i=t_{0}}^{t_{0}+b-1}n_{i}=r$. From Lemma 5 such a dispersion
vector always exists. Let $T=[t_{0},t_{0}+b-1]$ and

(4)

Let $u_{0}$,$v_{0}$ and $\epsilon_{0}$ be such that

$\displaystyle
x=\sum\limits_{i=u_{0}b+1}^{u_{0}b+\epsilon_{0}}n_{i}+\sum\limits_{i=v_{0}b+\epsilon_{0}+1}^{v_{0}b+\delta}n_{i}.$
(5)

Since $\underline{\Delta}$ satisfies (3), we have

$\displaystyle\sum\limits_{i=jb+1}^{(j+1)b}n_{i}\leq r,~{}~{}~{}\forall
j\in[0,u_{0}-1],$ (6)
$\displaystyle\sum\limits_{i=jb+\epsilon_{0}+1}^{(j+1)b+\epsilon_{0}}n_{i}\leq
r,~{}~{}~{}\forall j\in[u_{0},v_{0}-1],$ (7)
$\displaystyle\sum\limits_{i=jb+\delta+1}^{(j+1)b+\delta}n_{i}\leq
r,~{}~{}~{}\forall j\in[v_{0},m-1].$ (8)

Adding (5), (6), (7) and (8) gives an upper bound on $n$,

$\displaystyle n=\sum\limits_{i=1}^{\tau+1}n_{i}\leq mr+x.$ (9)

We will now prove an upper bound on $\frac{x}{r}$ to derive an upper bound on
the rate. Let $A_{j}=[jb+1,jb+\delta]$ for $j\in[0,m]$ and
$J=T\cap\left(\cup_{j=0}^{m}A_{j}\right)$. Define $\hat{A}$ to be the set of
indices of $q$ largest elements from set $T\setminus J$. It is possible to
pick $q$ elements from $T\setminus J$ as $|J|=\delta$ and $|T\setminus
J|=b-\delta\geq a-(m+1)\delta=q$. We construct a set $A$ comprising of $a$
elements given by $A=\cup_{j=0}^{m}A_{j}\cup\hat{A}$. Note that the sets
$A_{j}$’s and $\hat{A}$ are all disjoint by definition. This implies that:

$\displaystyle\sum\limits_{i\in A}n_{i}=\sum\limits_{j=0}^{m}\sum\limits_{i\in
A_{j}}n_{i}+\sum\limits_{i\in\hat{A}}n_{i}.$ (10)

Let $w\in[0,m-1]$ such that $wb<t_{0}\leq(w+1)b$, then $J=T\cap(A_{w}\cup
A_{w+1})$. Let us define:

$\displaystyle\sum\limits_{i\in J}n_{i}=s.$ (11)

By the definition of $x$ in (4):

$\displaystyle\sum\limits_{i\in\left(A_{w}\cup A_{w+1}\right)\setminus
J}n_{i}\geq x~{}~{}\text{and}~{}~{}\sum\limits_{i\in A_{j}}n_{i}\geq
x,~{}\forall j\in[0,m].$ (12)

As we pick $q$ largest element from $T\setminus J$ to get $\hat{A}$ it follows
that:

$\displaystyle\sum\limits_{i\in\hat{A}}n_{i}\geq\frac{(r-s)}{b-\delta}q.$ (13)

By substituting (11), (12), (2) in (10) it follows that:

$\displaystyle r$ $\displaystyle\geq$
$\displaystyle(m-1)x+x+s+\frac{r-s}{b-\delta}q.$ (14)

We will now show that $s\geq x$. From equation (3) we have

$\displaystyle\sum\limits_{i\in T\setminus J}n_{i}+\sum\limits_{i\in
A_{w}}n_{i}$ $\displaystyle\leq$ $\displaystyle r,$ $\displaystyle(r-s)+x$
$\displaystyle\leq$ $\displaystyle r\text{ from equations \eqref{Eq:Delta},
\eqref{Eq:Delta+}}.$

Therefore $s\geq x$. Substituting this in equation (14) we get

$\frac{x}{r}\leq\frac{b-\delta-q}{(m+1)(b-\delta)-q}=\frac{b-a+m\delta}{(m+1)b-a}=\theta.$

Now using (9), we have $\frac{n}{r}\leq m+\frac{x}{r}\leq m+\theta.$ Hence
$R_{\max}(a,b,\tau)=\frac{n-r}{n}\leq\frac{m-1+\theta}{m+\theta}$. $\Box$

##  IV Constructions

In this section we present two dispersion vector constructions. As explained
in Section II, streaming codes can be constructed by GSDE of appropriate MDS
codes guided by these dispersion vectors.

######  Construction 7.

Let $\tau+1=mb+\delta$, where $m\in\mathbb{N}$, $0\leq\delta<b$. We construct
dispersion vector $(n_{1},\dots,n_{\tau+1})$ as:

$\displaystyle n_{i}=\begin{cases}1~{}~{}~{}\text{if}~{}~{}~{}i\mod
b\in[1,a],\\\ 0~{}~{}~{}\text{otherwise}.\end{cases}$ (15)

######  Theorem 8.

The dispersion vector defined by (15) is an $(a,b,\tau,n,r)$ dispersion vector
with $n=ma+\min\\{a,\delta\\}$ and $r=a$.

Proof: Clearly, $\sum\limits_{i=1}^{\tau+1}n_{i}=ma+\min\\{a,\delta\\}$. Note
that $n_{i}\leq 1$ for all $i\in[1,\tau+1]$. Hence for any
$A\subseteq[1,\tau+1]$ with $|A|=a$, $\sum\limits_{i\in A}n_{i}\leq a$. It can
also be seen that $\sum\limits_{i=j}^{j+b-1}n_{i}=a$ for all
$j\in[1,\tau+2-b]$. $\Box$

The rate of above dispersion vector is
$R=\frac{(m-1)a+\min\\{a,\delta\\}}{ma+\min\\{a,\delta\\}}$, which matches
with the rate upper bound in Theorem 4 when $\delta=0$ or $a\leq(m+1)\delta$.
Hence we have the following corollary.

######  Corollary 9.

If $\delta=0$ or $a\leq(m+1)\delta$, then
$R_{\max}(a,b,\tau)=R_{SS}(a,b,\tau)=\frac{(m-1)a+\min\\{a,\delta\\}}{ma+\min\\{a,\delta\\}}$.

The GSDE of suitable MDS code with above dispersion vector results in SS codes
presented in [24]. Since all entries of dispersion vector belong to
$\\{0,1\\}$ here, GSDE is same as SDE for this case. For
$\\{a=3,b=5,\tau=5\\}$ example, this dispersion vector construction gives
$(1,1,1,0,0,1)$, which is a $(3,5,5,4,3)-$dispersion vector. Now GSDE of a
$[4,1]$ MDS code with $(1,1,1,0,0,1)$ leads to $(a=3,b=5,\tau=5)$ SS code of
rate $\frac{1}{4}$ shown in Fig. 1(b). Now we present a dispersion vector
whose rate is same as the rate upper bound in Theorem 6 for $a>(m+1)\delta>0$
case.

######  Construction 10.

Let $\tau+1=mb+\delta$ with $m\in\mathbb{N}$, $0\leq\delta<b$. Set
$t=\frac{lcm(b-a,m)}{b-a}$ and $\gamma=t\left(1+\frac{b-a}{m}\right)$. We note
that $t$ and $\gamma$ are always non-negative integers. Now we construct
dispersion vector $(n_{1},\dots,n_{\tau+1})$ as:

$\displaystyle n_{i}=\begin{cases}\gamma~{}~{}~{}\text{if}~{}~{}~{}i\mod
b=1,\\\ t~{}~{}~{}\text{otherwise}.\end{cases}$ (16)

######  Theorem 11.

If $\delta\neq 0$ and $a>(m+1)\delta$, then the dispersion vector defined in
(16) is an $(a,b,\tau,n,r)$-dispersion vector with
$n=t\left(mb+\frac{(m+1)(b-a)}{m}+\delta\right)$ and
$r=t\left(b+\frac{b-a}{m}\right)$.

Proof: By definition
$\sum\limits_{i=1}^{\tau+1}n_{i}=(m+1)\gamma+(\tau-m)t=t\left(mb+\frac{(m+1)(b-a)}{m}+\delta\right)=n$.
Pick an $a-$ element subset $\tilde{A}\subseteq[1,\tau+1]$ such that
$jb+1\in\tilde{A}$ for all $j\in[0,m]$. From $b\geq a$, it follows that
$\gamma\geq t$. Then it can be easily seen that
$\sum\limits_{i\in\tilde{A}}n_{i}\geq\sum\limits_{i\in A}n_{i}$, for all
$A\subseteq[1,\tau+1]$ with $|A|=a$. Now from the definition of $\tilde{A}$ we
have
$\sum\limits_{i\in\tilde{A}}n_{i}=(m+1)\gamma+(a-m-1)t=t\left(b+\frac{b-a}{m}\right)=r$.
Thus, (2) holds for all $A\subseteq[1,\tau+1]$ with $|A|=a$. Additionally, it
holds with equality for some cases. For any $j\in[1,\tau+2-b]$, it is easy to
see that
$\sum\limits_{i=j}^{j+b-1}n_{i}=\gamma+(b-1)t=t\left(b+\frac{b-a}{m}\right)=r$.
Hence (3) holds with equality for all the cases. $\Box$

For $a>(m+1)\delta>0$, the dispersion vector defined in (16) has rate

$\displaystyle R$ $\displaystyle=$
$\displaystyle\frac{t\left((m-1)(b+\frac{b-a}{m})+\frac{b-a}{m}+\delta\right)}{t\left(m(b+\frac{b-a}{m})+\frac{b-a}{m}+\delta\right)}=\frac{m-1+\theta}{m+\theta},$

where $\theta=\frac{b-a+m\delta}{(m+1)b-a}$. This rate matches with the upper
bound in Theorem 6, resulting in the corollary given below and thereby
completing the proof of Theorem 3.

######  Corollary 12.

Suppose $\delta\neq 0$ and $a>(m+1)\delta$. Then
$R_{\max}(a,b,\tau)=\frac{m-1+\theta}{m+\theta}$ where
$\theta=\frac{b-a+m\delta}{(m+1)b-a}$.

If $\delta=0$ or $a\leq(m+1)\delta$, then GSS code is defined to be same as SS
code. For $a>(m+1)\delta>0$, GSS code is obtained through GSDE of appropriate
MDS code with dispersion vector defined by (16). Thus, rate of GSS code
$R_{GSS}(a,b,\tau)=R_{max}(a,b,\tau)$. Consider $\\{a=3,b=5,\tau=5\\}$
example. The dispersion vector given by (16) for this case is $(3,1,1,1,1,3)$,
which is a $(3,5,5,10,7)-$dispersion vector. The resultant $(a=3,b=5,\tau=5)$
GSS code of rate $\frac{3}{10}$ is given in Fig. 1(c).

If $b>a>(m+1)\delta>0$, then $\frac{b-a+m\delta}{(m+1)b-a}>\frac{\delta}{a}$
and $R_{GSS}(a,b,\tau)=R_{\max}(a,b,\tau)>R_{SS}(a,b,\tau)$. It follows that
GSS codes have rate strictly greater than rate of SS codes if and only if
$b>a>(m+1)\delta>0$. Table I presents some parameters for which GSS code gives
rate improvement over SS code. The table also shows field size requirement for
those parameters. We note that $n\leq\frac{\tau^{2}}{b}+(\tau+1)b$ for GSS
codes and hence a finite field of size $\geq\frac{\tau^{2}}{b}+(\tau+1)b$ is
sufficient in the worst-case.

TABLE I: $R_{opt}$ is the optimal rate of an $\\{a,b,\tau\\}$ code. The field size $q_{opt}$ corresponds to the rate-optimal code construction in [9]. $R_{\text{\tiny SS}},\ q_{\text{\tiny SS}},\ R_{\text{\tiny GSS}},\ q_{\text{\tiny GSS}}$ are the respective rates and field size associated to an SS code and GSS code.  $(a,b,\tau)$ | $R_{opt}$ | $q_{opt}$ | $R_{\text{\tiny SS}}$ | $q_{\text{\tiny SS}}$ | $R_{\text{\tiny GSS}}$ | $q_{\text{\tiny GSS}}$
---|---|---|---|---|---|---
(3,5,5) | 0.375 | 25 | 0.25 | 3 | 0.3 | 9
(4,5,10) | 0.583 | 100 | 0.556 | 8 | 0.56 | 24
(5,8,16) | 0.6 | 256 | 0.545 | 10 | 0.558 | 42
(9,15,15) | 0.318 | 225 | 0.1 | 9 | 0.25 | 27
(10,18,20) | 0.379 | 400 | 0.231 | 12 | 0.297 | 36

##  V Conclusion

Simple streaming codes are generalized here by permitting each packet to
contain more than one code symbol from the underlying scalar code. This
results in an increase in code rate that is quantified. The generalized
streaming codes presented in this paper use MDS code as the underlying scalar
code along with conventional block decoding and hence are simpler to implement
than rate-optimal streaming codes known in literature.

## References

  * [1] G. Americas, “5G Services Innovation,” 2019.
  * [2] E. Martinian and C. W. Sundberg, “Burst erasure correction codes with low decoding delay,” _IEEE Trans. Inf. Theory_ , vol. 50, no. 10, pp. 2494–2502, 2004.
  * [3] E. Martinian and M. Trott, “Delay-Optimal Burst Erasure Code Construction,” in _Proc. Int. Symp. Inf. Theory_. IEEE, 2007, pp. 1006–1010.
  * [4] A. Badr, P. Patil, A. Khisti, W. Tan, and J. G. Apostolopoulos, “Layered Constructions for Low-Delay Streaming Codes,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 1, pp. 111–141, 2017.
  * [5] E. N. Gilbert, “Capacity of a burst-noise channel,” _Bell system technical journal_ , vol. 39, no. 5, pp. 1253–1265, 1960.
  * [6] E. O. Elliott, “Estimates of error rates for codes on burst-noise channels,” _The Bell System Technical Journal_ , vol. 42, no. 5, pp. 1977–1997, 1963\.
  * [7] G. Haßlinger and O. Hohlfeld, “The Gilbert-Elliott model for packet loss in real time services on the internet,” in _Proc. 14th GI/ITG Conference on Measurement, Modelling and Evaluation of Computer and Communication Systems_. VDE Verlag, 2008, pp. 269–286.
  * [8] M. Vajha, V. Ramkumar, M. Jhamtani, and P. V. Kumar, “On sliding window approximation of gilbert-elliott channel for delay constrained setting,” _CoRR_ , vol. abs/2005.06921, 2020.
  * [9] M. N. Krishnan, D. Shukla, and P. V. Kumar, “Low Field-size, Rate-Optimal Streaming Codes for Channels With Burst and Random Erasures,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 8, pp. 4869–4891, 2020.
  * [10] S. L. Fong, A. Khisti, B. Li, W. Tan, X. Zhu, and J. G. Apostolopoulos, “Optimal streaming codes for channels with burst and arbitrary erasures,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 7, pp. 4274–4292, 2019.
  * [11] M. N. Krishnan and P. V. Kumar, “Rate-Optimal Streaming Codes for Channels with Burst and Isolated Erasures,” in _Proc. Int. Symp. Inf. Theory_. IEEE, 2018, pp. 1809–1813.
  * [12] E. Domanovitz, S. L. Fong, and A. Khisti, “An explicit rate-optimal streaming code for channels with burst and arbitrary erasures,” pp. 1–5, 2019.
  * [13] D. Dudzicz, S. L. Fong, and A. Khisti, “An explicit construction of optimal streaming codes for channels with burst and arbitrary erasures,” _IEEE Trans. Commun._ , vol. 68, no. 1, pp. 12–25, 2020.
  * [14] M. Rudow and K. V. Rashmi, “Streaming codes for variable-size arrivals,” in _56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, Monticello, IL, USA, October 2-5, 2018_ , 2018, pp. 733–740.
  * [15] N. Adler and Y. Cassuto, “Burst-erasure correcting codes with optimal average delay,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 5, pp. 2848–2865, 2017\.
  * [16] D. Leong and T. Ho, “Erasure coding for real-time streaming,” in _Proceedings of the 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, USA, July 1-6, 2012_ , 2012, pp. 289–293.
  * [17] D. Leong, A. Qureshi, and T. Ho, “On coding for real-time streaming under packet erasures,” in _Proceedings of the 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, July 7-12, 2013_ , 2013, pp. 1012–1016.
  * [18] D. Malak, M. Médard, and E. M. Yeh, “Tiny codes for guaranteeable delay,” _IEEE Journal on Selected Areas in Communications_ , vol. 37, no. 4, pp. 809–825, 2019.
  * [19] S. Yang and R. W. Yeung, “Batched sparse codes,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 9, pp. 5322–5346, 2014.
  * [20] A. Shokrollahi, “Raptor codes,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 6, pp. 2551–2567, 2006.
  * [21] A. R. Iyengar, P. H. Siegel, R. L. Urbanke, and J. K. Wolf, “Windowed decoding of spatially coupled codes,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 4, pp. 2277–2292, 2013.
  * [22] A. J. Feltström and K. S. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix,” _IEEE Trans. Inf. Theory_ , vol. 45, no. 6, pp. 2181–2191, 1999.
  * [23] S. C. Draper and A. Khisti, “Truncated tree codes for streaming data: Infinite-memory reliability using finite memory,” in _8th International Symposium on Wireless Communication Systems, ISWCS 2011, Aachen, Germany, November 6-9, 2011_ , 2011, pp. 136–140.
  * [24] M. N. Krishnan, V. Ramkumar, M. Vajha, and P. V. Kumar, “Simple streaming codes for reliable, low-latency communication,” _IEEE Commun. Lett._ , vol. 24, no. 2, pp. 249–253, 2020.
  * [25] J. S. Plank and K. M. Greenan, “Jerasure: A library in C facilitating erasure coding for storage applications–version 2.0,” Technical Report UT-EECS-14-721, University of Tennessee, Tech. Rep., 2014.
  * [26] “Intel Intelligent Storage Acceleration Library,” https://software.intel.com/content/www/us/en/develop/tools/isa-l.html.
  * [27] V. Ramkumar, M. Vajha, M. N. Krishnan, and P. V. Kumar, “Staggered diagonal embedding based linear field size streaming codes,” in _IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, CA, USA, June 21-26, 2020_ , 2020, pp. 503–508.

###  -A Proof of Theorem 4

Let $\underline{\Delta}=(n_{1},\dots,n_{\tau+1})$ be an
$(a,b,\tau,n,r)$-dispersion vector with rate $R_{\max}(a,b,\tau)$. Suppose
$\delta<a\leq(m+1)\delta$. Let $a=p\delta+q$ where $p\in\mathbb{N},0\leq
q<\delta$. Let us set

$\displaystyle
x=\min\left\\{\sum\limits_{i=jb+1}^{jb+\delta}n_{i}~{}\Big{|}~{}j\in[0,m]\right\\}.$
(17)

We first obtain an upper bound on $n$ in terms of $r$ and $x$. Let $j_{\tiny
0}\in[0,m]$, such that

$\displaystyle x=\sum\limits_{i=j_{\tiny 0}b+1}^{j_{\tiny 0}b+\delta}n_{i}.$
(18)

Since $\underline{\Delta}$ satisfies (3),

$\displaystyle\sum\limits_{i=jb+1}^{(j+1)b}n_{i}\leq r,~{}~{}~{}\forall
j\in[0,j_{\tiny 0}-1],$ (19)
$\displaystyle\sum\limits_{i=jb+\delta+1}^{(j+1)b+\delta}n_{i}\leq
r~{}~{}~{}\forall j\in[j_{\tiny 0},m-1].$ (20)

Adding (18), (19) and (20),

$\displaystyle n=\sum\limits_{i=1}^{\tau+1}n_{i}\leq mr+x.$ (21)

Now we derive an upper bound on $\frac{x}{r}$ and then use it to obtain the
rate upper bound. Define $A_{j}=[jb+1,jb+\delta]$ for all $j\in[0,m]$. From
(17) we get

$\displaystyle\sum\limits_{i\in A_{j}}n_{i}\geq x,~{}~{}~{}\forall j\in[0,m].$
(22)

Let $\hat{A}$ be the set of indices of $q$ largest elements from
$\\{n_{i}~{}\mid~{}i\in[1,\delta]\\}$. Then by pigeonhole principle,

$\displaystyle\sum\limits_{i\in\hat{A}}n_{i}\geq\frac{qx}{\delta}.$ (23)

Let us define
$A=\begin{cases}\bigcup\limits_{j=0}^{i=m}A_{j}~{}~{}~{}\text{if}~{}a=(m+1)\delta,\\\
\bigcup\limits_{j=1}^{i=p}A_{j}\bigcup\hat{A}~{}~{}~{}\text{otherwise}.\end{cases}$

Note that $|A|=a$ in both cases since $A_{j_{1}}\cap A_{j_{2}}=\phi$ for any
two distinct $j_{1},j_{2}\in[0,m]$ and $\hat{A}\cap A_{j}=\phi$ for all
$j\in[1,m]$. If $a=(m+1)\delta$, it follows from (2) and (22) that

$\displaystyle r\geq\sum\limits_{i\in
A}n_{i}\geq(m+1)x\implies\frac{x}{r}\leq\frac{1}{(m+1)}=\frac{\delta}{a}.$

Now for $\delta<a<(m+1)\delta$, using (19), (22) and (23), we obtain

$\displaystyle r\geq\sum\limits_{i\in A}n_{i}\geq
px+\frac{qx}{\delta}\implies\frac{x}{r}\leq\frac{\delta}{p\delta+q}=\frac{\delta}{a}.$

From (21) we get

$\displaystyle\frac{n}{r}\leq m+\frac{x}{r}\leq m+\frac{\delta}{a}.$

Hence when $\delta<a\leq(m+1)\delta$,

$\displaystyle
R_{\max}(a,b,\tau)=\frac{n-r}{n}\leq\frac{m-1+\frac{\delta}{a}}{m+\frac{\delta}{a}}=R_{SS}(a,b,\tau).$

Now consider the $\delta=0$ case. Since $\underline{\Delta}$ satisfies (3),
$\sum\limits_{i=jb+1}^{(j+1)b}n_{i}\leq r,\forall j\in[0,m-1]$. Here
$\tau+1=mb$ and hence we have

$n=\sum\limits_{i=1}^{\tau+1}n_{i}\leq mr.$

Therefore,

$\displaystyle R_{\max}(a,b,\tau)\leq\frac{m-1}{m}=R_{SS}(a,b,\tau)$

when $\delta=0$.

###  -B Proof of Lemma 5

The Lemma 5 follows from repeated application of Lemma 13.

######  Lemma 13.

Let $\underline{\nu}=(n_{1},\dots,n_{\tau+1})$ be an
$(a,b,\tau,n,r)-$dispersion vector with rate $R_{max}(a,b,\tau)$. Define
$s=\max\left\\{\sum\limits_{i=j}^{j+b-1}n_{i}~{}\Big{|}~{}j\in[1,\tau+2-b]\right\\}$
and suppose $s<r$ . Then there exists an $(a,b,\tau,n,r)-$dispersion vector
$\underline{\mu}=(m_{1},\dots,m_{\tau+1})$ with
$\sum\limits_{i=j}^{j+b-1}m_{i}=s+1$ for some $j\in[1,\tau+2-b]$.

Proof: It is always possible to pick a subset $I\subseteq[1,\tau+1]$ with
$|I|=a$ such that $n_{i}\geq\max\\{n_{j}~{}\mid~{}j\in[1,\tau+1]\setminus
I\\}$ for all $i\in I$. Now suppose $\sum\limits_{i\in I}n_{i}<r$. Then, it
follows that $\sum\limits_{i\in A}n_{i}<r$, for all $A\subseteq[1,\tau+1]$
with $|A|=a$. Since $s<r$, $(n_{1},\dots,n_{\tau+1})$ doesn’t satisfy (3) with
equality for any $j\in[1,\tau+2-b]$. This contradicts the fact that
$(n_{1},\dots,n_{\tau+1})$ is an $\\{a,b,\tau,n,r\\}-$dispersion vector.
Hence,

$\displaystyle\sum\limits_{i\in I}n_{i}=r.$ (24)

Define $z=\min\\{n_{i}~{}\mid~{}i\in I\\}$ and $J=\\{i\in I~{}|~{}n_{i}>z\\}$.
Now we will argue that $n_{i}=z$ for all $i\in[1,\tau+1]\setminus J$. Let
$p\in[1,\tau+1]\setminus J$ with $n_{p}<z$. Assign $n^{\prime}_{p}=n_{p}+1$
and $n^{\prime}_{i}=n_{i},\forall i\in[1,\tau+1]\setminus\\{p\\}$. For any
$j\in[1,\tau+2-b]$,

$\displaystyle\sum\limits_{i=j}^{j+b-1}n^{\prime}_{i}\leq\sum\limits_{i=j}^{j+b-1}n_{i}+1\leq
r.$

Since $n^{\prime}_{p}\leq z$,

$\displaystyle\sum\limits_{i\in A}n^{\prime}_{i}\leq\sum\limits_{i\in
I}n_{i}=r$

for all $A\subseteq[1,\tau+1]$ with $|A|=a$. We also have

$\displaystyle\sum\limits_{i=1}^{\tau+1}n^{\prime}_{i}=\sum\limits_{i=1}^{\tau+1}n_{i}+1=n+1.$

Therefore $(n^{\prime}_{1},\dots,n^{\prime}_{\tau+1})$ is an
$(a,b,\tau,n+1,r)-$dispersion vector. This dispersion vector has rate
$\frac{n+1-r}{n+1}>\frac{n-r}{n}=R_{max}(a,b,\tau)$, which is a contradiction.
Hence,

$\displaystyle n_{i}=z,~{}~{}~{}\forall i\in[1,\tau+1]\setminus J.$ (25)

Suppose $J=\phi$, resulting in $n_{i}=z$ for all $i\in[1,\tau+1]$. Then, from
(24) we have $r=az$. It follows from statement of Lemma that $s=bz<r=az$.
Since $z\geq 0$ and $b\geq a$, this results in a contradiction. Therefore $J$
is non-empty. We note that $1\leq|J|\leq|I|-1<a$ and $n_{i}=z,~{}\forall i\in
I\setminus J$. From (24), we get

$\displaystyle\sum\limits_{i\in J}n_{i}+(a-|J|)z=r.$ (26)

Let $\sum\limits_{i=t}^{t+b-1}n_{i}=s$ and $T=[t,t+b-1]$. Since $|T|=b$ and
$|J|<a$, it follows from (25) that there exists some $q\in T\setminus J$ with
$n_{q}=z$. If $J\subseteq T$, then by (25) and (26) we have

$\displaystyle\sum\limits_{i=t}^{t+b-1}n_{i}=\sum\limits_{i\in
J}n_{i}+(b-|J|)z\geq r>s,$

which is not possible. Hence, there exists some $p\in J\setminus T$ such that
$n_{p}>z$. With this notation we define the new dispersion vector
$\underline{\mu}=(m_{1},\dots,m_{\tau+1})$ as:

$\displaystyle m_{p}=n_{p}-1,~{}~{}~{}m_{q}=n_{q}+1~{}~{}~{}\text{and}$
$\displaystyle m_{i}=n_{i},~{}~{}~{}\forall i\in[1,\tau+1]\setminus\\{p,q\\}.$

#### Claim 1

$\underline{\mu}$ is an $(a,b,\tau,n,r)-$dispersion vector with rate
$R_{max}(a,b,\tau)$.

#### Proof of Claim 1

Since $m_{p}=n_{p}-1\geq z\geq 0$, $\underline{\mu}$ is a $(\tau+1)$-tuple of
non-negative integers. Now from definition of $\underline{\mu}$ it follows
that

$\displaystyle\sum\limits_{i=1}^{\tau+1}m_{i}=\sum\limits_{i=1}^{\tau+1}n_{i}=n,$

thus satisfying (1). For all $j\in[1,\tau+2-b]$,

$\displaystyle\sum\limits_{i=j}^{j+b-1}m_{i}\leq\sum\limits_{i=j}^{j+b-1}n_{i}+1\leq
s+1\leq r.$

Thus $\underline{\mu}$ satisfies (3).

If $\sum\limits_{i\in A}n_{i}=r$ for $A\subseteq[1,\tau+1]$ with $|A|=a$, then
$J\subseteq A$. Otherwise, (2) is violated for
$\underline{\nu}=(n_{1},\dots,n_{\tau+1})$. It can be easily seen that

$\displaystyle\sum\limits_{i\in J}m_{i}=\sum\limits_{i\in J}n_{i}-1$
$\displaystyle~{}~{}~{}\text{and}~{}~{}~{}\sum\limits_{i\in
B}m_{i}\leq\sum\limits_{i\in B}n_{i}+1,~{}\forall B\subset[1,\tau+1].$

For all $A\subseteq[1,\tau+1]$ such that $|A|=a$ and $J\subseteq A$,

$\displaystyle\sum\limits_{i\in A}m_{i}$ $\displaystyle=$
$\displaystyle\sum\limits_{i\in J}m_{i}+\sum\limits_{i\in A\setminus J}m_{i}$
$\displaystyle\leq$ $\displaystyle\sum\limits_{i\in
J}n_{i}-1+\sum\limits_{i\in A\setminus J}n_{i}+1$ $\displaystyle\leq$
$\displaystyle\sum\limits_{i\in J}n_{i}-1+(a-|J|)z+1=r.$

For $A\subseteq[1,\tau+1]$ such that $|A|=a$ and $J\subsetneq A$,
$\sum\limits_{i\in A}n_{i}<r$. This means

$\displaystyle\sum\limits_{i\in A}m_{i}\leq\sum\limits_{i\in A}n_{i}+1\leq r,$

for all $A\subseteq[1,\tau+1]$ with $|A|=a$ and $J\subsetneq A$. Thus, (2)
holds for $\underline{\mu}$.

It is possible to pick an $A\subset[1,\tau+1]$ with $|A|=a$ and
$J\cup\\{q\\}\subseteq A$, then we have

$\displaystyle\sum\limits_{i\in A}m_{i}$ $\displaystyle=$
$\displaystyle\sum\limits_{i\in J}m_{i}+m_{q}+\sum\limits_{i\in
A\setminus(J\cup\\{q\\})}m_{i}$ $\displaystyle=$
$\displaystyle\sum\limits_{i\in J}n_{i}-1+z+1+(a-|J|-1)z=r.$

Thus, $\underline{\mu}$ is an $(a,b,\tau,n,r)-$dispersion vector. This
completes the proof of Claim 1.

Since $q\in T$ and $p\notin T$, it can be easily seen that
$\sum\limits_{i=t}^{t+b-1}m_{i}=\sum\limits_{i=t}^{t+b-1}n_{i}+1=s+1$. $\Box$