Non-equilibrium information envelopes and the capacity-delay-error-tradeoff of source coding

This paper establishes a link between information and queueing theory using an envelope-based approach. Unlike classical, equilibrium information theory, information envelopes focus on the dynamics of sources and coders, using functions of time that bound the number of bits generated. In the limit the information envelopes converge to the expected value and recover the entropy of a source, respectively, the average codeword length of a coder. In contrast, on short time scales and for sources with memory it is shown that large deviations from known equilibrium results occur with non-negligible probability. These can cause significant network delays. Using results from the stochastic network calculus, the envelopes yield a characterization of the operating points of source coders by the triplet of capacity, delay, and error. In the limit, assuming an optimal coder the required capacity approaches the entropy with arbitrarily small probability of error if infinitely large delays are permitted. We derive a corresponding characterization of channels and prove that the model has the desirable property of additivity, that allows analyzing sources and channels as if in isolation.