Abstract:
A pulse location search device ( 400 ) is equipped with: a first search unit ( 401 ) that obtains a first location where a first pulse is located by conducting a first preliminary selection with respect to a first candidate group, and conducting a first search; a second search unit ( 402 ) that obtains a second location where a second pulse is located by using the first location and conducting a second search with respect to all of the location candidates of a second candidate group of locations where the second pulse is located; and a third search unit ( 403 ) that obtains a third location where the first pulse is located by using the second location and conducting a second preliminary selection with respect to the first candidate group, and conducting a third search with respect to the result of the second preliminary selection.

Description:
TECHNICAL FIELD 
       [0001]    The claimed invention relates to a pulse position searching apparatus that searches positions of a plurality of pulses, a method thereof and a codebook searching apparatus that searches positions of a plurality of pulses making up a codebook and a method thereof. 
       BACKGROUND ART 
       [0002]    In mobile communication, compression coding of digital information of speech or image is indispensable for effective use of a transmission band. Among those technologies, there are high expectations of speech CODEC technologies widely used for mobile phones and there is a growing demand for better sound quality with respect to conventional high efficiency coding with a high compressibility. Furthermore, since the technologies are used in public, standardization is indispensable, and because of powerful intellectual property rights involved, research and development are being actively conducted in many companies worldwide. 
         [0003]    In recent years, the standardization of CODEC capable of coding both speech and music is under study in ITU-T and MPEG, and there is a demand for more efficient and higher quality speech CODEC. 
         [0004]    Performance of speech coding technologies has been greatly improved by CELP (Code Excited Linear Prediction) which is a basic scheme that models a speech vocalization mechanism established 20 years ago and skillfully applies vector quantization. CELP is adopted as many standard schemes in international standards such as ITU-T (International Telecommunication Union-Telecommunication Standardization Sector) standard G.729, ITU-T standard G.722.2, ETSI (European Telecommunications Standards Institute) standard AMR (Adaptive Multiple Rate Coding), ETSI standard AMR-WB (Adaptive Multiple Rate Coding-Wide Band) or 3GPP (3rd Generation Partnership Project) 2 standard VMR-WB (Variable Multiple rate-Wide Band). 
         [0005]      FIG. 1  is a block diagram illustrating a configuration of a CELP coding apparatus. In  FIG. 1 , spectral parameters (LSP, ISP or the like) in CELP are quantized. 
         [0006]    In  FIG. 1 , LPC analyzing section  101  applies linear predictive analysis (LPC analysis) to a speech signal, acquires an LPC parameter which is spectral envelope information and outputs the acquired LPC parameter to LPC quantization section  102  and perceptual weighting section  111 . 
         [0007]    LPC quantization section  102  quantizes the LPC parameter outputted from LPC analyzing section  101 . LPC quantization section  102  then outputs the acquired quantized LPC parameter to LPC synthesis filter  109  and outputs an index (code) of the quantized LPC parameter to the outside of CELP coding apparatus  100 . 
         [0008]    On the other hand, adaptive codebook  103  stores past excitation used in LPC synthesis filter  109 , and generates an excitation vector corresponding to one subframe from excitation vectors stored according to an adaptive codebook lag corresponding to an index indicated from distortion minimizing section  112 , which will be described later. This excitation vector is outputted to multiplier  106  as an adaptive codebook vector. 
         [0009]    Fixed codebook  104  is a codebook of excitation coding (also referred to as “excitation quantization” or “excitation vector coding”). Fixed codebook  104  stores beforehand a plurality of excitation vectors having a predetermined shape and outputs an excitation vector corresponding to the index indicated from distortion minimizing section  112  to multiplier  107  as a fixed codebook vector. Here, fixed codebook  104  is an algebraic excitation, and a case using an algebraic codebook will be described. The algebraic excitation is an excitation adopted in many standard CODECs. 
         [0010]    Above-described adaptive codebook  103  is used to express a component with strong periodicity such as voiced sound. On the other hand, fixed codebook  104  is used to express a component with weak periodicity such as white noise. 
         [0011]    Gain codebook  105  generates a gain for the adaptive codebook vector (adaptive codebook gain) outputted from adaptive codebook  103  and a gain for the fixed codebook vector (fixed codebook gain) outputted from fixed codebook  104 , according to an instruction from distortion minimizing section  112  and outputs the respective gains to multipliers  106  and  107 . 
         [0012]    Multiplier  106  multiplies the adaptive codebook vector outputted from adaptive codebook  103  by the adaptive codebook gain outputted from gain codebook  105  and outputs the adaptive codebook vector after the multiplication to adder  108 . 
         [0013]    Multiplier  107  multiplies the fixed codebook vector outputted from fixed codebook  104  by the fixed codebook gain outputted from gain codebook  105  and outputs the fixed codebook vector after the multiplication to adder  108 . 
         [0014]    Adder  108  adds up the adaptive codebook vector outputted from multiplier  106  and the fixed codebook vector outputted from multiplier  107  and outputs the excitation vector after the addition to LPC synthesis filter  109  as an excitation. 
         [0015]    LPC synthesis filter  109  generates a synthesized signal using a filter function, that is, LPC synthesis filter using the quantized LPC parameter outputted from LPC quantization section  102  as a filter coefficient and the excitation vector generated in adaptive codebook  103  and fixed codebook  104  as an excitation. This synthesized signal is outputted to adder  110 . 
         [0016]    Adder  110  calculates an error signal by subtracting the synthesized signal generated in LPC synthesis filter  109  from the speech signal and outputs this error signal to perceptual weighting section  111 . This error signal corresponds to coding distortion. 
         [0017]    Perceptual weighting section  111  applies perceptual weighting to the coding distortion outputted from adder  110  using the LPC parameter inputted from LPC analyzing section  101  and outputs the weighted distortion to distortion minimizing section  112 . 
         [0018]    Distortion minimizing section  112  acquires each index (code) of adaptive codebook  103 , fixed codebook  104  and gain codebook  105  such that the coding distortion outputted from perceptual weighting section  111  becomes a minimum for each subframe and outputs these indices to the outside of CELP coding apparatus  100  as coded information. To be more specific, distortion minimizing section  112  generates a synthesized signal based on above-described adaptive codebook  103  and fixed codebook  104 , a series of processes of acquiring coding distortion of this signal constitutes closed-loop control (feedback control) and distortion minimizing section  112  searches each codebook by changing the index to be indicated to each codebook in various ways within one subframe and outputs the finally acquired index of each codebook that minimizes coding distortion. 
         [0019]    With an algebraic codebook used as a fixed codebook (also referred to as “stochastic codebook”), better coding performance can be obtained with a limited amount of calculation. The algebraic codebook is widely used in above-described ITU-T standard G.729, ITU-T standard G.722.2, ETSI standard AMR or ETSI standard AMR-WB or the like. 
         [0020]    Here, the principles of the basic algorithm of fixed codebook search will be described. 
         [0021]    First, a search for an excitation vector (also called “codebook vector” or “code vector”) and derivation of the code will be performed by searching an excitation vector that minimizes coding distortion of equation 1 below. 
         [0000]        E=|u −( pHa+qHs )| 2   (Equation 1)
 
         [0022]    where E is coding distortion, 
         [0023]    u is a coding target, 
         [0024]    p is a gain of the adaptive codebook vector, 
         [0025]    H is a perceptual weighting synthesis filter, 
         [0026]    a is an adaptive codebook vector, 
         [0027]    q is a gain of the fixed codebook vector, and 
         [0028]    s is a fixed codebook vector. 
         [0029]    Since the adaptive codebook vector and the fixed codebook vector are generally searched through sequential optimization (in separate loops), the code of fixed codebook  104  is derived by searching the fixed codebook vector that minimizes coding distortion in equation 2 below. 
         [0000]    
       
      
       v≦u−pHa  
      
     
         [0000]        E=|v−qHs|   2   (Equation 2)
 
         [0030]    where E is coding distortion, 
         [0031]    u is a coding target (perceptual weighted speech signal), 
         [0032]    p is an optimum gain of the adaptive codebook vector, 
         [0033]    H is a perceptual weighting synthesis filter, 
         [0034]    a is an adaptive codebook vector (also called “adaptive excitation”), 
         [0035]    q is a gain of the fixed codebook vector (also called “fixed excitation”), 
         [0036]    s is a fixed codebook vector, and 
         [0037]    v is a target vector of a fixed codebook search (also called “fixed excitation search”). 
         [0038]    Here, since gains p and q are determined after searching the code of the excitation, the search will be continued with ideal gains (also called “optimum gain”). The ideal gain means a gain that minimizes coding distortion. Therefore, equation 2 above may also be expressed as equation 3 below. 
         [0000]    
       
         
           
             
               
                 
                   ( 
                   
                     Equation 
                      
                     
                         
                     
                      
                     3 
                   
                   ) 
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     v 
                     = 
                     
                       u 
                       - 
                       
                         
                           u 
                           · 
                           Ha 
                         
                         
                           
                              
                             Ha 
                              
                           
                           2 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     E 
                     = 
                     
                       
                          
                         
                           v 
                           - 
                           
                             
                               
                                 v 
                                 · 
                                 Hs 
                               
                               
                                 
                                    
                                   Hs 
                                    
                                 
                                 2 
                               
                             
                              
                             Hs 
                           
                         
                          
                       
                       2 
                     
                   
                 
               
               
                 
                   [ 
                   3 
                   ] 
                 
               
             
           
         
       
     
         [0039]    Minimizing equation 3 indicating coding distortion is equal to maximizing cost function C of equation 4 below. 
         [0000]    
       
         
           
             
               
                 
                   ( 
                   
                     Equation 
                      
                     
                         
                     
                      
                     4 
                   
                   ) 
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   C 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             v 
                             t 
                           
                            
                           
                             H 
                             · 
                             s 
                           
                         
                         ) 
                       
                       2 
                     
                     
                       
                         s 
                         t 
                       
                        
                       
                         H 
                         t 
                       
                        
                       Hs 
                     
                   
                 
               
               
                 
                   [ 
                   4 
                   ] 
                 
               
             
           
         
       
     
         [0040]    Therefore, in the case of a search for fixed codebook vector s composed of a small number of pulses such as an algebraic codebook, if v t H and H t H are calculated beforehand, above-described cost function C can be calculated with a small amount of calculation. That is, coding of the algebraic codebook is performed using an algorithm of searching a position and polarity that maximize above-described cost function C through a multiplexed loop of the same number of channels (also called “tracks”) as that of pulses. 
         [0041]    Furthermore, in the case of the pulse excitation, by preliminarily selecting the polarity based on whether the value of v t H is positive or negative simultaneously with multiplying the value of v t H and the value of H t H by the polarity, a polarity search can be omitted when searching pulse positions. This preliminary selection of polarity allows the amount of calculation to be exponentially saved. 
         [0042]    In recent years, CODEC for encoding a wideband signal (16 kHz sampling) and an ultra-wideband signal (32 kHz sampling) is required in order to meet the need of higher quality, and the standardization is being carried forward in ITU-T, MPEG (Moving Picture Experts Group) or 3GPP or the like. As the bit rate for encoding wideband and ultra-wideband digital signals increases, the number of information bits of the fixed codebook for encoding an excitation also increases. The algebraic codebook allows high performance to be obtained through a search in simultaneous optimization (multiplexed loop), and therefore when the number of bits increases (the number of pulses increases), the amount of calculation increases exponentially. 
         [0043]    Thus, in high quality CODEC, a method is widely adopted whereby pulses (channels or tracks) to be searched are divided into several groups, a search within each group is performed through a simultaneous optimization search and a search between groups is performed through sequential optimization. For example, when there are 32 candidates for positions at which one pulse among four pulses rises, 1048576 (32 to the fourth power) matching operations need to be performed. However, if four pulses are divided into two groups of two pulses each to be searched, performing a calculation of 32 to the second power twice requires only 2048 matching operations. In this case, since this search is a sequential optimization search, performance drops to a certain extent compared to a full simultaneous optimization search, but since the group is closed, there is no significant deterioration. For this reason, searches are performed by this grouping in recent years. 
         [0044]    As an example of this pulse search, a case will be described using  FIG. 2  where a search is performed assuming that the group size is two pulses.  FIG. 2  is a conceptual diagram illustrating a flow of conventional fixed codebook search processing. The flow of search processing of a fixed codebook can be expressed as shown in  FIG. 2  in a simplified manner. As shown in  FIG. 2 , two-pulse searches are performed the required number of times until the required number of pulses are searched. 
         [0045]    The results (pulses) obtained through the respective two-pulse searches are organized into a pulse sequence (not shown). There are various methods for organizing the results of two-pulse searches. For example, ITU-T standard G.718 uses an algorithm of increasing the number of pulses while searching two pulses at a time in a four-track configuration (see NPL 1). Here, the description thereof will be omitted. 
         [0046]      FIG. 3  is a diagram schematically illustrating an algorithm of searching pulse positions by conventional grouping.  FIG. 3  corresponds to one of the two-pulse searches in  FIG. 2 . 
         [0047]    Before starting a search, parameters necessary for the search are determined using an inputted target or the like as preprocessing. Here, the target can be expressed by a vector and the target corresponds to target vector v of the aforementioned fixed codebook search. As parameters, target time inverse order synthetic vector (polarity preliminarily selected) v t H, correlation matrix between pulse synthetic vectors (polarity preliminarily selected) H t H, track number, and interval of pulse candidate positions of each track or the like are provided. 
         [0048]    A search loop of track 1 is executed in a search loop of track 0 using these parameters. That is, the search loop of track 0 and the search loop of track 1 constitute a multiplexed loop. By conducting a search using this multiplexed loop, it is possible to obtain the searched position of each track, a correlation value forming the base of a synthetic numerator term until this search and a synthetic denominator term until this search. 
         [0049]      FIG. 4  is a flowchart indicating an algorithm of searching pulse positions by conventional grouping.  FIG. 4  is a more specific illustration of  FIG. 3 . 
         [0050]    In  FIG. 4 , symbol “d[n]” is a target time inverse order synthetic vector (polarity preliminarily selected). Symbol “c[n][m]” denotes a correlation matrix (polarity preliminarily selected) between pulse synthetic vectors, where nim and values of n and m are doubled. Symbols “x” and “y” denote pulse candidate positions. Symbols “xx” and “yy” denote finally searched pulse positions. “Track 0” or “track 1” denotes a track number (one of 0, 1, 2 and 3 in  FIG. 2 ). Symbol “ps_t” denotes the base of the numerator term of cost function C until before performing a search. Symbol “alp_t” denotes a synthetic value of the denominator term of cost function C until before performing a search. Symbol “L” denotes a subframe length. Symbol “step” denotes an interval of pulse candidate positions of each track (“4” in  FIG. 4 ). 
         [0051]    In  FIG. 4 , the flow starts when the aforementioned necessary parameters are inputted first. Then, to search pulse candidate position x, numerator term sqk of cost function C is set to “−1.0” and denominator term alpk is set to “1.0” (step ST 11 ). 
         [0052]    Next, it is determined whether or not pulse candidate position x is smaller than subframe length L (step ST 12 ). 
         [0053]    When pulse candidate position x is smaller than subframe length L (step ST 12 : yes), calculations ps0=ps_t+d[x] and alp0=alp_t+c[x][x] are performed (step ST 13 ). 
         [0054]    Next, a search of pulse candidate position y is started (step ST 14 ), and it is determined whether or not pulse candidate position y is smaller than subframe length L (step ST 15 ). 
         [0055]    When pulse candidate position y is equal to or greater than subframe length L (step ST 15 : no), the next candidate position is selected (x=x+step) (step ST 16 ) and the process is returned to step ST 12 . 
         [0056]    On the other hand, when pulse candidate position y is smaller than subframe length L (step ST 15 : yes), calculations ps1=ps0+d[y], alp1=alp0+c[y][y]+c[x][y] and sq=ps1*ps1 are performed (step ST 17 ). 
         [0057]    Next, it is determined whether or not the value of (alpk*sq) is greater than the value of (sqk*alp1) (step ST 18 ). 
         [0058]    When the value of (alpk*sq) is equal to or smaller than the value of (sqk*alp1) (step ST 18 : no), the next candidate position is selected (y=y+step) (step ST 19 ), and the process is returned to step ST 15 . 
         [0059]    On the other hand, when the value of (alpk*sq) is greater than the value of (sqk*alp1) (step ST 18 : yes), the denominator term and the numerator term of cost function C are fixed, finally searched pulse positions xx and yy are fixed (step ST 20 ), and the process is returned to step ST 19 . 
         [0060]    Furthermore, in step ST 12 , when pulse candidate position x is equal to or greater than subframe length L (step ST 12 : no), ps_t=ps_t+d[xx]+d[yy] is calculated, and the denominator term of cost function C before conducting a search is determined to be the final denominator term of cost function C (step ST 21 ). 
         [0061]    Next, final pulse positions xx and yy, and synthetic value alp_t of the denominator term of cost function C and the value of numerator term ps_t of cost function C in that case are outputted (step ST 22 ). 
         [0062]    In  FIG. 4 , the numerator term of cost function C in equation 4 is sq and the denominator term is alp1. Cost function C is obtained by dividing the numerator term by the denominator term, but since the division involves a large amount of calculation, cross-multiplication is adopted when determining the magnitude of cost function C. 
         [0063]    However, even when the above-described grouping is used, if the number of bits further increases, the amount of calculation becomes enormous. 
         [0000]    Thus, ITU-T standard G.718 adopts a preliminary selection of pulse positions when searching pulses (see NPL 1). The preliminary selection of pulse positions means that positions where pulses are likely to rise or assumed to rise are selected beforehand from among pulse candidate positions to thereby reduce the number of pulse candidate positions that are included in the next loop. 
         [0064]    An overview of a flow of search processing of the fixed codebook using a preliminary selection of pulse positions adopted in G.718 will be described using  FIG. 5 .  FIG. 5  is a conceptual diagram illustrating a flow of conventional fixed codebook search processing. As described above, there are various methods of organizing the two-pulse search results, and G.718 uses an algorithm of increasing the number of pulses while searching two pulses at a time in a four-track configuration. Here, the description thereof will be omitted. 
         [0065]    As shown in  FIG. 5  as in the case of  FIG. 2 , this search processing of the fixed codebook performs two-pulse searches the required number of times, but performs a preliminary selection in the respective two-pulse searches. At this time, a relationship in ascending order of magnitude is set in the preliminary selection number of the respective two-pulse searches. 
         [0066]      FIG. 6  is a diagram schematically illustrating an algorithm of searching pulse positions when performing a preliminary selection of pulse positions adopted in G.718.  FIG. 6  corresponds to one of the two-pulse searches shown in  FIG. 5 . 
         [0067]    As in the case of  FIG. 3 , before starting a search, parameters necessary for the search are acquired using an inputted target or the like as preprocessing. Here, the target can be expressed by a vector and corresponds to target vector v of the aforementioned fixed codebook search. As parameters, target time inverse order synthetic vector (polarity preliminarily selected) v t H, correlation matrix between pulse synthetic vectors (polarity preliminarily selected) H t H, track number, and interval of pulse candidate positions of each track or the like are provided. 
         [0068]    By performing a preliminary selection of track 0 in the search loop of track 0 using these parameters, the number of times of entering the search loop of track 1 in the search loop of track 0 is limited. In the case of  FIG. 6  as in the case of  FIG. 3 , the search loop of track 0 and the search loop of track 1 also constitute a multiplexed loop. By conducting a search using this multiplexed loop, the searched position of each track, correlation value forming the base of the synthetic numerator term until this search and the synthetic denominator term until this search are obtained. 
         [0069]      FIG. 7  is a flowchart illustrating an algorithm of searching pulse positions when performing a preliminary selection of pulse positions adopted in G.718.  FIG. 7  is a more specific illustration of  FIG. 6 . In  FIG. 7 , parts having the same processing as that in  FIG. 4  are assigned the same reference numerals and descriptions thereof will be omitted. 
         [0070]    In  FIG. 7 , symbol “pick[n]” denotes a sequence in which the order of adopting each pulse position is described in the pulse position. Symbol “thres” denotes a value acquired from the number of candidates of specified candidate position x. 
         [0071]    Furthermore, the specified number of candidates are searched through a search only when pick[n] is a value smaller than the value of thres. Meanings of the other symbols are the same as those in  FIG. 4 , and so descriptions thereof will be omitted. 
         [0072]    In  FIG. 7 , when pulse candidate position x is smaller than subframe length L (step ST 12 : yes), it is determined whether or not pick[x] is smaller than the value of thres (step ST 50 ). 
         [0073]    When pick[x] is smaller than the value of thres (step ST 50 : yes), calculations ps0=ps_t+d[x] and alp0=alp_t+c[x][x] are performed (step ST 13 ). 
         [0074]    On the other hand, when pick[x] is equal to or greater than the value of thres (step ST 50 : no), the next candidate position is selected (step ST 16 ), and the process is returned to step ST 12 . 
         [0075]      FIG. 8  is a block diagram illustrating a configuration of fixed codebook searching apparatus  300  that can conduct a pulse search of the fixed codebook using the above-described conventional pulse searching method. 
         [0076]    Preprocessing section  301  receives a target signal as input and acquires parameters necessary for a pulse search. Examples of parameters generated by calculation include “target time inverse order synthetic vector” (corresponding to v t H in equation 4) for which a polarity preliminary selection of each pulse position is performed and the result thereof is reflected, and “correlation matrix between pulse synthetic vectors” (corresponding to H t H in equation 4) for which the result of the polarity preliminary selection is reflected and values other than the diagonal term are doubled. Furthermore, examples of the parameters to be set include a track number to be searched, interval of pulse position candidates of the track with the number, subframe length and preliminary selection number. Preprocessing section  301  sends these parameters to control section  302 . 
         [0077]    Control section  302  receives the total number of bits as input, sends parameters necessary for a pulse search to multiplexed loop searching section  303  according to a timing signal from pulse sequence coding section  304 , which will be described later, and controls multiplexed loop searching section  303  so as to conduct a pulse search. Examples of the parameters to be sent to multiplexed loop searching section  303  include, in addition to parameters sent from preprocessing section  301 , a sequence in which the order of adopting each pulse position is described in the pulse position, a synthetic value of the numerator term and a synthetic value of the denominator term until before conducting a search. Control section  302  initializes the synthetic value of the numerator term and the synthetic value of the denominator term until before conducting a search when first driving multiplexed loop searching section  303  and sends the synthetic values sent from pulse sequence coding section  304  to multiplexed loop searching section  303  when conducting two-pulse searches in subsequent stages. 
         [0078]    Multiplexed loop searching section  303  searches pulse positions using the multiplexed loop. In this case, multiplexed loop searching section  303  performs a preliminary selection in the outermost loop using the preliminary selection number and the sequence in which the order of adopting each pulse position is described in the pulse position, and outputs the searched pulse position, and the synthetic value of the numerator term and the synthetic value of the denominator term calculated in the pulse positions, to pulse sequence coding section  304 . 
         [0079]    Pulse sequence coding section  304  performs pulse coding using the pulse position searched by multiplexed loop searching section  303 , the synthetic value of the numerator term and the synthetic value of the denominator term. Pulse coding as this fixed codebook is performed using the result of multiplexed loop searching section  303  operating a plurality of times. Pulse sequence coding section  304  sends the synthetic value of the numerator term and the synthetic value of the denominator term to control section  302  and sends a timing signal for urging multiplexed loop searching section  303  to perform the next operation to control section  302 . Pulse sequence coding section  304  then finally outputs the code as the fixed codebook. 
         [0080]    Here, when using the search processing in  FIG. 2  as the pulse searching method, multiplexed loop searching section  303  does not include any configuration to perform a preliminary selection. As the pulse searching method, when the search processing in  FIG. 5  is used, multiplexed loop searching section  303  is configured to perform a preliminary selection. 
         [0081]    Thus, in order to adapt to a high bit rate fixed codebook search, methods have been conventionally invented such as a method of grouping channels (tracks) in an algebraic codebook to conduct a search in units of a small number of pulses and conduct individual searches for a small number of pulses in a closed loop, and further a method of performing a preliminary selection of positions in an outside loop then to further reduce the amount of calculation, so that high quality speech or music can be encoded while suppressing the amount of calculation. 
       CITATION LIST 
     Non-Patent Literature 
       [0000]    
       
         NPL 1 
         ITU-T standard G.718 specifications, June 2008 
       
     
       SUMMARY OF INVENTION 
     Technical Problem 
       [0084]    However, since a multiplexed loop is adopted in a conventional apparatus, there is a problem that it is difficult to further reduce the amount of calculation involved in a pulse position search. For this reason, when the number of pulses searched in the fixed codebook increases, there is a problem that it is difficult to reduce the amount of calculation involved in a pulse position search without deterioration of the coding performance. 
         [0085]    It is an object of the claimed invention to provide a pulse position searching apparatus and a method thereof capable of reducing the amount of calculation involved in a pulse position search. Furthermore, as for a codebook, it is an object of the claimed invention to provide a codebook searching apparatus and a method thereof capable of, even when the number of pulses to be acquired by a search increases, reducing the amount of calculation involved in a pulse position search without deterioration of the coding performance. 
       Solution to Problem 
       [0086]    A pulse position searching apparatus according to the claimed invention is a pulse position searching apparatus that obtains, as input, parameters obtained by performing predetermined processing on a target signal, and searches a plurality of pulse positions, and adopts a configuration including: a first searching section that performs a first preliminary selection using the parameters on a first candidate group of positions where a first pulse is placed, and performs a first search on the result of the first preliminary selection to obtain a first position where the first pulse is placed; a second searching section that performs a second search using the first position on all position candidates of a second candidate group of positions where a second pulse is placed, to thereby obtain a second position where the second pulse is placed; and a third searching section that performs a second preliminary selection using the second position on the first candidate group, performs a third search on the result of the second preliminary selection to thereby obtain a third position where the first pulse is placed, and outputs the second position and the third position as a search result. 
         [0087]    A pulse position searching method according to the claimed invention is a pulse position searching method that obtains, as input, parameters obtained by performing predetermined processing on a target signal, and searches a plurality of pulse positions, the method including: a first searching step of performing a first preliminary selection using the parameters on a first candidate group of positions where a first pulse is placed, and performing a first search on the result of the first preliminary selection to obtain a first position where the first pulse is placed; a second searching step of performing a second search using the first position on all position candidates of a second candidate group of positions where a second pulse is placed, to thereby obtain a second position where the second pulse is placed; and a third searching step of performing a second preliminary selection using the second position on the first candidate group, performing a third search on the result of the second preliminary selection to thereby obtain a third position where the first pulse is placed, and outputting the second position and the third position as a search result. 
       Advantageous Effects of Invention 
       [0088]    The pulse position searching apparatus and the method thereof according to the claimed invention can further reduce the amount of calculation involved in a pulse position search compared to related art. Furthermore, applying this pulse position searching apparatus and the method thereof to a codebook searching apparatus and the method thereof makes it possible to reduce the amount of calculation involved in a pulse position search without deterioration of the coding performance even when the number of pulses to be obtained by a search increases. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0089]      FIG. 1  is a block diagram illustrating a configuration of a CELP coding apparatus; 
           [0090]      FIG. 2  is a conceptual diagram illustrating a flow of conventional fixed codebook search processing; 
           [0091]      FIG. 3  is a diagram schematically illustrating an algorithm of searching pulse positions by conventional grouping; 
           [0092]      FIG. 4  is a flowchart illustrating an algorithm of searching pulse positions by conventional grouping; 
           [0093]      FIG. 5  is a conceptual diagram illustrating a flow of conventional fixed codebook search processing; 
           [0094]      FIG. 6  is a diagram schematically illustrating an algorithm of searching pulse positions when performing a conventional preliminary selection of pulse positions; 
           [0095]      FIG. 7  is a flowchart illustrating an algorithm of searching pulse positions when performing a conventional preliminary selection of pulse positions; 
           [0096]      FIG. 8  is a block diagram illustrating a configuration of a conventional fixed codebook searching apparatus; 
           [0097]      FIG. 9  is a conceptual diagram illustrating a flow of fixed codebook search processing according to an embodiment of the claimed invention; 
           [0098]      FIG. 10  is a diagram schematically illustrating an algorithm of searching pulse positions according to the embodiment of the claimed invention; 
           [0099]      FIG. 11  is a block diagram illustrating a configuration of a pulse position searching apparatus according to the embodiment of the claimed invention; 
           [0100]      FIG. 12  is a flowchart illustrating a method of searching pulse positions according to the embodiment of the claimed invention; and 
           [0101]      FIG. 13  is a block diagram illustrating a configuration of the fixed codebook searching apparatus according to the embodiment of the claimed invention. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0102]    The claimed invention relates to quantization that performs coding by combining a plurality of searches for a small number of pulses to search many pulses. There are two types of searches for a small number of pulses: one using a loop of a channel (called “track” or “pulse”) for performing a preliminary selection (that is, limits a search target first) and the other using a loop of a channel for not performing any preliminary selection (that is, all candidates are considered to be search targets). The claimed invention has a feature of performing a sequential optimization search whereby the respective loops are sequentially performed without multiplexing the loops. The loop for which a preliminary selection is performed is preferably used a plurality of times for a sequential optimization search used to search for a small number of pulses. Particularly, the loop for which a preliminary selection is performed is more preferably used as at least the first loop and the last loop in the order in which loops are executed. The claimed invention relates to a pulse position searching apparatus that searches a small number of pulses using such a pulse position searching method. 
         [0103]    If a sequential optimization search for the above-described pulse position searching apparatus is used in a case where the preliminary selection number is sufficiently small, its performance does not significantly deteriorate from the performance of conventional simultaneous optimization search with a preliminary selection. Moreover, since the loop in question is not a multiplexed loop, the amount of calculation can be significantly reduced. 
         [0104]    Therefore, by using a pulse sequential optimization search using the pulse position searching apparatus according to the claimed invention for a coding apparatus in a case where the preliminary selection number is sufficiently small, it is possible to further reduce the amount of calculation without deterioration of the coding performance. 
         [0105]    The present embodiment will describe a case where the claimed invention is applied to quantization of a fixed codebook in CELP, which is a speech coding technology. Since CELP has been described above, the description thereof will be omitted. 
         [0106]    As described in the Background Art, G.718 uses two-pulse searches using a closed multiplexed loop a plurality of times, and thereby searches many pulses while suppressing the amount of calculation. In the searches, a preliminary selection in the outer loop of track 0 limits the number of times of entering the inner loop to thereby achieve an additional reduction in the amount of calculation. Furthermore, by significantly narrowing down a search range in the beginning and then gradually increasing the number of candidates, the performance is prevented from deteriorating significantly. This takes advantage of a tendency for accurate searching of the last half part to prevent the performance from deteriorating significantly even when the first half part is searched by significantly narrowing down the search candidates by a preliminary selection. 
         [0107]    Thus, the inventor of the claimed invention conceived of an idea that when the preliminary selection number was sufficiently small, a sequential optimization search using a loop for which a preliminary selection was performed was used a plurality of times to enable performance similar to that when using a simultaneous optimization search and to enable a significant reduction in the amount of calculation. 
         [0108]    Furthermore, in the sequential optimization search, there are cases where pulse positions different from search results in the simultaneous optimization search may be searched (referred to as “position errors”). This may directly lead to deterioration in performance. For this reason, the present embodiment first performs a search using a loop for which a preliminary selection is performed to thereby stochastically reduce a probability of location error in the first loop, search another track, and then conduct a search using the loop for which a preliminary selection is performed over again. Thus, even when the search result using the first loop is not necessarily optimum, this improves the probability that a correct position may be eventually searched. 
         [0109]    Furthermore, in the first loop, it is necessary to add two values; power (the same value as the “correlation value between the same pulse positions”) of a synthetic vector of newly added pulses as the denominator term of the aforementioned cost function and a correlation value between synthetic vectors of pulses searched until then, to the synthetic value of the denominator term until before conducting the search. However, the calculation of this correlation value is omitted to calculate only power, and the amount of calculation necessary for preprocessing is thereby omitted. 
         [0110]    Hereinafter, an embodiment of the claimed invention will be described in detail with reference to the accompanying drawings. Here, as an example, a pulse position searching apparatus will be described which searches pulse positions in a fixed codebook made up of an algebraic codebook in a CELP coding apparatus by diving pulses into groups of two pulses each. This pulse position searching apparatus is applied to a fixed codebook searching apparatus included in the CELP coding apparatus, and pulses searched by this pulse position searching apparatus are organized into a pulse sequence and coded in the fixed codebook searching apparatus. The CELP coding apparatus targets at, for example, speech, music or a signal which is a mixture of speech and music or the like. Furthermore, the pulse position searching apparatus is not limited to the CELP coding apparatus, but can also be used for a coding apparatus required to conduct a pulse position search. 
       Embodiment 
       [0111]    A flow of search processing of a fixed codebook of the present embodiment will be described using  FIG. 9 .  FIG. 9  is a conceptual diagram illustrating a flow of fixed codebook search processing according to the embodiment of the claimed invention. 
         [0112]    As shown in  FIG. 9 , in search processing of the fixed codebook of the present embodiment, searches are gradually conducted by two pulses at a time from a pulse search with a small preliminary selection number to a pulse search with a large preliminary selection number, and searches are performed a necessary number of times until the required number of pulses are searched (the preliminary selection number may be the same). The results (pulses) obtained in the searches in the respective stages are organized into a pulse sequence (not shown). The description of the method for organizing the searched pulses into a pulse sequence is omitted. Furthermore, the present embodiment assumes that pulse searches are conducted in track 0 and track 1 of an algebraic codebook in the respective stages. 
         [0113]    The search processing in  FIG. 5  and the search processing in  FIG. 9  are similar in that a two-pulse search is performed in the initial stage, but are different in that a sequential optimization search using the pulse position searching method according to the claimed invention is performed in the subsequent stages. Here, the “two-pulse search” refers to the simultaneous optimization search (closed-loop search) that performs a preliminary selection in  FIG. 7  described in the Background Art. Furthermore, it is assumed in this example that the two-pulse search is performed again in the final stage. 
         [0114]    In the present embodiment, the two-pulse search (closed-loop search) is adopted in the stage of the first search having smallest preliminary selection number NO. This is because in a real situation, if NO is too small, the amount of calculation in this stage may be smaller in a closed-loop search than a sequential optimization search of the claimed invention. Furthermore, the two-pulse search is also adopted in the stage of the final search having largest preliminary selection number Nm. This is because the performance of the claimed invention is fully displayed when the preliminary selection number is sufficiently small as described above, and so the possibility is taken into consideration that the performance of the claimed invention may deteriorate in the final stage having the largest preliminary selection number. The present embodiment uses two-pulse searches in the initial and final stages, but this configuration may not necessarily be adopted. 
         [0115]    In the example of  FIG. 9 , a sequential optimization search using the pulse position searching method according to the claimed invention is performed for the pulse search of the second stage or the like. That is, assuming that the preliminary selection number is sufficiently small in this stage, a search is conducted first for track 0 for which a preliminary selection is performed, the pulse position searched in track 0 is fixed next, a search is then conducted for track 1 without any preliminary selection, the position searched in track 1 is finally fixed, and a search is conducted again for track 0 for which a preliminary selection is performed. 
         [0116]      FIG. 10  is a diagram schematically illustrating an algorithm of searching pulse positions in the present embodiment.  FIG. 10  corresponds to the pulse search in the second stage or the like shown in  FIG. 9 . 
         [0117]    As in the cases of  FIG. 3  and  FIG. 6 , before starting a search, parameters necessary for a search are obtained using an inputted target or the like as preprocessing. Here, the target can be expressed by a vector and the target corresponds to target vector v of the aforementioned fixed codebook search. As parameters, target time inverse order synthetic vector (polarity preliminarily selected) v t H, correlation matrix between pulse synthetic vectors (polarity preliminarily selected) H t H, track number, and interval of pulse candidate positions in each track or the like are provided. 
         [0118]    Using these parameters, search loop R 1  is executed first for track 0 for which a preliminary selection is performed, the pulse position searched in track 0 is then fixed, search loop R 2  is executed for track 1 without performing any preliminary selection, and the position searched in track 1 is finally fixed to execute search loop R 3  again for track 0 for which a preliminary selection is performed. Through this processing, the searched position of each track, the correlation value which forms the base of the synthetic numerator term until this search, and the synthetic denominator term until this search are obtained. 
         [0119]    That is, as shown in  FIG. 10 , the present embodiment does not adopt the multiplexed loop unlike the conventional algorithm shown in  FIG. 3  and  FIG. 6  and uses an algorithm of performing a search loop of track 0 and a search loop of track 1 in the above-described order, and can thereby reduce the amount of calculation involved in the pulse position search. 
         [0120]      FIG. 11  is a block diagram illustrating a configuration of pulse position searching apparatus  400  according to the embodiment of the claimed invention.  FIG. 11  corresponds to the sequential optimization search shown in  FIG. 10 . 
         [0121]    Pulse position searching apparatus  400  includes first searching section  401  that executes search loop R 1  of track 0 for which a preliminary selection is performed, second searching section  402  that executes search loop R 2  of track 1 without any preliminary selection and third searching section  403  that executes search loop R 3  of track 0 for which a preliminary selection is performed. The number of pulses to be obtained by the search is two. 
         [0122]    First searching section  401  receives, as an input signal, parameters such as a target time inverse order synthetic vector with a preliminarily selected polarity, correlation matrix between pulse synthetic vectors, track number, and interval of pulse position candidates of each track, and searches the position of one pulse while performing a preliminary selection of pulse positions using these parameters. First searching section  401  outputs the search result to second searching section  402 . 
         [0123]    Second searching section  402  fixes the pulse position inputted from first searching section  401  as the search result and searches a pulse position in next track 1 without any preliminary selection of the pulse position. Second searching section  402  outputs the search result to third searching section  403 . 
         [0124]    Third searching section  403  fixes the pulse position inputted from second searching section  402  as the search result and searches a pulse again for the pulse position in track 0 while performing a preliminary selection of the pulse position. Third searching section  403  outputs the searched position of each track obtained by the search over again, a correlation value which forms the base of the synthetic numerator term of cost function C until this search and the synthetic denominator term of cost function C until this search as an output signal. 
         [0125]      FIG. 12  is a flowchart illustrating a method of searching pulse positions of the present embodiment.  FIG. 12  specifically illustrates operation of pulse position searching apparatus  400  in  FIG. 11 . 
         [0126]    In  FIG. 12 , symbol “d[n]” is a target time inverse order synthetic vector (polarity preliminarily selected). Symbol “c[n][m]” denotes a correlation matrix between pulse synthetic vectors (polarity preliminarily selected), where n≠m and the values of n and m are doubled. Symbols “x” and “y” denote pulse candidate positions. Symbols “xx” and “yy” denote finally searched positions. “Track 0” or “track 1” denotes a track number (one of 0, 1, 2 and 3 in the present embodiment). Symbol “p_t” denotes the base of the numerator term of cost function C until before conducting a search. Symbol “alp_t” denotes a synthetic value of the denominator term of cost function C until before conducting a search. Symbol “L” denotes a subframe length. Symbol “step” denotes an interval (“4” in the present embodiment) of the pulse candidate position of each track. Symbol “pick[n]” denotes a sequence in which the order of adopting each pulse position is described in the pulse candidate position. Symbol “thres” denotes a value obtained from the specified number of candidates of candidate position x. Furthermore, the specified number of candidates are searched through a search only when pick[n] is a value smaller than the value of thres. 
         [0127]    From  FIG. 12 , in order to search pulse candidate position x, first searching section  401  sets numerator term sqk to “−1.0” and sets denominator term alpk to “1.0” of cost function C (step ST 201 ). 
         [0128]    Next, first searching section  401  determines whether or not pulse candidate position x is smaller than subframe length L (step ST 202 ). 
         [0129]    When pulse candidate position x is smaller than subframe length L (step ST 202 : yes), first searching section  401  determines whether or not pick[x] is smaller than the value of thres (step ST 203 ). 
         [0130]    When pick[x] is equal to or greater than the value of thres (step ST 203 : no), first searching section  401  shifts to a search of next candidate position x (x=x+step) (step ST 204 ), and returns the process to step ST 202 . 
         [0131]    On the other hand, when pick[x] is smaller than the value of thres (step ST 203 : yes), first searching section  401  performs calculations ps0=ps_t+d[x], alp0=alp_t+c[x][x] and sq=ps0*ps0 (step ST 205 ). Here, as the denominator term of cost function C, power c[x][x] (the same value as a correlation value between the same pulse positions) of newly added pulse synthetic vector and correlation value c[x][*] between pulse synthetic vectors searched so far need to be added to a synthetic value of the denominator term of cost function C until before conducting a search. However, the calculation of this correlation value c[x][*] is omitted to calculate only power c[x][x], and the amount of calculation necessary for preprocessing is thereby omitted. 
         [0132]    Furthermore, first searching section  401  determines whether or not the value of (alpk*sq) is greater than the value of (sqk*alp0) (step ST 206 ). 
         [0133]    When the value of (alpk*sq) is equal to or smaller than the value of (sqk*alp0) (step ST 206 : no), first searching section  401  shifts to a search of next candidate position x (x=x+step) (step ST 204 ) and returns the process to step ST 202 . 
         [0134]    On the other hand, when the value of (alpk*sq) is greater than the value of (sqk*alp0) (step ST 206 : yes), first searching section  401  fixes the denominator term and the numerator term of cost function C and fixes final pulse position xx (step ST 207 ). 
         [0135]    Furthermore, in step ST 202 , when pulse candidate position x is equal to or greater than subframe length L (step ST 202 : no), second searching section  402  sets numerator term sqk of cost function C to “−1.0”, sets denominator term alpk to “1.0”, and performs calculations ps0=ps_t+d[xx] and alp0=alp_t+c[xx][xx] (step ST 208 ). 
         [0136]    Next, second searching section  402  determines whether or not pulse candidate position y is smaller than subframe length L (step ST 209 ). 
         [0137]    When pulse candidate position y is smaller than subframe length L (step ST 209 : yes), second searching section  402  performs calculations ps1=ps0+d[y], alp1=alp0+c[y][y]+c[xx][y] and sq=ps1*ps1 (step ST 210 ). 
         [0138]    Next, second searching section  402  determines whether or not the value of (alpk*sq) is greater than the value of (sqk*alp1) (step ST 211 ). 
         [0139]    When the value of (alpk*sq) is equal to or smaller than the value of (sqk*alp1) (step ST 211 : no), second searching section  402  shifts to a search of next candidate position y (y=y+step) (step ST 212 ) and returns the process to step ST 209 . 
         [0140]    On the other hand, when the value of (alpk*sq) is greater than the value of (sqk*alp1) (step ST 211 : yes), second searching section  402  fixes the denominator term and numerator term of cost function C and fixes final pulse position yy (step ST 213 ). 
         [0141]    In step ST 209 , when pulse candidate position y is equal to or greater than subframe length L (step ST 209 : no), third searching section  403  performs calculations ps1=ps_t+d[yy] and alp1=alp_t+c[yy][yy] (step ST 214 ). 
         [0142]    Next, third searching section  403  determines whether or not pulse candidate position x is smaller than subframe length L (step ST 215 ). 
         [0143]    When pulse candidate position x is smaller than subframe length L (step ST 215 : yes), third searching section  403  determines whether or not pick[x] is smaller than the value of thres (step ST 216 ). 
         [0144]    When pick[x] is equal to or greater than the value of thres (step ST 216 : no), third searching section  403  shifts to a search of next candidate position x (x=x+step) (step ST 217 ) and returns the process to step ST 215 . 
         [0145]    On the other hand, when pick[x] is smaller than the value of thres (step ST 216 : yes), third searching section  403  performs calculations ps0=ps1+d[x], alp0=alp1+c[x][x]+c[x][yy] and sq=ps0*ps0 (step ST 218 ). 
         [0146]    Next, third searching section  403  determines whether or not the value of (alpk*sq) is greater than the value of (sqk*alp0) (step ST 219 ). 
         [0147]    When the value of (alpk*sq) is equal to or smaller than the value of (sqk*alp0) (step ST 219 : no), third searching section  403  shifts to a search of next candidate position x (x=x+step) (step ST 217 ), and returns the process to step ST 215 . 
         [0148]    On the other hand, when the value of (alpk*sq) is greater than the value of (sqk*alp0) (step ST 219 : yes), third searching section  403  fixes the denominator term and the numerator term of cost function C and fixes final pulse position xx (step ST 220 ). 
         [0149]    Furthermore, in step ST 215 , when pulse candidate position x is equal to or greater than subframe length L (step ST 215 : no), third searching section  403  performs calculations ps_t=ps_t+d[xx]+d[yy] and alp_t=alpk (step ST 221 ). 
         [0150]    Next, third searching section  403  outputs final pulse positions xx and yy, and the values of synthetic value alp_t of the denominator term and of numerator term ps_t of cost function C at this time (step ST 222 ). 
         [0151]    In  FIG. 10 , search loop R 1  of track 0 corresponds to the processing in step ST 201  to step ST 208  in  FIG. 12 , search loop R 2  of track 1 corresponds to step ST 208  to step ST 214  in  FIG. 12 , and search loop R 3  of track 0 corresponds to step ST 214  to step ST 221  in  FIG. 12 . 
         [0152]      FIG. 13  is a block diagram illustrating a configuration of fixed codebook searching apparatus  500  capable of conducting a pulse search of a fixed codebook using the pulse searching method of the present embodiment. 
         [0153]    Preprocessing section  501  receives a target signal as input and obtains parameters necessary for a pulse search. Examples of parameters generated by calculation include a “target time inverse order synthetic vector” which reflects the result of a polarity preliminary selection of each pulse position (corresponding to v t H of equation 4) and “correlation matrix between pulse synthetic vectors” (corresponding to H t H of equation 4) which reflects the result of the polarity preliminary selection and doubles the value other than the diagonal term. Furthermore, examples of parameters to be set include a track number to be searched, interval of pulse position candidates in the track with the above-described number, subframe length, and preliminary selection number. Preprocessing section  501  sends these parameters to control section  502 . 
         [0154]    Control section  502  receives the total number of bits as input, sends parameters necessary for a pulse search to multiplexed loop searching section  503  or pulse position searching apparatus  600  according to a timing signal from pulse sequence coding section  504 , which will be described later, and performs control so that multiplexed loop searching section  503  or pulse position searching apparatus  600  conducts a pulse search. In the present embodiment, control section  502  performs control so as to drive multiplexed loop searching section  503  in the first and final stages and drive pulse position searching apparatus  600  in other stages. 
         [0155]    Examples of parameters to be sent to multiplexed loop searching section  503  or pulse position searching apparatus  600  include, in addition to the parameters sent from preprocessing section  501 , a sequence in which the order of adopting each pulse position is described in the pulse position, synthetic value of the numerator term until before conducting a search and synthetic value of the denominator term. Control section  502  initializes the synthetic value of the numerator term and the synthetic value of the denominator term until before conducting a search when first driving multiplexed loop searching section  503  in the first stage and sends the values sent from pulse sequence coding section  504  to multiplexed loop searching section  503  when conducting a two-pulse search (closed-loop search) in the subsequent stages (final stage in the example in  FIG. 9 ). 
         [0156]    Multiplexed loop searching section  503  searches pulse positions using a two-pulse search, that is, a closed-loop search using a multiplexed loop. In this case, multiplexed loop searching section  503  performs a preliminary selection in the outermost loop using the preliminary selection number and the sequence in which the order of adopting each pulse position is described in the pulse position, and outputs the searched pulse position, and the synthetic value of the numerator term and the synthetic value of the denominator term calculated in the pulse position to pulse sequence coding section  504 . 
         [0157]    Pulse position searching apparatus  600  corresponds to pulse position searching apparatus  400  shown in  FIG. 11 . Therefore, first searching section  401 , second searching section  402  and third searching section  403  correspond to first searching section  601 , second searching section  602  and third searching section  603  respectively, and have the same configuration. For this reason, detailed description of pulse position searching apparatus  600  will be omitted. 
         [0158]    Pulse sequence coding section  504  performs pulse coding using pulse positions searched in multiplexed loop searching section  503  or pulse position searching apparatus  600 , synthetic value of the numerator term and synthetic value of the denominator term. This pulse coding as a fixed codebook is performed using the result of multiplexed loop searching section  503  and the result of pulse position searching apparatus  600 . Pulse sequence coding section  504  sends the synthetic value of the numerator term and the synthetic value of the denominator term to control section  502 , and sends a timing signal to control section  502  to prompt the next operation of pulse position searching apparatus  600  or operation of multiplexed loop searching section  503 . Pulse sequence coding section  504  then finally outputs the code as the fixed codebook. 
         [0159]    Thus, in a search for a small number of pulses, the pulse position searching apparatus of the present embodiment conducts a sequential optimization search by sequentially executing loops in order of a search loop of track 0 in which a preliminary selection is performed without adopting a multiplexed loop, a search loop of track 1 in which no preliminary selection is performed, and a search loop of track 0 in which a preliminary selection is performed, and can thereby reduce the amount of calculation involved in the pulse position search compared to related art. Furthermore, when this pulse position searching apparatus is applied to a fixed codebook searching apparatus, even when the number of pulses to be searched in the fixed codebook increases, it is possible to reduce the amount of calculation involved in a pulse position search without deteriorating coding performance. By applying such a fixed codebook searching apparatus to a coding apparatus, it is possible to generate a high quality decoded signal when decoding a code in the decoding apparatus. 
         [0160]    Furthermore, according to the present embodiment, the pulse position searching apparatus first searches track 0 with a preliminary selection for pulse positions, and can thereby reduce the possibility of obtaining a result different from a result of a search conducted in a conventional multiplexed loop. 
         [0161]    According to the present embodiment, the pulse position searching apparatus searches track 0 with a preliminary selection for pulse positions again after searching track 1, and can thereby reduce the possibility of obtaining a result different from a result of a search conducted in a conventional multiplexed loop. 
         [0162]    According to the present embodiment, the pulse position searching apparatus calculates the denominator term of a cost function used to search track 0 with a preliminary selection for pulse positions to be used first by adding only power of a pulse synthetic vector to the synthetic value of the denominator term, and can thereby save the amount of calculation necessary to calculate a correlation value, and further reduce the amount of calculation. 
         [0163]    The present embodiment conducts a search for every two pulses, but this is for a comparison with G.718 which is a conventional example, and can conduct a search for every arbitrary number of pulses such as three pulses or four pulses. 
         [0164]    The fixed codebook searching apparatus of the present embodiment uses a conventional simultaneous optimization search (closed-loop search) in the first and final stages, but this configuration need not always be adopted. 
         [0165]    In the fixed codebook searching apparatus of the present embodiment, the control section may determine to conduct a pulse position search in the pulse group search in the final stage using a simultaneous optimization search (closed-loop search) no matter what the total number of bits is. 
         [0166]    Although the present embodiment adopts a three-loop configuration for a sequential optimization search of the claimed invention: search of track 0 (with preliminary selection), search of track 1 (no preliminary selection) and search of track 0 (with a preliminary selection), the claimed invention is not limited to this, but the amount of calculation can be significantly reduced, and the number of loops may, therefore, be further increased. 
         [0167]    Although the present embodiment uses an algebraic codebook as the fixed codebook, the claimed invention is not limited to this, but any codebook other than the algebraic codebook may also be used. 
         [0168]    Although the present embodiment conducts a search using a preliminary selection by taking G.718 as an example, the claimed invention is not limited to this, but may also be used for arbitrary coding using a plurality of searches for a small number of pulses. This is because the claimed invention is an invention related to a pulse position search and is independent of other configurations of the G.718 standard. 
         [0169]    Although the present embodiment adopts CELP as a coding scheme, the claimed invention is not limited to this, but since the claimed invention can also be used for vector quantization, the claimed invention is applicable to any coding scheme other than CELP. For example, the claimed invention is also applicable to spectral quantization using MDCT (Modified Discrete Cosine Transform) or QMF (Quadrature Mirror Filter) and is also applicable to an algorithm of searching a similar spectral shape from among spectra in a low frequency domain of a band extension technology. 
         [0170]    Although the present embodiment has shown a case where the pulse position searching apparatus is applied to a coding apparatus targeting at speech, music or a signal which is a mixture of speech and music, the claimed invention is not limited to this, but the claimed invention is also applicable to quantization used for speech recognition, image recognition or image coding or the like. This is because the claimed invention is an invention related to a pulse position search and is independent of the object of the entire algorithm. 
         [0171]    In the foregoing embodiment, the claimed invention is configured with hardware by way of example, but the invention may also be implemented by software in cooperation with hardware. 
         [0172]    Furthermore, each function block employed in the explanation of the aforementioned embodiment may typically be implemented as an LSI constituted by an integrated circuit. These may be individual chips or partially or totally contained on a single chip. “LSI” is adopted here but this may also be referred to as “IC,” “system LSI,” “super LSI,” or “ultra LSI” depending on differing extents of integration. 
         [0173]    Further, the method of circuit integration is not limited to LSI&#39;s, and implementation using dedicated circuitry or general purpose processors is also possible. After LSI manufacture, utilization of a programmable FPGA (Field Programmable Gate Array) or a reconfigurable processor where connections and settings of circuit cells within an LSI can be reconfigured is also possible. 
         [0174]    If a new integrated circuit implementation technology replacing LSI is introduced because of advancement in semiconductor technology or a different technology derived therefrom, the function blocks may of course be integrated using that technology. For example, application of biotechnology is also possible. 
         [0175]    The disclosure of Japanese Patent Application No. 2011-133750, filed on Jun. 15, 2011, including the specification, drawings and abstract, is incorporated herein by reference in its entirety. 
       INDUSTRIAL APPLICABILITY 
       [0176]    The claimed invention is suitable for use in a pulse position searching apparatus that searches a plurality of pulse positions or a codebook searching apparatus that searches a plurality of pulse positions making up a codebook, and is further applicable to a speech coding apparatus. 
       REFERENCE SIGNS LIST 
       [0000]    
       
           400 ,  600  Pulse position searching apparatus 
           401 ,  601  First searching section 
           402 ,  602  Second searching section 
           403 ,  603  Third searching section 
           500  Fixed codebook searching apparatus 
           501  Preprocessing section 
           502  Control section 
           503  Multiplexed loop searching section 
           504  Pulse sequence coding section