A video encoding apparatus for encoding a video stream comprises a reference frame cache for reference frame video data retrieved from a reference frame storage unit in external memory, which is derived from an individual frame of the video stream. First and second source frame storage units store first and second blocks of unencoded video data taken from first and second source frames of the video stream, respectively. First and second video encoders perform first and second encoding operations to encode the first and second blocks of unencoded video data with reference to the reference frame video data cached in the reference frame cache, respectively. The first video encoder and the second video encoder perform the first encoding operation and the second encoding operation in parallel with one another.