Provided is an encoding device which can obtain a sound quality preferable for auditory sense even if the number of information bits is small. The encoding device includes a shape quantization unit (111) having: a section search unit (121) which searches for a pulse for each of bands into which a predetermined search section is divided; and a whole search unit (122) which performs search for a pulse over the entire search section. The shape of an input spectrum is quantized by a small number of pulse positions and polarities. A gain quantization unit (112) calculates a gain of the pulse searched by the shape quantization unit (111) and quantizes the gain for each of the bands.