An encoding device reduces the encoding distortion as compared to the conventional technique and obtains a preferable sound quality for auditory sense. In the encoding device, a shape quantization unit quantizes the shape of an input spectrum with a small number of pulse positions and polarities. The shape quantization unit 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 calculates a gain of a pulse searched by the shape quantization unit for each of bands.