Metric bounds on losses in adaptive coding (Q1091348)

A noiseless-channel coding system in which the source probabilities change continuously in time is introduced. Using a geometry defined by the second derivative matrix of the information-theoretic entropy function, a bound on the number of excess channel symbols (the redundancy) sent by a retrospective encoder during a fixed time interval is derived. Results on minimal-cost coding and their implications for a real-time coding algorithm are then explored. Underlying most of the discussion here is the assumption made on the separability of the time scales corresponding to the (high) character rate as compared with the rate of change of the source probabilities.