An encoding unit separates converted coefficients obtained by frequency conversion into the upper-bit portion that is higher than a bit position specified by a boundary bit position determined when the previous macro block is encoded and the lower-bit portion, performs encoding on the upper-bit portion and outputs the encoded data and the lower-bit portion. When a maximum difference in the number of valid bits of the converted coefficients represented by the lower-bit portion remaining after deletion and the upper-bit portion of each pixel block when it is assumed that the number of bits i to be deleted is changed to 1, 2, . . . and so on in the range of the finite number of bits representing converted coefficients is represented as max_diff(i), a stream generating unit creates a histogram constituted by the bit number i and the frequency for max_diff(i) to determine the number of bits N to be deleted.