IMPROVED METHODS FOR CORRELATING TRANSFORMS IN MULTIPLE DESCRIPTION
CODING SYSTEMS
Claus Bauer, Corey Cheng
Dolby Laboratories, San Francisco, USA,{cb,cnc}@dolby.com
ABSTRACTMultiple description has been widely investigated as a qualityof service technology for the delivery of multimedia information over lossy channels. This paper presents generalized
methods for transform based multiple description that do not
introduce additional distortion to the transformed information. Previous noiseless methods place restrictions on how the
information may be quantized prior to correlation. Typically,
the information must be quantized with quasi-uniform quantizers which all have the same quantization step size. This
paper expands these methods so that the information may bequantized with any quantizer, and different parts of the information may be quantized with different quantization step
sizes. For speciﬁc correlating transforms, we propose a computationally efﬁcient correlation transform that makes use of
the Hadamard matrix.
1. INTRODUCTION
Multiple description has been widely researched as a qualityof service technology for sending information over lossy networks. In particular, correlating transform based methods [1],[2], [3] transform information into multiple, statistically correlated subsets of information, called descriptions, and these
multiple descriptions are sent over different paths or channels from the sender to the receiver. If the receiver receives
all descriptions, the content can be perfectly reconstructed at
the sender. If only a subset of the descriptions is received, thereceiver uses the statistical correlation among the received descriptions to estimate the content of the missing descriptions.
We review the principles of transform based multiple description as discussed in [1], [2]. Let x = (x1 , .., xN )tr bea set of N transform coefﬁcients that are all quantized by
the same uniform quantizer Q ([4]) with the same quantization step size Q . The xi represent a speciﬁc part of thesignal representation, e.g. a frequency presentation of an audio frame. Let there be G descriptions, and let the coefﬁcients xi be divided into N/G groups. In each group, theG coefﬁcients are transformed into a set of new coefﬁcientsy = (y1 , ..., yG )tr , where we call the elements of y multiple description (M D) coefﬁcients. The M D coefﬁcients yare independently entropy encoded and sent over the network,
possibly using diverse channels to ensure that description erasures are not concurrent.

1­4244­0367­7/06/$20.00 ©2006 IEEE

725

Following [1], we deﬁne a transform FT,Q (x) = y via an
G × G matrix T with determinant equal to one and via thequantizer Q. It is known that T can be decomposed in at least
one way as T = T1 ...Tk where each matrix G × G Ti has unit
entries at the diagonal and nonzero off-diagonal elements inonly one row or column. We deﬁne
y = FT,Q (x)= Qv (T1 Qv (T2 ...Qv (Tk x))).

(1)Here, Qv (z) is a vector which quantizes each component ofz ∈ RG with the quantizer Q and the same quantization step
size Q . In [1], [2] it is shown that the quantized coefﬁcientsx can be exactly recovered at the decoder from a decorrelatingtransform if all of the MD coefﬁcients are received:
x = FT −1 ,Q (y)= Q(Tk−1 ...Q(T2−1 ...Q(T1−1 y))). (2)As the transforms FT,Q and FT −1 ,Q do not add any distortion to the signal, we call them noiseless transforms. We notethat in this scheme, all quantization based distortion is due tothe quantization of the transform coefﬁcients that takes placeprior to the correlation transform.
If some of the M D coefﬁcients are lost, they are estimatedfrom the received M D coefﬁcients by calculating the conditional expectation for the missing M D coefﬁcients given
the received M D coefﬁcients. This estimation requires theknowledge of the variances - measured over time - of the coefﬁcients xi at the sender. Therefore, the variances are sent asside information with the M D coefﬁcients to the sender.
An analysis of the proofs in [1] shows that the noiselessrecovery of the coefﬁcients x from the transforms FT,Q and
FT −1 ,Q requires that for any real number x1 and x2 , the quantizer Q satisﬁes the following conditions:
Q(x1 + Q(x2 )) = Q(x1 ) + Q(x2 ),Q(−x2 ) = −Q(x2 ).

(3)
(4)

We call a regular (see [4]) quantizer satisfying these conditions a quasi − unif orm quantizer. We note that all uniform
quantizers are quasi-uniform. In addition to assuming a quasiuniform quantzier, the approach in [1] requires all coefﬁcientsxi to be quantized with the same step size.
In particular for audio coding applications, both assumptions are unrealistic. First, several audio codecs, such as AC-3

ICME 2006

