In a data updating apparatus for updating first data having plural bits according to a predetermined data format, a detector detects a domain point at which the first data are different from second data including plural bits decoded by Slepian-Wolf decoding according to the predetermined data format. The first data is used for decoding encoded data on a non-key frame separated from a stream of frames by Slepian-Wolf decoding and transformed from a predictive frame associated with the non-key frame and generated from information on a key frame. A data updater updates a less significant bit in the first data than the domain point supplied from the detector according to a predetermined updating scheme.