This invention is intended to prevent a mismatch from occurring between a re-encoded and recorded video stream and other data. A transport stream is input to a recording apparatus and is then supplied to a demultiplexer and an analyzing block. The analyzing block outputs non-video stream information to a coding controller. The coding controller controls the encoding operation of an encoder on the basis of the input information and outputs video coding control information to a coding block. On the basis of video coding control information, the coding block generates multimedia display sub-information (including information about a picture frame, for example) which prevents a mismatch from occurring on the reproducing side between video and other data, and outputs this information to a writing block. The writing block records the video stream and other data to a recording medium, as well as recording the multimedia display sub-information generated by the coding block.