In modern communication systems, low-bit-rate speech coder is widely employed to increase the bandwidth efficiency of the network. The ITU-T G.729 is one such speech coder extensively used in packet voice communication systems. Since the reduction in the complexity has been a major issue in designing and implementing low-bit-rate speech coder, the focus of this research is on reducing the complexity of the existing G.729 standard. Based on the fact that the fixed codebook search accounts for much of the computation in the coding process, in this thesis, the existing codebook search algorithm of G.729A, a reduced complexity version of G.729, is modified and incorporated into this standard. The test results on a general PC indicate that the modified search scheme reduces the computation load by about 40% with only a slight degradation in the perceptual quality of the speech.  In the second part of this project, the modified speech coder is implemented on the TMS320C5416 DSK DSP board. First, the implementation scheme is described and the initial results for both the G.729A and the modified coder are presented. Then, several optimization procedures are developed to effectively reduce the run-time of the algorithm. With the optimized implementation, the run-time of the speech coder is significantly reduced to meet the real time requirement to process a single frame within 10 ms. As for the savings on the computational load, the run-time of the modified fixed codebook search algorithm is about 30% smaller than that of the original search scheme used in G.729A.