Rate-Optimal Streaming Codes for Channels
with Burst and Isolated Erasures
M. Nikhil Krishnan, Student Member, IEEE, P. Vijay Kumar, Fellow, IEEE
Electrical Communication Engineering, Indian Institute of Science, Bangalore -

arXiv:1801.05919v1 [] 18 Jan 2018

560012
email: {nikhilkrishnan.m, pvk1729}@gmail.com

Abstract
Recovery of data packets from packet erasures in a timely manner is critical for many streaming
applications. An early paper by Martinian and Sundberg introduced a framework for streaming codes
and designed rate-optimal codes that permit delay-constrained recovery from an erasure burst of length
up to B. A recent work by Badr et al. extended this result and introduced a sliding-window channel
model C(N, B, W ). Under this model, in a sliding-window of width W , one of the following erasure
patterns are possible (i) a burst of length at most B or (ii) at most N (possibly non-contiguous) arbitrary
erasures. Badr et al. obtained a rate upper bound for streaming codes that can recover with a time delay
T , from any erasure patterns permissible under the C(N, B, W ) model. However, constructions matching
the bound were absent, except for a few parameter sets. In this paper, we present an explicit family of
codes that achieves the rate upper bound for all feasible parameters N , B, W and T .

I. I NTRODUCTION
In many multimedia streaming applications, where packet losses are a norm, fast recovery of
lost packets is often desirable. Conventional coding schemes like linear block codes, while helpful
in combating erasures, can have increased delays due to buffering of data. In [1], Martinian and
P. Vijay Kumar is also a Visiting Professor at the University of Southern California. This research is supported in part by
the National Science Foundation under Grant 1421848 and in part by an India-Israel UGC-ISF joint research program grant.
M. Nikhil Krishnan would like to acknowledge the support of Visvesvaraya PhD Scheme for Electronics & IT awarded by
Department of Electronics and Information Technology, Government of India.

January 19, 2018

DRAFT

Sundberg introduce a framework for convolutional codes with decoding delay as an explicit
parameter. We refer to these codes as streaming codes. The setting considered is as follows:
At each time instance t ∈ {0, 1, 2, . . .}, an encoder E receives a message packet s[t] from
a source stream. Each message packet s[t] consists of k symbols drawn from a finite field Fq
of size q. In other words, s[t] , (s0 [t] s1 [t] . . . sk−1 [t])| ∈ Fkq . E is a convolutional encoder
and emits a coded packet x[t] at time t, where x[t] , (x0 [t] x1 [t] . . . xn−1 [t])| ∈ Fnq . E is also
assumed to be causal, wherein each coded packet x[t] is a function of the message packets until
time t, i.e., s[0], s[1], . . . , s[t]. Between the encoder-decoder pair, there exists a channel which
introduces erasures at packet level. Let y[t] denote the packet received at the decoder end. We
have:
y[t] =




∗ if x[t] is erased,

 x[t] otherwise.
Let ŝ[t] denote the decoded packet corresponding to s[t]. The decoder is delay-constrained
with a delay parameter T . i.e., each decoded message packet ŝ[t] is obtained as a function of
received coded packets {y[0], y[1], . . . , y[t + T ]}. Note that some of these packets can possibly
be erased by the channel. The rate R of the code is naturally defined as nk .
In [1], the authors consider a channel which introduces a burst of length at most B. Together
with the delay-constraint T , the streaming codes designed for this channel can in fact tolerate
multiple erasure bursts, each of length at most B, with a guard space of at least T between
consecutive bursts. However, as the codes presented in [1] are tuned for burst erasures, they are
sensitive to isolated erasures. In a recent work by Badr et al. [2], the authors introduce a slidingwindow based channel model which accounts for burst erasures and isolated erasures. Under the
sliding-window channel model, in any sliding-window of width W , the channel will have one of
the following erasure patterns; (a) a burst erasure of length at most B or (b) up to N erasures at
arbitrary locations within the sliding-window. The channel is denoted by C(N, B, W ). Clearly,
N ≤ B as burst erasures are a special case of arbitrary erasures. Also, T ≥ B as otherwise nonzero rates are not feasible for a streaming code. Taken together with the delay-constraint T , the
C(N, B, W ) model specializes to the burst-erasure-only model in [1], if one chooses W = T + 1
and N = 1. Furthermore, a rate upper bound on codes for this channel has also been derived
in [2]. There are several other follow-up works that study various low-delay communication
schemes like [3], [4], [5], [6] and references therein.

DRAFT

January 19, 2018

In an independent, concurrent work [7], the authors prove the existence of rate-optimal
streaming codes for all parameters.
Our Results: In this work, we prove the tightness of the rate upper bound derived in [2] for
codes that allow both burst erasures and isolated erasures, with a delay-constraint of T . We
prove this by constructing explicit codes that meet the bound with equality. The family of codes
that achieve the bound are based on linearized polynomials, and require a field-size exponential
in T . For various range of parameters, we obtain rate-optimal codes that require lower fieldsize, which is of O(T 2 ). In some cases, even linear and binary field-sizes suffice. We obtain
rate-optimal streaming codes by reducing the problem to the design of linear block codes with
certain properties. For the corner case of B = N , these codes specialize to MDS codes.
II. P RELIMINARIES
A. Streaming Capacity [2]
In the context of streaming codes with decoding delay-constraint T , a rate R is said to be
achievable over C(N, B, W ), if there exists a streaming code with delay parameter T and rate R
that tolerates all the erasure patterns permitted by C(N, B, W ). The supremum of all such rates
is termed as the streaming capacity. In [2], the authors obtain the following upper bound for R:

