Preliminaries

Let $X\in{\mathbb{R}}^k$ be a random vector with independent components drawn from a $N(0,\sigma^2)$ memoryless Gaussian source. The probability density function (pdf) of $X$ is $f_X(Y) = (2\pi\sigma^2)^{-k/2} \exp(-\Vert Y\Vert^2 /(2\sigma^2))$ for $Y\in{\mathbb{R}}^k$. Let $\Omega _k = \{ Y\in{\mathbb{R}}^k : \Vert Y\Vert = 1 \}$ be the unit sphere in $k$-dimensions, and let $S_k = 2 \pi^{k/2} / \Gamma(k/2)$ be the $(k-1)$-dimensional content (``surface area'') of $\Omega _k$, where $\Gamma(u) = \int_0^\infty t^{u-1} e^{-t}\, dt$ is the usual gamma function. Also denote the beta function by $\beta(u,v) = {\Gamma(u) \Gamma(v) / \Gamma(u+v)}$. The following lemma gives some properties of $g = \Vert X\Vert$.

Lemma 1  

$$f_g(r) = f_{\Vert X\Vert}(r) = {2 r^{k-1} \exp\left({-r^2 \over 2 \sigma^2}\right) \over \Gamma(k/2) (2\sigma^2)^{k/2}}$$ pdf: (1)

$$E[\Vert X\Vert] = {\sqrt{2 \sigma^2} \, \Gamma\left({k+1 \over 2}\right) \over \G... ...ght)} = {\sqrt{2 \pi \sigma^2} \over \beta\left({k \over 2},{1 \over 2}\right)}$$ mean: (2)

$$E[\Vert X\Vert^2] = k\sigma^2$$ second moment: (3)

$$[\Vert X\Vert] = k\sigma^2 - {2 \pi \sigma^2 \over \beta^2\left({k \over 2},{1 \over 2}\right)}.$$ variance: (4)

Eq. (1) is the generalized Rayleigh law [29] and (2), (3), and (4) follow by direct computation.

A consequence of Lemma 1 is that the mean of $g$ is approximately $\sigma\sqrt{k-(1/2)}$ for large $k$ (by application of Stirling's formula), while the variance of $g$ is bounded by $\sigma^2/2$ for all $k$ [30]. Thus, as $k\rightarrow\infty$, the normalized quantity $g/\sqrt{k\sigma^2}$ has a mean which tends to one and variance which tends to zero. This is the so-called ``sphere-hardening'' effect [31], and implies that for large $k$, the random vector $X/\sqrt{k\sigma^2}$ is approximately uniformly distributed on $\Omega _k$, which provides motivation for mapping lattices from ${\mathbb{R}}^{k-1}$ to $\Omega _k$. The performance of lattice quantizers for a uniform source in a region of ${\mathbb{R}}^{k-1}$ (asymptotically optimal under Gersho's conjecture [32]) can then be transformed to the same performance for a uniform source in $\Omega _k$.

A $k$-dimensional vector quantizer is a mapping $Q : {\mathbb{R}}^k \rightarrow {\mathbb{R}}^k$ whose range, called a codebook, is finite. The elements of a codebook are called codevectors. A spherical vector quantizer (SVQ) with radius $r$ is a vector quantizer whose codevectors each have Euclidean norm $r$. A nearest neighbor quantizer $Q$ is a quantizer such that for every $x\in{\mathbb{R}}^k$, no codevector is closer to $x$ than $Q(x)$. The rate of the vector quantizer $Q$ is defined as $R = (\log_2 N)/k$ bits, where $N$ is the number of codevectors of $Q$. For notational convenience, $Q(x)$ is often replaced by $\hat x$.

A nearest neighbor spherical vector quantizer satisfies $Q(cX)=Q(X)$ for all $c>0$. Sakrison [25] showed that if a nearest neighbor spherical vector quantizer with radius $E[\Vert X\Vert]$ is used to quantize a Gaussian random vector $X$, then the resulting MSE distortion per dimension can be decomposed into shape and gain distortions as

Figure 1: Encoding using Sakrison's quantizer.

$$D = {1 \over k} E\left[\Vert X-\hat X\Vert^2\right] = \underbrace... ...distortion}} + \underbrace{\mbox{var}[\Vert X\Vert]/k}_{\text{gain distortion}}$$ (5)

where $X_p = E[\Vert X\Vert]\cdot{X \over \Vert X\Vert}$ (see Figure 1).

The gain distortion term of (5) becomes negligible as $k$ increases and an effective quantizer for $X$ is a spherical vector quantizer with radius $E[\Vert X\Vert]$ for a source uniformly distributed on $\Omega _k$. Using a random coding argument Sakrison described such a quantizer and showed that it approaches the distortion-rate function, but the complexity of his quantizer grows linearly with the codebook size.

In the present paper, we describe a high performance Gaussian quantizer using shape-gain vector quantization. The shape quantizer is a wrapped spherical quantizer that can be effectively implemented and which also has excellent distortion performance. No assumption is made that $k$ is asymptotically large, and hence it is not assumed that the gain distortion in (5) is negligible. For example, when $k = 25$ and $\sigma^2=1$, the gain distortion dominates the overall distortion performance at rates of three or higher.

A shape-gain vector quantizer decomposes a source vector $X$ into a gain $g = \Vert X\Vert$ and shape $S = X/g$, which are quantized to $\hat{g}$ and $\hat{S}$, respectively, and the output is $\hat X = \hat{g}\hat{S}$ (see Figures 2 and 3 ). As is common practice we assume the quantized shape satisfies $\Vert\hat{S}\Vert=1$. An advantage of shape-gain VQ is that the encoding and storage complexities grow with the sum of the gain codebook size and shape codebook size, while the effective codebook size is the product of these quantities. Necessary optimality conditions are known for optimal shape-gain quantization and these can be used to design locally optimal shape-gain vector quantizers [4, pg. 446]. However, such a design procedure yields unstructured shape codebooks, which can become too large in practice (we determine the optimal codebook sizes analytically for high rates in Section III-C). In our example implementation, the gain codebook has 15 or fewer codevectors for rates under 4, and the shape codebook can be implicitly computed and thus does not need to be stored.

Figure 2: Block diagram of shape-gain quantizer encoder.

Figure 3: Encoding using the shape-gain quantizer.