A data embedding apparatus including: a selecting unit for selecting, based upon the second data, a prediction system of calculating a prediction value with respect to data to be processed within the first data; a predicting unit for calculating the prediction value of the data to be processed by the prediction system selected by the selecting unit; a difference calculating unit for calculating a prediction error of the data to be processed by employing the prediction value; and a prediction error calculating unit for outputting the coded data, in which the predicting unit includes: a 0-embedding time predicting unit for performing prediction when a bit value of the second data is “0”; a 1-embedding time predicting unit for performing prediction when the bit value of the second data is “1”; and an embedding end time predicting unit for performing prediction when embedding of the second data is accomplished.