A coded bit stream generated on a coding side consists of a VO header, a VOL header, a GOV header, a VOP header and VOP data, and the VOL header multiplexes an object intra-coded indicator signal indicating whether all the VOP data contained in a VOL or GOV are intra coded or not. This enables a decoding side to recognize whether all the VOP data contained in the VOL or GOV in the coded bit stream are intra coded or not by only analyzing the object intra-coded indicator signal. This can facilitate such processings as frame skip control or random access of the VOPs.