
Blahut Algorithm for Calculating the RateDistortion Function
Contents

Introduction

Algorithm

Notes

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
 Input: .
 Initialization: .
 Calculate the following in order:
 If , go back to Step 3.
Otherwise go on to Step 5.
 Calculate the following in order:
 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 continuousalphabet source, Blahut algorithm may be used to
approximate the curve. This can be done by first approximating
the source using a highrate scalar quantizer and then calculating the
curve of the quantized source.
IV. Reference

R. E. Blahut, ``Computation of Channel Capacity and RateDistortion
Function,'' IEEE Transactions on Information Theory, Vol. 18, No. 4,
pp. 460473, July 1972.
