Stochastic codebook is one of the most important part in Codebook Excited Linear Prediction （CELP） technique. The codebook structure and its searching algorithm mainly affect the synthesized speech quality and the possibility of real-time realization of speech coding systems. The paper proposes a structured stochastic codebook-"Linear-Shifted"Gaussian Codebook

and discusses a set of bi-directional recursive formulations. Single-directional recursive algorithm is then presented

which highly increases the computational speed and reduces complexity by a factor of 1.76. In order to far more decrease the searching complexity

Suboptimal Local Searching strategy is introduced

leading to bi-directional recursive algorithm. With the same quality of synthesized speech

the later algorithm can increase the searching speed twice than that of the former one.