Method for reducing the search complexity in analysis-by-synthesis coding

DETAILED DESCRIPTION The present invention is directed to a method of encoding a frame of input speech signal by performing a limited search of a tree-code excitation codebook to find a codeword achieving an optimal representation of the speech frame.
The frame is partitioned into a predetermined number of sample segments of length equal to the length of each branch in a respective stage of the tree-code.
Each branch of the tree-code represents a sequence of codeletters so that each full path through the tree-code represents a codeword.
At each stage of the tree-code, the limited searching involves identifying a set of test paths by extending out a predetermined number of branches from a limited number of saved paths which lead up to the current stage from a root node.
The respective codeletters of these extended branches are then colored with a coloring filter.
The encoding method next minimizes an error distance measurement between a synthetic signal defined by each test path and the sequence of sample segments up to the current stage by optimizing a scaling factor of the synthetic signal.
A limited number of these test paths are saved based on lowest relative distance measurements.
These surviving test paths serve as the saved paths from which further searching occurs in a next stage.
The steps of path identification, codeletter coloring, error distance minimization by optimal scaling, and path saving are repeated in each successive stage of the tree-code.
After the final stage has been searched, the single one of the saved full paths having the lowest relative distance measurement represents the codeword achieving optimal representation of the frame of input speech signal.