R≤

Teff − N + 1
,
B + Teff − N + 1

(1)

where Teff = min{T, W − 1}. We shall refer to Teff as the effective delay. Achievability of this
rate bound is not known in general, except for a limited set of parameters. For the burst-alone
case, i.e., N = 1, Maximally Short (MS) codes ([1], [8]) are known to meet the bound (1).
For the other extreme case of N = B, Strongly-MDS convolutional codes [9] are shown to
be optimal in [2]. [10] provides a family of codes with R = 0.5 that meets (1). [2] shows the
existence of near-optimal codes for all feasible parameters B, N, Teff that have a guaranteed rate
of at least

Teff −N
.
B+Teff −N

Let [u, v] , {u, u + 1, . . . , v}. We have the following lemma.
Lemma II.1. If there is a streaming code Cstr which permits recovery of any packet x[t] from
erasure with a delay of at most Teff , even in presence of either (i) a burst erasure (involving
time t) of length at most B or (ii) at most N isolated erasures (again, including time t), then
Cstr tolerates all the erasure patterns permitted by C(N, B, W ) with a delay-constraint T .
January 19, 2018

DRAFT

Proof. Consider any erasure pattern that arises from the C(N, B, W ) model. Let j ∈ {1, 2, . . .}, J ∈
{2, 3, . . .}. Denote by tj , the coordinate at which the j th erasure happened. Let the induction
assumption be that, for all j ≤ (J − 1), x[tj ] is recovered by the ‘time’ (tj + Teff ), i.e., with a
delay Teff ≤ T . Hence during the decoding of x[tJ ], we can assume that, strictly before time tJ ,
there are no erasures occurring among the coordinates [0, tJ + Teff ].
Consider the window of width W consisting of coordinates [tJ , tJ + W − 1]. The coded packet
x[tJ ] is erased by assumption. By definition of the sliding window channel model, in the worst
case, there will be either (i) (B − 1) erasures at coordinates [tJ + 1, tJ + B − 1] or (ii) (N − 1)
erasures within [tJ + 1, tJ + W − 1]. As Teff ≤ (W − 1), when restricted to the set of coordinates
[0, tJ + Teff ], Cstr will be observing either a burst of length ≤ B including coordinate tJ or ≤ N
arbitrary erasures involving tJ (note that the induction assumption removes all erasures occurring
before time tJ ). In either case, Cstr will be able to recover x[tJ ] by time (tJ + Teff ), with delay
Teff ≤ T .
The base case of the induction can be shown to be true by taking J = 1. Thus we have shown
that for all j ≥ 1, x[tj ] can recover from any erasure pattern permitted by C(N, B, W ), with a
delay of Teff ≤ T .
Hence in order to construct streaming codes for C(N, B, W ) with a delay parameter of T ,
it is enough to focus on streaming codes that can handle an erasure burst of length B or N
isolated erasures, with a delay of at most Teff . We drop the subscript from the notation Teff for
brevity and refer to T as the (effective) delay parameter.

B. Diagonal Interleaving
Diagonal interleaving is a known technique that enables one to convert a block code into a
convolutional code. It has been used in the context of streaming codes in works like [1], [8]
to reduce the problem of designing rate-optimal streaming codes for burst-erasure-only case
(N = 1) to that of designing block codes having appropriate features. Consider an [n, k] linear
block code C , where n, k denote the code-length and dimension, respectively. We summarize
the diagonal interleaving using Fig. 1. In the figure, we consider a systematic encoder for C
and hence take xi [t] = si [t] for 0 ≤ i ≤ k − 1. In order to stress the point that the last (n − k)
symbols of a coded packet are parity symbols at any time t, we use the notation pj [t] , xk+j [t],
DRAFT

January 19, 2018

_

𝐷𝑘 2
_

.....

.....

𝐷0

𝐷1

𝐷2

....

𝐷𝑘 3

Parity symbols
at time 𝑡

Systematic Encoder for

_
𝐷𝑘 1

_

𝐷𝑛 𝑘

Fig. 1: A depiction of the diagonal interleaving technique. Here Dj denotes a delay of j time
units.

for 0 ≤ j ≤ n − k − 1. As an example, consider the following parameters for C ; n = 5, k = 3
. The diagonal interleaving technique will result in a convolutional code as shown in Fig. 2.

.......

Fig. 2: An illustration of the diagonal interleaving technique for a [5, 3] code. Each diagonal of
the form (s0 [t], s1 [t + 1], s2 [t + 2], p0 [t + 3], p1 [t + 4]) is a codeword in C , where t ≥ 0. For
notational consistency, define si [t] = pi [t] , 0 for t < 0.

Consider an [n, k] linear block code C over Fq . Let c , (c0 , c1 , c2 , . . . , cn−1 ) denote a codeword
in C .
Definition II.1. For i ∈ [0, n − 1] and I ⊆ [0, n − 1], the ith coordinate of C is said to be
January 19, 2018

DRAFT

recoverable from ( the set of coordinates ) I, if there exist λj ’s chosen from Fq such that:
ci =

X

λj cj ∀c ∈ C .

j∈I

If i ∈ I, it is straightforward to see that ith coordinate is recoverable from I. For parameters
N , B as in the channel model C(N, B, W ) and the delay parameter T , let ∆i , min{i+T, n−1}.
Definition II.2. C is said to be conforming to C(N, B, W ) with delay-constraint T , if both the
following statements hold for all i ∈ [0, n − 1]:
•

ith coordinate of C is recoverable from [0, ∆i ]\N , for all N ⊆ [0, n−1] such that |N | ≤ N .

