Video decoder decodes pictures B0, B1, I2, B3 of GOP-3 which have been read out from a recording medium along with recording of new compressed picture data onto the recording medium thereafter to further decode pictures B4, P5, B6 . . . to restore them. Namely, it is impossible to restore, only by the compressed picture data of pictures B4, P5, B6. . . , these pictures corresponding thereto. For this reason, picture data of pictures B4, P5, B6. . . which have not been caused to be missing by recording of new compressed picture data are re-encoded to generate new GOP. Thus, the video decoder decodes and restores those non-missing pictures on the basis of the pictures B0, B1, I2, B3 within the new GOP.