[5], routinely use uniform quantizers having different quantization step sizes for different frequency domain MDCT coefﬁcients. Thus, although it is useful to correlate different quantized MDCT coefﬁcients from different frequency regions inorder to increase error robustness and sound quality, this would
be impossible without adding distortion when using (1) and(2). Second, other common audio codecs such as MPEG-4
AAC [6] use quantizers that are not quasi-uniform.
This paper addresses these shortcomings of the existing
theory of multiple description and proposes generalized correlating and decorrelating transforms that do not add additional distortion to the signal.
Sec. 2 describes the ﬁrst contribution of this paper, anoiseless transform which permits the correlation of coefﬁcients that are quantized using the same quasi-unform quantizer and applying different quantization step sizes for different coefﬁcients. Sec. 3 describes the second contribution ofthis paper, a more complex type of transform that permits tocorrelate coefﬁcients quantized by any quantizer using different quantization step sizes for each coefﬁcient.
The third contribution addresses the high computational
complexity of the correlation transform (5). The complexity
derives from the involved matrix multiplications and the subsequent rounding operations. The complexity is particularly
impractical for hierarchical multiple description schemes as
described in [1]. For speciﬁc correlating transforms, in sec. 4
we present an application of the Hadamard matrix that significantly reduces the complexity of the transforms in hierarchical multiple description systems.
2. NOISELESS TRANSFORMS FORQUASI-UNIFORM QUANTIZERSIn this sec., we introduce transforms that allow noiseless correlation and decorrelation of G coefﬁcients x = (xi )1≤i≤G .
We consider a quantizer Q and deﬁne O = (Qi )1≤i≤G as theﬁnite set of quantization step sizes of Q. Thus, Qi (xi ) is thevalue of xi after quantization by Q with the step size Qi . We
assume that each coefﬁcient xi has been quantized by Q withthe stepsize Qi , i.e., xi = Qi (xi ), 1 ≤ i ≤ G.
For a matrix T = T1 ..Tk with determinant equal to 1, wedeﬁne the correlating and decorrelating transforms DT,O (x) =y and DT −1 ,O (y) = x as follows:
DT,O (x) =DT −1 ,O (y) =CT1 ,O (CT2 ,O (...CTk ,O (x)...)),(5)
CT −1 ,O (CT −1 ,O (...CT −1 ,O (y)...)), (6)
k

1

k−1