•

ith coordinate of C is recoverable from [0, ∆i ]\B, where B = [u, v], for all 0 ≤ u ≤ v ≤ n−1
such that (v − u + 1) ≤ B.

One can show without much difficulty that, if there is an [n, k] linear block code C which
conforms to C(N, B, W ) with delay-constraint T , by applying diagonal interleaving, it will result
in a streaming code Cstr that can tolerate an erasure burst of length B or N isolated erasures,
with delay-constraint T . By Lemma II.1, Cstr yields an achievable rate

k
n

over C(N, B, W ) with

effective delay-constraint T . Hence from here onwards we restrict our attention to designing
linear block codes that conform to C(N, B, W ) with (effective) delay-constraint T and have rate
R = k/n that meets (1) with equality. We refer to these codes as rate-optimal linear block codes
with delay-constraint T .
Let T = aB + δ, where a ≥ 0 and 1 ≤ δ ≤ B. If a = 0, δ = B (as B ≤ T ).
III. R ATE -O PTIMAL L INEAR B LOCK C ODES WITH D ELAY C ONSTRAINT T

FOR THE

C ASE

δ ≥ (B − N )
A. Construction-A
Given the channel C(N, B, W ) and effective delay constraint T , consider the parameters n =
(B + T − N + 1) and k = (T − N + 1) for the linear block code C to be constructed over Fq2 .
Let δ ≥ (B − N ) and m , [m0 m1 . . . mk−1 ] be the k-length message vector to be mapped to
the codeword c , (c0 , c1 , . . . , cn−1 ) ∈ C . Consider an [nMDS = T + 1, kMDS = k, dmin = N + 1]
MDS code CMDS over Fq ⊆ Fq2 , with a generator matrix GMDS having all the entries from
Fq ⊆ F2q . Let c0 = [c00 c01 . . . c0T ] = mGMDS . Assign these (T + 1) code-symbols {c0j }Tj=0 to the
coordinates {0, 1, . . . , T − 1} ∪ {n − 1} of c. i.e., ci = c0i for 0 ≤ i ≤ T − 1 and cn−1 = c0T . For
DRAFT

January 19, 2018

the (B − N ) coordinates {cT +j : 0 ≤ j ≤ (B − N − 1)}, take cT +j = αcj + cj+B + . . . + cj+aB .
{z
}
|
(a + 1) terms

Note that, since j ≤ (B − N − 1) ≤ δ − 1, all the (a + 1) code-symbols taking part in the
check-sum belong to the set of coordinates [0, T − 1]. Here α can be any field element from the
set Fq2 \ Fq . Existence of GMDS is guaranteed when q ≥ (T + 1). Hence C can be constructed
with a field-size of O(T 2 ).
Let N = 2, B = 4, T = 10. Hence a = 2, δ = 2. The dimension of C , k = T − N + 1 = 9
and length, n = B + T − N + 1 = 13. This example code is illustrated in Fig. 3.

Fig. 3: An illustration of construction-A for the parameters: N = 2, B = 4, T = 10. Here the
set {c0i }10
i=0 corresponds to code-symbols coming from an [nMDS = 11, kMDS = 9] MDS code.

Proposition III.1. Construction-A gives a rate-optimal family of linear block codes with delay
constraint T .
Proof. (Burst erasure recovery with delay constraint T ) Consider an erasure burst of length B.
Let  indicate the number of erasures occurred among the coordinates in [T, T + B − N − 1],
as a part of the erasure burst. Thus, the set of non-erased symbols among the coordinates
[T, T +B−N −1] is given by {ci+T :  ≤ i ≤ (B−N −1)}, where ci+T , αci +ci+B +. . .+ci+aB .
As ci+T is assumed to be a non-erased symbol, the burst of length B ends at some coordinate
≤ (T +i−1). Note that, at most one code-symbol in the sum given by each ci+T can be a part of
the burst erasure, as the code-symbols in the sum are chosen to be B apart. Suppose that none of
the code-symbols {ci , ci+B , . . . , ci+aB }, which constitute the sum given by ci+T , are part of the
erasure burst. As the erasure burst is of length B, the burst can start only on or after the coordinate
(i+aB +1). This means that the burst will end at a coordinate ≥ i+aB +B ≥ T +i (as δ ≤ B).
This is a contradiction, and hence each non-erased coordinate in the range [T + , T + B − N − 1]
will have lost precisely one code-symbol from the check-sum it contains. Each of these codesymbols can be recovered from the check-sums. Thus there will be (B − N − ) coordinates
recovered from the (B − ) erasures occurred across coordinates [0, T − 1] ∪ {T − N + B}. The

January 19, 2018

DRAFT

