A decoding device improves a cache hit rate in a decoding process of compressed encoded image data. The decoding device, before the decoding process, generates a sort table for each reference picture for a plurality of MPEG data streams included in a GOP and having a frame type of P- or B-picture. The decoding device, by using the generated sort table, selects a group of pictures composed of a plurality of decoding target macro blocks that refer to the same reference macro block. The decoding device obtains, from the reference picture, four macro blocks including the same reference macro block referred to by the selected picture group, and stores the four macro blocks into the cache memory. The decoding device sequentially decodes each decoding target macro block included in the selected picture group, by using the four macro blocks stored in the cache memory.