A picture coding apparatus which generates a stream so as to be able to decode a picture by obtaining a picture parameter set necessary for decoding the picture even at the time of trick-play, the apparatus including: a slice coding unit which codes the picture and generates coded data; a picture parameter set (PPS) generation unit which generates sequence parameter set (SPS); a PPS generation unit which generates the PPS; and an access unit (AU) determination unit which stores pieces of coded data respectively into access units of a random access unit (RAU) and stores the SPS into a first AU, and stores the PPS into the first AU or into the AU in which one piece of the coded data that refers to the PPS is stored.