remaining number of erasures is B −  − (B − N − ) = N . As C restricted to the coordinates
[0, T − 1] ∪ {T − N + B} is an N erasure correcting MDS code, the remaining erasures can be
corrected as well.
Furthermore, we need to show that all the erased coordinates in the erasure burst can be
recovered with a delay of at most T . Towards this, we need to consider only erasure bursts
involving at least one of the coordinates in [0, B − N − 1]. For all the remaining coordinates,
the delay constraint is trivially met as the last coordinate of C is (T + B − N ). Suppose
ci : i ∈ [0, B − N − 1] is erased (as part of a burst erasure of length B). Clearly, none of the
code-symbols {ci+B , ci+2B , . . . , ci+aB , cT +i } will be part of the erasure burst and hence ci can
be recovered with a delay of T .
(Recovery from N arbitrary erasures with delay constraint T ) C can recover from any N
arbitrary erasures, as it is formed by adding (B − N ) dependent coordinates to an N erasure
correcting MDS code. As in the case of recovery from burst erasures, in order to show that delay
constraints are met during the recovery, one needs to consider only those N -erasure patterns
involving at least one of the code-symbols from the set of coordinates [0, B − N − 1]. Suppose
ci is erased for some i ∈ [0, B − N − 1]. Among the set of T coordinates given by [0, i − 1] ∪
[i, T − 1] ∪ {T + i}, there can possibly be (N − 1) more erasures.
If the coordinate (T + i) is among the erased coordinates, there will be possibly (N − 1)
erasures among the coordinates [0, T − 1], inclusive of the coordinate i. As these coordinates
are part of an MDS code of dimension k = T − N + 1, the code-symbol ci can be recovered
with a delay < T .
Now consider the remaining case that (T + i) is not an erased coordinate. Let G1 be the
systematic k × (T + 1)-generator matrix for the code obtained by puncturing C to the coordinates [0, T − 1] ∪ {T + i}. For 0 ≤ j ≤ T − N , the j th column of G1 is taken as
ej , [ |0 .{z
. . 0} 1| 0 {z. . . 0} ]| . We remark that all the elements of the sub-matrix obtained by
j

(k − j)

restricting G1 to the coordinates corresponding to [0, T − 1], belong to Fq ⊆ Fq2 . Let G2 be the
(T − N ) × (T − 1) sub-matrix obtained from G1 after removing columns corresponding to the
coordinates {i, (T + i)} of C and the ith row. Note that G2 corresponds to the MDS generator
matrix of a code of length (T − 1) and dimension (T − N ). The column of G1 corresponding
to the coordinate (T + i) will have the form [∗| .{z
. . ∗} β ∗ . . . ∗]| , where ∗ indicates elements
| {z }
i

from Fq ⊆
DRAFT

F2q

and β ∈

F2q

\ Fq . Let

G01

(k − i)

be an (T − N + 1) × (T − N + 1) sub-matrix of G1 with
January 19, 2018

(T −N ) columns from [0, i−1]∪[i+1, T −1] and (T +i). After expanding the determinant of G01
based on the column corresponding to the coordinate (T +i), we have det(G01 ) = ∗+β ∗det(G02 ),
where ∗ denotes field elements from Fq ⊆ F2q and G02 is some (T − N ) × (T − N ) sub-matrix
of G2 . As G2 is an MDS generator matrix with all the entries from Fq , det(G02 ) 6= 0 ∈ Fq and
hence det(G01 ) 6= 0. Thus, ci can be recovered with a delay of T .
Corollary III.2. (Binary field-size) When N = 1 and δ ≥ (B − 1), C can be over F2 .
Remark III.1. When B = N , C reduces to an [n = T + 1, k = T − B + 1] MDS code.
Remark III.2. (Linear field-size for N = (B − 1)) For N = (B − 1), if the coordinates 0
and T are swapped in C , with α 6= 0 ∈ Fq , the resultant code will be rate-optimal with delay
constraint T . In this case, field-size requirement will be ≥ (T + 1).
IV. R ATE -O PTIMAL L INEAR B LOCK C ODES WITH D ELAY C ONSTRAINT T

FOR ALL

F EASIBLE PARAMETERS : δ, B, N, T
A. Linearized Polynomials
A linearized polynomial [11] of q-degree (k − 1) is a polynomial of the form f (x) =
Pk−1
qi
i=0 mi x , where mi ∈ Fq m and mk−1 6= 0. It satisfies the property that: f (a1 x1 + a2 x2 ) =
a1 f (x1 ) + a2 f (x2 ), where ai ∈ Fq , xi ∈ Fqm . Furthermore, a linearized polynomial of qdegree (k − 1) can be uniquely determined from evaluations at k points {θi }k−1
i=0 ⊆ Fq m , which
are linearly independent over Fq . Gabidulin codes [12] are constructed based on linearized
polynomial evaluations.

B. Construction-B
Given the channel C(N, B, W ) and effective delay constraint T , consider the parameters n =
(B + T − N + 1), k = (T − N + 1) for the linear block code C to be constructed over Fqm . The k
message symbols {mi }k−1
i=0 will be taken as coefficients of a linearized polynomial with q-degree
(k − 1) and evaluated at (T + 1) points {θi }Ti=0 . Here θi ∈ Fqm and {θi }Ti=0 is a collection of
independent field elements over Fq ⊆ Fqm . Let c00 , c01 , . . . , c0T be the code-symbols (evaluations)
thus obtained. Assign these code-symbols to the coordinates {0, 1, . . . , T − 1} ∪ {n − 1} of c.
i.e., cj = c0j for 0 ≤ j ≤ T − 1 and cn−1 = c0T . Let δ 0 , min{δ, (B − N )}. For coordinates
0 ≤ j ≤ δ 0 − 1, take cT +j = cj + cj+B + . . . + cj+aB . For coordinates in the range δ 0 ≤ j ≤
January 19, 2018

DRAFT

(B − N ) − 1, cT +j = cj + cB+j + . . . + c(a−1)B+j + γj,0 caB + γj,1 caB+1 + . . . + γj,δ−1 caB+δ−1 .
Here {γi,j }’s are selected in such a way that the (B − N − δ 0 ) × δ matrix of the form:


γδ0 ,0
γδ0 ,1
...
γδ0 ,δ−1


 γ0
γδ0 +1,1 . . . γδ0 +1,δ−1 
 δ +1,0

Γ,
,
.
.


..
..


