# An Upgraded Version of the Binary Search Space-Structured VQ Search Algorithm for AMR-WB Codec
## 3 Proposed Search Algorithm
### The BSS-VQ Search Algorithm  
As a prerequisite of a VQ codebook search in the BSS-VQ algorithm, an input vector is assigned in an efficient manner to a subspace, over which a small number of codeword searches is conducted through the combined use of lookup tables and a fast locating technique. As it turns out, the computational load can be reduced significantly. To begin with, each dimension is dichotomized into two subspaces, and an input vector is then assigned to a subspace according to the entries of the input vector. This is illustrated as follows. For instance, given a 9-dimensional subvector \(\mathbf{r}_{1}(n)\) associated with codebook CB1, there are up to \begin{table}
\begin{tabular}{l l l l l} \hline \hline  & \multicolumn{4}{c}{**Structure of S-MSVQ**} \\ \hline \multirow{2}{*}{Stage 1} & CB1: & & CB2: \\  & \(\mathbf{r}_{1}\) (1–9 order of \(\mathbf{r}\)) & & & \(\mathbf{r}_{2}\) (10–16 order of \(\mathbf{r}\)) \\  & (8 bits) & & & (8 bits) \\ \hline \multirow{2}{*}{Stage 2} & CB11: & CB12: & CB13: & CB21: & CB22: \\  & \(\mathbf{r}^{(2)}\),1–3 & \(\mathbf{r}^{(2)}\),1–6 & \(\mathbf{r}^{(2)}\),1–9 & \(\mathbf{r}^{(2)}\),2,1–3 & \(\mathbf{r}^{(2)}\),2,4–7 \\  & (6 bits) & (7 bits) & (7 bits) & (5 bits) & (5 bits) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Structure of split-multistage vector quantization (S-MSVQ) in adaptive multi-rate wideband (AMR-WB) in the 8.85–23.85 kbps coding modes. \(2^{9}=512\) subspaces, to one of which an input vector is then assigned by means of a dichotomy, according to each entry of the input vector. As defined in [10], a dichotomy position refers to the mean of all the codewords contained in a codebook, expressed as  
\[dp(j)=\frac{1}{CSize}\sum_{i=1}^{CSize}c_{i}(j),\;0\leq j<Dim, \tag{8}\]  
where \(\mathbf{c}_{i}(j)\) denotes the \(j\)th component of the \(i\)th codeword \(\mathbf{c}_{i}\), and \(dp(j)\) the mean value of all the \(j\)th components. For example, \(CSize=256\), \(Dim=9\) in the codebook CB1, all the \(dp(j)\) values are saved, and then presented in Table 2. That is, the values in Table 2 are obtained by way of using (8) to calculate the statistical mean of all the codewords in CB1. A quantity \(v_{n}(j)\) is then defined for vector quantization on the \(n\)th input vector \(\mathbf{x}_{n}\), expressed as  
\[v_{n}(j)=\left\{ \begin{array}{c}2^{j},\mathbf{x}_{n}(j)\geq dp(j)\\ 0,\mathbf{x}_{n}(j)<dp(j)\end{array} \right.,\;0\leq j<Dim, \tag{9}\]  
where \(\mathbf{x}_{n}(j)\) symbolizes the \(j\)th component of \(\mathbf{x}_{n}\). Subsequently, \(\mathbf{x}_{n}\) is assigned to subspace \(k\) (\(bss_{k}\)), where \(k\) is the sum of \(v_{n}(j)\) over all of the dimensions, expressed as  
\[\textit{Assigning}:\mathbf{x}_{n}\in bss_{k}|k=\sum_{j=0}^{Dim-1}v_{n}(j). \tag{10}\]  
Since \(0\leq k<BSize\) and \(BSize=2^{9}=512\) in this article, there are a total of 512 subspaces. For example, given an input vector \(\mathbf{x}_{n}=\{16.0,\,17.1,\,18.2,\,19.3,\,20.4,\,21.5,\,22.6,\,23.7,\,24.8\}\), \(v_{n}(j)=\{2^{0},\,0,\,2^{2},\,0,\,0,\,0,\,2^{7},\,2^{8}\}\) for each \(j,\,0\leq j\leq 8\), and \(k=389\) are given by (9) and (10), respectively. Thus, the input vector \(\mathbf{x}_{n}\) is assigned to the subspace \(bss_{k}\) with \(k=389\). In this manner, merely a small number of basic operations, i.e., comparison, shift, and addition, are required, meaning that an input vector is efficiently assigned to a subspace as requested. As stated in Reference [10], a lookup table is prebuilt in each subspace by performing a training mechanism after the dichotomy position for each dimension is determined. The lookup tables give the probability that each codeword works as the best-matched codeword in each subspace, referred to as the hit probability of a codeword in a subspace for short, and symbolized as \(P_{hit}(\mathbf{c}_{i}\;|\;bss_{k})\), \(1\leq i\leq CSize\), \(0\leq k<BSize\).