Computation-distortion characteristics of block transform coding

A distortion-computation function D(C) is defined as the minimum expected distortion in computing some quantity while using no more than C computational units. In a communication framework, where the computational problem is to determine a representation that can be transmitted with expected rate not exceeding R, this gives slices of a rate-distortion-computation surface. The convexity of distortion-computation functions and rate-distortion-computation surfaces is asserted. Transform coding is studied as a particular instance of this theory. Explicit comparisons between the efficacies of the Karhunen-Loeve transform and the discrete cosine transform for coding of a Gauss-Markov source are given. Results are also given on joint optimization of the block length and the computational precision