In this paper, we consider vector quantization of excitation gains in code-excited linear predictive (CELP) speech coder using the average error in reconstruction of the excitation signal as the distortion measure and use the same measure to design the codebooks. We have derived a generalized Lloyd's algorithm (GLA) to design a codebook for quantization so that the average of the above criterion over the training vectors is minimized. We have also derived an algorithm, referred
to as the Genetic GLA (GGLA), that can be shown to converge to the global optimum of the associated functional with probability one. The performance of ACELP using the codebooks obtained by the proposed algorithms is compared with that of the conjugate-structured ACELP-based ITU-T G.729 coder. Qualitative and quantitative comparisons show that their qualities are comparable.