The Choice of MPEG-4 AAC encoding
parameters as a direct function of theperceptual entropy of the audio signal
Claus Bauer, Mark Vinton
determining the set of the encoding parameters that optimize the AN M R/M N M R subject to an upper bound on
the permissible transmission rate. Obviously, low transmission rates that do not compromise the quality of thereceived audio are of strong interest to the delivery of audio content over bandwidth constrained networks.
Themost common procedure to solve the AN M R problem isthe Two Loop Search (TLS) [3]. The TLS uses a heuristic
approach, which neglects the inter-band dependencies ofthe side information and thus simplifies the problem significantly by optimizing the two encoding parameters - quantizer step size and Huffman Code Books - independently foreach band. This leads to an increased total transmission
rate and/or an increase of the AN M R.
In [1], a joint optimization of the encoding parameters of
all bands has been proposed. The possible choices of the encoding parameter are modeled as a trellis and the AN M R
problem is solved using an iterative Viterbi search throughthe trellis. The cost function includes a Lagrangian multiplier that penalizes any violation of the target rate. The
Trellis Search has been further refined in [13].
In [2], algorithms that find the optimal parameter settings for both the SF s and HCBs are presented. The authors show that both the Trellis Search [1], which achieves
distortions on average 10% above the optimum value, andthe optimal solution algorithms in [2] are computationally
too complex for real time applications.
In this paper, we propose the Fast Trellis Search algorithm, which qualitatively performs as well as the Trellis
Search [1], but is of significantly lower complexity than
the Trellis Search. The complexity of the Trellis Searchis caused by the iteration over the Lagrangian multiplierand the solution of an optimization problem for each iteration. Using results from mathematical analysis and digital
signal processing theory, we show that it is possible to derive a good estimate for the final Lagrangian multiplier without having to iterate over all initial Lagrangian multipliers - from the properties of the signal. In particular,
we express the final Lagrangian multiplier as a function of
the Perceptual Entropy of the signal and the target rate of
the encoding process. This relationship is the base of theFast Trellis Search as it avoids the iteration over various
Lagrangian multipliers, which reduces the computational
complexity. We will show that the Fast Trellis Search is acandidate for future real-time implementations of AAC.
In the next section, we develop an analytic formulation of
the problem under consideration. In section III, we develop

Abstract— This paper proposes a new procedure of lowcomplexity to determine the encoding parameters for the
MPEG-4 AAC encoder under real-time constraints. In particular, it addresses the optimization problem of minimizing
the distortion subject to a rate constraint for an MPEG-4
AAC encoder. Existing implementations use the heuristic
Two Loop search to solve this optimization problem. This
paper presents a new solution algorithm which achieves distortion values significantly lower than the Two Loop Search
and which, due to its low computational complexity, is apromising technology for future AAC implementations. We
show via simulations that the technology presented in thispaper significantly outperforms previous technologies.

I. Introduction
In recent years, the delivery of multimedia content overwireless networks has rapidly gained importance. Multimedia applications are expected to be the driving applications
for high bandwidth Third Generation Cellular, WiMAX,
and WiFi networks. The success of these technologies also
depends on the availability of low bit rate audio codecs
such as MPEG4-AAC.
AAC achieves perceptual qualities at low bitrates by exploiting perceptual redundancies in the signal. The AAC
encoder partitions each audio frame into a number ofbands, and for each band, dynamically allocates bits toencode the transform coefficients. In addition to the encoded transform coefficients, the quantizer step size andthe Huffman Code Book of each band are transmitted tothe decoder as side information. The total transmission
rate from the encoder to the decoder is the sum of thebits needed to encode the transform coefficients and thebits needed to encode the side information. The side information itself is encoded differentially and thus depends on
the relation of the parameters at adjacent bands. To ensure a low bit rate encoding, the encoder must choose thequantizer step size and the Huffman Code Books such thatthe total transmission rate is below a predefined threshold,while ensuring that a predefined objective measure for theperceptual quality of the decoded signal is satisfied. Theinter-band relationship of the transform parameters shows
the complexity of the optimization problem.
The most common perceptual quality measures is theaverage weighted (AN M R) noise to mask ratio, which arealso called the average distortion. We define the AN M R
in section II. In this paper, we investigate the problem of
The authors are with Dolby Laboratories, San Francisco, CA,
94103, Fax: 415 8631373, C. Bauer: Tel: 415 5580343, cb@dolby.com,
Mark Vinton: Tel : 415 5580785, msv@dolby.com.

1-4244-0000-7/05/$20.00 ©2005 IEEE.

1

2

