Joint Optimization of Scale Factors and Huﬀman Code Books for MPEG-4 AAC
Claus Bauer, Mark Vinton;

Dolby Laboratories, 100 Potrero Ave., San Francisco, CA, 94103, {cb, msv}@dolby.com
Abstract—The MPEG-4 AAC audio encoder achieves low
bit rates by appropriately choosing the two encoding parameters Huﬀman Code Books and Scale Factors. Existing AAC
implementations solve the implied optimization problem using an heuristic Two Loop Search. This paper presents two
novel optimization techniques that for the ﬁrst time ﬁnd
optimal solutions for the AAC optimization problem.

I. Introduction
The future development and success of wireless andwired internet technologies depends on their ability to deliver multimedia content with an acceptable quality of service. Low bit rate coders such as MPEG-4 Advanced Audio
Coding (AAC) play a crucial role in achieving this goal.
The AAC coder achieves transparent perceptual qualities
at low bitrates by exploiting perceptual redundancies in thesignal. For this purpose, the AAC encoder partitions eachaudio frame into a number of bands and for each band dynamically allocates bits for the transform coeﬃcients. The
transform coeﬃcients and the side information are transmitted to the decoder. The main side information for AAC
are the Scale Factors (SF ) and the Huﬀman Code Books(HCB). These parameters are encoded diﬀerentially, suchthat the bit cost depends on the relation of the parametersat adjacent bands. To achieve a low bit rate encoding theencoder chooses the SF s and the HCBs such that the total
bit cost is below a given target rate, while ensuring that apredeﬁned objective measure for the perceptual quality ofthe decoded signal is satisﬁed. The inter-band relationshipof these parameters shows that their appropriate choice requires the solution of a complex optimization problem.
Two common perceptual quality measures are the average noise to mask ratio (ANMR) and the maximum noise
to mask ratio (MNMR). The standard MPEG-4 AAC procedure to solve this optimization problem is the Two Loop
Search (TLS) ([3]). The TLS uses an heuristic approachthat neglects the inter-band dependencies of the side information and thus simpliﬁes the problem signiﬁcantly by
optimizing the parameters independently for each band. In[1], [2], Aggarwal proposed a joint optimization of the encoding parameters. The problem is formalized as the minimization of the ANMR/MNMR subject to a constraint
on the total transmission bit cost. Using a Lagrangian
multiplier-based approach that penalizes any violation of
the target rate, the ANMR problem is modeled as a trellis search, where each path through the trellis corresponds
to a speciﬁc choice of the SF and HCB parameters. Thismethod does not guarantee an optimal solution of the joint
optimization problem. For the MNMR problem, an iterative Viterbi search is used, which always provides an optimal solution. In [7], the authors propose a less complex
version of the methods in [1], that perform nearly as wellas the original methods in [1].

0-7803-8578-0/04/$20.00 ©2004 IEEE

The main contributions of this paper are two novel optimization techniques that solve the ANMR problem optimally. We also show a new optimal solution method for the
MNMR problem. First, we develop a linear programming
technique that applies to both quality measures. Our second method uses a dynamic programming technique that
does not use a Lagrangian multiplier. This method applies
to the ANMR problem only. To derive our optimization
procedures, we give a mathematical model of the MPEG-4
AAC encoder that improves on the model used in [1].
Both the Trellis/Viterbi searches for the AN M R andM N M R problem in [2] as well as the dynamic programming based method proposed for the AN M R problem inthis paper are based on diﬀerent applications of dynamic
programming. To avoid confusion, we denote the methodsin [2] as Trellis Searches, whereas our method is called the
Dynamic Programming Method.
In the next section, we develop an analytic formulationof the problem under consideration. In sections III and IV,
we present two novel, optimal techniques to the problem
of determining the encoding parameters. In section V, we
present numerical results, and we conclude in section VI.
II. Problem definition
The AAC encoder converts the time domain signal into
the spectral domain using the modiﬁed discrete cosine
transform. The 1024 spectral coeﬃcients are grouped into
N scale factor bands SF Bi , 1 ≤ i ≤ N. Within the i-thband SF Bi , all coeﬃcients are quantized using the samescalar quantizer step size, which is controlled by the i-th
scale factor si selected from a range of M1 possible values,i.e., 1 ≤ si ≤ M1 . Also within SF Bi , the quantized coeﬃcients are entropy encoded using a Huﬀman Code Book hi
selected from a set of M2 possible values, i.e., 1 ≤ hi ≤ M2 ,.
We set S = {s1 , .., sN } and H = {h1 , .., hN }. Both the si
and hi are indexes into sets of pre-determined Scale Factors and Huﬀman Code Books, respectively.
The noise to mask ratio (N M R) ([5]), which is the ratio of
the quantization noise to the masking threshold ([8]), is themost widely used objective measure for the evaluation of
an audio signal. Two types of N M R are widely used ([6]):the Average N M R (AN M R) and the Maximum N M R(M N M R). To deﬁne both N M R types analytically, we
introduce the following notations: We deﬁne d(si ) as thequantization error of the i-th scale factor band if the i-th
scale factor is chosen equal to si . wi denotes the weighting
applied to the i-th scale factor band which is deﬁned as theinverse of the masking threshold (see [8]) of the i-th band.
The ANMR is then analytically expressed as the sum

