An embedded coding unit for embedding first data in second data, and outputting coded data, comprises a selecting unit, predicting unit, and prediction margin of error computing unit. The selecting unit selects a predicting method for predicting data of interest in the first data, based on the second data, the predicting unit obtains a prediction value corresponding to the data of interest based on the prediction method selected by the selecting unit, and the prediction margin of error computing unit computes prediction margin of error based on the data of interest and the prediction value, and outputs this as the coded data.