Due to the double advantage of low bit rate and high speech quality, the algebraic code-excited linear-prediction (ACELP)-based speech coding technique (Adoul et al., 1987; Laflamme et al., 1991; Salami et al., 1998; Bessette et al., 2002) is the type of technique most widely used to digital speech communication systems, and is adopted in a great number of speech codec standards, such as G.723.1, G.729 (ITU-T Recommendation and 729, 1996), G.729.1 (ITU-T Recommendation and 1, 2006; Geiser et al., 2007) in International Telecommunication Union (ITU), adaptive multi-rate narrowband (AMR-NB) (3GPP TS 26.090, 2012a) and wideband (AMR-WB) (3GPP TS 26.190, 2012b; Ojala et al., 2006; Varga et al., 2006) in the 3rd Generation Partnership Project (3GPP). Among such protocols, an AMR-WB speech codec with a 16 kHz sampling rate is applied to 4G mobile communication system as a way to remarkably improve the speech quality of a smartphone.

An AMR-WB codec is a multi-mode speech codec with 9 wideband speech coding modes with bitrates of 23.85, 23.05, 19.85, 18.25, 15.85, 14.25, 12.65, 8.85 and 6.6 kbps. ACELP is developed as an excellent speech coding technique, but a price paid is a high computational complexity required in an AMR-WB codec, particularly much higher than in an AMR-NB one. Using an AMR-WB speech codec, the speech quality of a smartphone can be improved, but at the cost of high power consumption on a smartphone battery.

In an AMR-WB encoder, a depth-first tree search (DF) algorithm is performed for the purpose of an algebraic codebook search, and a DF search is found to occupy a significant computational load in various speech coding modes. A brief literature survey on the complexity reduction in algebraic codebook search is given as follows. An attempt is made to decrease the number of the candidate positions in a candidate scheme for fast ACELP search (Chen et al., 2002). As presented in Park et al. (2002), the least significant pulse is replaced in an iterative manner. Developed on the basis of Park et al. (2002), a global pulse replacement (GPR) (Lee et al., 2003), is adopted by G.729.1 (ITU-T Recommendation and 1, 2006). An iteration-free pulse replacement (IFPR) (Lee et al., 2007) method and a number of previously published reduced candidate mechanism (RCM) based search algorithms (Yeh and Su, 2012; Chu et al., 2014; Ku et al., 2014) are proposed to further reduce the search complexity in an efficient way. In addition, the issue of computational complexity reduction has been addressed in literature, as presented in Tsai and Yang (2006).

As can be found in literature, a continuous effort has been made to address the issue of computational complexity reduction for an AMR-WB speech codec. A major motivation behind this is to meet the energy saving requirement on handheld devices, e.g. smartphones, for an extended operational time period.

This improved algebraic codebook search algorithm is a combined use of the RCM approach (Yeh and Su, 2012) and a DF algorithm. An RCM approach requires to locate 2–6 candidate pulses of each track, as a prerequisite, in an algebraic codebook search at 12.65 kbps and higher AMR-WB modes. In this context, there is no way to reduce the search complexity using RCM. For this sake, a specified number of candidate pulses are located out of each track in advance of a search task, and then the scope of DF search for a set of best pulses is confined within all the candidate pulses. In this manner, the search complexity can be reduced significantly, and the mechanism of the candidate pulse determination will be detailed herein.

This paper is outlined as follows. The coding criterion of algebraic codebook search in AMR-WB is briefly reviewed in Section 2. Presented in Section 3 is an efficient approach for the purpose of search complexity reduction. Experimental results are demonstrated and discussed in Section 4. This work is summarized at the end of this paper.

In AMR-WB speech codec, the algebraic codebook structures corresponding to nine coding modes with bit rates of 23.85, 23.05, 19.85, 18.25, 15.85, 14.25, 12.65, 8.85 and 6.60 kbps are given in 3GPP TS 26.190 (2012b). The codebook is structured using an interleaved single-pulse permutation (ISPP) scheme, where each pulse is with an amplitude of +1 or −1. As can be found, a codebook contains 2 tracks, each with 32 pulse positions, in the 6.60 kbps mode, and a nonzero pulse is located. In contrast, a codebook has 4 tracks in the remaining eight coding modes with bit rates of 8.85–23.85 kbps, and 16 pulse positions are assigned to each track. Subsequently, 1–6 nonzero pulses are located according to the specified coding mode.

The optimal codevector c k = { c k ( n ) } is thus found by minimizing the mean squared weighted error between the original and the synthesized speeches (Bessette et al., 2002), defined as (1) ε k = ‖ x − g Hc k ‖ 2 , where x denotes the target vector, g a scaling gain factor, and H a lower triangular convolution matrix. It can be shown that the optimal codevector is the one maximizing the term  Q k (Bessette et al., 2002; 3GPP TS 26.190, 2012b): (2) Q k = ( x T Hc k ) 2 c k T H T Hc k = ( dc k ) 2 c k T Φ c k , where d = x T H, the correlation function, is expressed as (3) d ( n ) = ∑ i = n L − 1 x ( i ) h ( i − n ) , 0 ⩽ n ⩽ L − 1 , where h ( n ) is the impulse response of the weighted synthesis filter, L is the speech subframe size. The correlations of h ( n ) are contained in the symmetric matrix Φ = H T H, where the entries are given by (4) ϕ ( i , j ) = ∑ n = j L − 1 h ( n − i ) h ( n − j ) , 0 ⩽ i ⩽ L − 1 , i ⩽ j ⩽ L − 1 .