111

1 
wi d(si ).
N i=1
NAN M R(S) :=(1)∀i, 1 ≤ i ≤ N − 1, 1 ≤ a ≤ 2M1 − 1,
1, if hi+1 − hi = b − M2 ,=0, else,∀i, 1 ≤ i ≤ N − 1, 1 ≤ b ≤ 2M2 − 1.

Using the same notation, the MNMR is expressed as
M N M R(S) :=max wi d(si ).

1≤i≤N

We now derive an analytic expression for the transmission rate. The transmission rate consists of three parts:• Qi (si , hi ) counts the bits required to encode the quantized coeﬃcients of the ith band with the SF value chosen
as si and the HCB value chosen as hi . According to the
MPEG-4 AAC speciﬁcation [4], Qi (si , 1) = 0 for all possible values of si . We note that the function Qi (si , hi ) is
also a function of the actual signal X., i.e., Qi (si , hi ) :=QX,i (si , hi ). In general, for any two diﬀerent signals X andY, QX,i (a, b) = QY,i (a, b). In the sequel, we consider a ﬁxed
signal only and therefore omit the index X.
• F (si−1 , si ) counts the number of bits required to specify
the SF for the ith band. As the SF are encoded diﬀerentially, we write F (si−1 , si ) := F (si−1 − si ).
• G(hi−1 , hi ) := G(hi − hi−1 ) counts the number of bits
needed to encode the HCB value of the i-th band.
We deﬁne the transmission rate R(S, H) as follows:
R(S, H) = Q1 (s1 , h1 ) +

N 


Bi,b

(2)

We deﬁne the variables Zi,a,b ∀i, 1 ≤ i ≤ N, ∀a, 1 ≤ a ≤M1 ∀b, 1 ≤ b ≤ M2 that describe which values are takenby the variables si and hi at the i-th stage:
1, if si = a hi = b,
Zi,a,b =0, else.
Finally, we deﬁne the variable ei,m as the weighted distortion that occurs at the i-th band if si = m, i.e.,ei,m = wi d(si = m), ∀1 ≤ i ≤ N, 1 ≤ m ≤ M1 . We
model the ANMR joint optimization problem as follows:
M inimize=

R(Z, A, B) ≤ Rt ,

≤ 30,

(8)

M1 
M2
N 


Zi,a,b Qi (a, b)(9)i=1 a=1 b=1
N
−1 2M

1

+

Ai,a F ∗ (a) +i=1 a=0F ∗ (a2 − a1 )G∗ (b2 − b1 )
2M
1 −1


(4)

i

N
−1 2M

2

Bi,b G∗ (b),i=1 b=0= F (M1 + a2 − a1 ),= G(M2 + b2 − b1 ),

(10)
(11)

Ai,a

= 1,

∀i, 1 ≤ 1 ≤ N − 1,

(12)

Bi,b

= 1,

∀i, 1 ≤ 1 ≤ N − 1,(13)

Zi,a,b= 1,∀i, 1 ≤ 1 ≤ N,

(14)

Zi+1,c+a−M1 ,d4 − 1,(15)

Zi+1,d6 ,d+b−M2 − 1,

(16)

a=1
2M
2 −1


1 ≤ i ≤ N − 30, 1 ≤ b ≤ M2 . This constraint has not been
considered in [1]. For a given rate threshold Rt and a distortion measure N M R(S) ∈ {AN M R(S), M N M R(S)},the joint optimization problem is then deﬁned as follows:
M inimizesuch that

