Since its introduction in 1984, Code Excited Linear Prediction (CELP) [1] has been intensively investigated as a promising coding algorithm for providing good quality speech at low bit rates. CELP is the name for a class of coding algorithms that employs vector quantization (VQ) using a perceptually weighted error criterion measured in an Analysis-by-Synthesis loop. This process gives an efficient representation of the excitation signal and exhibits better performance than conventional coding methods. However, the codebook search requires a huge computational load, which is a major drawback in the practical implementation of CELP. In particular, for digital cellular communications, which is considered the biggest application for low bit-rate speech coding, reducing the complexity of CELP is important for small hardware size and low power consumption.