In a CELP-type speech coding apparatus, switching between an orthogonal search of a fixed codebook and a non-orthogonal search is performed in a practical and effective manner. The CELP-type speech coding apparatus includes a parameter quantizer that selects an adaptive codebook vector and a fixed codebook vector so as to minimize an error between a synthesized speech signal and an input speech signal. The parameter quantizer includes a fixed codebook searcher that switches between the orthogonal fixed codebook search and the non-orthogonal fixed codebook search based on a correlation value between a target vector for the fixed codebook search and the adaptive codebook vector obtained as a result of a synthesis filtering process.