M.Sc Thesis

M.Sc StudentReani Avraham
SubjectEfficient On-line Schemes for Encoding Individual Sequences
with Side Information at the Decoder
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Neri Merhav


We present adaptive on-line schemes for lossy encoding of individual sequences under the conditions of the Wyner-Ziv (WZ) problem, i.e., the decoder has access to side information whose statistical dependency on the source is known. Both the source sequence and the side information consist of symbols taking on values in a finite alphabet X. In the first part of this thesis, a set of fixed-rate scalar source codes with zero delay is presented. We propose a randomized on-line coding scheme, which achieves asymptotically (and with high probability), the performance of the best source code in the set, uniformly over all source sequences. The scheme uses the same rate and has zero delay. We then present an efficient algorithm for implementing our on-line coding scheme in the case of a relatively small set of encoders. We also present an efficient algorithm for the case of a larger set of encoders with a structure, using the method of the weighted graph and the Weight Pushing Algorithm (WPA). In the second part of this thesis, we extend our results to the case of variable rate coding. A set of variable rate scalar source codes is presented. We generalize the randomized on-line coding scheme, to our case. This time, the performance is measured by the Lagrangian Cost (LC), which is defined as a weighted sum of the distortion and the length of the encoded sequence. We present an efficient algorithm for implementing our on-line variable-rate coding scheme in the case of a relatively small set of encoders. We then consider the special case of lossless variable-rate coding. An on-line scheme which uses Huffman codes is presented. We show that this scheme can be implemented efficiently using the same graphic methods from the first part. Combining the results from former sections, we build a generalized efficient algorithm for structured set of variable-rate encoders. Finally, we show how to generalize all the results to general distortion measures. The complexity of all the algorithms is no more than linear in the sequence length.