A digital video recorder or similar apparatus implements a method of converting an input data stream having an MPEG-2 Transport Stream (TS) format into an output data stream having an MPEG-2 Program Stream (PS) format. The input data stream (TS) includes data of at least first and second elementary data streams (404, 406) formed and multiplexed in compliance with a TS decoder model. The first elementary stream is a video stream, while the second stream is an audio stream of lower data rate. The input stream is parsed (402) and the elementary streams are demultiplexed into respective FIFO queues 404/406. Each stream is further parsed to obtain and calculate time stamp information which is queued separately at (408/410) with pointers to the stream data (at 404/406). The schedule and packetisation applied to the elementary streams in the input stream (TS) cannot be applied directly in creating the output stream (PS). However, based on parameters and constraints imposed upon the input stream by the MPEG or other specifications, a remultiplexer 412 is able to reschedule and repacketise the elementary data streams into a valid output stream (TS), without the size of buffer that would be required for multiplexing of the elementary streams from scratch.