the Fast Tellis Search algorithm. We numerically evaluate
the Fast Trellis Search in section III-C and conclude insection IV.
II. Problem definition

N

=

1 X
wi d(si ).
N i=1

N µ
X
R(S, H) = Q1 (s1 , h1 ) +Qi (si , hi )i=2

The AAC encoder converts the time domain signal into
the spectral domain using the modified discrete cosine
transform (MDCT). The 1024 spectral coefficients obtained
via the MDCT are grouped into N scale factor bands(SF Bs). Within each band, all coefficients are quantizedusing the same scalar quantizer. As not all 1024 coefficients are relevant for the perception of the decoded signalby the human ear, not all coefficients are quantized. The
quantizer step size is controlled by a scale factor (SF) selected from a range of typically 60 SF s. Within a SF B,
the quantized coefficients are entropy encoded using a Huffman Code Book (HCB) selected from typically 12 HCBs.
The SF and HCB parameters are transmitted as side information.
In order to formalize the problem of minimizing the distortion subject to a rate constraint, we introduce the following notation. We assume that a frame consists of N
scale factor bands SF Bi , 1 ≤ i ≤ N, and that the encoder
can choose from a set of M1 scale factors and M2 Huffman
Code Books. Further, let si be the SF value and hi be theHCB value for the ith scale factor band in the frame. We
define vectors S = {s1 , .., sN } and H = {h1 , .., hN }. We
assume that the si and the hi only take integer values andrequire 1 ≤ si ≤ M1 , and 1 ≤ hi ≤ M2 , ∀i, 1 ≤ i ≤ N.
Both the si and hi are indexes into sets of pre-determined
Scale Factors and Huffman Code Books, respectively.
The average noise to mask ratio (AN M R) [3] is defined as
the ratio of the quantization noise to the masking threshold[14]. To express the AN M R analytically, we define d(si )as the quantization error of the i-th scale factor band if thei-th scale factor is chosen equal to si . wi denotes the weightof the i-th scale factor band which is defined as the inverseof the masking threshold (see [14]) of the i-th band. The
ANMR is expressed as
AN M R(S) :The transmission rate R(S, H) is defined as(1)

In the following, we derive an analytic expression for thetransmission rate. The transmission rate consists of threeparts:• Let Qi (si , hi ) be the bits required to encode the quantized coefficient indices of the ith band with the SF value
chosen as si and the HCB value chosen as hi . We notethat 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 different signals X and Y, QX,i (a, b) 6= QY,i (a, b). As
we only consider a fixed signal, we omit the index X.
• The function F (si−1 , si ) gives the number of bits required
to specify the SF for SF Bi . As the SF s are encoded differentially, we note that F (si−1 , si ) := F (si−1 − si ).
• Finally, G(hi−1 , hi ) = G(hi − hi−1 ) represents the number of bits needed to encode the HCB value of SF Bi .

¶+F (si−1 − si ) + G(hi−1 − hi ) .

(2)

For a given rate threshold Rt , the AN M R problem isthen defined as follows:
M inimizesuch that

AN M R(S)R(S, H) ≤ Rt .

(3)
(4)

III. Fast Trellis Search
A. Fast Trellis Search: A direct estimate of the final
Lambda multiplier in the Trellis Search
We first revisit the Trellis Search in [1]. The author
builds a trellis consisting of N stages where each stage corresponds to a SF B. The states of each stage i are the setof all possible choices of the parameters hi and si . Eachpath through the trellis corresponds to a specific choice ofthe quantization parameters si and hi . For the solution of
the joint optimization problem as defined in (3), the author uses an ”unconstrained” cost function that is the sumof the distortion as expressed in (1) and the product of a
Lagrangian multiplier Λ and the rate R(S, H). Using thedefinitions introduced in section II, the cost of choosing apath in the Trellis that includes the subpath from the i−1th band at stage (si−1 , wi−1 ) to the i-th scale factor bandat stage (si , wi ) is defined as
C(si−1 , hi−1 , si , hi ) = wi d(si )+Λ (Qi (si , hi ) + F (si−1 − si ) + G(hi−1 − hi )) .
The Trellis Search iterates over the Lagrangian multiplier Λ and uses a Viterbi search to find the cheapest path
relative to the norm C(si−1 , hi−1 , si , hi ) through the trellis
for each Λ. The iteration stops when AN M R(S) does notdecrease any further and the rate constraint (4) is satisfied.
The iteration over Λ leads to the high computational complexity of this approach which makes it not feasible forpractical applications. In the next section, we propose theFast Trellis Search which avoids this computational complexity. It derives a close guess for the value of the final
Lagrangian multiplier Λf inal in the iteration without having to iterate over all previous values of Λ.
B. Facts from digital signal processing theory
In (1), we have introduced the average noise to mask ratio AN M R as a unit-less number. Alternatively, using alogarithmic measure, we use the definitions in [15] to exdB
press the quantities average noise to mask ratio AN M RR,
dB
the Average Signal to Noise Ratio ASN RR and the Average Signal to Mask Ratio ASM RdB in dB. The AveragedB
Noise to Mask Ratio AN M RR
can then be expressed asdB
ASN RR− ASM RdB=

