According to an embodiment, an encoding device includes a storage controller, a difference generator, and a communication controller. The storage controller is configured to store a base stream in a storage. The base stream serves as basis for encoding and decoding and is shared with a decoding device. The difference generator is configured to generate a difference bit stream that represents difference between an input bit stream that has been input and the base stream. The communication controller is configured to control a communicating unit to transmit the difference bit stream.