Provided is an encoding device which can reduce the encoding distortion as compared to the conventional technique and can obtain a preferable sound quality for auditory sense. In the encoding device, a shape quantization unit (111) quantizes the shape of an input spectrum with a small number of pulse positions and polarities. The shape quantization unit (111) sets a pulse amplitude width to be searched later upon search of the pulse position to a value not greater than the pulse amplitude width which has been searched previously. A gain quantization unit (112) calculates a gain of a pulse searched by the shape quantization unit (111) for each of bands.