Timeliness in Lossless Block Coding
Jing Zhong and Roy D. Yates

arXiv:1802.09167v1 [] 26 Feb 2018

WINLAB, ECE Department
Rutgers, the State University of New Jersey
{jzhong, ryates}@winlab.rutgers.edu

Abstract—We examine lossless data compression from an
average delay perspective. An encoder receives input symbols
one per unit time from an i.i.d. source and submits binary
codewords to a FIFO buffer that transmits bits at a fixed rate to
a receiver/decoder. Each input symbol at the encoder is viewed
as a status update by the source and the system performance is
characterized by the status update age, defined as the number of
time units (symbols) the decoder output lags behind the encoder
input. An upper bound on the average status age is derived from
the exponential bound on the probability of error in streaming
source coding with delay. Apart from the influence of the error
exponent that describes the convergence of the error, this upper
bound also scales with the constant multiplier term in the error
probability. However, the error exponent does not lead to an
accurate description of the status age for small delay and small
blocklength. An age optimal block coding scheme is proposed
based on an approximation of the average age by converting the
streaming source coding system into a D/G/1 queue. We compare
this scheme to the error exponent optimal coding scheme which
uses the method of types. We show that maximizing the error
exponent is not equivalent to minimizing the average status age.

I. I NTRODUCTION
In this era of ubiquitous connectivity and computing with
mobile devices, real-time status updates ensure that a monitor
(receiver) stays current about the status of interest of the
source. This requires the status updates to be as timely as
possible. In [1], [2], a new delay metric, the average status
age, was introduced to measure the end-to-end timeliness of a
status updating system. In the context of updates delivered
through queues, general expressions of the average status
age have been derived for single and multiple sources. In
[3], [4], [5], status age analysis has been also applied to
other communication systems, including random networks that
deliver packets out of order and multi-class queueing systems.
Many real-time data compression and communication systems with low latency requirements can be modeled as status
updating systems in which the applications require the source
to be reconstructed at the decoder in a timely manner. These
range from real-time video surveillance to remote telesurgery
[6]. The analysis of these timely compression and communication problems can be simplified to a real-time source coding
problem over a data network. The timely decoding of messages
at receiver must balance data compression delays against
network congestion deriving from insufficient compression.
Streaming source coding with a delay constraint was first
discussed in [7] and [8], in which the decoding error probability is bounded exponentially as a function of the delay

constraint. In [9], the error exponent analysis is generalized to
distributed streaming sources, and an achievable error exponent is obtained by fixed rate coding schemes using random
binning. Compared to this previous work, we are interested
in the following question: how timely can the streaming
source coding system be if we are allowed to choose any
lossless fixed-to-variable block coding scheme? We approach
this question by first connecting the status update age to the
error exponent in lossless streaming source coding. Although
the error analysis provides an upper bound on the timeliness
measure, we will see that maximizing the exponent does not
optimize the timeliness of decoded source messages.
In this work, we start in Section 2 with the system model
of lossless streaming source coding problem, and derive an
expression of average status age in lossless block coding
schemes. In Section 3, we show the upper bound of the
average status age as a function of the error exponent. We
use an example of block coding scheme to demonstrate how
the constant term in the error probability leads to the difference
between the bound and the actual average status age. We then
propose a method to find the age-minimizing optimal block
coding scheme for average age in Section 4. We show in
Section 5 that this is generally differs from the error-exponent
maximizing coding scheme that uses the method of types. We
conclude with a summary of our work and possible future
extensions in Section 6.
II. S YSTEM M ODEL
The streaming source coding system introduced in [7] and
[8] is illustrated in Figure 1. We assume that the channel
between the encoder and decoder is a constant rate bit pipe
with zero propagation delay. Starting at time t = 1, discrete
memoryless source symbols with finite alphabet X arrive
at each time unit sequentially, so the source symbol Xi
arrives at time i. In this work, we focus on fixed-to-variable
length block coding schemes. The encoder groups every B
message symbols into a single block and maps entire blocks
into variable-length bit strings. The k th symbol block is Yk
such that Yk+1 = XkB+1 XkB+2 · · · X(k+1)B . The encoded
sequence is then fed into a first-in-first-out (FIFO) buffer,
which outputs one binary bit to the decoder through the
channel every 1/R seconds. If the buffer is empty, it outputs
a gibberish bit e independent of any codewords. In fixedto-variable length coding, the decoder is able to determine
whether the next received bit is a gibberish bit or not, since

