The Optimal Choice of Encoding Parametersfor MPEG-4 AAC Streamed over Wireless Networks
Claus Bauer
Dolby Laboratories
San Francisco, CA, USA

cb@dolby.com
ABSTRACTThis paper addresses a novel linear programming based approach to optimize the choice of the encoding parameters
for the MPEG-4 AAC audio codec. Current techniquessolve the encoding problem for MPEG-4 AAC by splitting
the encoding procedure into a sequence of smaller problems
that are solved heuristically. In contrast, we approach thecoding problem as multidimensional optimization problem
and achieve large performance gains compared with current
methods.
Categories and Subject Descriptors: Discrete Mathematics, G.2: Communications Applications, H.4.3. General
Terms: Algorithms. Keywords:Discrete Optimization,
Communication Systems.

encode the transform coefficients. The transform coefficientsare quantized using a dynamically chosen quantization stepsize, and the quantized coefficients are entropy encoded using Huffman Code Books. In addition to the encoded transforms, the encoder transmits the quantizer step size andthe Huffman Code Books as side information. The encoder
also uses a small number of bits to inform the decoder whichblocking/region structure was chosen. Consequently, the total transmission rate from the decoder to the encoder is thesum of the bits needed to encode the transform coefficients,
the sum of the bits needed to encode the region/block structure, and the sum of the bits needed to encode the side information.
In summary, we see that the encoder chooses four sets ofencoding parameters:
1. Block structure.

1.

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.
The AAC codec exploits perceptual redundancies to achievetransparent perceptual qualities at low bit rates. In the firststep, each audio frame is converted from the time to thefrequency domain using the MDCT transform. In a second
step, the AAC encoder divides the MDCT coefficients into
sets of blocks. It either combines all coefficients in a longblock or divides them into 8 short blocks. In general, a longblock leads to a higher time domain resolution of the signal
whereas a short blocks lead to a higher frequency domain
resolution of the signal. If the MDCT coefficients are divided into short blocks, adjacent blocks can be combined
into regions. Within a long block or within each region, thetransform coefficients are combined into scale factor bands(SF Bs). For each SF B, the AAC encoder allocates bits to

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
WMuNeP’05, October 13, 2005, Montreal, Quebec, Canada.
Copyright 2005 ACM 1-59593-183-X/05/0010 ...$5.00.

2. Grouping structure (for short blocks only).
3. Quantization step size.
4. Huffman code books.
To ensure a low bit rate coding, the encoder must choosethese four sets of parameters such that the total transmission rate is below a predefined threshold, while ensuring thata predefined objective measure for the perceptual quality ofthe decoded signal is met.
The most common perceptual quality measures are the average weighted (AN M R) and the maximum weighted noise
to mask ratio (M N M R), which are also called the average and the maximum distortion. We define both notions
in section 2. In this paper, we investigate the problem ofdetermining 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 the received
audio are of strong interest to the delivery of audio content
over bandwidth constrained wireless networks. Throughout
this paper, we refer to this problem as the AN M R/M N M R
encoding problem.
The optimal solution of the AN M R/M N M R encoding
problem is a highly-complex optimization problem becauseof the interdependencies of the four sets of parameters, which
we describe in the following. For a chosen specific blocking/regioning configuration, the encoder calculates the masking curve per long block or per region. The encoder tries
to choose a quantization stepsize such that the resulting
AN M R/M N M R - which per its definition also depends onthe masking curve - is small. The choice of the quantization
step size in turn influences the choice of the Huffman CodeBook used for the entropy encoding of the quantized transform coefficients. Consequently, the choice of the masking
curve influences both the choice of the quantization step
size and the Huffman Code Book. The complexity of the
AN M R/M N M R encoding problem is further increased by
the fact that the side information for the quantizer step size
and the Huffman code books is encoded differentially between adjacent bands because it depends among others on
the difference of the values chosen for the these parametersat adjacent bands.
Current AAC implementations do not solve the AN M R/
M N M R encoding problem optimally. Instead of performing
a four dimensional optimization over the encoding parameters described above, the existing technologies simplify the
AN M R/M N M R encoding problem significantly by choosing the different parameter sets sequentially, i.e., these methods neglect the relationship between these parameter. Moreover, in each sequential step, the existing technologies mostly
use - with regard to a given metric - non-optimal heuristics
to determine the respective parameter set. We give a detailed overview over these technologies in section 3.
In this paper, we develop the first mathematical modelof the complete MPEG4-AAC encoding process. Based on
this model, the first optimal solution algorithms to both the
AN M R and the M N M R encoding problem are presented.
These algorithms allows us to evaluate the performance ofexisting, non-optimal techniques as described in section 3
in comparison to the optimal results. Finally, we show how
the methods developed in this paper could be further developed to design computationally less complex, non-optimalversion of the methods presented here that lend themselves
to an implementation in future versions of AAC.
In the next section, we give an exact definition of the
AN M R and M N M R problems. We discuss existing algorithms to solve the AN M R/M N M R encoding problem in
section 3. In section 4, we present a mixed linear programming formulation and solution of the AN M R/M N M R encoding problem. In section 5, we use simulation results toevaluate the performance of previous techniques with the
optimal solutions presented in this paper. We conclude insection 6.

