Department of Electrical and Computer Engineering, University of Manitoba, Winnipeg, Manitoba R3T 5V6, Canada

Abstract

Transform coding (TC) is one of the best known practical methods for quantizing high-dimensional vectors. In this article, a practical approach to distributed TC of jointly Gaussian vectors is presented. This approach, referred to as

1 Introduction

Many new applications such as multi-camera imaging systems rely on networks of distributed wireless sensors to acquire signals in the form of high-dimensional vectors

Information-theoretic studies of distributed transform coding (DTC) can be found in

In contrast to WZ-TC, we consider in this article the practical design of two-terminal transform codes for jointly Gaussian vectors in which arbitrary transmission rates can be assigned to each terminal. Our approach is based on the idea of

This article is organized as follows. Section 2 presents a review of WZ-TC of Gaussian vectors and motivates the particular approach introduced in this article. Section 3 presents the idea of SP-DTC and develops the tree-search algorithm for finding the optimal transforms and the bit-allocation for SP-DKLT codes. Section 4 computes the achievable rate region of SP-DKLT codes for two example Gaussian source models, and presents experimental results obtained by designing SP-DTCs based on both KLT and DCT. Finally, some concluding remarks are given in Section 5.

**Σ**
_{
X
}denotes the auto-covariance matrix of the vector **X**. **Σ**
_{
XY
}and **Σ**
_{
X|Y
}, respectively denote the joint covariance matrix of (**X**, **Y**) and the conditional covariance matrix of **X **given **Y**. The eigenvalues _{1 }, . . ., _{M }
_{1 }
_{2 }. . . ≥ _{M }
**u**
_{
m
}is the eigenvector associated _{m}

2 WZ-TC of Gaussian vectors

Consider encoding of a Gaussian vector **X **be Σ_{
X
}= **XX**
^{
T
}}. In WZ-TC, a linear transform is first applied to **X **and each component of the **U **= **T**
^{
T
}
**X **is separately compressed by a WZ quantizer, considering **Y **as decoder side-information, where **T **is a _{1 }× _{1 }unitary matrix. Let **Û **be the quantized value of **U**. The decoder then estimates the source vector based on **Û **and **Y**. We wish to find the optimal transform and the allocation of _{1 }transform coefficients, which minimize the quantization MSE

Let the eigenvalues of the conditional covariance matrix **Σ**
_{
X|Y
}= **XX**
^{
T
}|**Y**} be **X **given **Y **is defined as **
θ
**=

where _{1 }is a positive integer.

2.1 RD-WZQ model

When RD-WZQ model is used, the quantization MSE for _{m }

