An encoding device includes: a frequency region converter which converts an inputted audio signal into a frequency region; a band selector which selects a quantization object band from a plurality of sub bands obtained by dividing the frequency region; and a shape quantizer which quantizes the shape of the frequency region parameter of the quantization object band. When a prediction encoding presence/absence determiner determines that the number of common sub bands between the quantization object band and the quantization object band selected in the past is not smaller than a predetermined value, a gain quantizer performs prediction encoding on the gain of the frequency region parameter of the quantization object band. When the number of common sub bands is smaller than the predetermined value, the gain quantizer non-predictively encodes the gain of the frequency region parameter of the quantization object band.