M.Sc Thesis

M.Sc StudentSabbag Erez
SubjectLarge Deviations Performance of Zero-Delay Finite-Memory
Lossy Source Coded and Source-Channel Codes
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Neri Merhav


Zero-delay finite-memory (ZDFM) codes are used for lossy data compression in numerous applications. ZDFM codes are causal codes with the additional property that the lossless source encoder is causal too. This extra property enables the use of these codes in applications where the decoding must be done instantaneously, with no delay. While these codes have been studied to considerable depth under the average rate-distortion performance criterion, much less work has been carried out from the viewpoint of the large deviations performance criterion, namely, source coding exponents. This work is an extension and further development of a recently published work by Merhav and Kontoyiannis which dealt with ZDFM codes for memoryless sources.  

In the first part of the work, we investigate the performance of ZDFM codes for Markov sources under the large deviations performance criterion. Performances of these codes are studied in two different regimes: the fixed-rate regime and the fixed-slope regime.  For the fixed-rate regime, probability of excess distortion is considered while the total rate is fixed. Upper bound is proposed on the source-coding exponent, where this bound represent the source-coding exponent of a code with perfect past side information. It is shown that for this class of codes, encoders whose memory size corresponding to the Markov order of the source are at least as good as any finite memory codes. A procedure is proposed for designing a sequence of encoders (with perfect past side information) having source-coding exponent arbitrarily close to the proposed upper bound.

In the fixed slope regime, a similar treatment is given, for a linear combination of code-length and distortion. The source-coding exponent is investigated and upper bounds are given in the spirit of the fixed rate regime.

The second part of the work deals with the problem of joint source-channel coding.

Using the same techniques used in the first part, it is shown that ZDFM encoders with memory size equals to the Markov order of the source are as good as any finite memory encoders.