This paper presents an improved CELP coder operating at 4 kb/s and below, which can provide speech quality equivalent to that reproduced by conventional CELP at around 8 kb/s. To maintain reproduced speech quality while reducing the bit rate, highly efficient coding schemes are employed both for spectral coding and excitation coding. For an efficient encoding of LSP parameters, 2-split, 2-stage vector quantizer (VQ) with partially adaptive codebook was applied. At 24 bits/frame, the proposed VQ exhibits the spectral distortion performance comparable to that of the conventional scalar quantizer at 30 bits/frame. The non-linear interpolation of LSP parameters was also adopted to cope with the degradation of prediction gain caused by the long analysis frame (40 ms). For a better representation of excitation signal, a coding strategy was switched frame by frame according to the phonetic nature of the speech signal. In the voiced frame, pitch synchronous pulse codebook was introduced to generate pitch periodicity. While in the unvoiced frames, computationally efficient stochastic codebook (Tree-delta codebook) was used. As a result of the computer simulation, the performance of our improved CELP coder at 3.4 kb/s was close to that of JDC (Japan Digital Cellular) standard VSELP operating at 6.7 kb/s. The estimated computational complexity of this coder is not as much as twice the complexity of VSELP.