A SIMPLE METHOD FOR CALCULATING THE RATE-DISTORTION FUNCTION OF A SOURCE WITH AN UNKNOWN PARAMETER

The rate distortion function R(D) measures the minimum information rat e of a source required to be transmitted at a fidelity level D. Althou gh Blahut developed an elegant algorithm to calculate R(D) for discret e memoryless sources, computing R(D) for other types of sources is sti ll very difficult. In this paper, we study the computation of R(D) for discrete sources with an unknown parameter which takes values in a co ntinuous space. According to the well known ergodic decomposition theo rem, a non-ergodic stationary source can be represented by a class of parameterized ergodic subsources with a known prior distribution. Base d on this theory, a source matching approach and a simple algorithm is presented for computational purposes. The algorithm is shown to be co nvergent and efficient. In order to see the performance of this simple algorithm, we consider a special class of binary symmetric first-orde r Markov sources which has been previously studied. R(D) is computed o ver this class of sources and compared with the bound developed in pre vious work by Gray and Berger. The example shows that the algorithm is very efficient and produces results close to Gray and Berger's bound. Other examples further demonstrate the efficiency of the algorithm.