Home
Theory
Lossless
VQ
Speech
Image
Download
Links

Data-Compression.com




Blahut Algorithm for Calculating the Rate-Distortion Function


Contents
  1. Introduction
  2. Algorithm
  3. Notes
  4. Reference

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 to .
 

II. Algorithm
 

  1. Input: .
  2. Initialization: .
  3. Calculate the following in order:
  4. If , go back to Step 3. Otherwise go on to Step 5.
  5. Calculate the following in order:
  6. Stop.

 

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.

Home
Theory
Lossless
VQ
Speech
Image
Download
Links

Support the EFF
Coding is Not a Crime

Copyright © 2000-2017. All rights reserved.