where _{m }
_{m}|**Y**) and var(

**Theorem 1 **
**X **
**Y **
_{m}, m _{1}, **U **= **T**
^{
T
}
**X**, **Y **
**T **
**X **
**Y**, _{m }is

_{m }≥ d^{∗ }
**
λ
**,

**Proof 1 **

Note that RD-WZQ model implies infinite-dimensional VQ of each coefficient and hence the above MSE is the OPTA in the Gaussian WZ-TC problem.

2.2 SWC-HRSQ model

The asymptotically (in rate) optimal solution to the WZ-TC problem under SWC-HRSQ model is given by the following theorem.

**Theorem 2 **
**X**, **Y**, _{m }, m _{1 }, **U **= **T**
^{
T
}
**X**, **Y **
**T **
**X **
**Y **
_{m}, m

**Proof 2 **

2.3 Sufficiency of scalar side-information

The WZ quantizers with vector-valued decoder side-information as considered in Theorem 1 are difficult to design in practice. However, the following theorem establishes that when CKLT is used and RD-WZQ model applies for quantization of coefficients, a linear transformation of the side-information vector can be used to convert the vector side-information problem into an equivalent scalar side-information problem. Furthermore, [

**Theorem 3 **
**T **
**X **
**Y**. _{m }, m _{1}, **U **= **T**
^{
T
}
**X**, **Y**. _{m}(**y**
_{m}|**y**} _{m }given **Y **= **y **
_{m}

**Proof 3 **

Wyner-Ziv transform coding is a special case of more general MT-TC where two or more terminals apply TC to their respective inputs and transmit the quantized outputs to a single decoder which exploits the inter-source correlation to jointly reconstruct all the sources. In this case, the problem is to optimally allocate a given bit budget among all the terminals such that the total MSE is minimized. However, the closed-from solution to this problem appears difficult, due to the inter-dependence of the encoders in different terminals. An iterative descent algorithm is given in

3 Source-splitting based distributed TC

In general, designing a multi-terminal VQ is more difficult than designing a WZ-VQ, due to the mutual dependence among the encoders. However, one could use WZ-VQs to realize a multi-terminal VQ by using source-splitting

A block diagram of the SP-DTC system is shown in Figure **X**
_{1 }at the rate **X**
_{1 }as the decoder side-information. Therefore, _{1 }× _{1 }unitary matrix. Given the side-information **X**
_{2 }using **T**
_{2 }is a _{2 }× _{2 }unitary matrix. Let **U**
_{2}, where _{2 }
_{2}. Then, given the quantized linear projections of both **X**
_{1 }and **X**
_{2 }available at the decoder, the terminal 1 quantizes the a linear projection **X**
_{1 }using _{1 }× _{1 }unitary matrix. Let **X**
_{1 }and **X**
_{2 }are, respectively given by **X**
_{1 }is thus _{1 }= _{1}/_{1 }and _{2 }= _{2}/_{2}, respectively.

The proposed source-split transform coding (SP-DTC) system for two-terminal distributed quantization of two correlated vectors

**The proposed source-split transform coding (SP-DTC) system for two-terminal distributed quantization of two correlated vectors**.

Let **X**
_{1 }and **X**
_{2}, the design of a SP-DTC involves determining the values of the transforms

is minimized. By writing the quantization MSEs of _{2,j
}as _{1}, _{2}, the total MSE can be expressed as

The bit allocation problem can now be stated as follows:

Given a total bit-budget of

subject to

where

However, an explicit solution can be found for a variant of this problem obtained by fixing _{2}, so that the number of bits allocated to each transform code is fixed and it is only required to optimize the bit allocation among the quantizers within each transform code. For simplicity, we refer to this problem as the

3.1 Solution to the constrained bit-allocation problem

3.1.1 RD optimal quantization

Let _{2 }be fixed in Figure **X**
_{1}. Let the eigenvalues of

for some _{1 }and

see [

where **X**
_{1 }are jointly Gaussian, and it follows that

Furthermore, **X**
_{2 }and

Next consider TC **X**
_{2 }given **T**
_{2 }as the CKLT of **X**
_{2 }given _{2,m
}is given by

for some _{2 }
_{2}. The resulting MSE is given by

As before, the quantized value of **U**
_{2 }up to a scaling factor, can be represented by [

where _{2 }× _{2 }matrix consisting of first _{2 }columns of **K**
_{2 }and the quantization noise **X**
_{2}. The covariance matrix of **Z**
_{2 }is given by _{2 }are given by

The covariance matrix of **Y**
_{2 }is

Therefore **X**
_{1 }and

where

and

Finally, consider quantizing **X**
_{1}, given **X**
_{2 }given **V**, and RD optimal WZ quantization of each element of **V**, based on a bit-allocation specified by the eigenvalues of

for some

Given a rate tuple

3.1.2 High-resolution scalar quantization and SW coding

Due to **T**
_{2 }and

A similar expression exists for the quantization noise variance in (17).

3.2 A tree-search solution to the unconstrained bit-allocation problem

We note that the optimal solution to the unconstrained problem defined in (8) corresponds to the MMSE solution of the constrained problem over the set of rate-tuples

The solution space

**The solution space **. The tree-search algorithm uses a search-grid of regularly spaced points (i.e., a cubic lattice) with a separation of Δ

The proposed algorithm is a generalization of a class of bit-allocation algorithms in which a small fraction Δ

In order to describe the proposed tree-search algorithm in detail, let Δ**T**
_{2}, then there are three possible choices for the rate-tuple **X**
_{1}, **X**
_{2}). In the second iteration of the algorithm, we allocate Δ_{2}. This requires the solution of three constrained bit allocations problems for each of the 3 nodes in the first-level. As a result, the tree will be extended to a second level of 3^{2 }nodes, in which each node corresponds to a SP-DTC of 2Δ^{
L
}nodes in the last level (terminal nodes). Each terminal node corresponds to a candidate SP-DTC of rate _{n }
^{
n
}in the ^{
L
}) is a prescribed constant, the complexity is linear in

Bit allocation tree with the values of the rate-tuple

**Bit allocation tree with the values of the rate-tuple **.

4 Numerical results and discussion

**X**
_{1 }be _{1 }consecutive samples of a first-order Gauss-Markov process with a unit-variance and the correlation coefficient _{1,m
}= _{1,(m-1) }+ _{m }, m _{1}, where _{m}, m _{1 }are mean-zero iid Gaussian variables such that **X**
_{2 }to be noisy observations of the components of **X**
_{1}, i.e., _{2,m
}= _{1,m
}+ _{m}
_{m }
_{1 }(_{2 }= _{1}). It follows that, **X**
_{1 }and **X**
_{2 }are not statistically similar and the components of **X**
_{1 }are more correlated than those of **X**
_{2}.

**X**
_{1 }and **X**
_{2 }to be observations picked-up by a pair of sensor arrays placed in this random filed. In this case, the auto-covariance matrix of **X**
_{1 }is given by _{ij }
_{1,i
}and _{1,j
}. The auto-covariance matrix of **X**
_{2 }also has a similar form. For simplicity assume that the sensors in each array are placed on a _{1 }= _{2 }= ^{2}), the two arrays are on parallel planes separated by a distance _{1i
}and _{2i
}is _{1i
}and _{2j
}is ^{2}}. This sensor structure ensures that **X**
_{1 }and **X**
_{2 }are statistically similar. However,

