Streaming Source Coding with Delay
Technical Report Identifier: EECS-2007-164
December 19, 2007
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.