γB−N −1,0 γB−N −1,1 . . . γB−N −1,δ−1
is Cauchy, with all the entries belonging to Fq ⊆ Fqm . Γ can be constructed explicitly (for
example, see [13, Ch. 5]) for q ≥ (δ + B − N − δ) = (B − N ). The evaluation points {θi } can
be chosen as follows. Let β̂ denote a primitive element of the extension field FqT +1 . A natural
candidate for θi , for 0 ≤ i ≤ T will be θi = β̂ i−1 . Hence construction-B is possible with a
field-size ≥ q (T +1) , where q ≥ (B − N ).
Proposition IV.1. Construction-B gives a rate-optimal family of linear block codes, for all
feasible parameters δ, B, N, T .
Proof. (Recovery from N arbitrary erasures with delay constraint T ) Similar to the scenario in
Proposition III.1, C is N -erasure correcting, as C is constructed by adding (B − N ) dependent
coordinates to an N -erasure correcting MDS code (obtained from linearized polynomial evaluations). Hence we only need to show that delay requirements are met for arbitrary erasures
involving at least one of the coordinates in [0, (B − N − 1)]. For i ∈ [0, (B − N − 1)], let i be an
erased coordinate. Consider the set of coordinates Ri , [0, i − 1] ∪ [i + 1, T − 1] ∪ {T + i}. The
corresponding code-symbols will be evaluations of a linearized polynomial at the evaluation
P
points (field elements): Ai ∪ {θi + θ∈Bi θ}, where Ai , {θ0 , θ1 , . . . , θi−1 , θi+1 , . . . , θT −1 },
Bi , {θi , θB+i , . . . , θ(a−1)B+i , θaB+i }, if 0 ≤ i ≤ δ 0 − 1 or Bi , {θi , θB+i , . . . , θ(a−1)B+i , γi,0 θaB ,
γi,1 θaB+1 , . . . , γi,δ−1 θaB+δ−1 }, if δ 0 ≤ i ≤ (B − N − 1).
The set of (T − 1) evaluation points Ai is an independent set over Fq by construction. Adding
P
{θi + θ∈Bi θ} to Ai will not add any dependency, as θi ∈
/ Ai . Thus, access to evaluations at
P
any k = (T − N + 1) out of the T points in Ai ∪ {θi + j∈Bi θj }, will be sufficient to recover all
the k message symbols. This essentially implies that even if there are (N − 1) erasures among
the coordinates in Ri , ci can still be corrected with a delay of at most T .
(Burst erasure recovery with delay constraint T ) If δ ≥ (B − N ), proof exactly follows as
in the case of Proposition III.1. For the remaining case of δ < (B − N ), proof is moved to
Appendix A.

DRAFT

January 19, 2018

Example IV.1. Consider the parameters B = 7, N = 2, δ = 3, T = 10. Hence for C , we have
the parameters n = (B + T − N + 1) = 16 and k = (T − N + 1) = 9. Also, δ = δ 0 = 3. Let α̂
be a primitive element of F5 and


1 α̂ α̂2
.
Γ=
1 α̂2 α̂4
Consider the set of (T + 1) = 11 field elements {θi }10
i=0 , which forms an independent set over
F5 . For example, let β̂ be a primitive element of F5m , where m ≥ (T + 1) = 11. Then, θi can
be chosen as β̂ i .
Let {mi }8i=0 be the set of k = 9 message symbols drawn from F5m . Consider the corresponding
P
i
linearized polynomial f (x) = 8i=0 mi x5 . The code-symbols will be as follows: ci = f (θi ), for
0 ≤ i ≤ (T − 1) = 9, c10 = c0 + c7 = f (θ0 + θ7 ), c11 = c1 + c8 = f (θ1 + θ8 ), c12 = c2 + c9 =
f (θ2 + θ9 ), c13 = c3 + c7 + α̂c8 + α̂2 c9 = f (θ3 + θ7 + α̂θ8 + α̂2 θ9 ), c14 = c4 + c7 + α̂2 c8 + α̂4 c9 =
f (θ4 + θ7 + α̂2 θ8 + α̂4 θ9 ), c15 = f (θ10 ).
Consider the recovery of C from N = 2 arbitrary erasures, with a delay at most 10. Clearly,
C can tolerate 2 erasures. This is because, it is constructed by adding (B − N ) = 5 additional
parity checks (at coordinates 10, 11, 12, 13 and 14) to a 2-erasure correcting [11, 9]-MDS code.
As the last coordinate of C is 15, delay constraint of 10 will be trivially met during the recovery
of any cj : j ≥ 5, which is a part of 2 arbitrary erasures. Hence we need to consider only
those 2-erasure patterns which involve at least one coordinate from [0, 4]. Suppose c1 is erased.
Consider the T = 10 coordinates, R1 = {0} ∪ [2, 9] ∪ {11}. The corresponding 10 evaluation
points {θ0 , θ2 , θ3 , . . . , θ9 , (θ1 +θ8 )} form an independent set over F5 . Therefore, even if one more
coordinate is lost (since N = 2, and coordinate 1 is already assumed to be lost) from R1 , there
will still be k = 9 independent evaluation points available from the non-erased coordinates in
R1 . As the last coordinate in R1 is (T + 1) = 11, c1 can be recovered with a delay at most 10.
Similar arguments hold when c0 , c2 , c3 or c4 is part of a 2-erasure pattern.
For the burst erasure case, consider consecutive erasures of length B = 7, which erases the set
of coordinates [u, v], where 0 ≤ u ≤ v ≤ (n − 1) and v = u + B − 1. Let  denote the number of
coordinates in [u, v] that intersect [T, T + B − N − 1] = [10, 14]. Clearly, 0 ≤  ≤ (B − N ) = 5.
•

 = 5: If the burst erasure is such that  = (B − N ) = 5, the [11, 9]-MDS code across