(7)

where
(3)

The MPEG-4 AAC speciﬁcation [4] mandates that theencoder cannot choose the same HCB value at more than
30 successive SF Bs. We deﬁne the characteristic function
σ(i, b), where
 the argument
 i represents the i-th SF B, as
1 if hi = b,σ(i, b) =. Now, we write the constraint
0 else.
on the choice of the vector H asσ(i, b)M(8) and (12) − (17) are satisf ied :such that

R(Z, A, B) =

i+30


M

b=1

Qi (si , hi )i=2+F (si−1 − si ) + G(hi−1 − hi ) .

1 
2
1 
ei,a Zi,a,b
N i=1 a=1

N

AN M R(Z) :N M R(S)
R(S, H) ≤ Rt ,(4) is satisf ied.

b=1
M2
M1 

a=1 b=1(5)(6)

Ai,a ≥

M2
Zi,c,d3 +d3 =1III. An optimal solution based on mixed integer
linear programming (MILP)

Bi,b ≥

A. MILP formulation for the ANMR problem

M1


d4 =1

Zi,d5 ,d +d5 =1

We introduce the variable Ai,d1 that is set equal to 1 if
si − si+1 = d1 − M1 , and is set equal to zero otherwise.
Similarly, the variables Bi,d2 describe the diﬀerence of thevalues hi and hi+1 . Thus, we deﬁne
1, if si+1 − s1 = a − M1 ,Ai,a =
0, else,

M2


M1

d6 =1

for 1 ≤ i ≤ N − 1, 1 ≤ a ≤ 2M1 − 1, 1 ≤ b ≤ 2M2 −1, max(1, 1 + M1 − a) ≤ c ≤ min(M1 , 2M1 − a), max(1, 1 +M2 − b) ≤ d ≤ min(M2 , 2M2 − b).

112

30

≥

M1
i+30

i

a=1

Zi,a,b ,(17)∀i, 1 ≤ i ≤ N −30, ∀b, 1 ≤ b ≤ M2 . The variables Zi,a,b are
required to be non-negative integers and the variables Ai,aand Bi,b are required to be non-negative real numbers.
We ﬁrst show that the variables Zi,a,b , Ai,a , and Bi,bconsistently express the choice of the SF and HCB values
at all SF Bs. The equation (14) ensures that for each bandi, exactly one variable Zi,a,b is equal to 1, whereas all theother variables are equal to zero, i.e., exactly one SF andone HCB are chosen per band. For ﬁxed values of thevariables Zi,a,b , the equations (12) and (15) ensure that if
si+1 − s1 = a − M1 , then Ai,a = 1 and all other Ai,a = 0 as
required by the deﬁnition of Ai,a . The equations (13) and(16) imply the analogous relation for the variables Bi,b .
By the deﬁnition of the variables Zi,a,b , the condition (4)is modeled by the equation (17). Also, the deﬁnitions of
the variables Zi,a,b and ei,m , show that the deﬁnitions of
the objective function in (7) and (1) are identical.
The functions F ∗ (n) and G∗ (n) are identical to the function F (n) and G(n) with the argument shifted by M1 andM2 , respectively. The shifts have been introduced in order
to avoid negative variables in the MILP formulation. Thus,
the expressions (3) and (9) are identical.
The MILP formulation is solved using the Simplex
method and then applying a branch and bound method
for the integer solution. The variables Ai,a and Bi,b are
not explicitly required to be integer, but their integrity isachieved via the relations (12) and (15) and the relations(13) and (16), respectively. This decreases the complexity
for the branch and bound algorithm.

(s1 , h1 ) in the ﬁrst stage SF B1 as Q1 (s1 , h1 ), we see thatthe cost of the path (s1 , h1 ), ...., (sN , hN ) through the trellisN
is Q1 (s1 , h1 ) +Qi (si , hi ) + F ∗ (si−1 − si ) + G∗ (hi−1 −
i=2hi ). This expression is identical to the expression for thetransmission rate in (9). Thus, the solution of the problem(5) or (7) - (17) is equivalent to ﬁnding a path throughthe trellis that minimizes the distortion associated withthis path under the constraint that the cost of the pathis below a given threshold Rt . As the solution algorithm
described below is based on dynamic programming, thenon-local condition (4) is not taken into account. We now
deﬁne an algorithm to determine the cheapest path throughthe trellis:
1. For each integer y, 0 ≤ y ≤ Rt , and each state (s2 , h2 ) ∈SF B2 , we ﬁnd a path from SF B1 to SF B2 , the cost of(s ,h )
which is deﬁned as f2 2 2 (y). It is deﬁned as(s ,h2 )

