An encoding device is provided for improving decoded signal quality. A local search unit conducts a local search on a plurality of sub-bands generated by dividing spectrum data, and calculates lattice vectors for the spectra in the plurality of sub-bands. A multi-rate indexing unit uses the lattice vectors to perform multi-rate indexing on each of the sub-bands, and generates indexing information showing the results thereof. A band selection unit determines certain sub-bands from amongst the plurality of sub-bands in a plurality of encoding layers as perceptually important sub-band groups, where these are: within a selection range of sub-bands wherein the total number of encoding bits allocated to each of the plurality of sub-bands in the indexing information is equal to or less than an already set value, and within a sub-band selection range with the highest total energy of each of the plurality of sub-bands.