In an attempt to locate the optimal vector, (2) is evaluated repeatedly and a full search is performed for N FS number of times, given as (5) N FS = ∏ i = 1 N T C N s ( T i ) N p = ∏ i = 1 N T ( N p ) ! ( N s ( T i ) ) ! ( N p − N s ( T i ) ) ! , where N T represents the number of tracks, N p the number of pulse positions assigned to each track, and N s ( T i ) the number of optimal pulses that need to be located in track i. Taking the 12.65 kbps mode in 3GPP TS 26.190 (2012b) as an instance, N T = 4, N p = 16, N s ( T i ) = 2 for all i, meaning that it requires as many as ( C 2 16 ) 4 full searches that is an impractically large load to implement. For this sake, a DF algorithm is employed in AMR-WB for search load reduction.

As listed in Table 1, the number of levels in a tree search is evaluated as one-half the total number of nonzero pulses. In other words, there are 2 nonzero pulse contained in each level, and a search is conducted on consecutive levels to locate a pair of best nonzero pulses. The search scope in each level is confined to 2 neighbouring tracks, say, ( T 0 , T 1 ), ( T 1 , T 2 ), ( T 2 , T 3 ), ( T 3 , T 0 ). A pulse is located until a set of best pulses is found. Besides, 3 parameters are specified for each speech coding mode. The first parameter, designated as the number of no search level, refers to the number of levels where a set of best pulses is specified directly, meaning that there is no need to perform any search task. The second, termed as NTested, refers to the test combinations in the remaining levels, and the third, denoted by NIter, represents the number of iterations. Accordingly, the total number of searches is given as NIter × NTested.

A DF search is illustrated with the example of 12.65 kbps mode. The goal is to locate the desired 8 best pulses, according to which there are 4 levels involved in a tree search. As the first step, a set of best pulses is specified directly, not by way of search, in level 1. Subsequently, respective numbers of searches are performed over the remaining levels, as specified in Table 1, i.e. 4 × 16, 8 × 16, 8 × 16, such that the best pulses for each level are located. In this manner, it requires 4 iterations to get the search done, that is, a total of 4 × ( 4 × 16 + 8 × 16 + 8 × 16 ) = 1280 searches are required. In short, the DF search accounts for a significant computational load in the AMR-WB encoder operation. Besides, two existing methods, the GPR and RCM approaches, will be discussed in this section.

Using a combination of RCM and DF approaches, an improved depth-first tree search (IDFT) is presented in this section as a way to reach the goal of search complexity reduction. This is done by means of a reduction in the number of candidate pulses contained in each track ahead of a DF search, and the reduction is made according to the contribution made by each pulse, but with a different criterion to evaluate individual pulse contribution than in RCM. Hence, this section firstly refers to the contribution made by a single pulse, and then details a search algorithm.

There are two experiments conducted in this work. The first is a search complexity comparison among various search approaches. The second is that various approaches are compared with ITU-T P.862 perceptual evaluation of speech quality (PESQ) ITU-T Recommendation and 862 (2001) as an objective measure of speech quality. The test objects are those selected out of a Chinese-language speech database, containing 1 694 syllables out of 50 sentences for a duration over 445 s and 89 020 subframes.

For the brevity of the following discussion, the proposed IDFT approach with M candidate pulses is abbreviated as IDFT-M, 1 ⩽ M ⩽ 16. For instance, IDFT-1 symbolizes the one with merely a candidate pulse extracted out of each track. Similarly, the GPR approach with R repetitions is designated as GPR-R.

Firstly, listed in Table 2 is a comparison on the search complexity, that is, the number of searches performed and those required in the evaluation of Q k defined in (2). The proposed IDFT search is performed among the first M ranked pulses on a condition that M be greater than the number of best pulses in each track. Table 2 firstly gives the number of searches required in a DF approach as a benchmark, and then gives relative search complexity change expressed in percentage form, i.e. computational saving (CS), in GPR and the proposed IDFT approaches for comparison purposes. A high value of CS reflects a high search complexity reduction, while a negative sign indicates a search complexity higher than in the DF case.

With DF as a benchmark, a noticeable computational saving is demonstrated, and the aim of search load reduction is achieved as expected by this proposal. It is noted that a CS above 50% can be reached for M ⩽ 8. Nevertheless, a comparison on speech quality must be made for a complete performance assessment of this presented search algorithm.

Table 3 gives a PESQ comparison, including the mean and the standard deviation (STD), in the 12.65, 15.85, 18.25 and 23.85 kbps modes. With DF as a benchmark, a minus sign in the comparison represents a superior PESQ relative to the benchmark. As pointed out in Yeh and Su (2012), a subjective speech quality can be well maintained even though there is a slight drop in PESQ.

A rearrangement of Tables 2 and 3 gives Table 4. As listed in Table 4, on a condition of PESQ drop stays below 1% as compared with the DF case, the best choice of R in GPR and M in IDFT are respectively tabulated in various modes, and a performance comparison in the 23.85 kbps coding mode is presented in a graphic form as Fig. 2. The overall performance superiority is demonstrated with a well maintained high speech quality and a computational load reduction beyond 73%. A noticeable superiority over GPR is particularly seen in a high bit rate coding mode.

An improved depth-first tree search approach is presented in this work as an efficient means to enhance the search performance of an algebraic codebook search when applied to an AMR-WB speech codec. This improved version of depth-first tree search algorithm is presented as a way not merely to well maintain a high speech quality but also to achieve the aim of complexity reduction in algebraic codebook search. It offers a search performance superiority over a DF and a GPR counterpart. It is worth noting that with DF as a benchmark, a search load reduction beyond 73% is seen in all the coding modes on a condition that PESQ drop stays below 1%.

Furthermore, this improved AMR-WB speech codec can be adopted to improve the VoIP performance on a smartphone. As a consequence, the energy efficiency requirement is achieved for an extended operation time period due to computational load reduction.