The computation and bounding of rate-distortion functions

Methods are given for the numerical computation of Shannon\´s rate-distortion function for certain memoryless message sources. It is first assumed that , the set of possible message-source outputs, and , the set of possible destination symbols, are countable. The computation of for this case is reduced to a minimization problem in which the variables are the destination-symbol probabilities. For arbitrary and , upper and lower bounds on are derived by partitioning and each into a countable collection of disjoint subsets and employing the results derived previously for the case of countable and . Conditions are then discussed under which these bounds can be made arbitrarily close to each other by choosing sufficiently fine partitions of and . Two examples are included to illustrate the results in detail.