dB
−AN M RR
.

(5)

3

We will make use of the notion of Perceptual Entropy
P E that was introduced by Johnston [7] and is summarized in [9]. Perceptual Entropy is defined as a measure ofperceptually relevant information contained in any audio
signal. Expressed in bits per sample, PE represents a theoretical limit on the compressibility of a particular signal.
An explicit calculation of P E has been given in [9]:
#
!
"
Ã "
bh
N
1 X XiRe(tbi )PE =log2 2 p+1
M i=1
6/wi kibi =bli#Ã "!#Im(tbi )+ log2 2 p+1 ,(7)
6/wi kiwhere

to (10) holds for non-uniform quantization steps. We answered this question affirmatively by doing the following
experiment: For a set of MPEG audio test items (see section ?? for a more detailed description of the test items),R- bit quanwe applied an AAC quantizer to compute a M
tization of the M DCT coefficients. Then, we computeddB
the ASN RR
as defined in [14]. Figure 1 shows the test
result for a typical MPEG audio test item: StatisticallyRdB
is a linear function of the ratio M
the ASN RR
with aslope close to 6.02. This result was achieved consistently
over the set of considered MPEG audio test items. Thus,
we assume in the sequel that also for non-uniform quantidB
can - statistically - be expressed as azation the ASN RR
R
linear function of M
as in (10).
40

35

30

25

ASNR (dB)dB
dB
We have indexed the ASN RR
and the AN M RR
withthe rate index R, because both quantities depend on theactual rate R. Using the definition (1), we see
Ã
!
N
1 X
dB
wi d(si ) .
(6)
AN M RR= 10 log10
N i=1

20

15

i
bli
bhi
ki
bi ,
tbi ,

index of critical band,
upper bound of band i,lower bound of band i,
number of transform components in band i,
index of the transform coefficients in the ith
critical band,transform coefficient in the ith critical band,

10

5

0

=

(8)

ASM RdB .

=

cR
− k,
M

4
5
Bits per sample (R/M)

6

7

8

c(R − P E)
M

=
=

dB
ASN RR− ASM RdBÃ!
N
1 X
−10 log10
wi d(si ) . (11)N i=1

Using (1) and (11), we express for fixed N, M, and P E theaverage distortion AN M R(S) as a function of R, i.e., wewrite AN M R(S) = DR , where
DR

=

10

c(P E−R)
10M

.

(12)

C. An interpretation of the final Lagrangian multiplierΛf inal .
(9)Assuming a uniform quantization step, we know from[15] that for any rate R, there holds statisticallydB
ASN RR3

We see from (5), (6), (9), and (10),We see from (5), (6), and (8) thatdB
ASN RPE

2dB as a linear function of bits per sample R
Fig. 1. The ASN RR
M

and wi is the inverse masking threshold as defined in section II. We note that in the literature the PE is often
1defined with an additional factor M
on the right side of(7).
It is known from [10] that a noise, in particular the quantization noise, that falls below the masking threshold isinaudible. Thus, when a signal is (theoretically) encodedwith P E bits, at each band the masking threshold is chosen
as equal to the inverse of the distortion, i.e.,1wi =.
d(si )

1(10)

where c = 6.02, M is the number of quantized coefficients(see section II), and k is a constant that depends on the
PDF of the signal. As AAC uses non-uniform quantization
steps, it is of interest to understand if a relation similar

We know from the theory of the Lagrangian multiplier([4],[5],[11],[12]) that the negative slope of the distortion
rate function is equal to the final Lagrangian multiplierΛR
f inal , where R denotes the rate, i.e.,
−

d DR
dR

=

ΛR
f inal .

(13)

Using (12), we write DR as follows:
DR

cP E

−cR

= 10 10M 10 10M
cP E=: 10 10M F (R).

(14)

4
c ln 10As F (R) = e−R 10M , there isd F (R)dR= −F (R)c ln 10
.
10M

(15)

From (13), (14), and (15) we obtain the following estimate
for ΛRf inal :ΛR
f inal =c(P E−R)c ln 1010M.
10M × 10(16)

