Optimal Lossless Source Codes for Timely Updates - Himanshu Tyagi скачать в хорошем качестве

Optimal Lossless Source Codes for Timely Updates - Himanshu Tyagi

JTG/IEEE IT Society Summer School on Information Theory, Signal Processing, Communications and Networks, IIT Bombay, 2-5 July, 2018 https://www.ee.iitb.ac.in/jtg18/ Optimal Lossless Source Codes for Timely Updates Himanshu Tyagi (joint work with Prathamesh Mayekar and Parimal Parag) Indian Institute of Science, Bangalore ISIT 2018 student paper award winning work! https://ieeexplore.ieee.org/document/... A transmitter observing a sequence of independent and identically distributed random variables seeks to keep a receiver updated about its latest observations. The receiver need not be apprised about each symbol seen by the transmitter, but needs to output a symbol at each time instant t. If at time t the receiver outputs the symbol seen by the transmitter at time U(t) ≤ t, the age of information at the receiver at time t is t − U(t). We study the design of lossless source codes that enable transmission with minimum average age at the receiver. We show that the asymptotic minimum average age can be attained (up to a constant bits gap) by Shannon codes for a tilted version of the original pmf generating the symbols, which can be computed easily by solving an optimization problem. Underlying our construction for minimum average age codes is a new variational formula for integer moments of random variables, which may be of independent interest.