A playback apparatus is capable of playing back video data at a variable speed ranging from a forward normal speed to a reverse normal speed, the video data having been encoded for compression through inter-frame compression based on predictive coding and recorded on a recording medium that allows random access. The playback apparatus includes a frame buffer configured to temporarily store video data of a plurality of frames; a target-pattern generator configured to generate a target pattern of the frame buffer for a target playback frame to be played back next; a comparator configured to compare a current state of the frame buffer with the target pattern; and a frame-buffer controller configured to extract a frame to be newly decoded and a frame no longer used in the current state of the frame buffer, on the basis of a result of the comparison by the comparator.