coordinates [0, 9] ∪ {15} will have B − (B − N ) = N = 2 coordinates erased and hence
all the erasures can be corrected.

January 19, 2018

DRAFT

•

 = 0: Each symbol from [10, 14] will recover one unique erased code-symbol. Let [u, u +
6] ⊆ [0, 9] denote the B = 7 coordinates involved in the burst erasure. Clearly, there exists
j0 , j1 , . . . , j4 ∈ [u, u+6] such that j` mod B = `, for 0 ≤ ` ≤ B −N −1 = 4. Code-symbol
at coordinate 10 + ` will be recovering precisely the corresponding j` .

•

 = 1: The erased coordinates belong to [4, 10]. As c11 = c1 +c8 and c12 = c2 +c9 , these two
code-symbols recover coordinates 8 and 9, respectively. From c13 (= c3 + c7 + α̂c8 + α̂2 c9 )
and c14 (= c4 +c7 + α̂2 c8 + α̂4 ), after removing the interference from the known code-symbols
{c3 , c8 , c9 }, we obtain the sums ĉ13 = c7 and ĉ14 = c4 + c7 , respectively. These two sums
essentially yield the symbols c4 and c7 .

•

 = 2: The erased coordinates are in [5, 11]. As c12 = c2 + c9 , it recovers coordinate 9.
After removing the known code-symbols {c3 , c4 , c9 }, the check-sums provided by c13 and
c14 result in ĉ13 = c7 + α̂c8 and ĉ14 = c7 + α̂2 c8 , respectively. These sums would recover
the code-symbols c7 and c8 (uses the Cauchy property of Γ).

•

 = 3: Here the erased coordinates are from the set [6, 12]. After removing the interference
from the known code-symbols {c3 , c4 }, ĉ13 = c7 + α̂c8 + α̂2 c9 = f (θ7 + α̂θ8 + α̂2 ), ĉ14 =
c7 + α̂2 c8 + α̂4 c9 = f (θ7 + α̂2 θ8 + α̂4 θ9 ). From the Cauchy property of Γ, the evaluation
points {θ7 + α̂θ8 + α̂2 θ9 , θ7 + α̂2 θ8 + α̂4 θ9 } are both independent. These evaluation points
along with {θ0 , θ1 , . . . , θ5 , θ10 } form an independent set of cardinality, k = 9.

•

 = 4: The erased coordinates are in [7, 13]. After removing the interference from the known
code-symbols {c4 }, ĉ14 = c7 + α̂2 c8 + α̂4 c9 = f (θ7 + α̂2 θ8 + α̂4 θ9 ). θ7 + α̂2 θ8 + α̂4 θ9 along
with {θ0 , θ1 , . . . , θ6 , θ10 } result in an independent set of size k = 9.

Thus, for every , the (5 − ) non-erased coordinates [10 + , 14] will provide one linearized
polynomial evaluation each. These (5 − ) evaluations along with the 11 − (7 − ) evaluations
corresponding to the non-erased coordinates in [0, 10] ∪ {15}, result in linearized polynomial
evaluations over 9 independent evaluation points and hence all the erased symbols can be
recovered.
In order to show that the delay constraint of T = 10 is met during the recovery from burst
erasures, we need to consider only the burst erasures involving at least one of the coordinates
[0, B − N − 1] = [0, 4]. Suppose ci , where i ∈ [0, 2], is part of a burst-erasure. The coordinates
{7 + i, 10 + i} will be non-erased, as they are at least B = 7 apart from coordinate i. Hence
using the check-sum provided by c10+i , the code-symbol ci can be recovered, with a delay of
10 time units.

DRAFT

January 19, 2018

For ci , where i ∈ [3, 4], which is part of a burst erasure, the symbol c10+i will be non-erased.
There are three possible cases for (i, ); (3, 0), (4, 0) and (4, 1). If  = 0, the code-symbols
{c7 , c8 , c9 } will be known by the time (10 + i). After removing the interference from the known
symbols at coordinates {7, 8, 9}, c10+i will yield the code-symbol ci . If  = 1, we have already
seen that, c4 will be recovered at time 14.
A PPENDIX A
P ROOF OF P ROPOSITION IV.1: B URST E RASURES , C ASE : δ < (B − N )
Consider the set of erased coordinates, B , [u, v], where 0 ≤ u ≤ v ≤ n−1 and v−u+1 = B.
Let |B ∩ [T, T + B − N − 1]| = .
1)  = (B − N ): The number of erasures across the coordinates {0, T − 1} ∪ {T − N + B}
will be B − (B − N ) = N , which can be corrected.
2)  = 0: Each code-symbol from the set {cT , cT +1 , . . . , cT +δ−1 } will correct one erased symbol
(argument similar to that in the proof of Proposition III.1). This essentially means that all
the code-symbols which are part of the check-sums given by {cT , cT +1 , . . . , cT +δ−1 }, are
known by time T + δ − 1. In particular, we have {caB , caB+1 , . . . , caB+δ−1 } known by
time T + δ − 1, irrespective of whether some of them are erased or not. From each codesymbol cT +j , cj + cB+j + . . . + c(a−1)B+j + γj,0 caB + γj,1 caB+1 + . . . + γj,δ−1 caB+δ−1 , for
δ ≤ j ≤ B −N −1, the interference from {caB , caB+1 , . . . , caB+δ−1 } can be canceled. Hence
cT +j ’s can be thought of as simply, ĉT +j = cj +cB+j +. . .+c(a−1)B+j . For 0 ≤ i ≤ B−N −1,
let `i be the unique coordinate ∈ [u, v] such that `i mod B = i. The check-sum provided
by the code-symbol at coordinate (T + i) will be recovering precisely the erased symbol c`i .
Thus in total, the set of symbols {cT , cT +1 , . . . , cT +B−N −1 } will correct (B − N ) erasures.
3) 0 <  < (B − N ): Let ζ indicate the number of non-erased coordinates lying in [T + , T +
δ − 1]. Clearly, ζ > 0 iff  < δ. Assuming ζ > 0, each such non-erased ci+T that lies in
 ≤ i ≤ δ − 1, helps in recovering one unique erased symbol from the erasure burst. The
