A transcoding apparatus and associated methodology of transcoding a first video stream into a second video stream, is provided. A separator extracts a video transport stream packet including the first video stream, a non-video transport stream packet, and timing information from a first transport stream. The timing information indicates a time at which the non-video transport stream packet is formed and the first transport stream relative to the video transport stream packet. A memory is provided to store the timing information. A conversion unit generates the second video stream based on the first video stream. A multiplexer multiplexes a converted video transport stream packed including the second video stream and a converted non-video transport stream packet based on the stored timing information to generate a second transport stream, including the second video stream.