f2 2

M2
M1 


p

(19)
2. For the i-th band SF Bi , 3 ≤ i ≤ N, do the following:
For each point (si , hi ) ∈ SF Bi and each integer y, 0 ≤ y ≤Rt , set(s ,hi )fi i∀i, 1 ≤ i ≤ N.

(s

i−1
fi−1

,hi−1 )(y − S(si−1 , hi−1 , si , hi )),whereS(si−1 , hi−1 , si , hi )= Qi (si , hi ) + F ∗ (si−1 − si ) + G∗ (hi−1 − hi ).

,(8) and (12) − (18) are satisf ied :≤p ,(y) = wi d(si ) +(si−1 ,hi−1 )∈SF Bi−1

3.
ei,a Zi,a,b

w1 d(s1 )Q1 (s1 , h1 ) + Q2 (s2 , h2 ) + F ∗ (s1 − s2 ) + G∗ (h1 − h2 ) ≤ y.

min

We deﬁne the variable p as the maximum weighted noise
to mask ratio of all bands, i.e., p = max1≤i≤N wi d(si ). The
MNMR problem is modeled as follows:min(s1 ,h1 )∈SF B1

where the minimization is over all (s1 , h1 ) such that

B. MILP formulation for the MNMR problem

M inimizesuch that(y) = w2 d(s2 ) +(18)

a=1 b=1

IV. An optimal solution based on dynamic
programming
In this section, we present an optimal solution algorithm
for the AN M R problem as deﬁned in (5) that is based ona dynamic programming technique.
Similar to [1], we construct a trellis as follows: The ith stage of the Trellis corresponds to SF Bi . The states ineach stage correspond to all possible combinations of the
SF and HCB variables si and hi . We connect all stagesof SF Bi−1 with all states of SF Bi . Each path through thetrellis corresponds to a choice of the encoding parameters
si and hi . We call the sum of the weighted distortions of thestates that form a path (see (1)) divided by the number of
SF Bs −N − the distortion associated with the path. We
deﬁne the cost to proceed from the state (si−1 , hi−1 ) in
SF Bi−1 to state (si , hi ) in SF Bi as Qi (si , hi ) + F (si−1 −si ) + G(hi−1 − hi ). Deﬁning the cost for choosing the statemin(si ,hi )∈SF BN(s ,hi )∈ fN i(Rt ) is the cost of the cheapest

path through the trellis.
(s ,h )
Remarks: In step 1, f2 2 2 (y) does not exist if the inequality (19) cannot be satisﬁed for any pair of states (s1 , h1 )and (s2 , h2 ). If in step 2, for a certain state (s∗i−1 , h∗i−1 ) ∈
(s∗

,h∗

)

i−1
i−1
SF Bi−1 , fi−1
(y − S(s∗i−1 , h∗i−1 , si , hi )) does not exist due to the reason given above (for i = 2) or becausey − S(s∗i−1 , h∗i−1 , si , hi ) < 0 (for i > 2), then the minimization over (si−1 , hi−1 ) excludes (s∗i−1 , h∗i−1 ).

V. Numerical comparison of different
optimization techniques
In this section, we use the new methods proposed inthis paper to evaluate the performance of the previous approaches, Two Loop Search and the Trellis Search. We
compared the diﬀerent methods using 4600 audio frames
and assumed 49 SF Bs, 60 SF s and 12 HCBs.
For the AN M R problem, both the MILP solution andthe Dynamic Programming Method provide an optimal solution. Only the MILP based approach takes into account113

TABLE I
Comparison of average AN M R values

1

0.9

0.8

ANMR ratio
2.4
1.1
2.2

Percentage of samples below x value

Compared optimization techniques
Two Loop Search/Dynamic Prog.
Trellis Search/Dynamic Prog.
Two Loop Search/Trellis Search

TABLE II
Comparison of average M N M R values

TLS/Trellis Search
TLS/Dynamic Programming
Trellis Search/Dynamic Programming

0.7

0.6

0.5

0.4

0.3

0.2

0.1

MNMR ratio
2.2

0

