A fixed codebook searching apparatus for a speech coding apparatus performing a code-excited linear prediction, CELP, encoding of an input speech signal using a pulse excitation vector searched in the fixed codebook searching apparatus and outputting an encoded bit sequence including a parameter corresponding to the pulse excitation vector, the fixed codebook searching apparatus, comprising: a pulse excitation vector generating section adapted to generate a pulse excitation vector (c k); a convolution operation section adapted to convolute an impulse response of a perceptually-weighted synthesis filter with an impulse response vector which has one or more non-zero values at negative times, to generate a second impulse response vector that has one or more non-zero values at negative times; a matrix generating section adapted to generate a Toeplitz-type convolution matrix using the generated second impulse response vector; and a searching section (153, 154, 155) adapted to: • input a target vector obtained from the input speech signal in the speech coding apparatus, • perform convolution processing on the generated pulse excitation vector (c k) using the generated Toeplitz-type convolution matrix to generate a perceptually-weighted synthesis signal, • control the generated pulse excitation vector for minimizing the energy of the error between the generated perceptually-weighted synthesis signal and the target vector, and • output the parameter corresponding to the pulse excitation vector that minimizes the energy of the error. a pulse excitation vector generating section adapted to generate a pulse excitation vector (c k); a convolution operation section adapted to convolute an impulse response of a perceptually-weighted synthesis filter with an impulse response vector which has one or more non-zero values at negative times, to generate a second impulse response vector that has one or more non-zero values at negative times; a matrix generating section adapted to generate a Toeplitz-type convolution matrix using the generated second impulse response vector; and a searching section (153, 154, 155) adapted to: • input a target vector obtained from the input speech signal in the speech coding apparatus, • perform convolution processing on the generated pulse excitation vector (c k) using the generated Toeplitz-type convolution matrix to generate a perceptually-weighted synthesis signal, • control the generated pulse excitation vector for minimizing the energy of the error between the generated perceptually-weighted synthesis signal and the target vector, and • output the parameter corresponding to the pulse excitation vector that minimizes the energy of the error. • input a target vector obtained from the input speech signal in the speech coding apparatus, • perform convolution processing on the generated pulse excitation vector (c k) using the generated Toeplitz-type convolution matrix to generate a perceptually-weighted synthesis signal, • control the generated pulse excitation vector for minimizing the energy of the error between the generated perceptually-weighted synthesis signal and the target vector, and • output the parameter corresponding to the pulse excitation vector that minimizes the energy of the error.