1. A fixed codebook searching apparatus, comprising: a convolution operator, implemented by at least one processor, that convolves an impulse response of a perceptually weighted synthesis filter with an impulse response vector that has values at negative times, to generate a second impulse response vector that has values at negative times; a matrix generator, implemented by at least one processor, that generates a Toeplitz-type convolution matrix using the second impulse response vector generated by the convolution operator; and a searcher, implemented by at least one processor, that performs a codebook search by maximizing a term using the Toeplitz-type convolution matrix, wherein energy of components of the second impulse response vector at negative times is smaller than the energy of components at non-negative times.