where we deﬁne the operator CT,O : RG → RG asyDt̃i,j xj )= CT,O (x), yi = Qi (j=1

with y = (y1 , ..., yG )tr , T = (t̃i,j )1≤i,j≤G , and CT −1 ,O isdeﬁned accordingly.

726

We now show that the transforms DT,O (x) and DT −1 ,O (x)allow a perfect recovery of the vector x if all descriptions arereceived at the receiver. To do so, it is sufﬁcient to show thatfor a vector x where each of its components xi has alreadybeen quantized with quantization step size Qi , there isCT −1 ,O (CTi ,O (x))
i

= x, 1 ≤ i ≤ k.

We assume that for Ti = (ti,j )1≤i,j≤G there is ti,j = 0 if
i = j with the exception of ti0 ,j0 , say. Then by (4)CTi ,O (x)= (x1 , .., xi0 −1 , Qi0 (xi0 + ti0 ,j0 xj0 ), xi0 +1 , .., xG )= (x1 , .., xi0 −1 , xi0 + Qi0 (ti0 ,j0 xj0 ), xi0 +1 , .., xG ),and therefore by (3) and by (4) and the regularity of Q :CT −1 ,O (CTi ,O (x))
i

= (x1 , .., Qi0 (xi0 + Qi0 (ti0 ,j0 xj0 ) − ti0 ,j0 xj0 ), .., xG )= (x1 , .., xi0 + Qi0 (ti0 ,j0 ) + Qi0 (−ti0 ,j0 xj0 ), .., xG )= x, q.e.d.
We note that the noiseless character of the transforms DT,O
and DT −1 ,O is achieved by the speciﬁc way of applying thequantization step sizes Qi in each operator CT,O .
3. NOISELESS TRANSFORMS FOR GENERALQUANTIZERSIn this sec., we design a correlation scheme that allows tonoiselessly correlate and de-correlate G coefﬁcients x = (xi )1≤i≤Gthat are quantized using any, not necessarily quasi-uniform
quantizer P . The basic idea of this correlation scheme isto pre-process the input coefﬁcients with an invertible function so that the outputs of the function are all quasi-uniformly
quantized. The outputs are then correlated using the correlating transform described in sec. 2. At the decoder, the inverse mapping is performed after performing the decorrelating transform from sec 2.
Let xi be coefﬁcients quantized with the quantization step
sizes Pk , 1 ≤ k ≤ H, respectively. The ﬁnite code book B of
the quantizer P consists of the output values bk , 1 ≤k ≤ U.
By deﬁning the mapping operator S : B → Υ := Z [1, U ],as S(bk ) = k, we deﬁne a one-to-one mapping from the codebook of B into the set Υ. The set Υ is naturally quantized by
the rounding operation that maps a real number to its nearest
integer. Obviously, this quantizer is quasi-linear and thus satisﬁes the condition of the original correlation transform proposed in [1]. Based on this observation, we propose the following transform:
1. At the sender, the mapping S is applied to the coefﬁcientsxi . The resulting integers hi , 1 ≤ i ≤ G, hi ∈ Υ are thentransformed to M D coefﬁcients J = (j1 , .., jG ) using theequation (1).

2. In case all descriptions are received at the receiver, the integers hi are recovered from the MD coefﬁcients ji (using (2))
and the coefﬁcients x are recovered from the hi by inverting
the map S.
3. In case some M D coefﬁcients ji are not received, they are
estimated from the received M D coefﬁcients as described in[1].
This estimation requires the knowledge of the variancesof the integers hi . We recall from the introduction that the
coefﬁcients xi = xi (t) are measured over time t. Using theprobability distribution of xi (t), one obtains the variance of
hi = hi (t) = S(xi (t)). We note that a value of hi guessedin such a way might ∈ Υ. In this case hi would be set equal
to the next integer ∈ Υ. This approximation might introduce
additional distortion when recovering the coefﬁcients xi .
We note that whereas the correlation scheme in sec. 2 provides noiseless recovery for all quasi-uniform quantizers, themapping scheme in 3 allows noiseless recovery for all quantizers. Its drawbacks are the additional complexity due to theintroduction of the mapping function S and the potential introduction of additional distortion if some M D coefﬁcientsare not received as described above.
4. EFFICIENT CORRELATING TRANSFORMS FORHIERARCHICAL MD SYSTEMS
4.1. Hierarchical multiple description systems
Hierarchical multiple description systems [1] involve the concatenation of several layers of correlating transforms such as
those given in (1), where the output of each transform layer isthe input for the subsequent transform layer. These systems
are useful in increasing and balancing the degree of correlation among the M D coefﬁcients.
A hierarchical M D system contains N initial transform
Quantized transform coefficients0First transform level

Second transform level00DT, O 0,4
1

1

2

2

3

S

4

5

5

6

6

3
7

2
2

D T, O 2,3

2
4

DT, O 1,3

2
6

DT, O 3,7
7

3
5

3
3

3
5

3
7

0

0

CT1, O a,b

1

MD coefficients0

C T2, O a,b1

0

CT3, O a,b

1

1

Fig. 2. Implementation of the DT,Oa,b operator.
Fig. 1 shows an example of a hierarchical multiple description system. Speciﬁcally, this hierarchical M D system
contains N = 8 initial transform coefﬁcients and L = 3
transform levels. After the g-th transform, each coefﬁcient
contains information about 2g transform coefﬁcients. Thus,
each M D coefﬁcient contains information about 2L transform coefﬁcients. The detailed implementation of an operator
DT,Oa,b where T is a 2 × 2 matrix and the set of quantization
step sizes Oa,b is deﬁned as Oa,b = (Qa , Qb ) is shown in ﬁg.
2. We note that different sets of quantization step sizes Qa,b
are applied to deﬁne the operators DT,Oa,b in different partsof the hierarchical multiple description system in ﬁg. 1.
The hierarchical multiple description system in ﬁg. 1 applies the mapping operator S deﬁned in sec. 3 and is thus
applicable to any quantizer. We note that hierarchical multiple description schemes could also be deﬁned by correlating M > 2 coefﬁcients at each hierarchy level as long as
N/M L ∈ Z.
4.2. Efﬁcient correlating transforms

3
3

2
4

D T, O 4,5

2
6

DT, O 5,7

Quantized transform coefficients

1

2
2

DT, O 4,62
4

DT, O 2,6

7

3
3

0

DT, O 0,1
1

2
2

3

4

D T, O 0,2
1

DT, O 1,5

Third transform level MD coefficients0vided into groups of size G = 2L . Within each group, at eachlevel of the hierarchy, sets of two coefﬁcients from the previous hierarchy level are correlated.

3
5

2
6

D T, O 6,7

3
7

Fig. 1. A hierarchical multiple description system with L =3 and a mapping operator S. Using the operator DT , two
coefﬁcients from the n − 1-th transform level are correlated
to create two coefﬁcients of the n-th transform level.
coefﬁcients, L transform levels, and the N coefﬁcients are di-727

The practical implementation of the hierarchical multiple description system shown in ﬁg. 1 is hindered by the successive
matrix multiplication and quantization steps deﬁning DT,O
and DT −1 ,O (see (5) and (6)). In order to reduce this computational complexity, we propose a computationally more efﬁcient implementation of the correlating (and decorrelating)transform for hierarchical multiple description systems.
Our proposed transforms
 are limited
 to 2 × 2 correlating
1
1. For hierarchical mulmatrices T deﬁned as √12
1 −1tiple description systems as shown in ﬁg. 1, these matrices
are of particular importance (see [1]) because each M D coefﬁcient contains the same amount of information about any of
the 2L transform coefﬁcients. This property is desirable whenT

the different descriptions are sent over different communication channels with similar packet loss characteristics.
The proposed transform is shown in ﬁg. 3 and consistsof three steps: the mapping operator S deﬁned in sec. 3, theHadamard transform HL , and a scaling operator W . Afterbeing passed through the operator S, the G coefﬁcients, sayx̃ = (x̃1 , .., x̃G ), belonging to a given group are multipliedwith the Hadamard matrix HL as follows:

1
2
3
4
5
6

ỹ = (y1 , ..., yG )trỹ = HL x̃,
Lwhere HL denotes the 2 × 2 Hadamard matrix deﬁned asHL−1 HL−1
1 1
,
H1 =
.
HL =
HL−1 −HL−1
1 −1

1

1

1

2

2

2
2

3

S

3

Hadamard
Transform H 3

Scaling operator W

0

3
3

2
4

4

4

5

5

3
5

6

6

2
6

7

7

3
7

In this paper we extend the theory of transform based multiple description. We propose a noiseless correlation schemethat permits the correlation of coefﬁcients quantized with thesame quasi-uniform quantization scheme while using different quantization step sizes for different coefﬁcients. We extend this transform to allow for the noiseless correlation of
coefﬁcients with any quantizer while applying different quantization step sizes to different coefﬁcients. Finally, we use theHadamard matrix to design an efﬁcient and noiseless correlating transform for hierarchical multiple description schemes.
The work presented here was part of a research study at Dolby
Laboratories and is not intended for commercial applications.
6. REFERENCES[1] Goyal, V.K., Kovac̆ević, J., Generalized multiple description coding with correlating transforms, IEEE
Trans. on Information Theory, Vol.47, No. 6, Sep. 2001.
[2] Goyal, V., Kovac̆ević, Optimal multiple description
transform coding of Gaussian vectors. Proc. IEEE Data
Compression Conference 1998.
[3] Wang, Y., et al., Multiple description coding using
pairwise correlating transforms, IEEE Trans. on Image
Proc. 10(3): 351-366 (2001)[4] Gersho, A., Gray, R.M., Vector Qunatization and Signal
Compression, Kluwer Academic Publishers, 1992.
[5] Davidson, G.A., Digital Audio Coding: Dolby AC-3, in’The Digital Signal Processing Handbook’, V. K. Madisetti and D. B. Williams Eds., Boca Raton, Florida: CRC
Press LLC, 1998, pp. 41-1 - 41-21.
[6] 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.
[7] Cheng, C., Jiang, W., Multiple description error mitigation techniques for streaming compressed audio over a802.11 wireless network. AES 120th Conv., May 2006.
[8] Lee, M.H., Kaveh, M., Fast Hadamard transform basedon a simple matrix factorization, IEEE Trans. on Acoustics, Speech, and Signal Proc., vol. ASSSP-34, no.6, pp.
1666-1667, 1986

MD coefficients0Complexity reduc.
of efﬁc. trans.
44.9%
48%
49.32%
49.98%
50.4%
50.6%

5. CONCLUSIONSThe scaling operator W is a power normalization step andcorresponds to a multiplication of the coefﬁcients ỹi by 2−L/2 .
The complete implementation of the transform is shown inﬁg. 3. The decorrelating transform can be implemented in theanalogous way.
Fig. 3 is an equivalent and more efﬁcient replacement forﬁg. 1 when equal information about each transform coefﬁcient is prescribed for each M D coefﬁcient in a single group,i.e., the correlation matrix T is deﬁned as above. The mathematical equivalence of the schemes in ﬁg. 1 and 3 can beeasily shown using induction but due to space constraints is
not proved here. The implementation in ﬁg. 3 is computationally signiﬁcantly more efﬁcient than the implementation
in ﬁg. 1 because of two factors:
1. No quantization steps are required for the implementation
0

Efﬁc. trans.,
N(T+1) Ops.
2048
3072
4096
5120
6144
7168

Table 1. Comparison of the number of numerical operations
between the original transform, ﬁg. 1 and the efﬁcient transform ﬁg. 3 for N = 1024.

L

Quantized transform coefficients

Orig. trans.,
4.5N T Ops.
4608
9216
13824
18432
23040
27648

Fig. 3. Efﬁcient implementation of a hierarchical multiple
description system using the Hadamard matrix.
in ﬁg. 3. The complexity of the operator W is much lower
than the complexity of the quantization operations in ﬁg. 3.
2. A multiplication of a vector with G = 2L elements with
the Hadamard HL matrix can be computed in 2L L operations([8]).
Table 1 gives a comparison of the number of operations
for the two implementations in ﬁg. 1 and ﬁg. 3 as a function of the number of transform coefﬁcients N and transform
levels T .

728