Ph.D Thesis

Ph.D StudentKaspi Yonatan
SubjectLimited Delay Source Coding in the Presence of Side
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Neri Merhav


The classical source coding theorems and their converse counterparts provide fundamental limits which are usually asymptotic in the sense that they can be achieved by systems that introduce delay and/or require complexity that grows exponentially. In many practical scenarios, however, delay is not tolerable. The focus of this work is on the fundamental limits achievable by systems with small or zero delay. The research unifies two active research areas: the problem of delay and complexity constrained information theory and that of coding in the
presence of side information (SI).

We start with the design of real-time variable-rate lossy coding systems for Markov sources where the decoders are finite-state devices. The general encoders use the whole history to compute their output. We show that there is no loss if attention is confined to encoders with a state space of the same size as decoder (fixed complexity). Furthermore, we derive upper bounds on the loss incurred by using sub-optimal, shift register state as compared to the use of the optimal next state functions whose optimization is prohibitively complex.

We continue with considering zero-delay single-user and multi-user source coding with average distortion constraint and decoder side information. The zero-delay constraint translates into causal (sequential) encoder and decoder pairs as well as the use of instantaneous codes. For the single-user setting, we show that optimal performance is attained by time sharing at most two scalar encoder-decoder pairs that use zero-error side information codes. Furthermore, we show that even without delay constraints, if either the encoder or decoder are restricted a-priori to be scalar, the performance loss cannot be compensated by the other component. Finally, we show that the multiterminal source coding problem can be solved in the zero-delay regime.

In the last part of this work, we consider zero-delay secure source coding. Our system is composed of an encoder, a legitimate decoder and an eavesdropper, traditionally referred to as Alice, Bob and Eve respectively. Alice and Bob share a secret key with which they encrypt the transmission and the goal is to find the tradeoffs between the rate of transmission and the key rate for both lossless and lossy secure transmission. We investigate two models of eavesdroppers: a strong eavesdropper that can parse the bit-stream passing from Alice to Bob into the separate messages and a weaker one that. We also obtain new results for the less constrained causal setting where delay is allowed.