To provide a moving picture stream generation apparatus and the like that generates a moving picture stream that can be played back in trick-play such as variable-speed playback and reverse playback even in a Coding format such as the MPEG-4 AVC in which flexible prediction structures are allowed. A moving picture stream generation apparatus includes: a trick-play information generation unit TricPlay for generating supplemental information on a random access unit basis, the supplemental information being referred to at the time of playback of each random access Unit and each random access unit including one or more pictures; and a variable length coding unit VLC for generating a stream including the generated supplemental information and the one or more pictures by adding the supplemental information to each corresponding random access unit.