An encoding device enables the amount of processing operations to be significantly reduced while minimizing deterioration in the quality of an output signal. This encoding device (101) encodes an input signal by determining the correlation between a first signal generated by using the input signal and a second signal generated by a predetermined method. An importance assessment unit (202) sets the importance of each of a plurality of processing units obtained by dividing the frames of the input signal. A CELP coder (203) performs sparse processing in which the amplitude value of a predetermined number of samples among multiple samples constituted by the first signal and/or the second signal in each processing unit is set to zero according to the importance that was set for each processing unit, and calculates the correlation between the first signal and the second signal, either of which was subjected to sparse processing.