Cheng Chang

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-164

December 19, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-164.pdf

Traditionally, information theory is studied in the block coding context --- all the source symbols are known in advance by the encoder(s). Under this setup, the minimum number of channel uses per source symbol needed for reliable information transmission is understood for many cases. This is known as the capacity region for channel coding and the rate region for source coding. The block coding error exponent (the convergence rate of the error probability as a function of block length) is also studied in the literature.

In this thesis, we consider the problem that source symbols stream into the encoder in real time and the decoder has to make a decision within a finite delay on a symbol by symbol basis. For a finite delay constraint, a fundamental question is how many channel uses per source symbol are needed to achieve a certain symbol error probability. This question, to our knowledge, has never been systematically studied. We answer the source coding side of the question by studying the asymptotic convergence rate of the symbol error probability as a function of delay --- the delay constrained error exponent.

The technical contributions of this thesis include the following. We derive an upper bound on the delay constrained error exponent for lossless source coding and show the achievability of this bound by using a fixed to variable length coding scheme. We then extend the same treatment to lossy source coding with delay where a tight bound on the error exponent is derived. Both delay constrained error exponents are connected to their block coding counterpart by a ``focusing'' operator. An achievability result for lossless multiple terminal source coding is then derived in the delay constrained context. Finally, we borrow the genie-aided feed-forward decoder argument from the channel coding literature to derive an upper bound on the delay constrained error exponent for source coding with decoder side-information. This upper bound is strictly smaller than the error exponent for source coding with both encoder and decoder side-information. This ``price of ignorance'' phenomenon only appears in the streaming with delay setup but not the traditional block coding setup.

These delay constrained error exponents for streaming source coding are generally different from their block coding counterparts. This difference has also been recently observed in the channel coding with feedback literature.

Advisors: Anant Sahai

---

BibTeX citation:

@phdthesis{Chang:EECS-2007-164,
    Author= {Chang, Cheng},
    Title= {Streaming source coding with delay},
    School= {EECS Department, University of California, Berkeley},
    Year= {2007},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-164.html},
    Number= {UCB/EECS-2007-164},
    Abstract= {Traditionally, information theory is studied in the block coding
context --- all the source symbols are known in advance by the
encoder(s). Under this setup, the minimum number of channel uses per
source symbol needed for reliable information transmission
is understood for many cases. This is known as the capacity region
for channel coding and the rate region for source coding. The block
coding error exponent (the convergence rate of the error probability
as a function of block length)  is also studied in the literature.

 In this thesis, we consider the problem that source symbols stream into
  the encoder in real time and the decoder has to make a
decision within a finite delay on a symbol by symbol basis. For a
finite delay constraint, a fundamental question is how many channel
uses per source symbol are needed to achieve a certain symbol error
probability. This question, to our knowledge, has never been
systematically studied. We answer the source coding side of the
question by studying the asymptotic convergence rate of the symbol
error probability as a function of delay --- the delay constrained
error exponent.

 The technical contributions
of this thesis include the following. We derive an upper bound on
the delay constrained error exponent for lossless source coding and
show the achievability of this bound by using a fixed to variable
length coding scheme. We then extend the same treatment  to lossy
source coding with delay where a  tight bound on the error exponent
is derived. Both delay constrained error exponents are connected to
their block coding counterpart by a ``focusing'' operator. An
achievability result for lossless multiple terminal source coding is
then derived in the delay constrained context. Finally, we borrow
the genie-aided feed-forward decoder argument from the channel
coding literature to derive an upper bound on the delay constrained
error exponent for source coding with decoder side-information. This
upper bound is strictly smaller than the error exponent for source
coding with both encoder and decoder side-information. This ``price
of ignorance'' phenomenon only appears in the streaming with delay
setup but not the traditional block coding setup.

These delay constrained error exponents for streaming source coding
are generally different from their block coding counterparts. This
difference has also been recently observed in the channel coding
with feedback literature.},
}

EndNote citation:

%0 Thesis
%A Chang, Cheng 
%T Streaming source coding with delay
%I EECS Department, University of California, Berkeley
%D 2007
%8 December 19
%@ UCB/EECS-2007-164
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-164.html
%F Chang:EECS-2007-164