Computational Complexity

The arithmetic functions needed to implement the quantizer are addition, multiplication, division, trigonometric functions, square root, and comparison. To make a rough estimate of computational complexity (which of course is machine dependent) we count one operation for any arithmetic function.

In Table III, Step 1 requires no computation, and Step 2 requires $k$ multiplies, $k-1$ additions, and one square root to calculate the gain; and $k$ divisions to calculate the shape. Step 3 requires one scalar quantization operation, which can be performed by a binary search with at most $kR_g$ comparisons. Step 4 requires $\log_2 N \le kR_s$ comparisons to identify $i$; one additional trigonometric function, one difference, one division, and one multiplication to compute $\Vert S_L - S\Vert = 2\sin((\sin^{-1}x_k)-\alpha_i)/2)$; one trigonometric function to compute $\Vert(S_L)'\Vert = \cos(\alpha_i)$; one difference to compute $\Vert(S_L)'\Vert - \Vert S_L - S\Vert$; one multiplication, one difference, and one square root to compute $\Vert S'\Vert = \sqrt{1 - x_k^2}$; and 1 division and $k-1$ multiplications to compute $h_i(S)$. Thus, Step 4 requires no more than $k+kR_s+10$ operations. Step 5 requires the number of steps in a nearest neighbor algorithm for $\Lambda$. For the Leech lattice, the fastest known algorithm requires about 2955 operations on average [45]. Step 6 requires $k-1$ squarings, $k-2$ additions, and one square root to determine $\Vert\hat h_i(S)\Vert$; one difference and one division to determine $1/(\Vert(S_L)'\Vert - \Vert\hat h_i(S)\Vert)$; $k-1$ multiplications to determine the first $k-1$ coordinates of $h_i^{-1}(\hat h_i(S))$; and one square, one difference, and one square root to determine the last coordinate. Thus, Step 6 requires $3k+2$ operations. Step 7 requires one multiplication and two additions to determine the index. Altogether, this amounts to at most $k(R+7) + L + 15$ arithmetic operations, where $k$ is the dimension, $R$ is the rate, and $L$ is the computational complexity of the nearest neighbor algorithm of $\Lambda$. Thus, per sample, the computational complexity is at most $R+7 +(L+15)/k$. For the ${\rm W}_{\Lambda _{24}}$, the parameters are $k = 25$ and $L=2955$, and the computational complexity is upper bounded by $R+119$.

Thus, the computational complexity of ${\rm W}_\Lambda$ grows linearly with rate, and is comparable to that of trellis-coded quantization (TCQ). Table IV-C summarizes these complexities.

Table IV: Comparison of computational complexities of quantization schemes for a memoryless Gaussian source. Data for other methods are taken from [20, Table XII]. $k$ = dimension, $R$ = rate, $S$ = number of trellis states.

Method	Computations
${\rm W}_{\Lambda _{24}}$	$R+126$
TCQ (doubled alphabet) [20]	$3S + 4R + 4$
TCQ (quadrupled alphabet) [20]	$3S + 8R + 8$
Generalized Lloyd algorithm (GLA) [4]	$2^{kR+1}$
Wilson's stochastic trellis [44]	$S\cdot 2^{R+1}$
Pearlman's stochastic trellis [3]	$(S+2) 2^R$