such that the total number of SF Bs is Rq, 1 ≤ q ≤ 8, where
q is the number of regions. We note for further usage that
R < T < 8R.

(1)

In order to simplify our terminology, whenever in this document we talk about a specific blocking and region structure
chosen by the encoder, we will talk about a configuration.
We number the configurations g from g = 0 to g = G + 1
where the configurations g = 0, .., G = 127 correspond to
specific groupings of short blocks and g = G + 1 = 128 corresponds to a long block configuration.
Within either a long block or a region, in case a short
block configuration is chosen, the encoder chooses the scale
factors and the Huffman Code Books for each SF B.
All coefficients belonging to the same SF B are encodedusing the same quantization step size. The quantizer step
size of each band is controlled by a scale factor (SF ) selected from a range of M1 SF s. Also, within a SF B, thequantized coefficients are entropy encoded using the same
Huffman Code Book (HCB) selected from M2 HCBs. Typically, M1 = 60 and M2 = 12. The SF s and HCBs aretransmitted as side information.
We define si as the SF value and hi as the HCB value forthe ith scale factor band in the frame. We assume that the si
and the hi only take integer values and require 1 ≤ si ≤ M1 ,and 1 ≤ hi ≤ M2 , ∀i, 1 ≤ i ≤ N. Both the si and hi areindexes into sets of pre-determined Scale Factors and Huffman Code Books, respectively. Finally, we define vectors
the S = {s1 , .., sN } and H = {h1 , .., hN }.
The noise to mask ratio (N M R) [6], which is the ratioof the quantization noise to the masking threshold [12], isthe most widely used objective measure for the evaluationof an audio signal. Two types of N M R are widely used[9]: the Average N M R (AN M R) and the Maximum N M R(M N M R). In order to define both N M R types analytically, we introduce the following notations: We define byd(si ) the quantization error of the i-th scale factor band if
the i-th scale factor is chosen equal to si . wg,i denotes theweight of the i-th scale factor band in the g-th configuration which is defined as the inverse of the masking threshold(see [12]) of the i-th band. The AN M R is then analytically
expressed as the sum
1 X
wg,i d(si ),
N i=1
N

2.

PROBLEM DEFINITION

We first describe the encoding procedure in AAC. The
AAC encoder converts the time domain signal into the spectral domain using the modified discrete cosine transform(MDCT). As not all 1024 MDCT coefficients are relevant
for the perception of the decoded signal by the human ear,
not all coefficients are encoded individually. The perceptually relevant MDCT coefficients are divided into blocks,
regions, and scale factor bands (SF Bs). Now, we explainthese divisions in detail. The encoder decides if the transform coefficients are encoded in a long block structure or inshort block structure. In a long block structure, the perceptually relevant coefficients are divided among typicallyT = 49 SF Bs. In a short block structure, the coefficientsare initially divided into 8 blocks which have the approximate same number of coefficients. Adjacent blocks are thengrouped into regions where a region consists of between 1
and 8 adjacent blocks. Thus, there are 27 = 128 possible choices of regions. Each regions contains R = 15 SF Bs

AN M R(S, g) :=(2)

where N is the number of SF Bs, i.e, N ∈ {T, Rq}, 1 ≤ q ≤8. Using the same notation, the M N M R is expressed as
M N M R(S, g) :=max wg,i d(si ).

1≤i≤N

(3)

In the following, we derive an analytic expression for thetransmission rate. We first introduce the notation 1g : We
say i ∈ 1g ⇔ if (i = 1 ∨ g = G + 1) ∧ (SF Bi is the first SF B
in a region of the configuration g ∨ g ≤ G). Obviously, if g ≤G + 1, then all i ≡ 1(mod R) belong to ig . The transmission
rate consists of five parts:• The amount of bits required to inform the decoder if
a long or short block configuration is chosen does notdepend on the actually chosen configuration. Thus,
it has a non-variable impact on the transmission rate
and for this reason we do not consider it further in thispaper.