argument, again, is similar to the one in the proof of Proposition III.1. This also means that
the symbols {caB+j :  ≤ j ≤ δ − 1} are known by time T + δ − 1.
Now let us see how non-erased symbols in the range cT +i : max{δ, } ≤ i ≤ (B − N − 1)
help in the recovery of erased symbols. Note that each cT +i in the range max{δ, } ≤ i ≤
(B − N − 1) takes the form: cT +i = ci + cB+i + . . . + c(a−1)B+i + γi,0 caB + γi,1 caB+1 +
. . . + γi,δ−1 caB+δ−1 . As we assume  > 0, we can remove interference from the set of
January 19, 2018

DRAFT

non-erased symbols {ci , cB+i , . . . , c(a−2)B+i } (these can be easily verified to be non-erased
symbols, when  > 0). For ζ > 0, we can remove the interference from the set of symbols
{caB+j :  ≤ j ≤ δ − 1} (these are known by time T + δ − 1). Thus effectively, each
non-erased symbol cT +i in the range max{δ, } ≤ i ≤ (B − N − 1) provides the sum
ĉT +i = c(a−1)B+i + γi,0 caB + γi,1 caB+1 + . . . + γi,min{,δ}−1 caB+min{,δ}−1 . There are the
following two possibilities.
•

(B − ) ≤ (N + δ): This condition essentially means that none of the c(a−1)B+i terms
appearing in ĉT +i , for max{δ, } ≤ i ≤ (B − N − 1), are part of the burst erasure
considered. In this scenario, we can further remove the interfering c(a−1)B+i ’s from ĉT +i ’s,
where max{δ, } ≤ i ≤ (B − N − 1). Furthermore, if (B − ) < δ, not all of the symbols
{caB , caB+1 , . . . , caB+δ−1 } will be erased. Hence we can rewrite the effective check-sum
contributed by each ĉT +i as ĉT +i = γi,max{δ−B+,0} caB+max{δ−B+,0} + γi,1 caB+1 + . . . +
γi,min{,δ}−1 caB+min{,δ}−1 . The number of remaining erased symbols caB+i in the range
0 ≤ i ≤ min{, δ} − 1, {caB+max{δ−B+,0} , caB+max{δ−B+,0}+1 , . . . , caB+min{,δ}−1 } and
number of non-erased symbols in the coordinate range [T + max{, δ}, T + B − N − 1]
is given in Table I, for all the cases with (B − ) ≤ (N + δ). From Table I, for all the
cases, the number of remaining erased symbols ≥ number of code-symbols (evaluations)
in the range [T + max{, δ}, T + B − N − 1]. As γx,y ’s are chosen carefully as part of
a Cauchy matrix, all these equations (evaluations) will be independent. Thus the number
of independent equations provided by coordinates in the range [T + , T + B − N − 1]
is equal to (B − N − ).

•

(B − ) > (N + δ): Let α0 , (B −  − N − δ). The number of erased symbols recovered
by the non-erased coordinates lying in [T + , T + δ − 1] is max{δ − , 0}. Note that
α0 < (B − N − δ). For each c(a−1)B+i such that i ∈ [B − N − α0 , B − N − 1], there
exists a non-erased cT +i which results in a ĉT +i = c(a−1)B+i + γi,0 caB + γi,1 caB+1 +
. . . + γi,min{,δ}−1 caB+min{,δ}−1 , after removing the known interfering symbols. To the
contrary, if cT +i is part of the erased symbols, this would mean that B ≥ (B − N −
i) + N + δ + i =⇒ δ ≤ 0, which is a contradiction. Thus cT +i for i ∈ [B − N −
α0 , B − N − 1] gives α0 independent equations as they all give one unique component
c(a−1)B+i each. For j ∈ [max{, δ}, B − N − α0 − 1], cT +j ’s are non-erased and results in
a ĉT +j = γj,0 caB + γj,1 caB+1 + . . . + γj,min{,δ}−1 caB+min{,δ}−1 , after removing the known

DRAFT

January 19, 2018

Condition

No. of remaining erased (unknown)

No. of equations

symbols among the coordinates

from the coordinates

[aB, aB + δ − 1]

[T + max{, δ}, T + B − N − 1]

(B − ) ≥ δ,  ≥ δ

δ

(B − N − )

(B − ) ≥ δ,  < δ



(B − N − δ)

(B − ) < δ,  ≥ δ

(B − )

(B − N − )

(B − ) < δ,  < δ

(B − δ)

(B − N − δ)

Table I: A summary of all the conditions, when (B − ) ≤ (N + δ).