For a fixed value of R, and assuming that c is a positive
constant, we see from (16) that ΛR
f inal increases with increasing P E. This can be intuitively explained as follows:
For increasing P E, the minimum number of bits needed by
the encoder to encode an audio sample increases, such thatthe transmission rate tends to increase and potentially violates the rate constraint. However, for an unconstrained
cost function defined as in (5), if the transmission rate ishigh, the value of Λ must be large in order to strongly penalize a violation of the rate constraint.sectionApplications
and Simulation results

values for N, M, P E, and R and determine Λf inal by iteration over all initial Λ values. Taking the logarithm on bothsides of the formula (17), we use the experimental data to
determine the constants c1 , c2 and c3 as a two-dimensional
least square problem. We obtain the values c1 = −9248.3,
c2 = 11.712, and c3 = 8.897. We see that the constants c1 c3 differ significantly from the value c = 6.02 in (10). Thiscan be expected as the relation (10) is only a very roughapproximation for non-uniform quantization. In order toevaluate the formula (17) with the constant values chosen
as above, we compared the formula (17) with experimental values for Λf inal obtained by iterating over all initial Λvalues. Figure 2 shows that the actual values for Λf inal areindeed very well approximated by the formula (17). Fig.
Rate=1000
0.16
Experimental result
Analytic value
0.14

0.12

For practical applications, we note that the MPEG specification foresees a bit reservoir for the encoding process,i.e., a reservoir of bits is provided to the encoder to encode
the content of a given audio file. Consequently, it is notstrictly necessary that the encoder meets the target rate for
all frames of an audio file, but it must ensure that it meetsthe target rate on average over the whole file. Indeed, theexperiments presented in section III-E show that although
the rate constraint is violated by the Fast Trellis Search on
individual frames, it is met on average over all samples ofa typical audio file. This is due to the fact that the Fast
Trellis Search often finds solutions that require less transmission bits than the target rate.
As another possible application, one could use the Λf inal
determined by formula (16) as an initial value for an iterative Trellis Search that - due to the close guess of Λf inal
- would require significantly less iterations over Λ than aTrellis Search that randomly picks an initial Λ value.

0.08

0.06

0.04

0.02

0
300

400

500

600

700

800

900

1000

PE

Fig. 2. Comparison of the experimental value and analytic estimateof Λf inal for a target rate R=1000, M= 768, N=1024

100
Distortion for analytic value of Lambda final
Distortion for experimental value of Lambda
90

80

70

Distortion

D. Applications of the Fast Trellis Search

Final Lambda

0.1

60

50

40

E. Simulation results

30

In this section, we apply the formula (16) to determine
the value of Λf inal and compare it with the actual experimental value for Λ. For the experiments, we used the AAC
encoder in bit reservoir mode and used common MPEG
audio test samples. We compared the different methods
using ∼ 30000 audio frames, 43 SF Bs, 60 SF s, and 12
HCBs. Our sample rate was 44100 Hz, we used a single
channel (mono), and we chose a rate of ∼ 32 kbps.
As the formula (10) - and so (16) - is only asymptoticallycorrect, we try to improve the accuracy of (16) by introducing an additional degree of variability into the relation(16), and writeΛR
f inal =c2 P E−c3 R
c1 ln 1010M.
10M × 10(17)

In order to determine the values of the constants c1 , c2
and c3 , we execute the Trellis Search over a wide range of

20

10

0

10

20

30

40

50
60
Index of sample

70

80

90

100

Fig. 3. Comparison of the average distortion for experimental andanalytic values of Λf inal for a target rate R=800

3 shows that the distortions that are respectively achieved
susing the Fast Trellis Search, by estimating Λf inal using
formula (17), and the Trellis Search, by iterating over all
initial values of are nearly identical. Figure 4 shows thatthe rate which is achieved by the Trellis Search using theanalytic Λf inal value violates the rate constraint in ∼ 30%of all samples. However, the simulations also show that theachieved transmission rate is always less than 10% above
the target rate. Also, the simulation results show that therate constraint is met on average which allows a deploy-5coder. The Fast Trellis Search outperforms the Two Loop
Search as it finds AN M R values which on average are only
10% above the optimal values and are below the masking
curve with a probability of 86%. The simulations showthat when using the MPEG bit reservoir the Fast Trellis
Search and the Trellis Search achieve nearly identical distortions for each frame and the Fast Trellis Search meetsthe rate constraint on average over the samples of an audio
file. Due to its low complexity, the Fast Trellis Search is apromising technology for future AAC implementations.

880
Rate for analytic value of Lambda final
Rate for experimental value of Lambda final
Target rate
860

Transmission rate