• If a short block configuration is chosen, the number ofbits B required to inform the decoder about the chosen
regions is proportional to the number of chosen regions
q minus one i.e., B = c(q − 1), for a given constant c.
If a long block configuration is chosen, then B = 0.
• Let Qi (si , hi , g) be the bits required for the g-th configuration to encode the quantized transform coefficientof the ith band with the SF value chosen as si andthe HCB value chosen as hi . We note that the function Qi (si , hi , g) is also a function of the actual signal X., i.e. Qi (si , hi , g) := QX,i (si , hi , g). In general,
for any two different signals X and Y, QX,i (a, b, g) 6=
QY,i (a, b, g). In the sequel, we consider a fixed signal
only and therefore omit the index X.
• The function F (si−1 , si ) gives the number of bits required to specify the SF for the ith band. As fori 6∈ 1g , the SF are encoded differentially, we note that
F (si−1 , si ) := F (si − si−1 ). The index si for i ∈ 1g
is not encoded differentially, but with its actual value.
We denote this value as F̃ (si ).
• Gi (H, g) represents the number of bits needed to encode the HCB value of the i-th band in the g-th configuration. If i 6∈ 1g and hi = hi−1 , then there is
Gi (H, g) = 0. If hi 6= hi−1 , then the value of Gi (H, g)depends on the length of the HCB section startingat SF Bi . A HCB section is defined as a sequence of
SF Bi , a ≤ i ≤ b, such that ha−1 6= ha , ha = ha+1 =.. = hb , and hb 6= hb+1 where possibly a = b. For a longblock configuration, if a = 1 or/and b + 1 = T the firstor/and third condition do not apply. For short block
configurations, the notion of a HCB section is only
defined per region, i.e., HCB sections cannot overlap
regions. If the last SF B of a given section and the first
SF B of the next section have the same HCB value,then this is not considered as a part of one HCB section, but one says that an HCB of the current section
terminates at the last SF B of this section and that a
new HCB section starts at the first SF B of the next
region. For a short block configuration, the conditions
ha−1 6= ha and hb 6= hb+1 do not apply if a is the first
SF B of a region and b + 1 is the last SF B of a region
respectively. We say that the HCB section defined inthis way starts at SF Ba , terminates at SF Bb , and has
length l(a) = b − a + 1.
For a long block configuration, i.e., g = G + 1, there
holds according to [5] for 1 ≤ i ≤ T,

8 0, if i 6∈ 1g , hi = hi−1 ,>>< 9, if i ∈ 1g , l(hi ) ≤ 30, or i 6∈ 1g ,hi 6= hi−1 , l(hi ) ≤ 30,
Gi (H, G + 1) =>>: 13, if i ∈ 1g , l(hi ) ≥ 31, or i 6∈ 1g ,hi 6= hi−1 , l(hi ) ≥ 31.

In the case of short block configurations, i.e, g ≤ G,
Gi (H, g) is defined in [5] as follows:

8 0, if i 6∈ 1g , hi = hi+1 ,>> 7, if i ∈ 1g , l(hi ) ≤ 6 or i 6∈ 1g ,>hi 6= hi−1 , l(hi ) ≤ 6,<
10, if i ∈ 1g or i 6∈ 1g , 7 ≤ l(hi ) ≤ 13,
Gi (H, g) =>hi 6= hi−1 , 7 ≤ l(hi ) ≤ 13,>>
i 6∈ 1g , l(hi ) ≥ 14,>: 13, hif i6=∈ h1g or, l(h) ≥ 14.
i

i−1i• The definitions of the functions F (·), F̃ (·), and G(·)
show that for i ∈ 1g the contribution of SF Bi to therate is calculated differently from the contributions of
the SF Bi with i 6∈ 1g . In particular, for i 6∈ 1g , thecontribution of the SF Bi depends also on the difference of adjacent hi and si values which is not true fori ∈ 1g . Thus, in order to simplify the notation in thefollowing sections, we redefine for i ∈ 1g :Qi (si , hi , g) → Qi (si , hi , g) + F̃ (si ) + Gi (H, g).
We use these definitions to define the transmission rate
R(S, H, g, B) as follows:
R(S, H, g, B) =

+

N 
X

N
X
i=1

Qi (si , hi , g)F (si − si−1 ) + Gi (H, g) + B,

(4)

i=1
i6∈1g

where N ∈ {T, Rq}, 1 ≤ q ≤ 8 is the number of bands of theconfiguration g. For a given rate threshold Rt and a distortion measure N M R(S, g) ∈ {AN M R(S, g), M N M R(S, g)},the AN M R/M N M R encoding problem is then defined asfollows:
M inimizesuch that3.

N M R(S, g)
R(S, H, g, B) ≤ Rt .

(5)
(6)

PREVIOUS WORK

Previous research has not investigated the MPEG4-AAC
encoding problem as a four dimensional optimization problem, but has chosen the four sets of parameters described in
section 1 sequentially. This significantly simplifies the problem as the interdependencies between the 4 parameter sets
are neglected.
A typical AAC implementation chooses the four sets ofparameters in the following order: First, the encoder decides if a long or a short block configuration is chosen. In
case a short block configuration is chosen, the short blocks
are grouped into regions. In the last step, the SF s and the
HCBs are chosen either in an iterative procedure or jointly.
Any AAC implementation that determines a configuration
g before deciding the values of the SF s and HCBs faces thefollowing dilemma. Because the encoder does not know theactual SF and HCB values when choosing a configurationg, it must use an estimate for both the distortion and side
cost expected to be induced by the SF s and HCBs to bechosen for the configuration g. We now describe the technologies commonly used to decide the long block length andthe grouping structure and show how they use the Perceptual
Entropy and the Energy level of the transform coefficients asmeasures for the expected distortion, respectively.
In [11], a method to decide between a long and a short
block structure is presented. This technology uses the concept of Perceptual Entropy (P E) introduced in [7]. P E isdefined as a measure of perceptually relevant information
contained in an audio signal. Expressed in bits per sample,
P E represents a theoretical limit on the compressibility of aparticular signal and thus gives an indication on how muchbits would be needed to encode the signal without introducing any distortion. An explicit calculation of P E has been

given in [10]:

"
bh
N
1 X X
i

PE

=

+

M i=1
log2

log2

"

bi =bli2#"

pIm(tb )!