the condition (4). However, our numerical experiments
showed that the Dynamic Programming Method only very
rarely determines sets of encoding parameters that contradict the condition (4). The Two Loop Search takes into
account the condition (4), whereas the Trellis Search ([1])
does not. As the dynamic programming based solution, theTrellis Search very rarely violates the condition (4). Thus,in order to compare the diﬀerent optimization techniques,
we compared the performance of the Dynamic Programming Method, the Trellis Search, and an implementationof the Two Loop Search by Dolby Laboratories, and did
not consider the cases where the Trellis Search violated thecondition (4).
For the ANMR problem, table I shows that the Trellis
Search is on average about 10% worse than the optimal
solution. The Two Loop Search is on average more than
two times worse than both other methods. The CDFs of
the ratio of the distortions achieved by the diﬀerent optimization techniques are shown in ﬁgure 1. The solution of
the MILP with an LP solver based on the Simplex methodrunning on a Pentium 5, 1.7 Ghz took 70 seconds, whereas
the Dynamic Programming Method needed about 12 minutes to solve the problem. The Trellis search needs about
2 seconds to solve the problem. The huge gap in running
time and the small diﬀerence of 10 % in the average distortion show the strength of the Trellis Search. The Two
Loop Search is the only real-time method as it needs several milliseconds to solve the ANMR problem.
For the M N M R problem, both the Trellis search and the
MILP presented in section VII.B provide optimal solutions.
As for the AN M R problem, we compare the Trellis Searchwith the Two Loop search, and disregard the cases where
the Trellis Search violates the constraint (4). Table IIshows that the Two Loop Search is on average more than
two times worse than the Trellis Search. The corresponding CDF is shown in ﬁgure 2. The running times for the
Trellis Search is about 2 seconds and the Two Loop Searchneeds several milliseconds.

1

1.5

3
2.5
2
Ratio of distortion for ANMR

3.5

4

4.5

5

0.95

0.9

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5

0.45

1

3.5
3
2.5
2
1.5
Ratio of distortion between Two Loop Search and Trellis Search for MNMR

4

Fig. 2. Comparison of Two Loop search and Trellis search for MNMR

methods that for the ﬁrst time solve the joint optimization
problem optimally. The ﬁrst method models the joint optimization problem as a Mixed Integer Linear program. The
second method uses a Dynamic Programming approach.
For the AN M R problem, the Trellis Search achieves distortions that are about 10% worse than the optimal solutions. However, the optimal MILP and the Dynamic Programming Method are computationally far more complex
than the Trellis Search. For both the AN M R and the
M N M R problem, the Two Loop Search is the only realtime capable solution, but it achieves distortions that are
signiﬁcantly higher than the optimal distortions.
References
[1]
[2]
[3]
[4]
[5]
[6]

VI. Conclusions[7]

This paper proposes new methods to solve the joint optimization problem for the MPEG-4 AAC encoder. We
developed an analytic model of the encoding process that
improves on previous approaches. Then, we presented two

0.5

0Fig. 1. Comparison of TLS, Trellis Search and Dynamic Programming for ANMR

Percentage of samples below x value

Compared optimization techniques
Two Loop Search/Trellis Search

[8]

114

Aggarwal. A., Towards weighted mean-squared optimality of
scalable audio coding. Dissertation, UCSB, Dec. 2002.
Aggarwal, A., Regunathan, S., Rose, K., Trellis-Based Optimization of MPEG-4 Advanced Audio Coding. IEEE Workshop
on Speech Coding, September 2000, Wisconsin, USA.
Bosi, M., et al., ISO/IEC MPEG-2 Advanced Audio Coding.
Journal of the AES, Vol. 45, No. 10, 1997, Oct, pp.791 -811.
ISO/IEC, IS-14496 (Subpart 4) 2001.
Beaton, R.J. et al.,Objective perceptual measurement of audio
quality. Collected Papers of Audio Bit - Rate Reduction(1996),
Gilchrsit, N., Grewin, C.; pp. 126 - 152.
Najafzadeh, H., Kabal, P., Perceptual bit allocation for low rate
coding of narrowband audio. ICASSP 2000, Istanbul, Turkey,
June 2000.
Yang, C.H., Hang, H.M.,Cascaded Trellis-Based Optimization
for MPEG-4 Advanced Audio Coding. 115th AES convention,
October 2003, New York City.
Zwicker, E., Fasthl, H., Psychoacoustics: Facts and Models.
Second Edition, Springer Publishing House, 1990c1999.