Blahut Algorithm for Calculating the Rate-Distortion Function

Info on Grad Schools:

Buy Books, CDs, & Videos:

Digital Camera:

Rio MP3 Player:

Memory Upgrade:

$1.23 per issue:

Ebay Auction:

$1.83 per issue:

Blahut Algorithm for Calculating the Rate-Distortion Function

Contents

I. Introduction
Given a discrete memoryless source with probability mass function

and a distortion measure

Choose a negative number

and small positive number

The following is Blahut Algorithm for calculating the point on the

curve with slope

represents the accuracy of

. In the algorithm, the indices

and

are integers ranging from

II. Algorithm

III. Notes

It is recommended that you select according to: where and is the number of points on the curve which you wish to calculate. You need to experiment with these three parameters.
Setting is recommended. The calculated value of is accurate up to .
It is possible to generalize the algorithm to the case where the reproduction alphabet is different from the source alphabet. In that case, just change the range of from through to through , where .
There is a minor error in Fig.3 of Blahut's paper. A negative sign is missing from and . This adversely affects Step 4 of the algorithm.
For a continuous-alphabet source, Blahut algorithm may be used to approximate the curve. This can be done by first approximating the source using a high-rate scalar quantizer and then calculating the curve of the quantized source.

IV. Reference

R. E. Blahut, ``Computation of Channel Capacity and Rate-Distortion Function,'' IEEE Transactions on Information Theory, Vol. 18, No. 4, pp. 460-473, July 1972.