pRe(tb ) + 1
6/wi ki
# !#
i

2

i

6/wi ki

+1

,

(7)

where
i
bli

index of critical band,
upper bound of band i,bhilower bound of band i,

ki
bi ,

number of transform components in band i,
index of the transform coefficientstbi ,in the ith critical band,transform coefficient in the ith critical band,

where for a fixed configuration g, wi is the inverse masking
threshold as defined in section 2, and M is the number ofquantized coefficients. The formula (7) shows that the perceptual entropy depends on the chosen SF B structure andthus - by our discussion in section 2 - depends on whether
a long or a short block configuration is chosen. By its definition, the P E is well correlated with the bit rate in a waythat a lower P E suggests a lower N M R at a low bit ratecost. According to the method proposed in [11], the P E iscalculated for both a long block configuration and a short
block configuration consisting of 8 regions. If the long block
configuration has a lower PE, the long block configurationis chosen. Otherwise a short block configuration is chosen.
As current AAC implementations decide between a long or
short block configuration before deciding the region structure of the short blocks, the approach in [11] does not take
into account the actual grouping of the short blocks andcalculates the PE assuming that each region consists of one
block. Thus, for a short block configuration, the actual PE
chosen in the next encoding step by a grouping algorithm
most likely different from the PE calculated for the specificgrouping consisting of 8 regions.
For the case of a short block configuration, algorithms todetermine the grouping of the short blocks into regions areproposed in [4]. The idea of these algorithms is to combine
adjacent short blocks into regions, if the transform coefficients in the blocks have similar average or maximum energy, i.e, absolute value. This approach is motivated by thefact that coefficients with same absolute value tend to havea similar masking curve. In turn, following our discussionof the relation between masking curve and the choice of thequantization step size and Huffman Code Books in section
1, a similar masking curve implies that the coefficients canbe encoded with the same quantization step size and a Huffman Code books while achieving a low AN M R at a low bitcost.
In [4], a metric is defined that measures the cost of joining the adjacent blocks as a function of the expected distortion and the bits required to transmit the grouping structure. Several optimal and non-optimal ways to find the bestgrouping scheme with regard to the described metric are described.
For a given configuration g, the SF s and HCBs have to
be chosen. The Two Loop Search (TLS) [3] is the mostcommon procedure to solve this optimization problem. The

TLS uses a heuristic approach, that neglects the inter-band
dependencies of the side information and thus simplifies the
problem significantly by optimizing the two encoding parameters quantizer step size and Huffman Code Books independently for each band. This leads to an increased totaltransmission rate and/or a decrease in the quality of the decoded signal in relation to a predefined quality measure.
In [1], for the first time a joint optimization of the encoding parameters of all bands has been proposed. The problem
of determining the encoding parameters is modeled as a Trellis Search. The AN M R problem is solved using an iterative
Viterbi search through a trellis. The cost function includesa Lagrangian multiplier based approach that penalizes any
violation of the target rate. For the M N M R problem, an
iterative Viterbi search that does not use a Lagrangian multiplier is used. It always provides an optimal solution.
In [2], two algorithms that determine the optimal choiceof the SF and HCB for a given configuration in the AN M R
problem are proposed. They are based on a mixed integer
linear and a dynamic programming solution, respectively.
For the M N M R problem, an optimal algorithm based on amixed linear integer programming formulation is shown.

4.

AN OPTIMAL SOLUTION BASED ON
MIXED INTEGER LINEAR
PROGRAMMING

In this section, we propose a method to solve the MPEG4AAC encoding problem (5) optimally as a mixed integer
linear program (MILP).

4.1

Preliminary concepts and variables

We introduce additional notation. We see from (1) thatthe maximum number of bands for any configuration g is 8R.
In the model we develop in this section, we assume the existence of 8R SF Bs for any configuration g, but we divide the
8R SF Bs in valid SF Bs which are part of the configurationg and invalid SF Bs, which are not a part of the configuration g and which we only introduce for modeling purposes.
For the model, the invalid SF Bs will make a zero contribution to N M R(S, g) and R(S, H, g, B) in (5) and (6). For
g = G+1, the first T SF Bs are valid, whereas the last 8R−T
bands are invalid. For short block configurations, we denoteby SBj , 1 ≤ j ≤ 8, the 8 short blocks and assign R SF Bs toeach SBj . We introduce the binary variables uj , 0 ≤ j ≤ 7,
where always u0 = 1, and say that the short blocks SBj andSBj+1 belong to the same region if uj = 0, 1 ≤ j ≤ 7. Thus,
there is a one-to-one relation between all short block configurations g and all possible choices of the set uj , 1 ≤ j ≤ 7. We
call the band SBj valid if uj = 1. Thus, for a short block
configuration with s, 1 ≤ s ≤ 8 regions, we have s short
blocks SBaj , 1 ≤ j ≤ s, 1 ≤ a1 < .. < aj < .. < as ≤ 8 withvalid bands and the SF Bs of SBaj correspond to the SF B
of the j-th of the s regions. The other 8 − s SBs are notvalid. For any configuration g, we denote the set of valid
bands as Ng .
In the next step, we transform the functions Gi (H, g) into
a set of other function which can be more easily integrated
in a linear programming formulation.
First, we consider the difference a of the HCB values of
two adjacent SF Bs a = hi − hi−1 . For the long block configuration, we define a function GL (a) and a variable x1 asfollows:GL (a)=

