Estimation of Mean Error for a Discrete Successive-Approximation Scheme

The article investigates coding of discrete memoryless sources by the successive-approximation method. A coding theorem is proved and a generalized Omura bound [IEEE Trans. Inf. Theory, 1973, vol. 19, no. 4, pp. 490–497] is derived for the mean error of the last step of the approximations. The results are applied to a special narrow class of additive approximation schemes. The question of investigating the complexity of the latter is raised.