An encoding method comprising: a vector quantization step of vector-quantizing a plurality of samples collectively to obtain a vector quantization index and the quantized value of each of the plurality of samples; and a coefficient group selection step of outputting index information indicating a group of coefficients that minimizes the sum of the error between the value of each sample and the value obtained by multiplying the quantized value of the sample by a coefficient corresponding to the position of the sample, for all sample positions, among a plurality of groups of predetermined coefficients corresponding to the positions of the samples, wherein the groups of coefficients are each formed of coefficients disposed on a straight line in a plane having values corresponding to frequency or time corresponding to the sample positions with which the coefficients are associated on a first axis thereof and the values of the coefficients on a second axis thereof; and the coefficients of each of the plurality of groups of coefficients are disposed in the plane on a straight line having a different gradient from straight lines for the other groups, characterized in that: the number of bits of the index information output in the coefficient group selection step is equal to or smaller than the value obtained by subtracting the number of bits actually used for a code corresponding to the vector quantization index from the number of bits assigned for the code corresponding to the vector quantization index. a vector quantization step of vector-quantizing a plurality of samples collectively to obtain a vector quantization index and the quantized value of each of the plurality of samples; and a coefficient group selection step of outputting index information indicating a group of coefficients that minimizes the sum of the error between the value of each sample and the value obtained by multiplying the quantized value of the sample by a coefficient corresponding to the position of the sample, for all sample positions, among a plurality of groups of predetermined coefficients corresponding to the positions of the samples, wherein the groups of coefficients are each formed of coefficients disposed on a straight line in a plane having values corresponding to frequency or time corresponding to the sample positions with which the coefficients are associated on a first axis thereof and the values of the coefficients on a second axis thereof; and the coefficients of each of the plurality of groups of coefficients are disposed in the plane on a straight line having a different gradient from straight lines for the other groups, characterized in that: the number of bits of the index information output in the coefficient group selection step is equal to or smaller than the value obtained by subtracting the number of bits actually used for a code corresponding to the vector quantization index from the number of bits assigned for the code corresponding to the vector quantization index. the number of bits of the index information output in the coefficient group selection step is equal to or smaller than the value obtained by subtracting the number of bits actually used for a code corresponding to the vector quantization index from the number of bits assigned for the code corresponding to the vector quantization index.