0,9,

a = 0,
a 6= 0.

,

8
9= G + 1 and a HCB section >>< 1, ifofg length=≥ 31 exists
x1 =between SF B1 and SF BT .
>>:;0, else .

Here and in the following, between a and b is to be understood as including a and b. We note that if no HCB sectionof length ≥ 31 exists, then Gi (H, 128) = GL (hi − hi−1 ) for
all 2 ≤ i ≤ T. As T = 49, at most one HCB section of length≥ 31 exists. Thus, we see that Gi (H, 128) = GL (hi − hi−1 )for all SF Bi except the SF Bi where the HCB section starts.
For this SF Bi , there is Gi (H, 128) = GL (hi − hi−1 ) + 4x1 .
For short block configurations g ≤ G, we define the following functions:GS (a)

x2,j

x3,j

x4,j

=

0, a = 0,7, a =
6 0.



,

8
9
3, if uj = 1, g ≤ G, and a HCB section >><=of length ≥ 7 exists between=
BRj+1 and SF BR(j+1)>>: 0, SF;else.
89uj = 1, g ≤ G and two HCB>>< 3, ifsections=of length ≥ 7 exists=
SF BRj+1 and SF BR(j+1) , >>: 0, between
;
else.
8
9
>
j = 1, g ≤ G and a HCB section >< 3, ifof ulength=≥ 14 exists=
between SF BRj+1 and SF BR(j+1) , >>:;the variable Ai,a is set equal to 1 if the actual difference
between si and si−1 is equal to a − M1 , and is set equal tozero otherwise. Ai,a is equal to zeros for all possible valuesof a if SF Bi is an invalid SF B. Similarly, for the case of along block configuration, i.e., g = G + 1, the variables BL,i,b
describe the difference of the values hi and hi−1 , and thevariables BS,i,b describe the difference of the values hi andhi−1 for g ≤ G. We defineAL,i,b=BL,i,b

=

N
X
i=1
i∈Ng

+

Gi (H, g) =TX

2 ≤ i ≤ 8R, 1 ≤ a ≤ 2M1 − 1,
We define the variables Zg,i,a,b ∀i, 1 ≤ i ≤ N, ∀a, 1 ≤ a ≤M1 ∀b, 1 ≤ b ≤ M2 that describe which values are taken by
the variables si and hi at the i-th stage of the g-th configuration:

89< 1, if si = a, hi = b,=configuration g is chosen,
Zg,i,a,b =: 0, else.
;

GL (hi − hi−1 ) + 4x1

8X

eg,i,m3(x2,j + x3,j + x4,j ).

=wg,i d(si = m), ∀1 ≤ i ≤ 8R, 1 ≤ m ≤ M1 .

Further, in order to avoid negative function arguments weset F ∗ (a2 − a1 ) = F (M1 + a2 − a1 ) and G∗ (b2 − b1 ) =G(M2 +b2 −b1 ). Finally, we abbreviate the set of all variables
Zg,i,a,b as Z, AL,i,b and AS,i,b as A, the set of all variables
BL,i,b and BS,i,b as B, the set of variables uj as U, and theset of the variables x1 , x2,j , x3,j , x4,j as X.

MILP formulation for the AN M R problem

M inimize

i=1i∈Ng , i6∈1g+

Next, we define the variable ei,m as the weighted distortion
that occurs at the i-th band when the g − th partition modeis chosen and if si = m, i.e.,

For the ANMR distortion measure, we now formulate theMPEG4-AAC encoding problem as follows:

i=2
8R
X



8
9
< 1, if 0 ≤ g ≤ G, SF Bi is valid, =and hi − hi−1 = b − M1 ,AS,i,b =: 0, else,;89< 1, if 0 ≤ g ≤ G, SF Bi is valid, =and hi − si−1 = b − M2 ,BS,i,b =: 0, else,;

4.2
GL (hi − hi−1 )1, if g = G + 1, , and hi − hi−1 = b − M2 ,0, else,2 ≤ i ≤ T, 1 ≤ b ≤ 2M2 − 1.

0, else.

We see that if uj = 0, then the variables xi,j , 2 ≤ i ≤ 4, 0 ≤j ≤ 7 are equal to zero which reflects the fact the short block
SBj only contains invalid SF Bi . For uj = 1, if no HCB
section of length ≥ 7 exists, then Gi (H, g) = G(hi − hi−1 )for all Rj + 2 ≤ i ≤ R(j + 1). In the other case, we notethat there exist either one or two HCB sections of length
between 7 and 13 or there is a section of length ≥ 14. A caseby case analysis shows that for the SF Bi where this(these)
section(s) start, there is Gi (H, g) = G(hi − hi−1 ) + r, wherer = 3 = 3x2,j if a (first) HCB section of length between
7 and 13 starts at SF Bi , r = 6 = 3x3,j if a second HCB
section of length between 7 and 13 starts at SF Bi , or r =6 = 3(x2,j + x4,j ) if a HCB section of length > 13 starts at
SF Bi .
Combining these definitions, we se1, if g = G + 1, and si − si−1 = a − M1 ,0, else,1 X XXXeg,i,a Zg,i,a,b ,N g=0 i=1 a=1G+1 8R M1 M2

