Patent ID: 8805681

Claim:
An apparatus to search at least one of a codebook and an extended codebook which are including pulses that model a predetermined component of a speech signal, the apparatus comprising: a Trellis structure database to store a predetermined Trellis; a selection unit to select a predetermined number of paths corresponding to a predetermined number of pulse locations which 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 every state belonging to a stage of the predetermined Trellis structure to other states belonging to the other stages of the predetermined Trellis structure, where an extended track of the extended codebook is allocated to each stage of the predetermined Trellis structure; a memory unit to store the predetermined number of pulse locations and the paths; and an output unit to output information about pulse locations which are most consistent with the predetermined component and information about paths corresponding to the pulse locations, based on the pulse locations and the paths stored in the memory unit, wherein the predetermined pulse location set corresponds to a sub-codebook generated by dividing the extended codebook, and each of the extended tracks of the extended codebook corresponds to a union of at least two tracks of an algebraic codebook.