An approximate theory of prediction for data compression

This paper presents results applicable to data-compression systems of the prediction-comparison type. In this type of system advantage is taken of the inherent predictability of the data. Any sample which can be predicted to within some threshold is not transmitted and the prediction is inserted in place of the actual sample in the data. This error feedback affects data predictability in a nonlinear fashion resulting in a difficult theoretical problem. In this paper the probability of prediction is given asymptotically as the error threshold goes to zero for a stationary Gaussian time series using linear prediction. The effect of error feedback is shown to be of prime significance. A comparison is made between the optimum open-loop predictor, the optimum closed-loop predictor, and a polynomial approximation. It is shown that the optimum closed-loop system is significantly better than the other two. Computer simulations confirm the theoretical results.