The paper discusses several new approaches for efficiently modeling and selecting the excitation in CELP coding of speech. Modified error criteria and structured codebooks lead to a wide range of complexity reduction methods, that are evaluated in terms of quality and computational requirements. A very low complexity, though high quality, Regular Pulse (RP) CELP technique is then derived. Finally we address the design of a robust 6 kbps RPCELP coder for mobile radio communications.