Source Symbol
Generator

X1 X2 …
Lossless Encoder

1101…

X1 X2 …

bit pipe

FIFO

Decoder

Receiver
(Monitor)

Rate: R
Fig. 1. System diagram of streaming source coding controlled by the FIFO buffer.

coding can be expressed as
N
1 X
Qk ,
N →∞ BN

∆ = lim

1
N →∞ N

= lim

t
Fig. 2. Example of variation in status age at a receiver of streaming fixedto-variable length coding with blocklength B = 3.

the generation time of next symbol block is known to the
decoder [7].
When the decoder receives the prefix-free codeword, it
reconstructs the corresponding message block immediately.
The delivery time of the block Yk is denoted by Dk . Note
that all the message symbols contained in a single message
block are decoded at the same time and thus have the same
delivery times.
In the source coding problem, the status age is defined as
the age of the most recently decoded symbol from when that
symbol was generated. That is, if the most recently decoded
symbol at time t is Xi , which was produced by the source
at time i, the instantaneous status age is ∆(t) = t − i. We
observe that ∆(t) is a random process that varies in time with
the receiver’s reconstruction of the source. The time-average
status age of the coding system observed by the receiver is
given by
1
∆ = lim
T →∞ T

Z

In streaming block coding, the status age at time t is the
same as the age of the last symbol in the most recently decoded
block, since all symbols in the same block are decoded
simultaneously. Fig. 2 shows a sample realization of status
age, as a function of time, at the receiver. We observe that kB
is the arrival time of symbol block Yk at the input of encoder.
The age is a sawtooth function that increases linearly in time
in the absence of any symbol blocks and is reset to Dk − kB
at time Dk when symbol block Yk is decoded at the receiver.
Using the same approach as [1], the integration of the
sawtooth area is equivalent to the sum of disjoint polygon
areas Qk shown in Fig. 2. The average status age for block

k=1

B
.
2

(3)

B
.
(4)
2
Intuitively, the timeliness metric ∆ is translated into a end-toend average delay measure in block coding schemes. In (4)
the expected system time in a queue is given by the sum
∆ = E[T ] +

E[T ] = E[S] + E[W ],

(5)

where E[S] and E[W ] are the expected service time and
the expected waiting time. In streaming block coding, each
encoded bit takes 1/R time unit to be transmitted by the
FIFO buffer, thus the service time of the symbol block Yk
with corresponding binary code length Lk is Sk = Lk /R, and
E[S] = E[L]/R. Applying the upper bound for G/G/1 queue
in [10], the expected waiting is upper bounded by
E[W ] ≤

(1)

0

(Dk − kB) +

(2)

From a queueing perspective, we can view a block Yk as a
customer arriving at time kB and departing at time Dk . The
system time of this customer is Dk − kB. Since Dk ≥ kB,
the average status age is always lower bounded by B/2.
The interarrival times of customers are deterministic since
the interarrival time of symbol blocks is exactly the block
length B. As a result, the term E[Dk − kB] in (3) is the
expected system time that block Yk spends in the queue. Let
E[T ] , E[Dk − kB], for an arbitrary customer k when the
queue has reached steady-state. Thus,

T

∆(t) dt .

k=1
N
X

E[L2 ] − E2 [L]
.
2R(BR − E[L])

(6)

Thus the average status age is upper bounded by
∆≤

E[L2 ] − E2 [L]
E[L] B
+
+ .
2R(BR − E[L])
R
2

(7)

III. C ONNECTING S TATUS AGE TO E RROR E XPONENT
In [11], the traditional block coding error exponent is
generalized to a streaming source coding problem, and the
delay-constrained error exponent is introduced to describe
the convergence rate of the symbol-wise error probability as
a function of the decoding delay. At time n, the decoder
estimates the k th source symbol as x̂k (n), for all k < n.
A delay constrained error exponent Es (R) is said to be
achievable if and only if for all  > 0 and decoding delay