AN M R(Z) :
(8)

=

b=1

j=1

We introduce additional variables: For a given configuration g, the variables Ai,a describe the difference of thevalues si and si−1 . In particular, if SF Bi is a valid band,

such that (9) - (40) are satisfied, where
R(Z, A, B, g, U, X) ≤ Rt ,(9)

X XXX

G+1 8R M1 M2

R(Z, A, B, g, U, X) =
T 2M
X
X

AL,i,a F (a) +i=2 a=0

i=1
i6∈1g

T 2M
X
X

8R 2M
X
X

2

+

8R 2M
X
X

1

∗

M
X

BL,i,b G∗L (b) +

i=1
i∈Ng

7
X

AS,i,a F (a)

2

M
X
1

BS,i,b G∗S (b)

M
G X
X

2 ≤ i ≤ T,
7
X

AS,i,a + 2 − uj ≥
uj ,

(10)

j=1

M
G X
X
2

M
G X
X

7
X

=

uj 2j−1

=

1

G
X

(11)

gvg ,

≥

Zg,i,a,b=vg ,0 ≤ g ≤ G + 1, i ∈ Ng , (13)1 X
BL,i,M2 − 1,
30

(27)

X

T −29

T x1

≥

2

tk ,

(28)

k=2

Zg,i,a,b=0,

0 ≤ g ≤ G + 1, i 6∈ Ng ,(14)

a=1 b=1

X≥≤

AL,i,a1,(15)≥

2M2 −1≤

BL,i,b1,(16)∀i, 2 ≤ i ≤ T.

2M1 −1

≤

1,

(17)

a=1

2M2 −1≤

BS,i,b1,
1 ≤ i ≤ 8R, i 6≡ 1g≥

1 X
BS,i,M2 − 1,
11 Rj+2

(31)

e1,j

≥

1 − BS,Rj+8,M2 − BS,Rj+9,M2 ,

(32)

e2,j
e3,j

≥
≥

1 − BS,Rj+8,M2 − BS,Rj+15,M2 ,1 − BS,Rj+2,M2 − BS,Rj+9,M2 ,

(33)
(34)

d2,j

≥

e4,j

≥

x3,j

≥

x3,j

≥

R(j+1)

AL,i,a=(T − 1)vG+1 ,

(19)

wk

≥

BL,i,b=(T − 1)vG+1 ,

(20)

b=1

X X

AS,i,a=(R − 1)uj ,(21)

BS,i,b=(R − 1)uj ,

(22)

a=1

X X

R(j+1) 2M2 −1

i=Rj+2

(37)
(38)

12

BS,i,M1 − 1,

(39)

i=k

Rx4,j

≥

X

wk ,

(40)

k=Rj+2R(j+1) 2M1 −1

i=Rj+2

1 X(36)

R(j+1)−122i=22 − BS,Rj+8,M2 − BS,Rj+9,M2 ,1(d1,j + e1,j + e2,j + e3,j ) − 1,3
d2,j + e4,j − 1,

(35)

i+12

a=1

T 2M
X
X−1

1 X
BS,i,M2 − 1,
13 i=Rj+2
R(j+1)

2

i=2

(30)

d1,j

(18)

b=1

T 2M
X
X−1

gk ,

k=Rj+2b=1

AS,i,aX

R(j+1)−6

Rx2,j

X

(29)

i=k

a=1

X

1X
BS,i,M2 − 1,
5
k+5

gk

2M2 −1

X

(26)

i=k

a=1 b=1
1

Zg,i,d6 ,d+b−M2 ,g=1 d6 =1

k+29

tk

2

M M
X
X

M
G X
X

for 0 ≤ j ≤ 7, Rj + 2 ≤ i ≤ R(j + 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).

(12)

g=0

j=1
M M
X
X

1,

(25)

1

Zg,i−1,d5 ,d +g=1 d5 =1vg

Zg,i,c+a−M1 ,d4 ,g=1 d4 =1

1

G+1

M
G X
X
2

Zg,i−1,c,d3 +BS,i,b + 2 − uj ≥g=0

ZG+1,i,d6 ,d+b−M2 , (24)g=1 d6 =1

g=1 d3 =1

X

(23)

1

ZG+1,i−1,d5 ,d +

d5 =1

b=0

j=0

ZG+1,i,c+a−M1 ,d4 ,

d4 =1

BL,i,b + 2 − vG+1 ≥a=0(x2,j + x3,j + x4,j ) + c

MX

ZG+1,i−1,c,d3 +

d3 =1

∗

2

i=2 b=0+4x1 + 3

AL,i,a + 2 − vG+1 ≥2

g=0 i=1 a=1 b=1

1+

Zg,i,a,b Qg,i (a, b)

b=1

0 ≤ j ≤ 7.

