Transform Coding - Introduction to Data Compression - page 423

a relationship between λ , the distortion, and the rate, we can develop an algorithm to find the

λ that will result in the desired rate.

Let's take another look at the unconstrained problem proposed by Shoham and Gersho in
the context of our bit allocation problem. Define

( ) =

D i ( R i )

( ) =

D B and R B R i

i i

where R i is the number of bits allocated to the coefficient is the corresponding

distortion. The function for the unconstrained minimization problem then becomes

θ i and D i ( R i )

J = D i ( R i ) + λ R i

i i

Taking the derivative of this function with respect to the bit allocation for the j th coefficient
R j for j = 1 , 2 ,... N , we obtain

∂

R j = ∂

J D j ( R j )

+ λ j = 1 , 2 ,... N

∂ ∂ R j

Setting this equal to zero for all j , we obtain

∂ D j ( R j )

=− λ j = 1 , 2 ,... N (60)

∂ R j

This is an interesting result with several consequences. It provides us with an explanation
for what represents. The left side of Equation ( 60 ) is the derivative of the distortion-rate

function for the j th coefficient. Thus

λ

λ

is simply the negative of the slope of the distortion-rate
function for the j th coefficient. This equation also indicates that for an optimal bit allocation,
this slope of

− λ is identical for each coefficient. Thus for the optimum bit allocation for each

coefficient θ j we should pick a rate R j at which point the slope of the rate-distortion function

for θ j is exactly the same as the slope for the distortion-rate function for all other coefficients

θ i , i

j .
We can easily show this latter result that the slopes of the distortion-rate functions at the
operating rates for an optimum bit allocation have to be the same for each coefficient. Consider
the case of a transform with two coefficients. Let's suppose that the optimum bit assignment
(

=

for a rate constraint R b results in distortions D 1 and D 2 and, contrary to our assertion
above, that the slopes

R 1 , R 2 )

R 1 , D 1 ) R 2 , D 2 )

− λ 1 and − λ 2 at ( and ( are not the same. Without loss

of generality, we can assume . Because these

are the optimum bit assignments, any change in these assignments should lead to a decrease
in the total distortion. Let's check to see if this is actually true. Let's increase R 1 by an
arbitrarily small amount

λ 1 <λ 2 , and we can define λ 1 = λ 2 − λ

is
very small, we can approximate the distortion-rate function with the first term of the Taylor
series expansion of the distortion-rate function and represent the decrease by D 1 − λ 1

> 0. This will result in a decrease in the distortion. As

.Ifwe

increase R 1 by , the total rate R 1 + R 2 . In order to keep the total number of

bits the same, the bit assignment R 2 has to be decreased by

increases by

. This will increase the distortion

for the second coefficient by an amount equal to λ 2 . Thus the new total distortion will be