interfering symbols. These corresponds to (B−N −α0 −max{, δ}) = min{, δ} equations
and min{, δ} unknowns and hence are all independent. Therefore, the total number of
independent evaluations supplied by the non-erased coordinates in [T + , T + B − N − 1]
is max{δ − , 0} + α0 + min{, δ} = δ + α0 = B − N − .
Therefore for all the cases of 0 ≤  ≤ (B − N ), (B − N − ) non-erased code-symbols in the
range [T +, T +B −N −1] provide that many evaluations, which are independent (over Fq ), with
respect to the T + 1 − (B − ) evaluation points corresponding to the (T − B +  + 1) non-erased
locations in [0, T − 1] ∪ {T − N + B}. This essentially adds up to T − N + 1 evaluations over
independent evaluation points. As k = T − N + 1, all the erasures can be corrected.
In order to prove that the delay constraint of T is met during the recovery from burst erasures,
we need to consider only the burst erasures involving at least one of the coordinates [0, B −
N − 1]. It is enough to show that for any erasure burst of length B that starts at coordinate
i ∈ [0, B − N − 1], the code-symbol ci can be recovered with a delay of at most T .
If ci , where i ∈ [0, δ − 1], is part of a burst-erasure, we fall back on the proof of the
corresponding part in Proposition III.1 to see that delay conditions are met. In the following
we consider the case of i ∈ [δ, B − N − 1].
Consider an erasure burst which starts at i, where i ∈ [δ, B −N −1]. The symbols {ci+B , ci+2B ,
. . . , ci+(a−1)B , cT +i } will be non-erased. Let  be as defined previously. If  = 0, all the codesymbols in {caB , caB+1 , . . . , caB+δ−1 } will be known by the time (T + i). This follows from the
fact that all the symbols cT , cT +1 , . . . , cT +δ−1 are non-erased. After removing the interference
January 19, 2018

DRAFT

from known symbols at coordinates {i+B, i+2B, . . . , i+(a−1)B, aB, aB +1, . . . , aB +δ −1},
the code-symbol cT +i will yield ci .
For  > 0, we first note that, for a burst starting at coordinate i ∈ [δ, B − N − 1], a is
forced to be equal to 1. i.e., T = B + δ. From the max{δ − , 0} non-erased coordinates in
[T + , T + δ − 1], we can obtain code-symbols in the coordinate range [aB + , aB + δ − 1 =
T − 1]. Note that i = T − B +  = δ + . Number of non-erased coordinates in the range
[T + max{δ, }, T + i] = i − max{δ, } + 1. For each j ∈ [max{δ, }, i − 1], cj is a nonerased symbol. This follows from our assumption that, the error burst is starting at time i. For
j ∈ [max{δ, }, i], cT +j , cj + γj,0 cB + γj,1 cB+1 + . . . + γj,δ−1 cB+δ−1 (as a = 1). After removing
the known symbols from the coordinate range [B + , B + δ − 1] and [max{δ, }, i − 1], we have
the resultant sums:

ĉT +j =




γj,0 cB + γj,1 cB+1 + . . . + γj,min{,δ}−1 cB+min{,δ}−1 if max{δ, } ≤ j ≤ i − 1,

 cj + γj,0 cB + γj,1 cB+1 + . . . + γj,min{,δ}−1 cB+min{,δ}−1 j = i.

For the i − max{δ, } = δ +  − max{δ, } = min{δ, } equations in the range max{δ, } ≤
j ≤ i − 1, there are that many unknowns. As γx,y ’s are carefully chosen to be part of a
Cauchy matrix, these equations can be solved (at time (T + i − 1)) to obtain the code-symbols:
{cB , cB+1 , . . . , cB+min{,δ} }. Thus at time (T + i), the contribution from these code-symbols can
be removed from ĉT +i to obtain ci . This completes the proof.
R EFERENCES
[1] 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.
[2] 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.
[3] Z. Li, A. Khisti, and B. Girod, “Correcting erasure bursts with minimum decoding delay,” in Proc. Asilomar Conference
on Signals, Systems and Computers, 2011, pp. 33–39.
[4] Ö. F. Tekin, T. Ho, H. Yao, and S. Jaggi, “On erasure correction coding for streaming,” in Proc. Information Theory and
Applications Workshop, 2012, pp. 221–226.
[5] D. Leong, A. Qureshi, and T. Ho, “On coding for real-time streaming under packet erasures,” in Proc. Int. Symp. Inf.
Theory, 2013, pp. 1012–1016.
[6] 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.
[7] S. L. Fong, A. Khisti, B. Li, W. Tan, X. Zhu, and J. Apostolopoulos, “Optimal Streaming Codes for Channels with Burst
and Arbitrary Erasures,” arXiv preprint arXiv:1801.04241, 2018.

DRAFT

January 19, 2018

[8] E. Martinian and M. Trott, “Delay-Optimal Burst Erasure Code Construction,” in Proc. Int. Symp. Inf. Theory.

IEEE,

2007, pp. 1006–1010.
[9] H. Gluesing-Luerssen, J. Rosenthal, and R. Smarandache, “Strongly-MDS convolutional codes,” IEEE Trans. Inf. Theory,
vol. 52, no. 2, pp. 584–598, 2006.
[10] A. Badr, A. Khisti, W. Tan, and J. G. Apostolopoulos, “Streaming codes for channels with burst and isolated erasures,” in
Proc. INFOCOM.

IEEE, 2013, pp. 2850–2858.

[11] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications.

New York, NY, USA: Cambridge

University Press, 1986.
[12] E. Gabidulin, “Theory of Codes with maximum rank distance,” Problems of Information Transmission, vol. 21, no. 7, pp.
1–12, 1985.
[13] R. M. Roth, Introduction to coding theory.

January 19, 2018

Cambridge University Press, 2006.

DRAFT