4.1 RD performance

We compute the rate-pairs (_{1}, _{2}) achievable with a SP-DKLT code for a given a total MSE _{1 }(or _{2}) and then searching for minimum _{2 }(or _{1}) required to achieve the MSE **X**
_{1 }split)" corresponds to a system in which the input to terminal 1 (which applies source splitting) is **X**
_{1 }as shown in Figure **X**
_{2 }split)" corresponds to a system in which the input to the terminal 1 is **X**
_{2}. Note that the two curves are not symmetric in rates and they coincide if _{1 }and _{2 }are inter-changed in one of the curves. This is because **X**
_{1 }and **X**
_{2 }have different auto-covariance matrices, and hence inter-changing the rates is equivalent to inter-changing the terminals. Importantly, this result indicates that when the two sources are not statistically identical, which source is chosen for splitting does not affect the SP-DKLT performance. Table _{1}, _{2}), the rate-split between **X**
_{1 }is applied to the terminal 1 is not identical to that when **X**
_{2 }is applied to the terminal 1.

Comparison of rate-regions achievable with different TC approaches in quantizing 16-dimensional vectors (_{1 }= _{2 }= 16) of

**Comparison of rate-regions achievable with different TC approaches in quantizing 16-dimensional vectors ( M _{1 }= M_{2 }= 16) of source model A (ρ = 0.9, γ = 0.9)**. "SP-DKLT (X

Bit allocations found by the tree-search algorithm for 16-dimensional SP-DKLT coding of

_{1 }Split

_{2 }Split

**
X
_{1}
**

**
X
_{2}
**

**
X
_{2}
**

**
X
_{1}
**

**
B
_{1}
**

**
B
_{2}
**

**
B
**

**
B
_{1}
**

**
B
_{2}
**

**
B
**

0

14.8

14.8

96

110.8

0

22

22

96

118

0

15

15

80

95

0

22.4

22.4

80

102.4

0

15.8

15.8

64

79.8

0

22.6

22.6

64

86.6

0

19

19

48

67

0

24.4

24.4

48

72.4

0

22

22

44

66

0

25.6

25.6

44

69.6

3.2

22.8

26

40

66

0

26.8

26.8

40

66.8

10

20

30

36

66

0

30

30

36

66

16.6

16.4

33

33

