In classical rate-distortion formulation, the aim is to represent a source with a fidelity criterion given a rate constraint. This fidelity criterion is measured with a distortion metric that assigns costs to misrepresented symbols in the reconstruction. It is known that the best rate-distortion tradeoff can be achieved at large blocklengths. However, this implies that the reconstruction is received late. Therefore, timely reconstruction of the source is an aspect not directly addressed in classical rate-distortion theory. Inspired by this observation, we formulate a setup to examine timeliness-vs-distortion tradeoff: We consider a discrete-time model where each packet has a cost of not being sent depending on its content. The model consists of a sender-receiver pair, where the packet rate is limited by an external scheduler. Whenever the sender is allowed by the scheduler to send a packet, it must choose a packet from the past. At one extreme, if the sender always sends the freshest packet, valuable content may be discarded. At the other extreme, if the sender tries to send each and every packet, the cost is zero but the timeliness deteriorates. Thus there is a tradeoff between the cost and timeliness and we seek the optimal tradeoff when the sender is confined to packet-based strategies. We show that the optimal tradeoff can be attained with finite-memory strategies and we devise an efficient algorithm to find these optimal strategies. Lastly, we show that allowing coding across packets significantly improves the packet-based strategies when payloads are small.
Yunus Inan, EPFL
Yunus Inan received the B.S. degree in Electrical and Electronics Engineering from Bilkent University, Ankara, in 2018. He is currently pursuing the Ph.D. degree in computer and communication sciences under the supervision of Prof. Emre Telatar, in the Information Theory Laboratory (LTHI) at EPFL, Switzerland. His research interests are in communication and information theories.