for 0 ≤ j ≤ 7. The variables Z, X, vg , uj , ei,j , di,j , gk , tk , wk
are required to be integers ∈ {0, 1} and the variables A and
B are required to be non-negative real numbers.
Now, we show that this model correctly represents the
MPEG4-AAC encoding problem as defined in (5).
The equation (11) shows that exactly one configuration
g is chosen by the encoder. For g ≤ G, the equation (12)establishes the one-to-one relation between g and a possible
choice of the uj discussed in section 4.1. For a long block
configuration, the equations (11) and (12) force all uj , j ≤ 2
to vanish which is of no significance for the solution of the
MILP because the uj play no role for a long block configuration (see 4.1.)
We now explain how the variables Zi,a,b , Ai,a , BL,i,a , andBS,i,b consistently express the choice of the SF and HCB
values at all SF Bs. The equations (13) and (14) ensure thatfor the chosen configuration g and each valid band SF Bi exactly one variable Zg,i,a,b is equal to 1, whereas all the othervariables are equal to zero, i.e., exactly one SF and one
HCB are chosen per band. For an invalid band SF Bi , allZg,i,a,b = 0. For a long block configuration and fixed values of the variables ZG+1,i,a,b , the equations (15), (19), and(23) ensure that if i 6∈ Ng and si − si−1 = a − M1 , thenAL,i,a = 1, and all other AL,i,a = 0 as required by the definition of AL,i,a . The equations (16), (20), and (24) imply
the analogous relation for the variables BL,i,b .
For g ≤ G, and fixed values of the variables Zg,i,a,b , theequations (17), (21), and (25) ensure that for any uj = 1,
and Rj + 2 ≤ i ≤ R(j + 1), if there is si − si−1 = a − M1 ,then AS,i,a = 1 and all other AS,i,a = 0 as required by thedefinition of AS,i,a . The equations (18), (22), and (26) imply the same relations for the variables BS,i,b . For all invalid
bands, the variables A and B are equal to zero.
Finally, we analyze the equations (27) - (40) and compare
the values taken by the variables X with their definition insection 4.1. If within a long block configuration at least one
HCB section of length ≥ 31 exists, the equations (27) and(28) show that x1 = 1 which corresponds to the definitionof x1 in section 4.1. In the second possible case that no longblock configuration with a HCB section of length ≥ 31 ischosen, the equations (27) and (28) allow x1 to take any
value ∈ {0, 1} which contradicts the definition of x1 = 0 in
section 4.1. By its definition in section 4.1, the variable x1
does not represent any choice of the encoding variables itself,
but merely expresses the impact of specific choices of the encoding variables on the rate. If x1 is chosen equal to 1, thenx1 makes a higher contribution to the rate R(Z, A, B, X)
than defined in section 4.1 and thus eventually reduce thesolution space of the variables Z, A, and B. To avoid this reduction, the linear program will in the second case always set
x1 = 0. Thus, we see that with regard to x1 , the MILP formulation allows to find the optimal solution of the MPEG4- AAC encoding problem under the exact constraints formulated in section 4.1. For the discussion of the remaining
variables of the set X, the same arguments apply. Thus, wewill only show that if their definition in section 4.1 requires
them to be equal to 1, then the MILP will force them also tobe equal to one, whereas in the case that their definition insection 4.1 requires them to be equal to 0, the MILP allows
them to take any value ∈ {0, 1}.
The equations (29) and (30) force the variables x2,j tobe equal to 1 if at least one HCB section of length ≥ 7exists between the SF BRj+1 and SF BR(j+1) . If such an
HCB section does not exist, then x2,j can take any value∈ {0, 1}. The relations (31) - (38) imply that x3,j = 1 if two
HCB sections of length ≥ 7 exists between the SF BRj+1
and SF BR(j+1) . This can be seen by a case-by-case analysisof all the possible choices of HCBs that contain two HCB
sections of length ≥ 7. The equations (31) - (34) and (37)model the case when two HCB sections of length 7 exist,

where as the equations (35), (36), and (38) model the casewhen one HCB of length and one HCB section of length 8 exist. Finally, the equations (39) and (40) imply that x4,j = 1
if one HCB section of length ≥ 14 exists.
Using the definition of the variables Zg,i,a,b and eg,i,m ,one sees that the definition of the objective function in (9)corresponds to the definition of the objective function in (2).
We now consider the expression for the rate in (10). The
functions F ∗ (n) and G∗ (n) are identical to the function F (n)and G(n) with the argument shifted by M1 and M2 , respectively. The shifts have been introduced in order to avoid
negative variables in the MILP formulation. Recalling thedefinitions of the variables Zi,a,b , Ai,a , and Bi,b , we see thatthe expressions (4) and (10) are identical. WeP
note that fora short block configuration, there is q − 1 =uj , where2≤j≤8

q is the number
regions, and that for a long block conP of
figuration,
uj = 0. Thus the value of B as defined in1≤j≤7

section 2 and used in (4) is correctly expressed in (10).

4.3

MILP formulation for the MNMR
problem

For the M N M R distortion measure, we introduce an additional variable p, which in accordance with the definitionof M N M R(S) in (3) is defined as
p

=

max

1≤i≤N

G
X

G M
P
P MP e1

We note that wi d(si ) =wi d(si ).

g=1
2g,i,a Zg,i,a,b . Thus,we

g=1 a=1 b=1