66

2.8

30.2

33

33

66

18.6

15.4

34

32

66

4.2

29.8

34

32

66

23.2

12.8

36

30

66

7.6

28.4

36

30

66

34.2

5.8

40

27.2

67.2

17.4

22.6

40

26

66

44

0

44

25.8

69.8

32

12

44

22

66

48

0

48

24.4

72.4

43.8

4.2

48

19.4

68.4

64

0

64

22.6

86.6

64

0

64

16

90

80

0

80

22.2

102.2

80

0

80

15.2

95.2

96

0

96

22

118

96

0

96

14.8

110.8

Figure **X**
_{1 }and **X**
_{2 }are functions of

Comparison of rate-regions achievable with different TC approaches in quantizing 16-dimensional vectors (_{1 }= _{2 }= 16) of

**Comparison of rate-regions achievable with different TC approaches in quantizing 16-dimensional vectors ( M _{1 }= M_{2 }= 16) of source model B for α = 0.32 and different values of θ**.

The RD performance in Figures _{1 }or _{2 }is sufficiently high. That is, the terminal with the higher bit rate can independently transform code its input with negligible distortion, and the other terminal can then apply WZ-TC at the minimum rate achievable with "almost unquantized" decoder side-information. However, for both source-models the rate-region achievable with source-splitting is strictly inside that of DKLT. In other words, there are some rate-pairs inside the DKLT rate-region for a given MSE _{1}, _{2}), the sumrate _{1 }+ _{2 }of SP-DKLT codes remains constant and reaches its minimum. For example, it can be seen from Figure **X**
_{1 }is in the range 1.375 - 2.5 bits/sample. From Table

The optimal SP-DKLT codes at

**The optimal SP-DKLT codes at D = 0.005 for source model B with α = 0.32 and θ = 0.9**. The minimum sum-rate is 2.5 bits/sample, which can also be achieved by time sharing of codes

4.2 Design examples

In this section, we focus on the practical design of SP-DKLT codes for a given pair of rates (_{1}, _{2}) based on both scalar and block-quantization. RD-WZQ model used in Section 3.1.1 implies infinite block-length WZ-VQ of each coefficient. A practically realizable approach to block WZ quantization is SWC-TCQ ^{6 }bits and TCQs up to 8,192 states are presented in

Suppose that a sequence of source samples {_{n }
_{n }
_{1}, _{2}, . . ., into a _{TCQ }bits/sample output sequence _{1}, _{2}, . . . . However, CEC-TCQ output satisfies the additional property that the conditional entropy _{n}|Y_{n}
_{2 }
_{n}|Y_{n}
_{n}
_{n }- Û_{n}
^{2}}, subject to the constraint _{2 }
_{n}|Y_{n}

where _{1}, _{2}, . . ., the CEC-TCQ encoder should use the Viterbi algorithm based on the path-cost function

In a rate _{TCQ }TCQ, each codeword _{k }
_{TCQ}-bit binary string _{i }
_{2}
_{i}|Y_{2}
_{i}
_{2 }
_{i}|Y_{n}, Y_{n}
_{2 }
_{i }|Y

where _{i}
_{k}
_{k}
_{i}
_{i, k }
_{i}, Ŷ = η_{k}
_{2 }
_{n }|Y_{n}

