Patent ID: 8560306

Claim:
A method of searching at least one of a codebook and an extended codebook which are including pulses that model a predetermined component of a speech signal, the method comprising: (a) selecting a predetermined number of paths corresponding to a predetermined number of pulse locations that are most consistent with the predetermined component, from among paths corresponding to pulse locations of a predetermined pulse location set allocated to at least one branch that connects one state belonging to a stage of a predetermined Trellis structure to an other state belonging to the other stages, where an extended track of the extended codebook is allocated to each stage; (b) performing operation (a) on each of states other than the one state; and (c) selecting a path corresponding to pulse locations that are the most consistent with the predetermined component, from among paths including the paths selected in operations (a) and (b), wherein the predetermined pulse location set corresponds to a sub-codebook, generated by dividing the extended codebook, and each extended tracks of the extended codebook corresponds to a union of at least two tracks of an algebraic codebook.