840

820

800

780

760

740

720

References
0

10

20

30

40

50
60
Index of sample

70

80

90

100

Fig. 4. Comparison of the total transmission rate for experimental
and analytic values of Λf inal for a target rate R=800
TABLE I
Distortion relative to masking curve

Optimization technique
Two Loop Search(Fast) Trellis Search
Optimal solution

Probab. that ANMR
is below masking curve
57%
86%
93%

ment of the Fast Trellis Search in the bit reservoir mode.
We recall from [2], that the Trellis and thus - based on
the results from this section - also the Fast Trellis Searchis on average 10% above the optimum value. Whilst the
AN M R is an effective measure of ultimate performance ofthe encoding process, the objective of perceptual compression is to achieve an AN M R that is satisfactory, regardlessof whether it is the best AN M R possible or not. In thecontext of audio coding, an AN M R is widely considered
as satisf actory if it is below or at least not far above themasking curve. The AN M R is below the masking curve if
AN M R < 1. Our experiments - see I - show that whereas
the TLS achieves an AN M R below the masking curve witha probability of 57%, both the Trellis as well as the Fast
Trellis Search obtain AN M R values below the masking
curve with a probability of 86%, whereas the optimal solutions, which we calculated using the algorithms in [2],achieve such AN M R values with a probability of 93%.
The experiments show that the Trellis Search needs
about 2 seconds, whereas the Fast Trellis Search needs
about 80 ms to solve the AN M R problem. Currently, theTLS is the only real-time method as it needs only several
milliseconds to solve the ANMR problem. However, in viewof the rapidly increasing capacity of commercial processors,
the Fast Trellis Search could soon be suitable for real-time
implementations. Optimal methods [2] are far too complex
for real-time implementations.
IV. Conclusions
This paper proposes a new method to solve the problemof minimizing the average distortion subject to a constraint
on the total transmission rate for the MPEG4-AAC en-[1]

Aggarwal. A., Towards weighted mean-squared optimality of
scalable audio coding. Dissertation, UCSB, Dec. 2002.
[2] Bauer, C., Vinton, M., Joint Optimization of Scale Factors andHuffman Code Books for MPEG-4 AAC, IEEE International
Workshop on Multimedia Signal Processing 2004, Siena, Italy.
[3] Bosi, M., et al., ISO/IEC MPEG-2 Advanced Audio Coding.
Journal of the AES, Vol. 45, No. 10, 1997, Oct, pp.791 -811.
[4] Chou, P.A., Lookabaugh, T., Gray, R.M., Entropy-Constrained
Vector Quantization. IEEE Transactions on Acoustics, Speechand Signal Processing, Vol. 37, no. 1, Jan. 1989, pp. 31 - 42.
[5] Everett, H., Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources. Operations
Research, Vol. 11, 1963, pp. 399 - 417.
[6] Geoffrion, A.M., Duality in Nonlinear programming: A simplified applications-oriented development. SIAM Review, Vol. 13,
No.1 , Jan 1971.
[7] Johnston, J.D., Transform Coding of Audio Signals Using perceptual Noise critera. IEEE JSAC, Vol. 6, No. 2, Feb. 1998.
[8] Najafzadeh, H., Kabal, P., Perceptual bit allocation for low rate
coding of narrowband audio. ICASSP 2000, Istanbul, June 2000.
[9] Painter, T., Spanias, A., Perceptual Coding of Digital Audio.
Proc. of the IEEE, Vol. 88, No. 4, April 2000, pp. 451 - 513.
[10] Schroeder, M.R., Atal, B.S., Hal, J.L., Optimized Digital Speech
Coders by exploiting masking propoerties of the human ear. J.
acoustic. Soc. Am. 66(6), Dec. 1979, pp. 1647 - 1652.
[11] Shoham, Y., Gersho, A., Efficient Bit Allocation for an Arbitrary set of Quantizers. IEEE Transactions on Acoustics, Speechand signal processing, Vol. 36, Sept. 1988, pp. 1445 - 1453.
[12] Wiegand, T., Girod, B.; Lagrange Multiplier Selection in Hybrid
Video Coder Control. Proc. of ICIP’01, Thessaloniki, Greece.
[13] Yang, C.H., Hang, H.M.,Cascaded Trellis-Based Optimization
for MPEG-4 Advanced Audio Coding. 115th AES conv., 2003,
NYC.
[14] Zwicker, E., Fasthl, H., Psychoacoustics: Facts and Models. Second Edition, Springer Publishing House, 1990c1999.
[15] Zoelzer, U., Digital Audio Signal Processing. John Wiley Sons
Ltd. 1997.