Method and apparatus to search fixed codebook using tracks of a trellis structure with each track being a union of tracks of an algebraic codebook

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 memory unit including a Trellis structure database to store a predetermined Trellis structure and a predetermined number of pulse locations and Trellis paths corresponding to pulse locations of a predetermined pulse location set, where the predetermined pulse location set is allocated to at least one branch that connects one state belonging to a stage of the predetermined Trellis structure to an other state belonging to the other stages, and an extended track of the extended codebook is allocated to each stage;
• a calculation unit to receive the predetermined component of the speech signal and the predetermined Trellis structure, to calculate predetermined equation values, and to output calculation results;
• a selection unit in communication with the calculation unit and the memory unit to select a predetermined number of Trellis paths corresponding to a predetermined number of pulse locations which are most consistent with the predetermined component;
• and
• an output unit to output information about pulse locations and corresponding Trellis paths which are most consistent with the predetermined component based on the predetermined number of pulse locations and the Trellis paths stored in the memory,
• 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.

An extended codebook decoding apparatus to restore a predetermined component of a speech signal modeled on pulses, comprising:

• a Trellis structure database to store a predetermined Trellis and a predetermined number of pulse locations and Trellis paths corresponding to pulse locations of a predetermined pulse location set;
• a codebook decoding unit to receive information about pulse locations and corresponding Trellis paths and to restore the predetermined component based on the predetermined number of pulse locations and the Trellis paths stored in the memory, and based on a selection of a predetermined number of Trellis 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 of the predetermined Trellis structure to other states;
• and
• an output unit to output the restored predetermined component of the decoding 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.