A decoding device includes: a data obtaining unit configured to obtain a key block and a non-key brock, the key block forming a part of image data of one frame, and the non-key block forming a part of the image data of one frame on at least a part of which a coding process is performed; a characteristic information storage unit configured to store characteristic information regarding a pixel value correlation characteristic in a frame; and a decoding unit configured to perform repeated decoding by a belief-propagation method based on a first log-likelihood ratio and a second log-likelihood ratio to estimate the non-key block before the coding process, the first log-likelihood being obtained from the non-key block, and the second log-likelihood ratio being obtained from the key block and the characteristic information.