A video decoding device includes a demultiplexing unit which demultiplexes a video bitstream including video data of an encoded slice, first Supplemental-Enhancement-Information having information indicating segments where a refresh has completed in a current picture, and second Supplemental-Enhancement-Information having information indicating a synchronization starting picture and a synchronization completed picture, an extracting unit which extracts the information indicating segments where a refresh has completed in a current picture from a message which is part of the demultiplexed Supplemental-Enhancement-Information; and a video decoding unit which decodes image data from the demultiplexed video bitstream by using at least inter prediction, wherein the synchronization starting picture is a leading picture within a refreshing period, and the synchronization completed picture is the end position of the refreshing period.