An image encoding device comprising: a setting unit configured to set header information related to a hypothetical reference decoder in accordance with position information indicating a relative distance between the position of the access unit at the end of the bitstream and the position of a previous non-discardable picture, information indicating bitstream concatenation, information indicating a NAL unit type, and reference information indicating whether or not the current picture is a reference picture; and an encoding unit configured to encode the image data and generate a bitstream containing the encoded data of the image data and the header information set by the setting unit, the bitstream being for concatenation with another bitstream, and when the current picture is a first picture of the other bitstream, the setting unit sets the information indicating the NAL unit type at a value indicating an IDR picture, sets the information indicating bitstream concatenation at "true", and sets the information indicating the difference between the position of the access unit at the end of the bitstream and the position of the previous non-discardable picture at 0, and when the current picture is either a last picture of the bitstream, neither a first picture of the other bitstream nor a last picture of the bitstream, but is a reference picture, or neither a first picture of the other bitstream nor a last picture of the bitstream, and is not a reference picture, the setting unit sets the information indicating the NAL unit type at a value indicating either a trailing picture to be referred to if the current picture either is a reference picture or a last picture, or a non-reference picture if the current picture is not a reference picture, the trailing picture or the non-reference picture not being of a temporal sublayer, sets the information indicating bitstream concatenation at "false", and sets the information indicating the difference between the position of the access unit at the end of the bitstream and the position of the previous non-discardable picture at 0. a setting unit configured to set header information related to a hypothetical reference decoder in accordance with position information indicating a relative distance between the position of the access unit at the end of the bitstream and the position of a previous non-discardable picture, information indicating bitstream concatenation, information indicating a NAL unit type, and reference information indicating whether or not the current picture is a reference picture; and an encoding unit configured to encode the image data and generate a bitstream containing the encoded data of the image data and the header information set by the setting unit, the bitstream being for concatenation with another bitstream, and when the current picture is a first picture of the other bitstream, the setting unit sets the information indicating the NAL unit type at a value indicating an IDR picture, sets the information indicating bitstream concatenation at "true", and sets the information indicating the difference between the position of the access unit at the end of the bitstream and the position of the previous non-discardable picture at 0, and when the current picture is either a last picture of the bitstream, neither a first picture of the other bitstream nor a last picture of the bitstream, but is a reference picture, or neither a first picture of the other bitstream nor a last picture of the bitstream, and is not a reference picture, the setting unit sets the information indicating the NAL unit type at a value indicating either a trailing picture to be referred to if the current picture either is a reference picture or a last picture, or a non-reference picture if the current picture is not a reference picture, the trailing picture or the non-reference picture not being of a temporal sublayer, sets the information indicating bitstream concatenation at "false", and sets the information indicating the difference between the position of the access unit at the end of the bitstream and the position of the previous non-discardable picture at 0.