In this paper, a 6.7-kbps vector sum excited linear prediction (VSELP) coder with less computational complexity is presented. A very efficient VSELP codebook with nine basis vectors and a heuristic K-selection method (to reduce the search space and complexity) is constructed to obtain the stochastic codebook vector. The nine basis vectors are obtained by optimizing a set of randomly generated basis vectors. During the optimization process, we have trained the basis vectors to give the system apriori knowledge of the characteristics of the input. The coder is implemented on a TMS320C541 digital signal processor. The performance is evaluated by testing the 6.7-kbps VSELP coder with different test speech data taken from different speakers. The quality of the coder is estimated by comparing the performance of the 6.7-kbps VSELP coder with an 8-kbps VSELP speech coder based on the IS-54 standards. © 2002 Elsevier Science B.V. All rights reserved.