The present invention relates to an encoding device and a method, a decoding device and a method, an editing device and a method, a storage medium, and a program which can perform encoding and decoding so that buffer failure does not occur. Information, such as a minimum bit rate, a minimum buffer size, and a minimum initial delay time, is contained in a random access point header contained in an accessible point in a bitstream. A bitstream analyzing unit 72 analyzes an input bitstream, sets the above-mentioned information, and outputs the resulting information to a buffer-information adding unit 73. The buffer-information adding unit 73 adds the input information to the input bitstream and outputs the resulting bitstream. The present invention is applicable to an encoding device and a decoding device which process bitstreams.