# An Upgraded Version of the Binary Search Space-Structured VQ Search Algorithm for AMR-WB Codec
## 1 Introduction  
The development of the adaptive multi-rate wideband (AMR-WB) speech codec [1; 2; 3; 4] aims to considerably improve the speech quality on handheld mobile devices. It is an algebraic code-excited linear-prediction (ACELP)-based coding technique [4; 5], and is equipped with nine coding modes with bitrates between 6.6 and 23.85 kbps. Regardless of its excellent speech coding technique, the price paid is a high computational complexity during coding. In other words, the speech quality of a smartphone can be improved at the cost of high battery power consumption, using an AMR-WB codec.  
It takes an AMR-WB encoder a tremendous amount of time to quantize immittance spectral frequency (ISF) coefficients in various coding modes [6; 7; 8; 9]. The ISF coefficient in AMR-WB is quantized through the combined use of a split vector quantization (SVQ) and a multistage VQ technique, designated as split-multistage VQ (S-MSVQ) [1]. Traditionally, a full search is employed to obtain a codeword best matched with an arbitrary input vector, and an enormous computational load is required consequently. Accordingly, efforts have been made to reduce the search complexity of an encoding process in [10; 11; 12; 13; 14; 15; 16; 17; 18], among which the binary search space-structured VQ (BSS-VQ) search algorithm in [10], a piece of our previous studies, was presented as a simple but efficient way to quantize the ISF coefficient in AMR-WB. A remarkable computational load reduction is achieved therein with a well-maintained speech quality. The BSS-VQ search algorithm was also experimentally validatedto outperform an equal-average equal-variance equal-norm nearest neighbor search (EEENNS) algorithm [11; 12; 13; 14] and triangular inequality elimination (TIE)-based algorithms [15; 16; 17], e.g., the DI-TIE algorithm [15], short for a TIE with a dynamic and an intersection mechanism, and a multiple TIE (MTIE) approach [17].  
A deeper investigation reveals that the search performance of the BSS-VQ algorithm is subject to the codeword distributions. As a way to boost the search performance, an upgraded version of the BSS-VQ algorithm is developed herein through a sequential use of the BSS-VQ algorithm and the iterative TIE (ITIE) approach [18]. To begin with, an input vector is assigned to a search subspace in an efficient manner using the BSS-VQ algorithm, and subsequently, a codebook search is performed over the subspace using the ITIE approach. Via the use of the codeword rejection mechanisms equipped in BBS-VQ and ITIE, the search load is reduced significantly as intended. The presented algorithm is ultimately validated to well outperform its counterparts, and is fit to meet the energy saving requirement when implemented on an AMR-WB codec of mobile devices. In addition, the Enhanced Voice Services (EVS) codec [19] is a new standard of audio codec optimized for operation with voice and music/mixed content signals. The EVS codec also provides interoperation with AMR-WB over all nine coding modes. That is to say the contribution of this study is also applicable to the speech coding in EVS codec.  
The rest of this paper is organized as follows. The ISF coefficient quantization in AMR-WB is described in Section 2. Section 3 presents the proposed search algorithm for ISF quantization. Experimental results are demonstrated and discussed in Section 4, and finally Section 5 concludes this work.