can model the joint optimization problem (5) as follows:
M inimize p such that
M M
G X
X
X
1

2

ei,a Zi,a,b≤p,∀i, 1 ≤ i ≤ 8R

g=1 a=1 b=1

and(9) − (40) are satisf ied.

As for the AMNR MILP model, the variables Zi,a,b are required to be non-negative and the variables Ai,a and Bi,b
are required to be non-negative real numbers.

5.

NUMERICAL RESULTS

In this section, we compare our method numerically with
two well-known ways of encoding an MPEG-4 AAC bitstream. In order to choose a configuration we apply themethods given in [4] and [11], whereas for the choice of
the SF and HCB we consider both the Two-Loop search[3] and the Trellis [1] described in 3. We note that while the
Two Loop Search can be executed in real-time, whereas theTrellis Search cannot be used in a real-time encoder. The
optimization procedure presented in this paper cannot be
executed in real-time either. For the purpose of the experiments and to reduce the execution time, we have relaxed
several of the constraints of the MILP formulation. Thus,
the results presented here are not the best possible that canbe achieved with our method. However the performancegains achieved with the relaxed constraints are already verysignificant. We are currently developing simulations to test
the unrelaxed formulation of the MILP.
For the ANMR problem, Table 1 shows that the MILP solution is on average about 10% better than the Trellis Search

Table 1: Comparison of average AN M R values
Compared optimization techniques ANMR ratio
Two Loop Search vs. MILP
2.4
Trellis Search vs. MILP
1.1
Table 2: Distortion relative to masking curve
Optimization techniques
Two Loop Search
Trellis Search
MILP

Probab. that ANMR isbelow masking curve
57%
86%
93%

and more than two times better than the Two Loop Search.
We achieved similar results for the MNMR problem.
Whereas the N M R is an effective measure of ultimate performance of the encoding process, the objective of perceptual compression is to achieve an N M R that is satisfactory,
regardless of whether it is the best N M R possible or not. In
the context of audio coding, an N M R is widely considered
as satisf actory if it is below or at least not far above themasking curve. Table II shows that whereas the Two Loop
Search achieves an AN M R below the masking curve with aprobability of 57%, the Trellis Search and the MILP formulation obtain AN M R values below the masking curve witha probability of 86% and 93%, respectively. Again, similar
results were achieved for the M N M R problem.

6.

CONCLUSIONSThis paper develops the first complete model of the encoding process for the MPEG-4 AAC audio codec. Previous
technique to solve the AAC encoding problem divide theencoding problems into sub-problems which are then solved
heuristically. In contrast, we model the encoding process
as a four dimensional optimization problem. The numerical experiments show that even a relaxed version of the
MILP formulation developed in this paper achieves significant performance gains compared to existing technologies.
For future work, we develop a test environment to evaluate
a non-relaxed version of the MILP and we investigate ways
to reduce the execution speed of the algorithm without compromising the quality of the encoded audio signal.

7.

REFERENCES[1] Aggarwal, A. et al., Trellis-Based Optimization of
MPEG-4 Advanced Audio Coding. IEEE Workshop on
Speech Coding, September 2000, Wisconsin, USA.
[2] Bauer, C., Vinton, M., Joint Optimization of Scale
Factors and Huffman Code Books for MPEG-4 AAC,
Proceedings of the IEEE MMSP 2004, Siena, Italy.
[3] Bosi, M., et al., ISO/IEC MPEG-2 Advanced Audio
Coding. Journal of the Audio engineering society, Vol.
45, No. 10, 1997, Oct, pp.791 -811.
[4] Feller, M. Bauer, C.; Vinton, M.; Davidson, G.;
Encoding Blocks of Audio Information Arranged in
Frames with Constrained Optimization of Segmenting
the Frames into Groups of Blocks. Pending patentapplication PCT/US2005/001715.
[5] ISO/IEC, IS-14496 (Part 3) 2001.
[6] Beaton, R.J., Beerends, J.G., Keyhl, M., Treurniet,
W.C., Objective perceptual measurement of audio
quality. Collected Papers of Audio Bit - Rate
Reduction(1996), Gilchrsit, N., Grewin, C.; AES, pp.
126 - 152.
[7] Johnston, J.D.; Estimation of perceptual entropy using
noise masking criteria, ICASSP, 1988, New York, NY,
May 1998.
[8] Johnston, J.D.; Transform Coding of Audio Signals
Using Perceptual Noise Criteria. IEEE Journal on
Selected Areas of Communications, Vol. 6, No. 2,
February 1988.
[9] Najafzadeh, H., Kabal, P., Perceptual bit allocation for
low rate coding of narrowband audio. ICASSP 2000,
Istanbul, Turkey, June 2000.
[10] Painter, T., Spanias, A., Perceptual Coding of Digital
Audio. Proc. of the IEEE, Vol. 88, No. 4, April 2000,
pp. 451 - 513.
[11] Princen, J., Johnston, J.D., Audio coding with signal
adaptive filterbanks. ICASSP 1995, Detroit, May 1995.
[12] Zwicker, E., Fasthl, H., Psychoacoustics: Facts andModels. Second Edition, Springer Publishing House,
1990c1999.