For block WZ-code designs, the transforms and the bit allocations are found by RD-WZQ model (Section 3.1.1) and WZ quantizers are implemented using CEC-TCQ followed by binary SW coding. More specifically, the rate found by the bit allocation algorithm for each transform coefficient is used as the conditional entropy constraint in the design of a CEC-TCQ for that coefficient. As described in Section 2.3, the CEC-TCQ designs are based on scalar-side information obtained by a linear transform of the vector side-information at the decoder, see ^{5 }have been used. Since, the main focus this paper is the design of transforms and the quantizers, we assume ideal SW coding of the binary output of each CEC-TCQ, so that our results do not depend on any particular SW coding method. In a practical implementation (e.g.,

We also consider SP-DKLT code designs based on scalar quantization. In this case, the transforms and bit allocations are found by using the SWC-HRSQ model (Section 3.1.2). While it is possible to use the step-size predicted by SWC-HRSQ model to design uniform quantizers, we found that such quantizers in reality do not satisfy the required entropy constraint at lower rates. We instead use conditional entropy constrained scalar quantizers (CEC-SQ), designed by modifying the algorithm in

The reconstruction signal-to-noise ratio (RSNR) [with MSE as given by (6)] of SP-DKLT code designs for

RSNR (in dB) of KLT-based transform code designs for quantizing 16-dimensional vectors (_{1 }= _{2 }= 16) of _{1 }= _{2 }=

**R**

**IKLT**

**SP-DKLT**

**(bits/sample)**

**EC-SQ**

**EC-TCQ**

**CEC-SQ**

**CEC-TCQ**

0.5

10.3

11.7

12.4

14.0

(Analytical)

10.3

11.0

11.6

12.7

(design)

1

16.6

18.0

19.1

20.6

16.4

17.3

18.6

19.6

1.5

21.6

23.0

23.8

25.6

21.7

22.5

23.3

24.4

2

25.7

27.1

28.2

29.8

25.2

26.6

27.8

28.6

Analytical values refer to SNR of the quantization model assumed for determining the optimal transforms and the bit-allocation

From a practical view point, the use of DCT instead of KLT is interesting

SNR (in dB) of DCT-based transform code designs for quantizing 16-dimensional vectors (_{1 }= _{2 }= 16) of _{1 }= _{2 }=

**R**

**IDCT**

**SP-DDCT**

**(bits/sample)**

**EC-SQ**

**EC-TCQ**

**CEC-SQ**

**CEC-TCQ**

0.5

7.9

9.1

11.7

12.6

(Analytical)

8.0

8.4

11.0

12.0

(design)

1

11.9

13.2

15.9

17.8

11.9

12.6

16.6

17.0

1.5

15.3

16.8

19.7

21.9

15.3

16.1

20.5

21.3

2

18.9

20.3

23.6

25.6

18.7

19.4

24.5

25.1

Analytical values refer to SNR of the quantization model assumed for determining the bit-allocation.

5 Concluding remarks

Rate-distortion analysis and experimental results demonstrate that SP-DTC is a promising practical approach to implementing distributed VQ of high-dimensional correlated vectors. The comparisons shown in Table

1 Appendix

1.1 Proof of Theorem 2

The optimality of CKLT is proved in _{m }
_{m }
_{m }
_{m }|**Y**) bits/sample, _{1}, where _{m}|**Y**) _{m}|**Y**) - log_{2}(Δ_{
m
}), where Δ_{
m
}is the quantizer step-size and _{m}
**Y **is _{m}
**Y**) are jointly Gaussian, it follows that _{m}|**Y**) = (1/2) log_{2 }(2_{m}
_{m }

Since (27) and (1) are the same within a constant factor of

and hence the overall MSE is given by (5). Furthermore,

for

1.2 Proof of Theorem 3

For jointly Gaussian and mean-zero **X **and **Y**, there exists a matrix **A **and a mean-zero Gaussian vector **W**
_{1 }independent of **Y **such that **X **= **AY **+ **W**
_{1}, where **Λ **is the diagonal matrix of eigenvalues of ∑_{
X|Y
}. Furthermore **U **= **T**
^{
T
}
**AY **+ **W**
_{2}, where **W**
_{2 }= **T**
^{
T
}
**W**
_{1 }is an uncorrelated Gaussian vector since **T**
^{-1 }= **T**). Therefore ∑_{
U|Y
}= **Λ**. The MMSE estimate of **U **given **Y **is **Ũ **= **U**|**Y**} = **T**
^{
T
}
**X**
**Y**} = **T**
^{
T
}
**AY**. Thus, **U **= **Ũ **+ **W**
_{2 }and **∑**
_{
U|Ũ
}= **Λ**, and it follows that _{i }
_{j }
_{i}| Ũ_{i}
_{i }|**Y**), where var(_{i}|**Y**) = _{i}| Ũ_{i}
_{i }
**Y **in WZ quantization of _{i}

Competing interests

The author declares that they have no competing interests.