δ > 0, there exists a constant K < ∞ for a fixed-delay δ
encoder-decoder pair such that
Pr[x̂n−δ (n) 6= xn−δ ] ≤ K2

,

for all n > δ.
(8)

In a lossless block coding system, a symbol block is successfully decoded only after the entire encoded bit sequence
corresponding to that block departs from the FIFO buffer. An
error occurs at time n if some queueing delays cause some
encoded bits of the symbol n − δ to be still in the buffer. The
exponential convergence rate of error in delay δ comes from
the randomness of the lengths of encoded bit sequences.
Proposition 1: A block coding scheme with achievable error
exponent ES (R) has average status age ∆ satisfying
K 22ES (R)
, f (K, ES (R)).
(9)
∆ ≤ E (R)
(2 S
− 1)2
Proof of this proposition is shown in Appendix B. Despite the
fact that the constant K may vary for different ES (R), we
observe that as ES (R) → ∞, f (K, ES (R)) → K. This tells
us both the error exponent and the constant term K influences
the status age in a streaming coding system. Although the
exponent ES (R) provides a tight upper bound on the error
probability when the delay constraint δ is large enough, it does
not accurately describe the complicated error events when δ
is small. In the following discussion, we will use a prefix
block code example to show the effect of K and explain why
an exponential bound is sometimes not good enough for the
description of delay.
The following simple example was used in [11, Sec. 2.2.2]
to demonstrate a non-asymptotic error exponent result for a
prefix-free block code. Consider a source with alphabet size 3
and distribution PX (A) = a, PX (B) = PX (C) = (1 − a)/2,
where a ∈ [0, 1]. Assume the encoder has no information about
the source distribution, and chooses a block encoding strategy
with blocklength B = 2 as follows: It maps the block AA → 0
and all other blocks to 4-bit sequences led by a single 1, e.g.,
AB → 1000. This coding scheme is not adapted to the source
distribution, but it was shown to provide a convenient way
to obtain a closed form expression of the error probability. It
is also assumed that the channel rate is R = 3/2, meaning
that the FIFO buffer outputs 3 bits every 2 symbol periods.
The average age ∆ is finite if and only if the average length of
2
2
codeword is less than
)<
√ the channel rate BR, i.e. a +4(1−a
2
3. That is, a > 1/ 3 or q > 1/3 if we define q = a .
Compared to [11] that seeks an exponential upper bound for
the error probability, the calculation of (9) requires an exact
expression including the constant K. The error probability of
this coding system is upper bounded by

1,
0≤δ<1

3
Pe ≤ 1 − q + η −3/2 [q(1 − η)]2δ( 2 log2 η) , 1 ≤ δ < 3
 −9/2
3
η
[1 − q(1 − η 3 )]2δ( 2 log2 η) ,
δ≥3
(10)
q
4(1−q)
−1+ 1+ q

where η =
. The detailed procedure to obtain
2
Pe is described in Appendix B.

Upper Bound from Error Exp.
Upper Bound on D/G/1 Queue
Numerical Simulation

25

Average Status Age

(−δES (R)−)

30

20

15

10

5

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Offered Load: H(X)/R

Fig. 3. Sample average age for prefix block code with blocklength B = 2.

We observe in (10) that the achievable error exponent that
satisfies (8) is − 23 log2 η. However, the exponential bound is
loose for small delay, specifically 0 ≤ δ < 3. Intuitively,
the decoder is still waiting for the binary codeword when
0 ≤ δ < 1, so the probability is always upper bounded by
1 for any decoding strategy; when 1 ≤ δ < 3, the decoder
can successfully recover the message if the codeword is 0
and the buffer delivers this bit no later than δ; when δ ≥ 3,
we have the most general case that can be described by
the exponential bound. The error exponent analysis usually
requires δ to be large enough, but the accumulation of average
age also counts small values of δ that lead to large probability
of error. Following the steps of the proof of Proposition 1 in
Appendix A, we express the upper bound on the average status
age as


3
5
2η
2
2
∆ ≤ 8 − 3q 1 − η + η +
3
−2ES (R)
3K2
K2−ES (R)
+ E (R)
+ E (R)
,
(11)
2 S
−1
(2 S
− 1)2
where K = η −9/2 [1 − q(1 − η 3 )] is the constant term from
the exponential bound when δ ≥ 3 in (10).
Figure 3 depicts a comparison among the numerical simulation of average age, the upper bound obtained from D/G/1
queue in (7) and the upper bound obtained from error exponent
in (11). In this plot, the channel rate R is fixed
√ at 3/2, and the
symbol probability a is varied within (1/ 3, 1] such that the
entropy H(X) is also varied. The sharp transition effect occurs
as the offered load of the system approaches 1 for all curves.
This is because the average codeword length approaches R,
and the number of bits queued in the FIFO buffers becomes
unbounded. This effect occurs earlier than H(X)/R = 1 since
the coding scheme is not adapted to the source distribution. We
observe that the bound obtained from D/G/1 waiting time (7)
is tight to the true simulation, while the delay-constrained error
exponent provides only a loose characterization of status age
in a block coding system. As a → 1, i.e. H(X) → 0, the upper
bound obtained from error exponent (11) is dominated by the
constant terms come from the sum of high error probabilities
in the small δ region.

IV. AGE O PTIMAL B LOCK C ODE

C1(Huffman)

A block coding scheme is age-optimal if it minimizes
the average status age for a given B and R. Since the
bound in (7) is simple and reasonablly tight, we use it as
an approximation of the average status age and treat it as a
penalty function with respect to variable L. Figure 4 depicts
a graphical representation of all the possible codebooks in
the two dimensional space constructed by E[L] and E[L2 ].
It is proved in [12] that the set of all possible codebooks
forms a convex hull for block coding schemes, and a linear
approximation algorithm is introduced to iteratively search all
code trees lying on the lower left boundary of the convex hull.
The non-linear penalty function in (7) is approximated by a
linear function

C2
C3
decreasing age

Fig. 4. The illustration of convex hull algorithm and the representation of
code trees in the coordinate.

f (L) = α E[L] + β E[L2 ],
and it is assumed there is an efficient algorithm
Find best(α, β) which returns the codebook that minimizes
the penalty function f (L) given any α, β ∈ [0, 1]. The
algorithm starts from two extreme cases: (α, β) = (1, 0) and
(α, β) = (0, 1). Note (α, β) = (1, 0) is the penalty function
that returns a code C1 that is a Huffman code. Furthermore,
(α, β) = (0, 1) returns the minimum second moment code
C2 . Given any two codebooks C1 and C2 , new values are
assigned to α and β as follows:
α0 = E[L2 ](C1 ) − E[L2 ](C2 )

(12)

β 0 = E[L](C2 ) − E[L](C1 ).

(13)

Afterwards, Find best(α0 , β 0 ) is called to search for a possible
codebook between the points of C1 and C2 . Intuitively, this
operation works as follows: we first draw a line segment l that
connects the points C1 and C2 , and then Find best identifies
the lowest line l0 parallel to l that meets the boundary of the
convex hull of all codebooks. If l0 lies below l, then l0 contains
at least one new codebook C3 . This step repeats iteratively by
renewing the value of α and β at each step for the C1 − C3
and C3 − C2 line segments, until we find all the feasible code
trees. A detailed description of the algorithm can be found in
[12].
Then the problem becomes how to efficiently return the best
codebook given a linear penalty function f (L). In [13], it is
shown that the problem of source coding for linear penalties
can be reduced to a coin collector’s problem, and a recursive
Package-Merge algorithm is introduced to solve the problem
in linear time.
Figure 5(a) depicts a numerical example of the average age
using age optimal code with different blocklength B. We use
the three symbols A, B, C with P (A) = 0.6, P (B) = 0.3 and
P (C) = 0.1. And the channel rate R is varied above H(X)
to vary the offered load. When R is large compared to H(X),
the average age grows almost linearly with the blocklength B.
Encoding with large blocklength is a losing proposition, since
what we gain by reducing the output rate of the encoder is
forfeited because the delay of the system is dominated by long
interarrival times of large blocks. Hence, the optimal strategy

in the high FIFO rate region is to choose the smallest possible
blocklength B. In contrast, as R decreases, the sharp transition
effect occurs earlier for smaller B since the corresponding
average code length is larger. Since the redundancy of block
coding decays with the blocklength B, the threshold of the
= 1 as B increases. We say that B
transition approaches H(X)
R
is a valid blocklength for rate R if and only if R is larger than
the code rate using blocklength B. In this region of transition,
it is complicated to obtain the optimal blocklength analytically.
V. C OMPARISON TO O PTIMAL E RROR E XPONENT C ODE
It is shown in [11] that the optimal error exponent ES (R)
can be achieved by a prefix-free block coding scheme that uses
the method of types. For a message block of length B, the
encoder first describes the type of the message block τ using
O(|X | log2 B), then represent the index of the realization
within this type by BH(τ ) bits, where H(τ ) is the entropy
of the type.
Figure 5(b) compares our age-optimal code to the coding
scheme using method of types. We use the same source
distribution as in Section 4 with blocklength B = 3. In this
example, we observe that the age optimal code outperforms
Huffman code when the offered load is high, implying that
Huffman code is nearly optimal in the low load region.
Although the type coding scheme achieves the largest error
exponent, it gives slightly larger average status age compared
to the other two block coding schemes. This is because
the type coding is asymptotically optimal in error, but the
minimization of average age requires us to choose small
blocklength since the term B/2 dominates in (3) when the
channel rate R is much larger than the source entropy H(X).
VI. C ONCLUSION AND F UTURE W ORK
We applied the status age analysis to a real-time lossless
source coding system in which source symbols are encoded sequentially and sent to an interested recipient through an errorfree channel, and showed that the timeliness metric is strongly
connected to the end-to-end delay of the coding system. We
connected the average age to the source coding error exponent
with delay and discussed why the error exponent does not

10
9
8

Average Status Age

(8) becomes too complicated when the blocklength gets large.
Nevertheless, in practical settings of high speed networks,
techniques for handling large blocklengths will be needed.
Similarly, sources with memory and age-optimized universal
coding schemes also merit attention. Finally, this work has
shown that optimal real-time compression over a network
depends strongly on the available network resources, even
if the network is just a fixed-rate bit pipe. More realistic
scenarios with shared network resources are also likely to be
a rich source of unsolved problems.

B=4
B=3
B=2

7
6
5
4
3

A PPENDIX

2

A. Proof of Proposition 1

1
0

0

0.2

0.4

0.6

0.8

1

Offered Load: H(X)/R

Dk = min{t|x̂k (n) = xk , for all n ≥ t }.

(a)
6

Average Status Age

5

(14)

Using the fact that Dk − k only takes non-negative integer
values, the differential time of the k th symbol in the coding
system can be written as

Method of Types
Huffman Code
Age Optimal Code

5.5

For any lossless coding schemes, the delivery time Dk in
(3) can also be defined as

4.5

E[Dk − k] =

4
3.5

=

∞
X
t=0
∞
X

3

t=0

2.5

∞
X

=

2

Pr[Dk − k > t]
Pr{∃x̂k (n) 6= xk , for some n ≥ t + k}



[

Pr

t=0

xk (n) 6= xk .

(15)

n≥t+k

1.5
1

0

0.2

0.4

0.6

0.8

1

Following from the union bound of all the possible error
events, we obtain

Offered Load: H(X)/R

(b)

E[Dk − k] ≤

∞ X
X

Pr[xk (n) 6= xk ].

(16)

t=0 n≥t+k

Fig. 5. Two numerical examples: (a) age optimal code with different
blocklength B. (b) comparison between age optimal block code and the
optimal error exponent code using method of types with blocklength B = 3.

describe the delay in a non-asymptotic setup. Exploiting the
quasi-linear property of the average age expression in block
coding, we also proposed the age optimal block coding scheme
that minimizes the average age. By comparing this scheme to
the optimal coding scheme for error exponent which uses the
method of types, we further showed that maximizing the error
exponent is not equivalent to minimizing the average status
age.
While we have focused here on toy examples, this work
is a starting point for the application of status age analysis
to real-time data compression. We examined how timely the
streaming source coding system can be using lossless block
coding schemes. We presented the connection between the
age and error exponent numerically for small block length
regime, although the asymptotic behavior remains unknown as
the blocklength becomes large. A primary reason is that the
exact expression of the constant K of the error probability in

Note that for any lossless block codes in a point-to-point transmission system controlled by FIFO buffer, the error probability
of the whole sequence is equivalent to the symbol-wise error
probability since a source symbol is decoded only after all
previous symbols were successfully decoded in advance. That
is, Pr[x̂k (n) 6= xk ] = Pr[x̂k (n) 6= xk ]. Using the upper bound
on the error exponent in (8), we have
E[Dk − k] ≤

∞
X
t=0

K

∞
X

2−δES (R) =

δ=t

K22ES (R)
. (17)
(2ES (R) − 1)2

B. Error Probability of Prefix Block Code Example.
Let Bk to be the number of bits in the buffer after the
transition at time 2k, then Bk forms a Markov chain since
the incoming codeword every two symbol time is either of
length 1 or length 4. That is, Bk+1 = Bk − 2 with probability
q = a2 , and Bk+1 = Bk + 1 with probability 1 − q. Note that
the boundary condition is Bk > 0. The stationary distribution
of Bk is obtained as
µj = Λη j ,

(18)

P
where Λ is the normalizer such that j≥0 µj = 1 and η =
q
− 12 + 12 1 + 4(1−q)
. Thus we rewrite µj = Λη j = η j −η j+1 .
q
The stationary distribution exists iff η < 1, requiring q ∈
( 13 , 1]. Denote Lk+1 as the next incoming codeword length
after the buffer state Bk , and βδ = b3(δ − 1)/2c. Following
the stationary distribution in (18), we can bound the symbolwise error probability using the outage probability of the buffer
and obtain
Pe ≤ Pr[Lk+1 = 1] Pr[Bk > βδ − 1]
+ Pr[Lk+1 = 4] Pr[Bk > βδ − 4]
=




1,
0≤δ<1
3
1 − q + η −3/2 [q(1 − η)]2δ( 2 log2 η) , 1 ≤ δ < 3
 −9/2
3
η
[1 − q(1 − η 3 )]2δ( 2 log2 η) ,
δ ≥ 3.
(19)
R EFERENCES

[1] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should
one update?” in Proc. INFOCOM, Apr. 2012, pp. 2731–2735.
[2] R. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in
Proc. IEEE Int. Symp. Inform. Theory, Jul. 2012, pp. 2666–2670.
[3] C. Kam, S. Kompella, and A. Ephremides, “Age of information under
random updates,” in Proc. IEEE Int. Symp. Inform. Theory, Jul. 2013,
pp. 66–70.
[4] M. Costa, M. Codreanu, and A. Ephremides, “Age of information with
packet management,” in Proc. IEEE Int. Symp. Inform. Theory, 2014,
pp. 1583–1587.
[5] L. Huang and E. Modiano, “Optimizing age-of-information in a multiclass queueing system,” in Proc. IEEE Int. Symp. Inform. Theory, Jun.
2015, pp. 1681–1685.
[6] S. Butner and M. Ghodoussi, “Transforming a surgical robot for human
telesurgery,” IEEE Trans. Robotics and Automation, vol. 19, no. 5, pp.
818–824, Oct. 2003.
[7] C. Cheng and A. Sahai, “The error exponent with delay for lossless
source coding,” in IEEE Inf. Theory Workshop, Mar. 2006, pp. 252–
256.
[8] C. Chang and A. Sahai, “Delay-constrained source coding for a peak
distortion measure,” in Proc. IEEE Int. Symp. Inform. Theory, 2007, pp.
576–580.
[9] S. C. Draper, C. Chang, and A. Sahai, “Lossless coding for distributed
streaming sources,” IEEE Trans. Inf. Theory, vol. 60, no. 3, pp. 1447–
1474, 2014.
[10] K. Marshall and R. V. Evans, “Some inequalities in queuing,” Operations
Research, pp. 651–668, 1968.
[11] C. Chang, “Streaming source coding with delay,” Ph.D. dissertation, UC
Berkeley, 2007.
[12] L. L. Larmore, “Minimum delay codes,” SIAM Journal on Computing,
1989.
[13] M. B. Baer, “Source coding for quasiarithmetic penalties,” IEEE Trans.
Inf. Theory, vol. 52, no. 10, pp. 4380–4393, 2006.

